Hash collision

Last updated
John Smith and Sandra Dee share the same hash value of 02, causing a hash collision. Hash table 4 1 1 0 0 1 0 LL.svg
John Smith and Sandra Dee share the same hash value of 02, causing a hash collision.

In computer science, a hash collision or hash clash [1] is when two distinct pieces of data in a hash table share the same hash value. The hash value in this case is derived from a hash function which takes a data input and returns a fixed length of bits. [2]

Contents

Although hash algorithms, especially cryptographic hash algorithms, have been created with the intent of being collision resistant, they can still sometimes map different data to the same hash (by virtue of the pigeonhole principle). Malicious users can take advantage of this to mimic, access, or alter data. [3]

Due to the possible negative applications of hash collisions in data management and computer security (in particular, cryptographic hash functions), collision avoidance has become an important topic in computer security.

Background

Hash collisions can be unavoidable depending on the number of objects in a set and whether or not the bit string they are mapped to is long enough in length. When there is a set of n objects, if n is greater than |R|, which in this case R is the range of the hash value, the probability that there will be a hash collision is 1, meaning it is guaranteed to occur. [4]

Another reason hash collisions are likely at some point in time stems from the idea of the birthday paradox in mathematics. This problem looks at the probability of a set of two randomly chosen people having the same birthday out of n number of people. [5] This idea has led to what has been called the birthday attack. The premise of this attack is that it is difficult to find a birthday that specifically matches your birthday or a specific birthday, but the probability of finding a set of any two people with matching birthdays increases the probability greatly. Bad actors can use this approach to make it simpler for them to find hash values that collide with any other hash value – rather than searching for a specific value. [6]

The impact of collisions depends on the application. When hash functions and fingerprints are used to identify similar data, such as homologous DNA sequences or similar audio files, the functions are designed so as to maximize the probability of collision between distinct but similar data, using techniques like locality-sensitive hashing. [7] Checksums, on the other hand, are designed to minimize the probability of collisions between similar inputs, without regard for collisions between very different inputs. [8] Instances where bad actors attempt to create or find hash collisions are known as collision attacks. [9]

In practice, security-related applications use cryptographic hash algorithms, which are designed to be long enough for random matches to be unlikely, fast enough that they can be used anywhere, and safe enough that it would be extremely hard to find collisions. [8]

Collision resolution

In hash tables, since hash collisions are inevitable, hash tables have mechanisms of dealing with them, known as collision resolutions. Two of the most common strategies are open addressing and separate chaining. The cache-conscious collision resolution is another strategy that has been discussed in the past for string hash tables.

John Smith and Sandra Dee are both being directed to the same cell. Open addressing will cause the hash table to redirect Sandra Dee to another cell. HASHTB12.svg
John Smith and Sandra Dee are both being directed to the same cell. Open addressing will cause the hash table to redirect Sandra Dee to another cell.

Open addressing

Cells in the hash table are assigned one of three states in this method – occupied, empty, or deleted. If a hash collision occurs, the table will be probed to move the record to an alternate cell that is stated as empty. There are different types of probing that take place when a hash collision happens and this method is implemented. Some types of probing are linear probing, double hashing, and quadratic probing. [10] Open Addressing is also known as closed hashing. [11]

Separate chaining

This strategy allows more than one record to be "chained" to the cells of a hash table. If two records are being directed to the same cell, both would go into that cell as a linked list. This efficiently prevents a hash collision from occurring since records with the same hash values can go into the same cell, but it has its disadvantages. Keeping track of so many lists is difficult and can cause whatever tool that is being used to become very slow. [10] Separate chaining is also known as open hashing. [12]

Cache-conscious collision resolution

Although much less used than the previous two, Askitis & Zobel (2005) has proposed the cache-conscious collision resolution method in 2005. [13] It is a similar idea to the separate chaining methods, although it does not technically involve the chained lists. In this case, instead of chained lists, the hash values are represented in a contiguous list of items. This is better suited for string hash tables and the use for numeric values is still unknown. [10]

See also

Related Research Articles

<span class="mw-page-title-main">Hash function</span> Mapping arbitrary data to fixed-size values

A hash function is any function that can be used to map data of arbitrary size to fixed-size values, though there are some hash functions that support variable-length output. The values returned by a hash function are called hash values, hash codes, hash digests, digests, or simply hashes. The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter-storage addressing.

<span class="mw-page-title-main">Hash table</span> Associative array for storing key-value pairs

In computing, a hash table is a data structure that implements an associative array, also called a dictionary or simply map; an associative array is an abstract data type that maps keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored. A map implemented by a hash table is called a hash map.

The MD5 message-digest algorithm is a widely used hash function producing a 128-bit hash value. MD5 was designed by Ronald Rivest in 1991 to replace an earlier hash function MD4, and was specified in 1992 as RFC 1321.

In cryptography, SHA-1 is a hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecimal digits. It was designed by the United States National Security Agency, and is a U.S. Federal Information Processing Standard. The algorithm has been cryptographically broken but is still widely used.

A birthday attack is a bruteforce collision attack that exploits the mathematics behind the birthday problem in probability theory. This attack can be used to abuse communication between two or more parties. The attack depends on the higher likelihood of collisions found between random attack attempts and a fixed degree of permutations (pigeonholes). Let be the number of possible values of a hash function, with . With a birthday attack, it is possible to find a collision of a hash function with chance in where is the bit length of the hash output, and with being the classical preimage resistance security with the same probability. There is a general result that quantum computers can perform birthday attacks, thus breaking collision resistance, in .

<span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

In cryptography, a collision attack on a cryptographic hash tries to find two inputs producing the same hash value, i.e. a hash collision. This is in contrast to a preimage attack where a specific target hash value is specified.

The MD2 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1989. The algorithm is optimized for 8-bit computers. MD2 is specified in IETF RFC 1319. The "MD" in MD2 stands for "Message Digest".

<span class="mw-page-title-main">Radix tree</span> Data structure

In computer science, a radix tree is a data structure that represents a space-optimized trie in which each node that is the only child is merged with its parent. The result is that the number of children of every internal node is at most the radix r of the radix tree, where r = 2x for some integer x ≥ 1. Unlike regular trees, edges can be labeled with sequences of elements as well as single elements. This makes radix trees much more efficient for small sets and for sets of strings that share long prefixes.

<span class="mw-page-title-main">Open addressing</span> Hash collision resolution technique

Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternative locations in the array until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. Well-known probe sequences include:

SHA-2 is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression function itself built using the Davies–Meyer structure from a specialized block cipher.

<span class="mw-page-title-main">Linear probing</span> Computer programming method for hashing

Linear probing is a scheme in computer programming for resolving collisions in hash tables, data structures for maintaining a collection of key–value pairs and looking up the value associated with a given key. It was invented in 1954 by Gene Amdahl, Elaine M. McGraw, and Arthur Samuel and first analyzed in 1963 by Donald Knuth.

A rainbow table is a precomputed table for caching the outputs of a cryptographic hash function, usually for cracking password hashes. Passwords are typically stored not in plain text form, but as hash values. If such a database of hashed passwords falls into the hands of attackers, they can use a precomputed rainbow table to recover the plaintext passwords. A common defense against this attack is to compute the hashes using a key derivation function that adds a "salt" to each password before hashing it, with different passwords receiving different salts, which are stored in plain text along with the hash.

<span class="mw-page-title-main">Cuckoo hashing</span> Data structure hashing scheme

Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table, with worst-case constant lookup time. The name derives from the behavior of some species of cuckoo, where the cuckoo chick pushes the other eggs or young out of the nest when it hatches in a variation of the behavior referred to as brood parasitism; analogously, inserting a new key into a cuckoo hashing table may push an older key to a different location in the table.

In mathematics and computing, universal hashing refers to selecting a hash function at random from a family of hash functions with a certain mathematical property. This guarantees a low number of collisions in expectation, even if the data is chosen by an adversary. Many universal families are known, and their evaluation is often very efficient. Universal hashing has numerous uses in computer science, for example in implementations of hash tables, randomized algorithms, and cryptography.

<span class="mw-page-title-main">Merkle–Damgård construction</span> Method of building collision-resistant cryptographic hash functions

In cryptography, the Merkle–Damgård construction or Merkle–Damgård hash function is a method of building collision-resistant cryptographic hash functions from collision-resistant one-way compression functions. This construction was used in the design of many popular hash algorithms such as MD5, SHA-1, and SHA-2.

<span class="mw-page-title-main">Fingerprint (computing)</span> Digital identifier derived from the data by an algorithm

In computer science, a fingerprinting algorithm is a procedure that maps an arbitrarily large data item to a much shorter bit string, its fingerprint, that uniquely identifies the original data for all practical purposes just as human fingerprints uniquely identify people for practical purposes. This fingerprint may be used for data deduplication purposes. This is also referred to as file fingerprinting, data fingerprinting, or structured data fingerprinting.

The following tables compare general and technical information for a number of cryptographic hash functions. See the individual functions' articles for further information. This article is not all-inclusive or necessarily up-to-date. An overview of hash function security/cryptanalysis can be found at hash function security summary.

In computer science, a family of hash functions is said to be k-independent, k-wise independent or k-universal if selecting a function at random from the family guarantees that the hash codes of any designated k keys are independent random variables. Such families allow good average case performance in randomized algorithms or data structures, even if the input data is chosen by an adversary. The trade-offs between the degree of independence and the efficiency of evaluating the hash function are well studied, and many k-independent families have been proposed.

The HAT-trie is a type of radix trie that uses array nodes to collect individual key–value pairs under radix nodes and hash buckets into an associative array. Unlike a simple hash table, HAT-tries store key–value in an ordered collection. The original inventors are Nikolas Askitis and Ranjan Sinha. Askitis & Zobel showed that building and accessing the HAT-trie key/value collection is considerably faster than other sorted access methods and is comparable to the array hash which is an unsorted collection. This is due to the cache-friendly nature of the data structure which attempts to group access to data in time and space into the 64 byte cache line size of the modern CPU.

References

  1. ↑ Thomas, Cormen (2009), Introduction to Algorithms, MIT Press, p. 253, ISBN   978-0-262-03384-8
  2. ↑ Stapko, Timothy (2008), "Embedded Security", Practical Embedded Security, Elsevier, pp. 83–114, doi:10.1016/b978-075068215-2.50006-9, ISBN   9780750682152 , retrieved 2021-12-08
  3. ↑ Schneier, Bruce. "Cryptanalysis of MD5 and SHA: Time for a New Standard". Computerworld. Archived from the original on 2016-03-16. Retrieved 2016-04-20. Much more than encryption algorithms, one-way hash functions are the workhorses of modern cryptography.
  4. ↑ Cybersecurity and Applied Mathematics. 2016. doi:10.1016/c2015-0-01807-x. ISBN   9780128044520.
  5. ↑ Soltanian, Mohammad Reza Khalifeh (10 November 2015). Theoretical and Experimental Methods for Defending Against DDoS Attacks. ISBN   978-0-12-805399-7. OCLC   1162249290.
  6. ↑ Conrad, Eric; Misenar, Seth; Feldman, Joshua (2016), "Domain 3: Security Engineering (Engineering and Management of Security)", CISSP Study Guide, Elsevier, pp. 103–217, doi:10.1016/b978-0-12-802437-9.00004-7, ISBN   9780128024379 , retrieved 2021-12-08
  7. ↑ Rajaraman, A.; Ullman, J. (2010). "Mining of Massive Datasets, Ch. 3".
  8. 1 2 Al-Kuwari, Saif; Davenport, James H.; Bradford, Russell J. (2011). Cryptographic Hash Functions: Recent Design Trends and Security Notions. Inscrypt '10.
  9. ↑ Schema, Mike (2012). Hacking Web Apps.
  10. 1 2 3 Nimbe, Peter; Ofori Frimpong, Samuel; Opoku, Michael (2014-08-20). "An Efficient Strategy for Collision Resolution in Hash Tables". International Journal of Computer Applications. 99 (10): 35–41. Bibcode:2014IJCA...99j..35N. doi: 10.5120/17411-7990 . ISSN   0975-8887.
  11. ↑ Kline, Robert. "Closed Hashing". CSC241 Data Structures and Algorithms. West Chester University. Retrieved 2022-04-06.
  12. ↑ "Open hashing or separate chaining". Log22.
  13. ↑ Askitis, Nikolas; Zobel, Justin (2005). Consens, M.; Navarro, G. (eds.). Cache-Conscious Collision Resolution in String Hash Tables. International Symposium on String Processing and Information Retrieval. String Processing and Information Retrieval SPIRE 2005. Lecture Notes in Computer Science. Vol. 3772. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 91–102. doi:10.1007/11575832_11. ISBN   978-3-540-29740-6.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.