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.
ACK.
> > 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
noticed.
- Rolf
Reply to: