Darren New wrote:
> 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.

Wikipedia. (So... utterly trustworthy then. Mind you, I believe there's 
a reference at the bottom.)

You know how it is - somebody posts a near-break, somebody else extends 
it, somebody else makes it go faster, etc.

>> 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, two *arbitrary* messages will 
> have low probablility of a hit.

Well... the fact that collisions can be constructed prove that they 
exist, which might suggest the function is "less random" than it should 
be...

>> (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.

True. I'd just like to put a number to it, that's all. ;-)

>> Actually, according to the Birthday Paradox, the probability in this 
>> case is much lower.
> 
> Not with only two messages.

Probability is defined as "if you did this X times, Y times the event 
would occur". So even with 2 messages, it matters.

>> 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.

Well, if people searched for decades without finding any collisions, 
they must be reasonably rare then. (At least, for the kinds of messages 
people tried hashing.) That suggests that at least the function doesn't 
collide *massively* more often than it should...

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

Ah yeah, sure, MD5 isn't cryptographically secure. I get that. I'm just 
wondering how useful it is for detecting random alterations.

>> 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... 
> 
> I'd say 1/3rd of my CDs that 
> coaster have a good TOC and no actual file data on them.

...which is why just checking that you can "see" the filenames is no 
good at all. Clearly the person who wrote the official procedure is a 
legal expert not a computer expert...

>> 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. :-)

The worrying thing being, how likely is it that such a thing might just 
happen by accident? :-}

Post a reply to this message