[Mac_crypto] Apple should use SHA! (or stronger) to authenticate software releases

[Andy Isaacson]

On Mon, Apr 12, 2004 at 06:00:26PM -0700, Joseph Ashwood wrote:
> > From: Nicko van Someren <nicko at ncipher.com>
> >
> > It's not clear to me that you need all this complexity.  All you need
> > if to arrange that the attacker does not know exactly what will be
> > signed until it has been signed.  So you append some randomness from a
> > good random number source to the end of the file just before you sign
> > it, and you're safe.
> 
> I'm not quite sure that's a good solution, that random tail provides exactly
> what the attacker needs to make this as easy as possible. Since the random
> tail cannot be know beforehand it cannot be known by the user of the patch.
> If anything this would actually make an attack easier. It is only if the
> random data is from a _bad_ random source that you might actually gain some
> security (a bad source would at the very least have redundancy, internal or
> external, that could be verified by the end user, making it more complex to
> compute valid numbers). Instead it would probably be more useful to include
> the same random number between each file, this should short circuit all but
> the most fatal of hash flaws, but might open up other possibilities (I don't
> have the time right now to prove things about it).

You and Nicko are discussing different attacks.

One attack is "Find two patches which have the same MD5".  This falls to
a birthday-paradox attack with 2^64 work, and is somewhat easier if the
patch format includes a random tail.  (The collision attack needs 64
bits of controllable input in the message.)  Short of a compromise of the
developer's machine, it's hard to see how this type of hash collision can
be leveraged into getting a malicious patch distributed as genuine.

Another attack is "Submit a carefully sculpted change through normal
channels which results in the new patch having an attacker-determined
hash value".  The work factor is somewhat difficult to estimate, but is
probably a significant multiple higher than 2^64, primarily due to the
more-complex iterator due to having to emulate the workflow of the
developer when computing hash values.  In this attack, the assumption is
that the attacker submits a diff (a very innocuous one, but with a
special structure), which is integrated, and the result is a (binary)
patch which is signed by the developer.  The attacker was able to craft
the diff so as to cause MD5(patchA) to match MD5(patchB) and then
distributes patchB with the signature from patchA.

This second attack is made infeasible by simply appending 64 bits of
randomness to the patch before signing it.  Since the attacker could not
possibly know those bits, so his work required increases by a *power* (I
believe -- haven't done the math carefully) of 64.

These are straightforward extensions of Van Oorschot & Wiener's 1994
paper "Parallel Collision Search with Application to Hash Functions and
Discrete Logarithms".

The obvious conclusion is that nobody should be using MD5 any more;
follow the OpenBSD project's lead and distribute SHA1 alongside your MD5
distribution.  Or SHA-256 if you're really paranoid.

> On a related note does anyone happen to know of any useful papers on
> patching, specifically patch integrity/source verification?

I don't see how this is any different from the generic source validation
problem.

-andy

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com