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.
confirmed.
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 :)
summarizing:
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.
Thanks,
Almut
--
To UNSUBSCRIBE, email to debian-security-REQUEST@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
Reply to: