8
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Consider this question as an educative perspective to see the nice examples around. $\endgroup$
    – kelalaka
    Dec 22, 2020 at 16:31
  • $\begingroup$ Would an attack against double encryption with little memory count? Or factoring, Discrete log using Pollard's rho? These are collision search, and it's only a matter of calling what's made to collide a hash. $\endgroup$
    – fgrieu
    Dec 22, 2020 at 17:22
  • $\begingroup$ @fgrieu any attack that uses collision. I'm not looking for how to find collisions. Not clear? $\endgroup$
    – kelalaka
    Dec 22, 2020 at 17:28
  • 1
    $\begingroup$ Ok I see what you mean now. $\endgroup$
    – Modal Nest
    Dec 22, 2020 at 19:50
  • 1
    $\begingroup$ Maybe you should change the title somewhat if you accept fgrieu's answer, as it explicitly requests examples of hash collisions. $\endgroup$
    – Maarten Bodewes
    Dec 24, 2020 at 15:18

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.