[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: MD5 collisions found - alternative?

>>>>> "Almut" == Almut Behrens <almut-behrens@gmx.net> writes:

Almut> On Tue, Aug 24, 2004 at 11:09:39PM +0200, Danny De Cock wrote:


Danny> being able to invert a hash function clearly means that the
Danny> function is not collision-resistant,

Almut> does it?  (presuming that retrieving that x from hash(x) is not
Almut> considered 'finding a collision' -- there might not necessarily
Almut> exist another input value with the same hash, after all)

But there must exist some hash value that is mapped from multiple
inputs.  And most likely, most hash values would be mapped from
multiple inputs.  Of course finding a collision still involves some
luck, but not nearly as much as if you didn't have an inverse.
Basically, if you take a random string, hash it, and take the inverse,
the odds are pretty low that the inverse is the same as the original
string.  If you repeat multiple times with different random initial
strings, you'll be very unlucky to have to do that for a long time.

Almut> On a related note, as hash functions typically are many-to-one
Almut> type of mappings, how can they ever be inverted anyway?

I assume it to mean: find any string for which the hash value is the
same as the given hash value.  The string does not have to be the same
as the original.  (Of course, any hash function is invertible by using
brute force.  So when Danny says "being able to invert a hash function",
there's an implicit "efficiently" or "easily" in there.)


Almut> Let me just use a trivial example - the simple addition operation
Almut> - to elaborate on my notions of 'onewayness' and 'collision
Almut> resistance': When we add 2+3, we get 5.  Great. :) That sum kind
Almut> of represents the 'hash' or checksum. This operation is clearly
Almut> not reversible (i.e. when only being given the 5, you can never
Almut> tell for sure whether 2+3, 1+4, -13+18, etc. were being added
Almut> up). Thus, it's 'oneway', as I understand the term.

Ah, but then using that definition of "oneway", every hash is oneway,
since there must always be some hash value corresponding to two
different input strings (assuming the input space is larger than the
output space, which is generally the case).  Since every hash is oneway,
this renders the term meaningless.  So the only useful notion of oneway
is that the hash is not easily invertible (i.e. you can't easily find
some string that produces a given hash value).

Hubert Chan <hubert@uhoreg.ca> - http://www.uhoreg.ca/
PGP/GnuPG key: 1024D/124B61FA
Fingerprint: 96C5 012F 5F74 A5F7 1FF7  5291 AF29 C719 124B 61FA
Key available at wwwkeys.pgp.net.   Encrypted e-mail preferred.

Reply to: