Does "Shattered" actually show SHA-1-signed certificates are "unsafe"?

Question

Note: I am not advocating anyone continues using SHA1-signed certificates: they are dead as far as security is concerned and should no longer be used. I'm just trying to clarify my understanding of the theoretical implications of Shattered as they might apply to such certificates.

Prompted by this recent question: After Google's collision attack, is RSA-SHA1 signature still safe?, to which the overwhelming response is "no", I want to ask to what degree does the Shattered result actually show that SHA1-signed certificates are "in danger"?

The existence of the Shattered result is not, I think, in itself a surprise: everyone knows that in theory you can create two streams of bytes that hash to the same value. Google's achievements (which I don't wish to downplay) are (a) that they mustered enough resources to actually do this, and (b) they did so while keeping the colliding file a valid PDF (that also matched the format of the original very closely, and included the "obvious" difference in background colour).

As the accepted answer to Does “SHAttered” only work for PDF files? explains, Google had the "luxury" of an effectively "free-form" block of data that they could alter at will to achieve the collision. As I understand it, the "collision blocks" embedded in the JPG data (itself embedded in the PDF) have no (visible) effect on either the image itself nor on the PDF. Therefore (to grossly simplify things), "all" they had to do was vary this block until a collision was achieved¹.

However, in the case of a SHA1-signed certificate, there is nothing like the same freedom to inject unconstrained data: the amount of data that is signed is much smaller; and far less of it is free to be varied without consequence – you might find a collision, but the result is likely not to be usable as a certificate.

So: is it correct to say that while Shattered was a significant event, it does not in itself show that the chances of creating a usable, collided, SHA1-signed certificate are increased, and, in fact, the chances of doing so are still small?

---

¹ As per parts of Maarten Bodewes's answer, I realise that Google's attack wasn't completely random: the "magic" was in their tailoring of the attack and an "academic level knowledge to construct such an attack". While the targeting was important to being able to find a collision, so too was the ability to put arbitrary data into the file without compromising the file's validity. It is the latter aspect I'm asking about, and whether the same freedom extends to X.509 certificates.

Answer 1

Yes, SHA1-signed certificates are unsafe.

The SHAttered paper is instructive. From the introduction:

The MD-SHA family of hash functions is the most well-known hash function family, which includes MD5, SHA-1, and SHA-2 that have all found widespread use. This family originally started with MD4 in 1990, which was quickly replaced by MD5 in 1992 due to serious security weaknesses. Despite early known weaknesses of its underlying compression function, MD5 was widely deployed in the software industry for over a decade. A project MD5CRK that attempted to find a collision by brute force was halted in early 2004, when a team of researchers led by Xiaoyun Wang demonstrated collisions in MD5 found by a groundbreaking cryptanalytic attack that pioneered new techniques. In a major development, Stevens et al. later showed that a more powerful type of attack (the so-called chosen-prefix collision attack) could be performed against MD5. This eventually led to the forgery of a Rogue Certification Authority that in principle completely undermined HTTPS security in 2008. Despite this, even in 2017 there are still issues in deprecating MD5 for signatures.

Let me draw out the timeline here:

