A collision attack is an attack on a cryptologic hash function with the goal of finding two different documents mapped to an identical hash value. In contrast to preimage attacks, both documents (and thus also the hash value) are freely selectable. If such collisions are found, this means, among other things, that the hash function is not suitable for cryptographic applications (data encryption, digital signature methods). For hash functions that were not designed to meet cryptologic requirements, such collisions are often easy to find.
A generic attack on keyless hash functions is the birthday attack, which uses the eponymous birthday paradox to achieve a high probability of success. This attack is possible on any hash function and significantly reduces the number of attempts (to the square root of the possible hash values). Since this attack is always possible, it forms a benchmark against which other attacks are measured: a successful attack on a hash function must be more efficient than the birthday attack. To do this, it must exploit weaknesses in the hash function.
Most standardized hash functions are based on the Merkle-Damgård construction. Due to their structure, once a collision has been found, it is easy to create further collisions, i.e. message pairs with the same hash value. The MD5 algorithm is even known to have collisions in which the beginning of the message is freely selectable. Thus, an attacker can create two documents with different content but the same hash value. For example, it can create two certificates that have the same hash value. One of them is an unsuspicious certificate, the second certificate entitles him to issue further certificates, which actually only a certificate authority is allowed to do. He now has the first one signed by a certification authority. In the case of a digital signature, however, it is usually not the entire message that is signed, but only its hash value. This means that the attacker also has a signature for the second one and can now create valid certificates for any key.
---
One of the most famous examples of a collision attack occurred with the MD5 hash function. In 2004, researchers demonstrated that it was possible to generate two different inputs that produced the same MD5 hash value. This discovery undermined the security of systems that relied on MD5 for integrity checks and digital signatures, prompting the deprecation of MD5 in favor of more secure hash functions like SHA-1 and SHA-256.
Another notable example is the SHAttered attack, published in 2017, which exploited vulnerabilities in the SHA-1 hash function to find collisions. The SHAttered attack demonstrated that SHA-1 was no longer suitable for cryptographic use due to its susceptibility to collision attacks, leading to widespread abandonment of SHA-1 in favor of stronger hash functions.
In summary, collision attacks pose a significant threat to the security of cryptographic systems that rely on hash functions. Understanding these attacks and using secure hash functions with robust collision resistance properties is crucial for maintaining the integrity and security of cryptographic protocols and applications.
