Hash collision

From Wikipedia, the free encyclopedia

In computer science, a hash collision is a situation that occurs when two distinct inputs into a hash function produce identical outputs.

Most hash functions have potential collisions, but with good hash functions they occur less often (or are harder to find) than with bad ones. 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 function which maps all inputs to different outputs. But in a function which can take input of arbitrary length and returns a hash of a fixed length (such as MD5), there will always be collisions, because any given hash can correspond to an infinite number of possible inputs.

Contents 1 In searching 2 Strong and weak collisions 3 In cryptography 4 See also 5 References

[edit] In searching

Main article: Hash table

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 list of 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 time of the number of elements.

[edit] Strong and weak collisions

For a given block x, if it is easy to find blocks x and y, with H(x) = H(y), it is referred to as weak collision resistance. Additionally, if the pair (x,y) is difficult to find, the hash function is said to have strong collision resistance.

[edit] In cryptography

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 method which is 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.

[edit] See also

• Pigeonhole principle

[edit] References

• http://www.cryptography.com/cnews/hash.html
• http://www.cits.rub.de/MD5Collisions/
• http://eprint.iacr.org/2005/425.pdf - Improved Collision Attack on Hash Function MD5, very technical.

Cryptographic hash functions and Message authentication codes (MACs) v • d • e
Hash algorithms: Gost-Hash | HAS-160 | HAS-V | HAVAL | MDC-2 | MD2 | MD4 | MD5 | N-Hash | RadioGatún | RIPEMD | SHA family | Snefru | Tiger | VEST | WHIRLPOOL | crypt(3) DES
MAC algorithms: DAA | CBC-MAC | HMAC | OMAC/CMAC | PMAC | UMAC | Poly1305-AES | VEST
Authenticated encryption modes: CCM | EAX | GCM | OCB | VEST   Attacks: Birthday attack | Collision attack | Preimage attack | Rainbow table | Brute force attack
Standardization: CRYPTREC | NESSIE   Misc: Avalanche effect | Hash collision | Hash functions based on block ciphers
Cryptography v • d • e
History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography
Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers