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 -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
