Collision (computer science)


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.
Due to the possible applications of hash functions in data management and computer security, collision avoidance has become a fundamental topic in computer science.
Collisions are unavoidable whenever members of a very large set 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, using techniques like locality-sensitive hashing. Checksums, on the other hand, are designed to minimize the probability of collisions between similar inputs, without regard for collisions between very different inputs.

Computer security

Hash functions can map different data to the same hash, malicious users can take advantage of this to mimic data.
For example; consider a hash function that hashes data by returning the first three characters of the string it is given. A hacker, who does not know the user's password, could instead enter "Pass" - which would generate the same hash value of "Pas". Even though the hacker does not know the correct password, they do have a password that gives them the same hash - which would give them access. This type of attack is called a preimage attack.
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.