Re: MD5 collisions found - alternative?
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...
> >
> >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)
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?
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).
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...
Also, here again, as I tried to point out in my previous post, I'd say
that with finding passwords, you have more degrees of freedom. All
that matters is that their hashes are identical, when you want to get
access -- the string itself is totally irrelevant. While with signing
documents, you'd probably have some very specific message in mind (at
least not some random string) that you'd like to fake as originating
from someone else.
Thanks,
Almut
Reply to: