Invisible wrote:
> Quoting RFC #1321, Section 1:
> 
> "It is conjectured that it is computationally infeasible to produce
> two messages having the same message digest, or to produce any
> message having a given prespecified target message digest."
> 
> This conjecture has now been determined to be false. In fact, a single 
> laptop can perform both these tasks in a few minutes using a suitable 
> algorithm.

Do you have a cite for this? I'd heard of the first problem being 
broken, but not the second one.

> However, one might also conjecture that the probability of any two 
> arbitrary messages having the same [MD5] hash code would be 2^(-128).
> 
> Does the existence of a collision-generation algorithm for MD5 
> contradict this second conjecture?

Only if you do it on purpose. Obviously, to *arbitrary* messages will 
have low probablility of a hit.

> (In othe words, it is possible to *maliciously* alter a message without 
> affecting the MD5 hash, but what is the probability of an *accidental* 
> modification going undetected? Is it 2^(-128)? Or is it some higher 
> probability?)

It's still a low probability. You have to alter the message in a way 
that takes specifically into account how MD5 works. That's why the same 
technique doesn't work on other hashes.

> Actually, according to the Birthday Paradox, the probability in this case is much
lower.

Not with only two messages.

> But this depends on just how "random" MD5 really is. Apparently it's not something
anybody has looked at much. 

People looked for any collision for a decade or more before the folks 
who professionally analyze cryptographic systems figured out how to 
cause a collision. It's sufficiently unlikely a random change in a file 
will cause you any grief that you need to worry about it.

The reason people worry about it is they fear an active, intelligent 
adversary changing that which has been signed.

> In a sense, the important point about MD5 is that checking a CD this way ensures
that every single bit of data is physically read from the surface of the disk. If you
can do that, the data is probably correct anyway... 

Since the TOC is at the start of the CD, I find this much more likely to 
be broken. Checksum the TOC, the first file, and the last file, and 
*then* you don't have to read the whole CD. I'd say 1/3rd of my CDs that 
coaster have a good TOC and no actual file data on them.

> there are loads of places where you can say "hmm, if somehow the same numbers got
here, the results would be identical".

And that's exactly how they went about cracking it. :-)

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message