How does the attack on MD5 work that allows a file to show its own (full) hash?

Question

I've recently stumbled across this "moment" on Twitter, where there are three files, that show their own MD5 hashes.

As an example, this GIF (screen-shotted in the following image), has the hash:

f5ca4f935d44b85c431a8bf788c0eaca

They obviously match. Also this looks like the sort of attack that would normally take $2^{128}$ evaluations instead of the usual $2^{64}$ for a collision because you're going for a very specific message-hash pair.

So, how does this work, that a file can display its own MD5 hash?

Answer 1

TO understand what is going on, you have to consider how MD5 works and how the collision attack works.

MD5 is a Merkle-Damgård hash function: it process the input data by blocks (of 64 bytes each), with a "running state" of 128 bits. So there is an internal function $f$ that takes as inputs the current state $s$ and the next message block $m$, and outputs the new state. The state after processing the last message block is the hash value.

The known collision attacks produce pairs of two-block messages that trigger a collision, with an arbitrary starting state value $s$. That is, given a 128-bit value $s$, the attack produces blocks $m_1$, $m_2$, $m'_1$ and $m'_2$, such that $(m_1,m_2) \neq (m'_1,m'_2)$, and $f(f(s, m_1), m_2) = f(f(s, m'_1) m'_2)$. The important point here is that since $s$ is arbitrary, then one can "chain" collisions: taking as value of state the output $s'$ of the expression above (i.e. what you get after processing $m_1||m_2$ or $m'_1||m'_2$), then you can run the attack again and find a new colliding pair $m_3||m_4$ and $m'_3||m'_4$.

At that point you have a four-way multicollision: the following four messages:

• $m_1||m_2||m_3||m_4$
• $m_1||m_2||m'_3||m'_4$
• $m'_1||m'_2||m_3||m_4$
• $m'_1||m'_2||m'_3||m'_4$

all hash to the same value.

Now iterate that process, by running the attack 128 times. You end up with 128 two-block collisions that can be chained, allowing a grand total of $2^{128}$ messages (each consisting of 128 pairs of blocks, i.e. 16384 bytes in length) that all hash to the same value.

Another crucial consequence of the Merkle-Damgård structure is that once you have a collision, then you can add an arbitrary suffix to the colliding messages, and it is still a collision. Similarly, since the attack works with any starting state value, you can also have an arbitrary prefix.

The rest of the attack is non-cryptographic hackery. Basically, you need a document format that is flexible enough to perform a "selection": something that can print out different pictures based on specific bytes somewhere else in the file. Roughly speaking, the file will have this format:

prefix || multicollision || suffix

where the prefix and suffix select the picture to display based on the contents of the "multicollision" part. Then you just have to select the right combination in the "multicollision" part (among the $2^{128}$) such that what is displayed matches the intended output: since this is a multicollision, the choice does not alter the final hash value.

This "image selection" mechanism can be more or less easy based on how flexible the format is. With Turing-equivalent languages (e.g. PostScript), this is trivial(*). With PDF and animated GIF, this is doable. With some formats, this is extremely hard or even impossible (e.g. if the format is "plain ASCII text readable by a human, then there is no "selection" mechanism).

---

^{(*) In fact, with a fully Turing-equivalent format, one can use Quine techniques to display the file hash even without leveraging any collision. It would work with unbroken hash functions like SHA-256 as well. But that's quite something else, and is not really a question of cryptography.}