# 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
```

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

```
```

```