[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 09:18:46PM +0200, Danny De Cock wrote:
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...

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)

just to make sure we're using the same terminology: 1. is what I'd consider collision resistance, whereas the oneway aspect (2.) refers to the difficulty of retrieving the original string (x above) used in computing the hash in the first place.


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.

but that's property 1 then (i.e. collision resistance), isn't it?

not exactly the same, but it is true that the two properties are somehow related: if you can find a z so that hash(z) equals hash(x), and x and z are different, then you have found a collision, if not, you have inverted the hash function.

being able to invert a hash function clearly means that the function is not collision-resistant, but finding collisions does not mean that the hash function is not one-way :)

 an attack relying on the collision-resistance takes as
	input two values x and y and results in an
	output hash(x) which equals hash(y), but
 an attack on the one-way property of the hash function takes as
	input hash(x) and produces an
	output z so that hash(z) equals hash(x).

this is quite different, isn't it? :)

And that's essentially what I was trying to point out, as I don't think that, WRT password verification, you'll ever need to know the original x. It's completely sufficient to find some other password y, z, or whatever, such that

 hash(some_password) == stored_hash

where the stored/given hash has originally been computed as hash(x).

this is true, but this relies on the one-way property of the hash function, not on its collision-resistance: in userid/password verification schemes, one is given an output of the hash function, namely hash(password), and even if there were a collision for the hash function, chances are slim that the password equals the particular input which produces the collision...

the attack scenario is different...

Thus, I'd still say it's not the oneway aspect that matters here, but rather the collision resistance of the hash function...

Of course, as Mike has already pointed out, it's a completely different story whether you can find _any_ collision (for an arbitray hash value), or a collision for some _given_ cryptographic hash value.

Otherwise, I hardly have any objections to what you wrote :)

does this clarify things a bit more? :))

not so sure... :) -- i.e. I don't really see a huge conceptual difference between two 'passwords' or 'documents' hashing to the same value...

there is a difference: the passwords are not directly fed to the hash function. they are first encoded/expanded to make them of the proper size (i.e., 512 bits) for the hash function. in what I said/wrote, `document' one might read `input block for the hash function' ];-)

the attacks described in the papers referred to in the original post deal with input blocks which are crafted to produce a collision, and these input blocks can be preceded by any number of `document' content, so the attacks do not really apply to password-based schemes, but they do on documents...

cu, g.


To UNSUBSCRIBE, email to debian-security-REQUEST@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org

Reply to: