# 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:**