The First SHA-1 Collision: What It Means for Certificates and Git

Last Thursday, February 23, Google and CWI Amsterdam announced the first practical SHA-1 collision. As proof, they published two PDF files that show different content and have the same SHA-1 hash. People have been warning about SHA-1 for more than a decade, so in one sense nothing new happened. But “theoretically weak” just turned into “here are the files,” and that changes conversations. I want to walk through what the attack actually is, why your HTTPS certificates were already on their way out, and what the Git developers are saying, since Git names everything with SHA-1.

What a collision is, and what it isn’t

A hash function takes input of any size and returns a short, fixed-size digest. For a cryptographic hash, finding two different inputs with the same digest is supposed to be computationally infeasible. A collision is exactly that: two distinct messages, one hash.

The detail that matters is who gets to pick the messages. In a collision attack, the attacker makes both of them. The team’s paper, The first collision for full SHA-1, describes theirs as an identical-prefix collision. Both files begin with the same prefix, each then gets its own two specially computed blocks, and from that point on the two produce the same hash for any identical suffix you append. The researchers chose that prefix carefully so it works as a PDF header, which is what lets the two documents display arbitrarily chosen, different content. The paper also recalls that a more powerful kind of attack, the chosen-prefix collision, was demonstrated against MD5 years ago and eventually led to a rogue certificate authority. What was announced for SHA-1 last week is the identical-prefix kind.

A preimage attack is a different and much harder problem. There, the hash already exists, maybe for a file somebody else wrote, and the attacker has to come up with a new input that matches it. Nothing announced last week does that. On the Git mailing list, Joey Hess noted that this break doesn’t let someone take an object already sitting in a repository and generate a colliding replacement for it, and Linus Torvalds stressed that the new attack is not a preimage attack.

How big the computation was

Google’s post gives the scale: nine quintillion SHA-1 computations in total, 6,500 years of CPU computation for the first phase of the attack, and 110 years of GPU computation for the second. The paper puts the total effort at the equivalent of 2^63.1 SHA-1 compressions, and its abstract rounds the GPU figure to about 100 GPU years. Both say that is still more than 100,000 times faster than a brute force search.

The paper also prices the expensive second phase on rented Amazon GPUs: about US$560K using p2.16xlarge instances at the nominal hourly price, or about US$110K for a patient attacker waiting for low spot prices on smaller g2.8xlarge instances. That’s out of reach for casual vandals and very much within reach of a well-funded attacker. Google says it will wait 90 days before releasing code that creates colliding PDF pairs, that it has added protection for Gmail and G Suite users, and that it’s offering a free detection system to the public.

Why certificates were already moving

A certificate’s signature is computed over a hash of the certificate, so the hash algorithm is part of what the CA is vouching for. CWI’s press release spells out the danger: a SHA-1 signature obtained for one file can be misused as a valid signature for a file that collides with it. That’s the reason browsers and CAs started leaving SHA-1 long before anyone had colliding files.

In September 2014, Google announced that Chrome would start sunsetting SHA-1 in HTTPS certificate signatures with Chrome 39, showing a degraded security indicator for sites whose chains used SHA-1 and stayed valid past January 1, 2017. The same month, Mozilla said it agreed with Microsoft and Google that SHA-1 certificates shouldn’t be issued after January 1, 2016, or trusted after January 1, 2017. In October 2014 the CA/Browser Forum passed Ballot 118, which says that effective January 1, 2016, CAs must not issue new subscriber or subordinate CA certificates using SHA-1. That rule is still there in section 7.1.3 of the Baseline Requirements, version 1.4.2 from January. It doesn’t cover root certificates, and Chrome’s 2014 post explains why that’s fine: clients trust roots by their identity, not by the signature on them.

The Baseline Requirements picked up one more change that’s relevant here. Since September 30, 2016, CAs have had to generate non-sequential serial numbers containing at least 64 bits of output from a CSPRNG. My understanding is that this helps because an identical-prefix attack has to fix its prefix before the long computation starts, and the serial number sits near the top of the certificate, chosen by the CA, where an attacker can’t predict it.