1990. MD4 published.
1991. -
1992. MD5 published.
1993. -
1994. -
1995. SHA-1 published. Hans Dobbertin reports collisions in MD4 within seconds.
1996. Hans Dobbertin reports collisions in the MD5 compression function. Cryptographers advise against the use of MD5. SHA-1 is available as an unbroken alternative.
1997. -
1998. -
1999. -
2000. -
2001. -
2002. NIST publishes SHA-2 in FIPS 180-2.
2003. -
2004. Xiaoyun Wang's team reports collisions in MD5 in a few hours. It is sheer idiocy to use MD5 at this point. SHA-2 is available as an unbroken alternative.
2005. Xiaoyun Wang's team reports a $2^{69}$-cost collision attack on SHA-1, later lowered to $2^{63}$. Cryptographers advise against the use of SHA-1, and even go out of their way to tell engineers to use SHA-2 instead of MD5 or SHA-1. Cryptographers realize there are sheer idiots out there and try to persuade them to stop using MD5 by making colliding pairs of x.509 certificates, albeit only sharing the same names.
2006. -
2007. Stevens et al. demonstrate chosen-prefix collision attacks on MD5, enabling potential forgery of certificates with different names.
2008. Cryptographers realize that even the operators of certification authorities are sheer idiots and try to persuade them to stop using MD5 by forging x.509 certificates in real time on a real CA. Some HTTPS CA operators grudgingly acknowledge that there might be a problem.
2009. -
2010. -
2011. CA/Browser Forum writes down first draft of Basic Requirements so web browsers can formalize justification for kicking out incompetent HTTPS CAs.
2012. BLAKE2 is published based on a SHA-3 finalist. The governments of the United States and Israel are documented to forge code-signing certificates using an independently developed chosen-prefix collision attack on MD5 in the Flame malware deployed in an international incident of industrial sabotage attacking Iran's nuclear program. This attack was presumably developed before 2007—otherwise, why not use the published attack?
2013. -
2014. CAB Forum votes to sunset SHA-1 next year.
2015. HTTPS CAs whine and demand to push SHA-1 sunset back a year. NIST publishes SHA-3 in FIPS 202.
2016. HTTPS CAs whine and demand to push SHA-1 sunset back another year. CAB Forum votes to require random ≥64-bit serial numbers, the first mitigation for chosen-prefix collision attacks on certificates (but not on signatures in general) in eight years since MD5 certificate forgery was demonstrated in practice.
2017. Stevens et al. report collisions in SHA-1. It is sheer idiocy to use SHA-1 at this point. SHA-2, SHA-3, and BLAKE2 are available as unbroken alternatives with high confidence from years of analysis.
2018. -
2019. [Update, 2019-05-10: Gaëtan Leurent and Thomas Peyrin report chosen-prefix collisions in SHA-1 at only a few times the cost of SHAttered, a major step toward certificate forgery.]

The technique demonstrated in the SHAttered paper is an identical-prefix collision attack. Specifically, the attack takes a prefix $p$ and finds two pairs of message blocks $(m_0, m_1) \ne (m'_0, m'_1)$ such that $$\operatorname{SHA-1}(p \mathbin\Vert m_0 \mathbin\Vert m_1 \mathbin\Vert s) = \operatorname{SHA-1}(p \mathbin\Vert m'_0 \mathbin\Vert m'_1 \mathbin\Vert s)$$ for any suffix $s$. In contrast, the MD5 certificate forgery used a chosen-prefix collision attack, which takes two prefixes $p \ne p'$ and finds middle parts $m \ne m'$ such that for any suffix $s$, $$\operatorname{MD5}(p \mathbin\Vert m \mathbin\Vert s) = \operatorname{MD5}(p' \mathbin\Vert m' \mathbin\Vert s).$$

Can this specific attack on SHA-1 be used to forge x.509 certificates? Probably not. Can someone find a chosen-prefix collision attack on SHA-1? It took one year from first collision to identical-prefix collision attacks on MD5. It took two more years from identical-prefix to chosen-prefix collision attacks on MD5. We already have identical-prefix collision attacks on SHA-1. I hope that we don't need to demonstrate another CA forgery in practice before people will listen to advice to stop using SHA-1. [Update, 2019-05-10: We now have chosen-prefix collision attacks on SHA-1 at only a few times the cost of the identical-prefix attacks of SHAttered.]

There are mitigations like randomized serial numbers, so maybe for public HTTPS certificates—which by CA/Browser Forum Baseline Requirements 1.5.9 §7.1 must use randomized ≥64-bit serial numbers for all certificates issued after 2016-09-30—it is sufficient that SHA-1 be eTCR, enhanced-target-collision-resistant, which is a much weaker property than collision resistance.

Of course, the CAB Forum requirements also (§7.1.3, p. 44) forbid new certificates signed using SHA-1 starting 2016-01-01 anyway—as is sensible! Do all HTTPS CAs respect that rule? I hope so, but if they don't respect it, maybe they won't respect the rule for random serial numbers either.

But there are many other kinds of certificate out there, like the code-signing certificates that were forged for Flame. Even if you restrict your question to x.509 certificates, e.g., the openssl ca command-line tool—which many people build private CAs out of—suggests and makes it easy to use sequential serial numbers and doesn't advertise a built-in way to randomly generate serial numbers.

_{P.S. No matter how many caveats you put on them, questions like this are frustrating to cryptographers because they provide fodder for self-important Hacker News readers to disregard all the context around the specific individual scientific result and instead conclude that the specific individual scientific result does not tattoo a collision on their foreheads and that therefore there's no need to replace SHA-1 yet.}

Answer 2

The existence of the SHAttered result is not, I think, in itself a surprise: everyone knows that in theory you can create two streams of bytes that hash to the same value. Google's achievements (which I don't wish to downplay) are (a) that they mustered enough resources to actually do this, and (b) they did so while keeping the colliding file a valid PDF (that also matched the format of the original very closely, and included the "obvious" difference in background colour).

