Hash collision
Encyclopedia
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
.
Collisions are unavoidable whenever members of a very large set (such as all possible person names, or all possible computer files) are mapped to a relatively short bit string. This is merely an instance of the pigeonhole principle.
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. Checksums, on the other hand, are designed to minimize the probability of collisions between similar inputs, without regard for collisions between very different inputs.
In most other applications, however, collisions of any kind are equally undesirable. Any collision in a hash table
increases the average cost of lookup operations. When fingerprints are used to avoid unnecessary file storage or transfer, e.g. in a proxy server
or backup system
, a collision may cause incorrect operation and even permanent data loss. A successful collision attack
on a cryptographic hash function may compromise the security
of computer and communication systems. Therefore, much effort is devoted to the design of algorithms that minimize the occurrence of collisions for various applications.
In the context of cryptographic hash function
s, the inability of an adversary to compute collisions efficiently is often essential to the security of the protocol. A collision-free hash function is a type of one-way function
that formalizes this property: it is not possible for a randomized polynomial-time algorithm to locate a collision of a collision-free hash function with non-negligible probability. It is unknown whether such a function exists.
Collision domain
A collision domain is a section of a network where data packets can collide with one another when being sent on a shared medium or through repeaters, in particular, when using early versions of Ethernet. A network collision occurs when more than one device attempts to send a packet on a network...
.
In computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a collision or clash is a situation that occurs when two distinct pieces of data
Data
The term data refers to qualitative or quantitative attributes of a variable or set of variables. Data are typically the results of measurements and can be the basis of graphs, images, or observations of a set of variables. Data are often viewed as the lowest level of abstraction from which...
have the same hash value
Hash function
A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys. For example, a single integer can serve as an index to an array...
, checksum
Checksum
A checksum or hash sum is a fixed-size datum computed from an arbitrary block of digital data for the purpose of detecting accidental errors that may have been introduced during its transmission or storage. The integrity of the data can be checked at any later time by recomputing the checksum and...
, fingerprint
Fingerprint (computing)
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...
, or cryptographic digest
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
.
Collisions are unavoidable whenever members of a very large set (such as all possible person names, or all possible computer files) are mapped to a relatively short bit string. This is merely an instance of the pigeonhole principle.
The impact of collisions depends on the application. When hash functions and fingerprints are used to identify similar data, such as homologous
Homology (biology)
Homology forms the basis of organization for comparative biology. In 1843, Richard Owen defined homology as "the same organ in different animals under every variety of form and function". Organs as different as a bat's wing, a seal's flipper, a cat's paw and a human hand have a common underlying...
DNA
DNA
Deoxyribonucleic acid is a nucleic acid that contains the genetic instructions used in the development and functioning of all known living organisms . The DNA segments that carry this genetic information are called genes, but other DNA sequences have structural purposes, or are involved in...
sequences or similar audio files, the functions are designed so as to maximize the probability of collision between distinct but similar data. Checksums, on the other hand, are designed to minimize the probability of collisions between similar inputs, without regard for collisions between very different inputs.
In most other applications, however, collisions of any kind are equally undesirable. Any collision in a hash table
Hash table
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
increases the average cost of lookup operations. When fingerprints are used to avoid unnecessary file storage or transfer, e.g. in a proxy server
Proxy server
In computer networks, a proxy server is a server that acts as an intermediary for requests from clients seeking resources from other servers. A client connects to the proxy server, requesting some service, such as a file, connection, web page, or other resource available from a different server...
or backup system
Backup software
Backup software are computer programs used to perform backup; they create supplementary exact copies of files, databases or entire computers. These programs may later use the supplementary copies to restore the original contents in the event of data loss....
, a collision may cause incorrect operation and even permanent data loss. A successful collision attack
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...
on a cryptographic hash function may compromise the security
Data security
Data security is the means of ensuring that data is kept safe from corruption and that access to it is suitably controlled. Thus data security helps to ensure privacy. It also helps in protecting personal data. Data security is part of the larger practice of Information security.- Disk Encryption...
of computer and communication systems. Therefore, much effort is devoted to the design of algorithms that minimize the occurrence of collisions for various applications.
In the context of cryptographic hash function
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
s, the inability of an adversary to compute collisions efficiently is often essential to the security of the protocol. A collision-free hash function is a type of one-way function
One-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...
that formalizes this property: it is not possible for a randomized polynomial-time algorithm to locate a collision of a collision-free hash function with non-negligible probability. It is unknown whether such a function exists.
See also
- Birthday attackBirthday attackA birthday attack is a type of cryptographic 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...
- Collision attackCollision attackIn 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...
(cryptographic hash functions) - Collision resolution (hash tables)