- Hash collision
computer science, a hash collision or hash clash is a situation that occurs when two distinct inputs into a hash functionproduce identical outputs.
All hash functions have potential collisions, though with a well-designed hash function, collisions should occur less often (compared with a poorly designed function) or be more difficult to find. In certain specialized applications where a relatively small number of possible inputs are all known ahead of time it is possible to construct a
perfect hash functionwhich maps all inputs to different outputs. However, many hash functions, including most cryptographic hash functions, produce a fixed size output from an arbitrarily long message. In such a design, there will always be collisions, because any given hash has to correspond to a very large number of possible inputs.
An efficient method of searching can be to process a lookup key using a hash function, then take the resulting hash value and then use it as an index into an array of data. The resulting data structure is called a "
hash table". As long as different keys map to different indices, lookup can be performed in constant time. When multiple lookup keys are mapped to identical indices, however, a hash collision occurs. The most popular ways of dealing with this are "chaining" (building a linked listof values for each array index), and "open addressing" (searching other array indices nearby for an empty space). Both of these, however, degrade the worst-case lookup complexity to linear timeof the number of elements.
Given:A hash function , two passwords and .
Weak collision resistance: For a given , it is hard to find a such that . A user inputs a value, in this example a password, called initial value (). If the hash function is weakly collision resistant, the probability of finding a second password with the same hash value as the initial one is negligible in the output length of the hash function.
Strong collision resistance: It is hard to find any and such that . If the hash function is strongly collision resistant, the probability of finding any two passwords with the same hash value is negligible in the output length of the hash function.
One desirable property of
cryptographic hash functions is that it is computationally infeasible to find a collision. The value of a hash function can be used to certify an input is unchanged by publishing the signed value of the hash "if" it is not feasible to produce a collision. "Feasible" in this context refers to any algorithm with an asymptotic running time polynomial in the output length of the hash function, which is usually much faster than a brute-force birthday attack.
The process of finding two arbitrary values whose hashes collide is called a "collision attack"; the process of finding one arbitrary value whose hash collides with another, given hash is called a
preimage attack. A successful preimage attack is a much more serious break than a successful collision attack.
* http://eprint.iacr.org/2005/425.pdf - Improved Collision Attack on Hash Function MD5, very technical.
* [http://www.cryptography.com/cnews/hash.html Cryptography Research - Hash Collision Q&A]
* [http://www.networkdls.com/Software.Asp?Review=64 Free collision & hash reversal tool]
Wikimedia Foundation. 2010.