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 achieved1.

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?


1 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.

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:


MD4 published.
-
MD5 published.
-
-
SHA-1 published.  Hans Dobbertin reports collisions in MD4 within seconds.
Hans Dobbertin reports collisions in the MD5 compression function.  Cryptographers advise against the use of MD5.  SHA-1 is available as an unbroken alternative.
-
-
-
-
-
NIST publishes SHA-2 in FIPS 180-2.
-
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.
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.
-
Stevens et al. demonstrate chosen-prefix collision attacks on MD5, enabling potential forgery of certificates with different names.
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.
-
-
CA/Browser Forum writes down first draft of Basic Requirements so web browsers can formalize justification for kicking out incompetent HTTPS CAs.
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?
-
CAB Forum votes to sunset SHA-1 next year.
HTTPS CAs whine and demand to push SHA-1 sunset back a year.  NIST publishes SHA-3 in FIPS 202.
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.
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.
-
[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.
