Collision attack

A collision attack is an attack on a cryptological hash function with the aim of finding two different documents that are mapped to an identical hash value. In contrast to pre-image attacks , both documents (and thus the hash value) can be freely selected. If such collisions are found, this means, among other things, that the hash function is not suitable for cryptographic applications ( data encryption , digital signature processes ). Such collisions are often easy to find in hash functions that were not developed to meet cryptological requirements. An example of this is the CRC-32 checksum: The words "buckeroo" and "plumless" both lead to the check value 4ddb0c25.

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 every 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 comparison value against which other attacks are measured: A successful attack on a hash function must be more efficient than the birthday attack. To do this, he must exploit weaknesses in the hash function.

Naive approach

One of the most obvious approaches is to choose a document , calculate the hash value for it and then look for a second document that also has the hash value . This approach corresponds to a pre-image attack . ${\ displaystyle x}$ ${\ displaystyle y = H (x)}$ ${\ displaystyle x '}$ ${\ displaystyle y}$

 NaiveCollision(H)
     wähle zufälliges Dokument x
     y := H(x)
    REPEAT
        wähle zufälliges Dokument x' != x
    UNTIL H(x') = y
    RETURN (x, x')

This results in an average runtime of , where is the number of possible hash values. ${\ displaystyle m}$ ${\ displaystyle m}$

Example: SHA-1 always has a binary 160-bit output, i.e. 2 ¹⁶⁰ possible hash values. With SHA-1, this algorithm has to run the test an average of 2 ¹⁵⁹ repetitions before it finds a collision. For a computer that manages 1 billion attempts per second, the running time is 4.6 · 10 ³¹ years.

Birthday attack

A much higher probability of success is achieved with the birthday attack. We randomly select documents to calculate each up and then test whether, under the equal two. ${\ displaystyle q}$ ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {q}}$ ${\ displaystyle y_ {1} = H (x_ {1})}$ ${\ displaystyle y_ {q} = H (x_ {q})}$ ${\ displaystyle y_ {i}}$

 BirthdayCollision(H)
     wähle zufällige Dokumente x_1 ... x_q
    FOR i = 1 TO q
        berechne y_i := H(x_i)
     finde i, j mit i != j und y_i = y_j
    RETURN (x_i, x_j)

Analogous to the birthday paradox, this results in the probability of success with possible hash values ${\ displaystyle m}$

{\ displaystyle p = 1- \ left ({\ frac {m} {m}} \ cdot {\ frac {m-1} {m}} \ cdot {\ frac {m-2} {m}} \ cdots {\ frac {m-q + 1} {m}} \ right)}

After reshaping and estimating, it turns out that one has to scrutinize documents in order to obtain a probability of success of p = ½. ${\ displaystyle q = 1 {,} 18 \ cdot {\ sqrt {m}}}$

For the example SHA-1 this means that 1.18 · 2 ⁸⁰ attempts are required to find a collision with a probability of ½. For a computer that manages 1 billion attempts per second, the running time is only 4.5 · 10 ⁷ years.

Practical attacks

Most of the 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 generate further collisions, i.e. message pairs with the same hash value. Even collisions are known for the MD5 algorithm in which the beginning of the message can be freely selected. Thus, an attacker can create two documents with different content but the same hash value. For example, he can create two certificates that have the same hash value. One of them is a non-suspicious certificate, the second certificate authorizes him to issue further certificates, which actually only a certification authority is allowed to do. He now has the first signed by a certification authority . With a digital signature , however, the entire message is usually not signed, only its hash value. The attacker thus also has a signature for the second and can now create valid certificates for any key.

literature

Claudia Eckert: IT security: concepts - procedures - protocols . Oldenbourg, ISBN 978-3-486-58270-3 , pp. 349 .

Web links

Individual evidence

↑ Alexander Sotirov et al .: MD5 considered harmful today . December 30, 2008.

[1] Alexander Sotirov et al .: MD5 considered harmful today . December 30, 2008.