Re: [Gnu-arch-users] Re: MD5 is broken

[Adrian Irving-Beer]

On Wed, Mar 16, 2005 at 11:07:27AM -0800, Tom Lord wrote:

> But logically speaking, the combination of two hash functions is a
> single hash function.  It is just as "a priori" likely that the
> combination will be broken.

(n.b.  I'm not arguing for a particular strategy here, just
       reaffirming or augmenting my knowledge of hash functions.
       I'll leave the procedural discussion to others.)

Let's say I have a particular piece of data that MD5 hashes into a
paricular hash value (we'll call it MD5-A), and SHA1 hashes into
another value (SHA1-A).

Let's say I then manage to 'break' MD5, by creating another piece of
data that has the same MD5 hash (MD5-A).

My question is, would that different piece of data also have an SHA1
hash of SHA1-A?  Or would it have some other SHA1 code (SHA1-B)?

Reciprocally, if one breaks SHA1, and finds a new piece of data that
is different but has the same code (SHA1-A), would it similarly hash
to MD5-A, or to MD5-B?

I'm under the impression that they will both hash to something
different (*-B rather than *-A) if the other is broken.

So to be useful, you'd have to find a different piece of data that
has *both* SHA1-A and MD5-A as its two hashes -- i.e. one of the
intersection of all values that meet SHA1-A and all values that
meet MD5-A.

And even if MD5 became trivial to break, SHA1 would stand firm and
vice versa.

So while you *are* combining them into a 'single hash function', isn't
that a single hash function both

  a) much more difficult to brute force than either MD5 or SHA1, and

  b) half as likely to suffer a successful non-brute attack as using
     either one alone?

Both of the above seem true to me, but my knowledge of these matters
is mostly just anecdotal.

signature.asc
Description: Digital signature