What are other good attack examples that use the hash collision?

Question

When we consider the security of a cryptographic hash function with $n$ bit output, we simply say that it must have at least $\mathcal{O}(2^{n/2})$-time security against the (generic) collision attack due to the birthday attack / paradox.

When we talk about the attacks from an educative perspective, one needs to demonstrate good examples of the usage of the collision attack.

One attack example from Wikipedia based on the hash-and-sign paradigm

The usual attack scenario goes like this:

• 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.
• Mallory sends document A to Alice, who agrees to what the document says, signs its hash, and sends the signature to Mallory.
• 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 matches document B's hash, Bob's software is unable to detect the substitution.

Another one from our site: Squeamish Ossifrage's answer

I make three versions of a software package:

• the good one does what it is advertised to do which is something useful
• the bad one does something harmful noisily, like uploading credit card data to a bad place
• the sneaky one does something harmful quietly, like slowly making your screen look blurrier and blurrier over the course of a month, or silently disabling disk encryption

There's a sneaky catch: the good one and the sneaky one collide under MD5, but the bad one does not.

and in short, goes like this. The bad one is detected due to an incorrect hash, but the sneaky one survives since it has a hash collision with the good one.

What are other good attack examples that use the hash collision?

Answer 1

I think one of the most well known ones is the MD5 certificate attack.

This is a very long text, but let me just create an excerpt: they actually obtained a certificate from RapidSSL / Verisign for a proof of concept and then had two certificates with the same signature but for different sites. The main problem was getting the time to align, as the hash collision was only created for a specific time, as that is included in the hash.

Original:

 Common Name = "i.broke.the.internet.and.all.i.got.was.this.t-shirt.phreedom.org",

Rogue:

 Common Name = "MD5 Collisions Inc. (http://www.phreedom.org/md5)"

Note that they also chose a CA that issued certificates with a sequential serial number.

It will come at no surprise that these kind of services are generally automated, a human would probably have questioned that initial common name.

Answer 2

Collisions are a generic tool in many attacks beyond hashes. Examples:

1. Attack of double encryption $C=E_{(K_1,K_2)}(P)=E_{K_2}(E_{K_1}(P))$ given a few (say 2) plaintext/ciphertext pairs $(P_i,C_i)$, which basically finds a collision between $F(K_1)=(E_{K_1}(P_1),E_{K_1}(P_2))$ and $G(K_2)=(D_{K_2}(C_1),D_{K_2}(C_2))$.
2. Discrete logarithm, in Baby-Step/Giant-Step and it-s memory-lean variant Pollard's rho. Basically these solve $x[G]=A$ in some group (noted additively) with generator $G$ by finding a collision between $y[G]$ and $z[G]+A$ with $y$ and $z$ from disjoint sets, then get $x=y-z$ modulo the group order.
3. Integer factorization, using a different Pollard's rho.

The reduction of the effort from $O(n)$ to $O(\sqrt n)$ characteristic of collision search, combined with the possibility of parallel collision search on independent machines with little memory^*, is what makes these methods attractive. For 1, and 2 in the case of a generic group, this is the best known method.

---

^* See Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.