Hash collision

Hash collision

In computer science, a hash collision or hash clash is a situation that occurs when two distinct inputs into a hash function produce 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 function which 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.

In searching

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.

Collision resistance

Given:A hash function H, two passwords x and y.

Weak collision resistance: For a given x, it is hard to find a y eq x such that H(x) = H(y). A user inputs a value, in this example a password, called initial value (x). If the hash function H 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 x and y such that H(x) = H(y). If the hash function H 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.

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 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.

ee also

* Pigeonhole principle

References

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

External links

* [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.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • hash collision — maišos konfliktas statusas T sritis informatika apibrėžtis Situacija, kai dvi ↑maišos funkcijos duoda tą patį rezultatą esant skirtingiems argumentams. Tokia situacija reiškia, kad du skirtingi duomenys turėtų būti rašomi į tą pačią maišos… …   Enciklopedinis kompiuterijos žodynas

  • hash collision — noun The situation where two or more inputs to a hash function produce identical output …   Wiktionary

  • Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space …   Wikipedia

  • Collision attack — In cryptography, a collision attack on a cryptographic hash tries to find two arbitrary inputs that will produce the same hash value, i.e. a hash collision. In contrast to a preimage attack, neither the hash value nor one of the inputs is… …   Wikipedia

  • Collision (disambiguation) — A collision is an isolated event in which two or more bodies exert relatively strong forces on each other for a relatively short time. This may specifically refer to: Traffic collision, two vehicles colliding Mid air collision, two planes… …   Wikipedia

  • hash conflict — maišos konfliktas statusas T sritis informatika apibrėžtis Situacija, kai dvi ↑maišos funkcijos duoda tą patį rezultatą esant skirtingiems argumentams. Tokia situacija reiškia, kad du skirtingi duomenys turėtų būti rašomi į tą pačią maišos… …   Enciklopedinis kompiuterijos žodynas

  • Collision resistance — is a property of cryptographic hash functions: a hash function is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H(a) = H(b), and a ≠ b.[1]:136 Every hash function with… …   Wikipedia

  • Collision resolution — may refer to Hash table implementations in computer science Collision response in classical mechanics This disambiguation page lists articles associated with the same title. If an internal lin …   Wikipedia

  • Collision (computer science) — Not to be confused with wireless packet collision. In computer science, a collision or clash is a situation that occurs when two distinct pieces of data have the same hash value, checksum, fingerprint, or cryptographic digest.[1] Collisions are… …   Wikipedia

  • Hash — Fonction de hachage On nomme fonction de hachage une fonction particulière qui, à partir d une donnée fournie en entrée, calcule une empreinte servant à identifier rapidement, bien qu incomplètement, la donnée initiale. Les fonctions de hachage… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”