The end of the road came this winter. In November, Google said Chrome 56 would stop trusting SHA-1 certificates and show an interstitial warning instead, and Chrome 56 was promoted to the stable channel on January 25. Certificates chaining to locally installed roots follow in Chrome 57, due in March, unless an enterprise policy keeps them working. Mozilla had been disabling SHA-1 for a growing share of Firefox users since Firefox 51, and on the day of the announcement it wrote that the policy would reach all Firefox users the next day and is enabled by default in Firefox 52. That applies to certificates chaining to roots in Mozilla’s CA program, not manually imported ones. Microsoft’s Edge team removed the lock icon for SHA-1 sites in Edge and Internet Explorer 11 last summer, starting with the Windows 10 Anniversary Update, and has said both browsers will go further and block SHA-1 signed TLS certificates that chain to its trusted root program.

Checking your own certificates

This takes a minute with OpenSSL. The x509 command prints the whole certificate in text form with -text, including its signature algorithm:

openssl x509 -in server.crt -noout -text | grep "Signature Algorithm"

You want to see something like sha256WithRSAEncryption. If it says sha1WithRSAEncryption, that certificate needs replacing. To look at what a live server actually sends, s_client with -showcerts prints every certificate in the server’s list, not just the leaf:

openssl s_client -connect example.com:443 -servername example.com -showcerts < /dev/null

Copy each PEM block into its own file and run the x509 command on it. The intermediate matters as much as your own certificate, while a SHA-1 signature on a root’s self-signed certificate isn’t the concern.

What it means for Git

Git names every object it stores, whether it’s file contents, a directory tree, or a commit, with SHA-1. As Pro Git explains, the hash covers a small header with the object’s type and size, followed by the content. Those names are how commits point to trees and parents, so the hash sits under everything.

The reaction on the Git mailing list has been calm. Junio C Hamano, Git’s maintainer, wrote that the project wants to continue its work to switch away from SHA-1, but that the announcement doesn’t fundamentally change anything and nobody is panicking. Linus argued that this style of attack needs a chunk of random-looking data hidden in both colliding objects, which is easy in a PDF and harder to sneak into commits and trees unnoticed, and that cheap checks for the attack’s telltale patterns would make it pointless against Git. He still wants Git to move to a bigger hash, and he pointed out that opaque binaries like firmware images are more exposed than source code. Jeff King noted that the type and size header doesn’t save you, since the colliding files are the same length, but that git fsck already complains about things like NUL bytes in a commit.

On February 23, Jeff King posted patches that add a collision-detecting SHA-1 implementation behind an opt-in USE_SHA1DC build knob, so nothing changes unless you build with it. His timings showed SHA-1 itself about 3 to 4 times slower, though most everyday commands barely changed. As I write this it’s being reviewed on the list, it isn’t part of Git 2.12.0, which came out February 24, and it isn’t a default. There’s also a long thread about how Git could move to a longer hash, but Junio noted that people have discussed this for years without reaching a consensus design, and no transition plan has been announced.

So what should you do? I’d keep Git updated so you pick up whatever hardening lands. Junio suggested git config transfer.fsckObjects true in the thread; the git-config documentation says it makes fetch and receive abort on malformed objects, and it defaults to false. It won’t detect a collision by itself, and Jeff King warned that some older histories trip warnings that currently cause rejections, so test it first. And if you distribute binaries from a repository, I’d publish a SHA-256 checksum alongside them rather than treating the Git object name as proof of what’s inside.

The takeaway

For HTTPS, this announcement mostly confirms a decision the industry already made. The Baseline Requirements have barred public CAs from issuing new SHA-1 certificates since January 2016, Chrome and Firefox have stopped trusting publicly issued ones, and Microsoft has said Edge and IE11 will block them too. If you still have one anywhere, including on an intermediate or an internal service, now is the time to replace it. For Git, the maintainers see it as a reason to keep going on work they’d already started rather than a fire drill, and I think that’s the right read. A collision is serious, but it isn’t a preimage, and it helps to know which one you’re dealing with before deciding how worried to be.