No, that's not what SHAttered was about. SHAttered uses a tailored attack (detailed in the SHAttered paper). According to the Shattered FAQ:

The SHAttered attack is 100,000 faster than the brute force attack that relies on the birthday paradox. The brute force attack would require 12,000,000 GPU years to complete, and it is therefore impractical.

So the SHAttered attack certainly is not just about performing the calculations. It requires a academic level knowledge to construct such an attack.

Most of the vulnerabilities however were indeed already known, and constructing the attack was probably the most important contribution. Previous attacks such as the distributed "SHA-1 Collision Search" by IAIK did not succeed (and I wasted my CPU cycles for nought).

---

However, in the case of a SHA1-signed certificate, there is nothing like the same freedom to inject unconstrained data: the amount of data that is signed is much smaller; and far less of it is free to be varied without consequence – you might find a collision, but the result is likely not to be usable as a certificate.

An X.509 certificate is a very complex structure that may embed a lot of fields. Try and read the X.509 specifications and you'll quickly realize that embedding a block of seemingly random data is not that hard.

Note that similar attacks have been mounted on MD5 based certificates; although those attacks are not directly applicable they show what type of attacks we might expect in the future:

As a result of this successfull attack, we are currently in possession of a rogue Certification Authority certificate. This certificate will be accepted as valid and trusted by all common browsers, because it appears to be signed by one of the root CAs that browsers trust by default. In turn, any website certificate signed by our rogue CA will be trusted as well. If an unsuspecting user is a victim of a man-in-the-middle attack using such a certificate, they will be assured that the connection is secure through all common security indicators: a "https://" url in the address bar, a closed padlock and messages such as "This certificate is OK" if they chose to inspect the certificate.

Again, the authors of Shattered have seen this and the following text can be found in the aforementioned paper:

Any Certification Authority abiding by the CA/Browser Forum regulations is not allowed to issue SHA-1 certificates anymore. Furthermore, it is required that certificate authorities insert at least 64 bits of randomness inside the serial number field. If properly implemented this helps preventing a practical exploitation.

---

So: is it correct to say that while SHAttered was a significant event, it does not in itself show that the chances of creating a usable, collided, SHA1-signed certificate are increased, and, in fact, the chances of doing so are still small?

SHA-1 is clearly broken. Even unbroken it only gives 80 bits of security in many scenarios, which protocols generally strive for 128 bits of security or more. So SHA-1 should clearly not be used anymore.

That said, if there are internally issued, top level CA certificates out there signed with an old root certificate then they are still secure. Any newly issued certificates that have been requested by a third party should however be rejected. Now that the SHAttered attack is known it is just a question of buying computer time to perform the attack.

It is important to note that if a CA can be fooled in signing a prepared X.509 certificate that - after the attack - that it may be possible to alter the contents of said certificate and this may include the domain name. So if you are using a CA that is secure, the fact that somebody else may abuse another trusted CA is enough to make the certificate vulnerable to attack. This requires a relatively strong attack which doesn't seem feasible now.

---

And finally I'll end with quoting the RFC 4270 on vulnerabilities of internet protocols and SHA-1 in particular (released in 2005):

One of us (Bruce [ED: Schneier]) believes that everyone should start migrating to SHA-256 [SHA-256] now, due to the weaknesses that have already been demonstrated in both MD5 and SHA-1. There is an old saying inside the US National Security Agency (NSA): "Attacks always get better; they never get worse." The current collision attacks against MD5 are easily done on a single computer; the collision attacks against SHA-1 are at the far edge of feasibility today, but will only improve with time.

You are already too late. Migrate away from SHA-1 now.

Answer 3

The thing is CAs don't just sign a certificate provided by the customer, they generate a certificate based on a signing request and their own policies. So attacking a CA isn't a matter of simply generating a pair of colliding certificates and asking a CA to sign one of them.

A CA using MD5 was succesfully attacked http://www.win.tue.nl/hashclash/rogue-ca/. However there are two important things to note about that attack.

1. It involved a "distinct chosen prefix" collision attack. Not a simple collision attack like the ones that are currently known for sha1. (update: a distinct chosen prefix collision attack for sha1 has now been designed)
2. It involved using a CA that was not randomizing the serial numbers.
3. It still took numerous attempts.

So no attacking a CA is not simply a matter of taking googles attack and "buying computing time".