>>>>> "Almut" == Almut Behrens <[EMAIL PROTECTED]> writes:
Almut> On Tue, Aug 24, 2004 at 11:09:39PM +0200, Danny De Cock wrote: [...] Danny> being able to invert a hash function clearly means that the Danny> function is not collision-resistant, Almut> does it? (presuming that retrieving that x from hash(x) is not Almut> considered 'finding a collision' -- there might not necessarily Almut> exist another input value with the same hash, after all) But there must exist some hash value that is mapped from multiple inputs. And most likely, most hash values would be mapped from multiple inputs. Of course finding a collision still involves some luck, but not nearly as much as if you didn't have an inverse. Basically, if you take a random string, hash it, and take the inverse, the odds are pretty low that the inverse is the same as the original string. If you repeat multiple times with different random initial strings, you'll be very unlucky to have to do that for a long time. Almut> On a related note, as hash functions typically are many-to-one Almut> type of mappings, how can they ever be inverted anyway? I assume it to mean: find any string for which the hash value is the same as the given hash value. The string does not have to be the same as the original. (Of course, any hash function is invertible by using brute force. So when Danny says "being able to invert a hash function", there's an implicit "efficiently" or "easily" in there.) [...] Almut> Let me just use a trivial example - the simple addition operation Almut> - to elaborate on my notions of 'onewayness' and 'collision Almut> resistance': When we add 2+3, we get 5. Great. :) That sum kind Almut> of represents the 'hash' or checksum. This operation is clearly Almut> not reversible (i.e. when only being given the 5, you can never Almut> tell for sure whether 2+3, 1+4, -13+18, etc. were being added Almut> up). Thus, it's 'oneway', as I understand the term. Ah, but then using that definition of "oneway", every hash is oneway, since there must always be some hash value corresponding to two different input strings (assuming the input space is larger than the output space, which is generally the case). Since every hash is oneway, this renders the term meaningless. So the only useful notion of oneway is that the hash is not easily invertible (i.e. you can't easily find some string that produces a given hash value). -- Hubert Chan <[EMAIL PROTECTED]> - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
