Nicolas Alvarez wrote:

> The question is how easily you can "construct" a collision.

Actually, I think the question is how evenly scattered the collisions 
are... ;-)

Post a reply to this message

Tim Attwood wrote:
>> By the way, do you know how MD5 works? It's kind of interesting. I'm 
>> currently trying to implement it in Haskell - but I'm being thwarted 
>> because it uses that brain-deadness known as "little-endian integers". 
>> (These really shouldn't exist...)
> 
> Someone at Oxford has done it, but I think it uses the FFI.
> http://web.comlab.ox.ac.uk/oucl/work/ian.lynagh/md5/haskell-md5-0.1.0/ 

In fact, *several* people have done it - ranging from FFI bindings to 
existing MD5 libraries to pure Haskell implementations in different forms.

I'm mainly trying to implement it in Haskell for fun; it'll probably go 
too slow to be useful. (But we'll see about that...)

Post a reply to this message

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

Darren New wrote:

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

Indeed. But I'm using it for its randomness...

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

Depends where you live. Apparently in the USA the chance of being killed 
by lightning is only 1 in 700,000. That's actually quite a *high* 
probability. o_O

Apparently the changes of winning the National Lottery (absurdly 
improbable) is x * 10^(-8), for some "small" x. (I don't remember what 
it is.) 2^(-128) works out as x * 10^(-39) - the theoretical probability 
of winning the Lottery several times back to back. I guess even if we 
assume MD5 is moderately screwed, you'd still have to estimate the 
collision probability at 10^(-24) or something. That's still fairly 
improbable...

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

Yeah, I'm fairly sure it's quite a low probability too. I'd just like to 
be able to put an objective figure to it. ;-)

Post a reply to this message

Orchid XP v7 wrote:
> Depends where you live. Apparently in the USA the chance of being killed 
> by lightning is only 1 in 700,000. That's actually quite a *high* 
> probability. o_O

Exactly. Far far larger than 2^-128.

> Apparently the changes of winning the National Lottery 

Funny enough, I saw where someone had looked up the death statistics, 
and figured out you had a 2000x better chance of being killed between 
the time you bought your lottery ticket and the time the big winner was 
announced than the chance of you actually being the big winner.

> Yeah, I'm fairly sure it's quite a low probability too. I'd just like to 
> be able to put an objective figure to it. ;-)

If you could give a reliable objective number, you'd know enough of how 
it works to calculate it without going thru the actual math.

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

Orchid XP v7 wrote:

> I'm mainly trying to implement it in Haskell for fun; it'll probably go 
> too slow to be useful. (But we'll see about that...)

Oh my *God*, I've just spent my entire evening trying to make this damn 
thing work! I was thwarted by the following:

- I mis-typed certain magic numbers, causing the output to be a few 
digits wrong. >_<

- I forget the final state-add step. I spent literally *ages* trying to 
figure out why all the output was correct up until the very last stage.

- The hash is little-endian. Damn thing! I actually had the right 
output, it just looked wrong because you have to turn it half-backwards 
according to the dumb RFC. *sigh*

So yays! My program now correctly hashes the 0-byte string to yield an 
MD5 hash of D41D8CD98F00B204E9800998ECF8427E.

Now all I need to do is implement the very fiddly bit-padding algorithm 
and I'm golden...

It's TF2 time!

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> So yays! My program now correctly hashes the 0-byte string to yield an 
> MD5 hash of D41D8CD98F00B204E9800998ECF8427E.

  I could do that much faster than you. Probably in something like
10 seconds. ;)

-- 
                                                          - Warp

Post a reply to this message

Warp escribió:
> Orchid XP v7 <voi### [at] devnull> wrote:
>> So yays! My program now correctly hashes the 0-byte string to yield an 
>> MD5 hash of D41D8CD98F00B204E9800998ECF8427E.
> 
>   I could do that much faster than you. Probably in something like
> 10 seconds. ;)
> 

if (data.length == 0) {
	return "D41D8CD98F00B204E9800998ECF8427E";
} else {
	error("Not implemented yet");
}

Post a reply to this message

Nicolas Alvarez <nic### [at] gmailisthebestcom> wrote:
>         error("Not implemented yet");

  error("I'll implement this when I have the time.")

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
>> So yays! My program now correctly hashes the 0-byte string to yield an 
>> MD5 hash of D41D8CD98F00B204E9800998ECF8427E.
> 
>   I could do that much faster than you. Probably in something like
> 10 seconds. ;)

Well, I now have the full algorithm working. :-P

Or at least, it seems to work for messages shorter than 52 bytes anyway. 
It seems there's still a glitch in the padding algorithm that makes it 
go wrong for messages longer than 1 block...

I'm just amazed that I managed to implement an algorithm as complex and 
fiddly as MD5 in only 2 days. Heh.

Post a reply to this message