Re: MD5 collisions found - alternative?
On Tue, 24 Aug 2004, Almut Behrens wrote:
On Tue, Aug 24, 2004 at 12:44:53PM +0200, Danny De Cock wrote:
(...) but the verification of password hashes, such as used in pam,
rely on the hash function's oneway-feature rather than on its
collision-resistance...
not sure I understand -- so, if someone would like to explain this
aspect to the non-cryptographist, please go ahead :)
a cryptographic hash function, such as md5, sha1, ripemd-160, to name the
most commonly used cryptographic hash functions are constructed to have at
least the following properties:
1. it is hard to find two distinct inputs to the hash function, say x and
y, so that hash(x) equals hash(y)
2. they are one-way, i.e., it is hard to find the value x given hash(x)
note that these properties have nothing to do with encryption mechanisms.
that is a complete other business.
for password schemes, it is important that the hash function used is
one-way: if one knows the password, it must be very simple/easy to compute
the hash of that password, but if someone obtained the hash of a password,
it must be very difficult to find something, say z, so that hash(z) equals
the hash of the password.
for digital signature schemes, we need the first property: if I have
someone sign a document, say A, the document itself is not signed, but the
hash of that document.
if a hash function which is not collision-resistant is used in an
application where that property matters, the attack scenario goes as
follows: if I know there are two documents, say B and C, which hash to the
same hash value, i.e., hash(B) = hash(C), and I have you sign hash(B), you
have also produced a digital signature on document C.
the meaning of `the hash function is not collision-resistant' is this: I
know these documents B and C exist, and they are more or less easy to
find.
if the hash function were collision-resistant, I know they exist, but they
are *not* easy to find.
the attacks described in the paper referred to in the original post do
give examples of different inputs which hash to the same output. for some
of the hash algorithms that have been broken, this requires *very* limited
resources. the authors refer to `calculations by hand' ];->
the exact procedure to find these inputs does not really matter: showing
the existance of even a single pair of inputs is sufficient to show the
hash function is not collision-resistant, and that is what the authors
did, i.e., full stop.
therefore, the broken hash functions should not be used for schemes where
the collision-resistance is important. all this means that these
functions can still be used for applications if one only needs the one-way
property of the function, e.g., to hash passwords.
does this clarify things a bit more? :))
Almut
-----------------------------------------------------------------------------
expert in just too late deliveries and applied cryptography
-----------------------------------------------------------------------------
mail: decockd:at:esat:dot:kuleuven:dot:ac:dot:be http://godot.be
godot:at:advalvas:dot:be http://godot.studentenweb.org
godot:at:godot:dot:be web: http://www.esat.kuleuven.ac.be/~decockd
Reply to: