Collision attack

A collision attack is an attack on a cryptographic hash function with the aim to find two different documents, leading to an identical hash value. In contrast to pre-image attacks are both documents (and thus the hash value) freely selectable.

A popular strategy for keyless hash functions is the birthday attack that uses the eponymous birthday paradox, in order to achieve a high probability of success. As a result, the number of tests are greatly reduced. This attack is always assumed that there are no weaknesses in the algorithm are known, since one would otherwise use these weaknesses to solve the problem. It is also assumed that the set of possible documents is at least twice as large as the number of possible hashes. This is called compression property.

Naive approach

One of the most obvious approach is to select a document to calculate the hash value for this, and then seek a second document, which also has the hash value. This approach corresponds to a pre-image attack.

Naive Collision (H )       choose random document x       y: = H (x)       REPEAT          choose random document x '! = x       UNTIL H ( x ' ) = y       RETURN ( x, x ' ) This results in an average maturity of, the number of possible hash values ​​is.

Example: SHA- 1 always has a binary 160 -bit output, ie possible hash values ​​. This algorithm must therefore run the test on average repeats until it finds a collision in SHA-1. For a computer, which creates 1 billion attempts per second, the runtime is 4.6 · 1031 years.

Birthday attack

A much higher probability of success can be achieved with the birthday attack. Here we randomly select documents to calculate each up and then test whether, under the two are the same.

Birthday Collision (H )       select random documents x_1 ... x_q       FOR i = 1 TO q          calculate y_i: = H ( x_i )       find i, j with i! = j and y_i = y_j       RETURN ( x_i, x_j ) Here, then, analogous to the birthday paradox of possible hash values ​​of the probability of success

After transformation and analysis concludes that one must go through patterns about documents to obtain a success probability of p = ½.

For example, SHA-1, this means that 1.18 · 280 trials will be required to find a probability of ½ a collision. For a computer, which creates 1 billion attempts per second, the term is only 4.5 · 107 years here.

Practical attacks

Most standardized hash functions are based on the Merkle - Damgård construction. Due to their structure, it is easy even when a collision has been found to produce more collisions, that messages with the same hash value pairs. Even collisions are known for the MD5 algorithm, in which the beginning of the message is optional. Thus, however, create two documents with different content same hash value, an attacker. For example, he can create two certificates that have the same hash value. One of these is for an unsuspecting certificate, the second certificate entitling him to issue other certificates, which actually only one certification body is allowed. He can now sign the first from a CA. In a digital signature but not the whole message, only its hash value is signed in the rule. Thus, the attacker also has a signature for the second, and can now create valid certificates for any key.