Orchid XP v7 wrote:
> Wikipedia.

Of course. Duh. Still getting used to these intratubes, ya know.

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

First, yes, of course they exists. As soon as you have meesages >128 
bits, you by necessity have collisions. Second, the function isn't 
supposed to be random, it's supposed to be non-invertible.

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

Two arbitrary files? Probably very close to 2^(-128)

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

The birthday paradox says "how many people can you put in a room before 
there's a probability that two have the same birthday."  If there's only 
two, it's still 1/365.

So if you're just looking at one hash and saying "how many files will 
make this hash", there's no birthday paradox probability involved. If 
you look at a big pile of files, and you ask "how likely is it that two 
have the same hash", the birthday paradox comes into it.

But if you're talking 2^(-128) to start with, you can go an awful long 
time before you have 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...

Correct. It was best-of-breed for a long time, and then still used under 
warnings for a long time later.

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

Nobody can give you a perfect assurance. I would guess, however, that 
you're much more likely to have the disk get scratched and unreadable as 
you pick it up out of the tray than to have an existing change cause a 
collision in the MD5 hash.

Hell, you're much more likely to get struck by lightning as you head 
home from work than have an accidental collision in an MD5 hash.

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

Very slim, or it would have happened much earlier.

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