PDA

View Full Version : Quick Question



themillofkeytone
05-15-2004, 10:56 AM
I was reading the FAQ, and I had a quick question. What would happen if the MD5 algorithm were internally secure? By that, I mean is it possible that for every input that is the size of the MD5 digest, there is a unique output? Now, only a "perfect" algorithm could achieve that, but has that been taken into account?

jlcooke
05-15-2004, 12:22 PM
Originally posted by themillofkeytone
I was reading the FAQ, and I had a quick question. What would happen if the MD5 algorithm were internally secure? By that, I mean is it possible that for every input that is the size of the MD5 digest, there is a unique output? Now, only a "perfect" algorithm could achieve that, but has that been taken into account?

Even if it were, this does not change the fact that a collision will still only take 2^64 computations.

Point being - any 128 bit hash is not secure enough from collision attacks - perfect or not.

Mystwalker
05-15-2004, 07:41 PM
Assuming an algorithm f(x) = (x + 1) mod 2^128, we'd have an injective (bijective for that matter, but I don't need surjectivity here) function, where no collisions occur. Or did I miss something?

jlcooke
05-15-2004, 08:09 PM
Originally posted by Mystwalker
Assuming an algorithm f(x) = (x + 1) mod 2^128, we'd have an injective (bijective for that matter, but I don't need surjectivity here) function, where no collisions occur. Or did I miss something?

Bijection doesn't apply here.

Assuming MD5 is a perfect 128 bit hash doesn't change the fact that it's insecure to collision attacks.

I suggest reading http://www.md5crk.com/?sec=approach and a few CiteSeer papers on "collision attacks" and "birthday attacks". If you're the web surfing kind: http://www.google.ca/search?q=birthday+attack - the first page of links are worth exploring deeper (MathWorld is one my fav sites for this sort of thing).

The PVO-MW paper: http://www.scs.carleton.ca/~paulv/papers/acmccs94.pdf give more formal references for you to follow.

Mystwalker
05-16-2004, 07:22 AM
Already read that paper and the approach site and Mathworld is my favorite when it comes to maths. :)

Well, we only consider 128-bit values as input, right? Then my algorithm would create one big circle with every number of the value set in it. Thus, no two inputs provide the same output.

Granted, when there are more than 128^2 possible inputs, the pigeon hole can be applied. And a "perfect" algorithm, as themillofkeytone named it, is highly unlikely even for 128^2 possible inputs (and I don't think MD5 it such an algorithm).
AFAI get it, it's mainly a theoretical question...

jlcooke
05-17-2004, 01:01 PM
Originally posted by Mystwalker
Already read that paper and the approach site and Mathworld is my favorite when it comes to maths. :)

Well, we only consider 128-bit values as input, right? Then my algorithm would create one big circle with every number of the value set in it. Thus, no two inputs provide the same output.

Granted, when there are more than 128^2 possible inputs, the pigeon hole can be applied. And a "perfect" algorithm, as themillofkeytone named it, is highly unlikely even for 128^2 possible inputs (and I don't think MD5 it such an algorithm).
AFAI get it, it's mainly a theoretical question...

128^2 != 2^128 btw. ;)

And md5crk takes 256bit inputs since we encode a 128bit value into an ASCI string of printable characters.

Cheers.

Mystwalker
05-17-2004, 01:26 PM
Originally posted by jlcooke
128^2 != 2^128 btw. ;)

D'oh! ;)


And md5crk takes 256bit inputs since we encode a 128bit value into an ASCI string of printable characters.

Ah, ok. Thanks for the explanation, now I see through. :thumbs: