How a SHA-1 collision is made

It’s been almost a month since Google and CWI Amsterdam published SHAttered, two different PDF files with the same SHA-1 hash, and I’ve been meaning to write up how it works. Partly because most of the coverage stopped at “SHA-1 is broken”, and partly because I had to go and check what we use SHA-1 for, and the answer was more interesting than I expected.

Some history first, because none of this came out of nowhere. In 2005 Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu showed you could find SHA-1 collisions in about 2⁶⁹ operations instead of the 2⁸⁰ a brute-force birthday attack would take. That was the moment cryptographers started saying “move off SHA-1”, and it’s been twelve years of people mostly not moving. In October 2015 Marc Stevens, Pierre Karpman and Thomas Peyrin produced a “freestart” collision, which is a collision where the attacker also gets to pick the starting state of the hash, so it doesn’t apply to real files, but it showed the full attack was close. The SHAttered team (Stevens, Elie Bursztein, Karpman, Ange Albertini and Yarik Markov) finished the job: about 2⁶³ SHA-1 computations, which they describe as 6,500 CPU-years for the first phase and 110 GPU-years for the second. Big, but well within reach of a large company or a government, and it’ll only get cheaper.

How SHA-1 is put together

To see why a collision on two PDFs is possible, you need the shape of the hash. SHA-1 is a Merkle–Damgård construction, like MD5 and SHA-256. It works like this:

1. Pad the message (a 1 bit, then zeros, then the message length as a 64-bit number) so that it’s a multiple of 512 bits, and split it into 512-bit blocks.
2. Start with a fixed 160-bit state, five 32-bit words that are written into the standard.
3. For each block, run the compression function, which takes the current state and the block and mixes them through 80 rounds of adds, rotates and boolean functions into a new 160-bit state.
4. The final state is the hash.

The important property is in step 3. The compression function only sees the current state and the current block. It has no memory of how you got to that state. So if two different messages ever reach the same internal state after the same number of blocks, then from that point on you can append any identical suffix you like to both of them and they’ll keep producing the same states, all the way to the same final hash. One collision in the middle gives you an infinite family of colliding files.

Identical prefix

That’s what SHAttered is. Both files start with the same prefix P, which they chose in advance: a PDF header and the start of an embedded JPEG. Running SHA-1 over P gets both files to the same state. Then come two blocks that differ between the files, and these are where all the computing went: finding the first one was the 6,500 CPU-year phase, and the second was the 110 GPU-year phase. After the first differing block the two states are different but close, a carefully controlled near-collision. The second differing block is built so that its difference exactly cancels out what’s left, and both files land on the same state again. Everything after that is an identical suffix S.

The PDF trick on top of that is clever and kind of funny. The differing blocks sit inside a JPEG comment field in the embedded image, and the bytes that differ change the length of a comment. In one file the JPEG parser skips over one image’s data, in the other it skips over a different image’s. The suffix contains both images. So the two files have mostly identical bytes and an identical hash, and render as different pages. Ange Albertini has been doing this sort of file-format polyglot stuff for years, and you can see his fingerprints all over it.

What this means in practice is that the attacker has to control both documents from the start. You can make a pair, a harmless one and a nasty one, get the harmless one signed or approved or committed, and then swap. You can not take a document someone else wrote and make a second document that matches its hash. That would be a second-preimage attack, and nobody is anywhere near one for SHA-1 (or MD5, for that matter).

Chosen prefix, and why it’s the scary one

There’s a stronger kind of collision attack, the chosen-prefix collision. Here the two files can start with different prefixes, chosen by the attacker, say “certificate for my-domain.com” and “certificate for a CA that can sign anything”. The attack computes some blocks to append to each that make the two states converge. It’s a lot harder, because the starting states are completely unrelated rather than identical.

For MD5, this was done in 2007 by Stevens, Arjen Lenstra and Benne de Weger, and at the end of 2008 a team including Stevens used it to get a rogue CA certificate out of a real certificate authority that was still signing with MD5. Then in 2012 the Flame malware turned out to have used its own chosen-prefix MD5 collision to forge a Microsoft code-signing certificate and pose as Windows Update on local networks, which, as someone who spent the MVP years telling people Windows Update was the safe way to get patches, was not a fun week.

For SHA-1, as far as I know, no chosen-prefix collision has been shown. Stevens’ own estimate from a 2013 paper put the cost somewhere around 2⁷⁷, which is far more than SHAttered. I’m not going to guess how long that number holds. Twelve years ago 2⁶⁹ sounded theoretical too.

So what actually breaks

The first casualty showed up the day after the announcement. Someone committed the two PDFs to the WebKit Subversion repository to add a test for the collision, and broke the repo, because SVN’s deduplication assumed SHA-1 meant identical content. That’s the general shape of the risk: anything that uses SHA-1 to decide two things are the same.

Git is the big one people asked about. Git names every object by SHA-1, but it hashes a header (blob <size>\0) in front of the content, so the SHAttered PDFs don’t collide as git blobs. Someone would have to redo the expensive part with git’s header as part of the prefix, which is entirely possible for an identical-prefix attack, it just costs another 6,500 CPU-years plus 110 GPU-years. Linus’s view was roughly that this isn’t the end of the world for git and that there’s a plan for moving off SHA-1. The SHAttered team also released a collision detection library from Stevens and Dan Shumow, which notices the telltale patterns of this kind of attack while it hashes. GitHub announced yesterday that it now runs that check on every SHA-1 it computes and rejects anything that looks like half of a colliding pair. That seems like the right stopgap.

TLS certificates are mostly already handled. CAs were supposed to stop issuing SHA-1 certificates at the start of 2016, and Chrome 56, which shipped at the end of January, stopped trusting them. If you still have an internal service with a SHA-1 cert, though, this is a good excuse to go and find it.

HMAC-SHA1 isn’t affected. HMAC’s security doesn’t depend on collision resistance in the same way, so your webhook signatures and your old API tokens are fine. I’d still use HMAC-SHA256 for anything new, simply so nobody has to have this conversation in an audit.

What we found

When I went looking in our own code, the scary one wasn’t git or certificates. It was our upload deduplication. When a user uploads a file, we hash it, and if we’ve already stored something with that SHA-1, we point the new upload at the existing object instead of storing it twice. It saves a decent amount of storage. It also means that, as of last month, someone could upload the harmless half of a colliding pair, then the nasty half, and have the second upload silently resolve to the first. Or the reverse, depending on who uploads first, which is worse if the first uploader is the attacker and the second is a victim sharing what they think is their own file.

It’s a stretch as an actual attack on us. Making the pair costs serious money, and our users are not that interesting. But it was a one-line change to hash with SHA-256 for new uploads, and a background job to rehash the old ones, so we did it. While I was in there I found two more places using SHA-1 as a cache key, which I also switched, not because there’s a realistic attack but because I don’t want to be the person explaining the difference between collision resistance and second-preimage resistance to an auditor in three years.

If you’re doing the same audit, my order would be anything that dedupes or trusts content by SHA-1 hash, then anything that signs something an attacker could have prepared (code, documents, certificates), then everything else at your leisure. For the replacement, just use SHA-256. It’s in every standard library you’ll touch, including .NET since 1.0, and nobody will ask you to justify it.*

* In the public key crypto post I quoted Schneier’s “Trust the math” and argued that attackers usually go around the math rather than through it. SHA-1 is what it looks like when the math itself does weaken: slowly, in public, with twelve years of warning that most of us (me included) ignored.