Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 11:09:39PM +0200, Danny De Cock wrote:
> >>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.
I totally agree so far.
> being able to invert a hash function clearly means that the function is
> not collision-resistant,
does it?
(presuming that retrieving that x from hash(x) is not considered
'finding a collision' -- there might not necessarily exist another
input value with the same hash, after all)
On a related note, as hash functions typically are many-to-one type of
mappings, how can they ever be inverted anyway?
>
> 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? :)
hmm, well, I guess that's where our notions/terminology start to differ
slightly...
The main difference I see there is in the intent of the attacks, not
so much in the property they're trying a attack (or the lack of a
property the attack tries to exploit). The first type aims at
finding some y for some given x, so that their hashes do not differ,
but it's irrelevant what the specific hash value is. The second type
starts from some given hash(x), and tries to find some z that yields
the same hash (as in the password cracking case). But both types of
attacks are based on the existence of collisions. Only trying to find
that very x that originally produced hash(x) would be an attack on the
one-way property, IMHO.
I don't quite see why the second attack must have anything to do with
the function being one-way or not: even if the function was perfectly
one-way, but not collision-resistant, you might still find that z
(z is not necessarily the inverse of hash(x) after all -- at least not
as I understand the term... :)
Let me just use a trivial example - the simple addition operation - to
elaborate on my notions of 'onewayness' and 'collision resistance':
When we add 2+3, we get 5. Great. :) That sum kind of represents the
'hash' or checksum. This operation is clearly not reversible (i.e. when
only being given the 5, you can never tell for sure whether 2+3, 1+4,
-13+18, etc. were being added up). Thus, it's 'oneway', as I understand
the term. But it's more than trivial to come up with many, many pairs
of input values adding up to the same sum. That's essentially what I
thought is called 'finding a collision' -- leaving it entirely open
whether this can generally be done for some given hash (sum), or only
for some prior unknown hash...
Anyhow, as open as my definitions currently are, just as open am I to
adjust them as required :)
I guess we're basically all having the same concepts in the back of our
minds. We're just using different terminology (or the same terminology
in different ways) to talk about them -- which is always an unfailing
recipe for causing confusion...
Almut
Reply to: