Hash collision

related topics
{math, number, function}
{math, energy, light}
{system, computer, user}
{war, force, army}

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

See also

Full article ▸

related documents
Weierstrass–Casorati theorem
Double negative elimination
Borel-Cantelli lemma
Nowhere dense set
Subalgebra
Magma computer algebra system
Category (mathematics)
Partial function
Calculus with polynomials
Dyadic rational
Malleability (cryptography)
Stirling number
Algebraic number
T1 space
Cayley's theorem
C*-algebra
Steiner system
Byte-order mark
Algebraic extension
Residue (complex analysis)
Atlas Autocode
Real line
Regular space
Extractor
GNU Octave
Alternative algebra
Partial fractions in integration
BPP
Euler's criterion
Subtraction