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

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? :))


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: