Collision attack

Collision attack

The collision attack tries to find two messages that have the same hash value. A cryptographic hash function should resist collision attacks. It is not the hardest to execute but it is pretty hard to prevent.

Collision resistance: It should be hard to find different messages m1, m2 such that H(m1) =
H(m2).

Why is it so hard to prevent?

Mainly because there is an infinity of possible files and not an infinite possibility of hash if you want them to be a certain length: it is not an injective function. However with a large bit length which many hash functions use today, it is almost impossible to find a collision in a reasonable amount of time on some secured hash functions. We could argue that a random collision is useless, since it is hard to get a malicious behavior from a random file. This is why the most dangerous attacks are the collision attacks with a chosen prefix. The goal of this attack is to find a suffix S2 such as H(P1)=H(P2+S2), with P1 and P2 two imposed prefix and H() a hash function.

Chosen-prefix

An extension of the collision attack is the chosen-prefix collision attack, which is specific to Merkle–Damgård hash functions. In this case, the attacker can choose two arbitrarily different documents, and then append different calculated values that result in the whole documents having an equal hash value. This attack is much more powerful than a classical collision attack.

Mathematically stated, given two different prefixes p1, p2, the attack finds two appendages m1 and m2 such that hash(p1 m1) = hash(p2 m2) (where is the concatenation operation).

This attack can be used on digital signatures :

The attacker can choose two arbitrarily different documents, and then append different calculated values that result in the whole documents having an equal hash value. This attack is much more powerful than a classical collision attack.

The usual attack scenario goes like this:

  1. Mallory creates two different documents A and B that have an
    identical hash value, i.e., a collision. Mallory seeks to deceive
    Bob into accepting document B, ostensibly from Alice.

  2. Mallory sends document A to Alice, who agrees to what the document says, signs its hash, and sends the signature to Mallory.

  3. Mallory attaches the signature from document A to document B.

Mallory then sends the signature and document B to Bob, claiming that Alice signed B. Because the digital signature match document B’s hash, Bob’s software is unable to detect the substitution.