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

Re: MD5 collisions found - alternative?

* Quoting Almut Behrens (almut-behrens@gmx.net):

> On Tue, Aug 24, 2004 at 09:18:46PM +0200, Danny De Cock wrote:
> > 
> > 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...

If you can calculate the password from the hash it
would be a flaw in the one way funktion.

If you can calculate a collision from the hash and
the known password, that would be a lack off
collision resistance.

> 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.

The difference between a hash for a signature and
a hash for a password is that you know the plain
text in the first case.

> > 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...

See above.

> 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

But less knowledge.

> that matters is that their hashes are identical, when you want to get
> access -- the string itself is totally irrelevant.  While with signing

It has to meet certain criterias like being
printable characters and having a certain length,
but it doesn't have to have a meaning.

> 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.

This depends on how the attack really works. If
you just need to flip a few bits in a document it
might just look like typos (think crc32). If your
document is a tarball or a .deb you might be able
to insert a lot of "garbage" to it without being

- Rolf

Reply to: