34
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Also certificates these days tend to be randomized (using the serial number) so even if you can find a collision that works for a certificate you still need to predict the serial number before you start your massive computation effort. Also this wasn't a thing when the same was done with MD5. $\endgroup$ – SEJPM Jul 9 '18 at 8:27
  • $\begingroup$ I think if the CA does not sign on the original certificate, but change it before signing -- like some serial numbers as mentioned, maybe the problem is solved? $\endgroup$ – Weikeng Chen Jul 9 '18 at 8:42
  • 1
    $\begingroup$ Everyone knows collisions exist, the problem is that someone managed to actually find one. Hash functions are designed so you can't actually find one. That's their entire purpose. $\endgroup$ – user253751 Jul 11 '18 at 0:45
45
$\begingroup$

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:

  1. MD4 published.
  2. -
  3. MD5 published.
  4. -
  5. -
  6. SHA-1 published. Hans Dobbertin reports collisions in MD4 within seconds.
  7. Hans Dobbertin reports collisions in the MD5 compression function. Cryptographers advise against the use of MD5. SHA-1 is available as an unbroken alternative.
  8. -
  9. -
  10. -
  11. -
  12. -
  13. NIST publishes SHA-2 in FIPS 180-2.
  14. -
  15. 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.
  16. 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.
  17. -
  18. Stevens et al. demonstrate chosen-prefix collision attacks on MD5, enabling potential forgery of certificates with different names.
  19. 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.
  20. -
  21. -
  22. CA/Browser Forum writes down first draft of Basic Requirements so web browsers can formalize justification for kicking out incompetent HTTPS CAs.
  23. 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?
  24. -
  25. CAB Forum votes to sunset SHA-1 next year.
  26. HTTPS CAs whine and demand to push SHA-1 sunset back a year. NIST publishes SHA-3 in FIPS 202.
  27. 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.
  28. 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.
  29. -
  30. [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.

$\endgroup$
  • 1
    $\begingroup$ Suggest adding 'SHA-2 published, providing an upgrade path'; wikipedia says 2001, although the earliest copy I have is Aug. 2002. (Initially not including -224 but AFAICT nobody ever used -224 for certs except maybe with DSA-2048 and damn few use any DSA on the public net.) FWIW NIST SP800-131 initial draft in 2010 proposed to require SHA-2 starting 2011, but their users similarly whined that back to 2014. $\endgroup$ – dave_thompson_085 Jul 10 '18 at 4:34
  • 1
    $\begingroup$ It was close, but I think this answer helped clarify things for me more than Maarten's. I apologise for frustrating you with this type of question – I can (mostly) appreciate where your frustration comes from – but (to play devil's advocate somewhat), isn't not wanting to clarify the ramifications of a specific individual scientific result somewhat akin to relying on security by obscurity? Some people will always have their heads in the sand, or deliberately misrepresent the context around a result, but are they good enough reasons not to try and fully understand all the ramifications? $\endgroup$ – TripeHound Jul 10 '18 at 7:07
  • 1
    $\begingroup$ @TripeHound The precise nature of the result is one thing: it's an identical-prefix collision attack demonstrated to be within the budget of a single wealthy corporation. The ramifications of this step in the decades-long process of analysis are a different matter requiring the full context to understand. Confidence in security comes not from one paper by one team of smart cryptographers who couldn't break it. Confidence comes from years of analysis by many teams with enough context to extrapolate, from the boundaries of what they did, to an estimate of what someone could do. $\endgroup$ – Squeamish Ossifrage Jul 10 '18 at 14:57
  • $\begingroup$ @TripeHound If I had a euro for every engineer who has told me that they couldn't imagine a way to use the best current academic results to break their particular system and therefore they don't need to fix it, well, I'd be a rich bird who spends more time putting those funds toward dismantling the capitalist system and the state violence that enforces it than answering cryptography questions from pseudonymous strangers on the internet. It's not security through obscurity to be concerned that engineers who lack that context might focus on the individual result to the exclusion of context. $\endgroup$ – Squeamish Ossifrage Jul 10 '18 at 15:02
  • 1
    $\begingroup$ @TripeHound To be clear: I don't mean to group you among those engineers who owe me a euro. But this is now a Hot Network Question that thousands of people are reading, many of them from outside the cryptography community, and it is exactly the kind of question that participants in interminably insufferable Hacker News threads misrepresenting the state of cryptography will cherry-pick to cite as justification for their own overconfidence in security of cryptosystems that no self-respecting cryptographer would suggest anyone use. $\endgroup$ – Squeamish Ossifrage Jul 10 '18 at 15:07
29
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. For the record, I'm not in anyway condoning still using SHA1. I also accept Google's breakthrough in actually finding a collision was their tailoring of the search. However, it's still the case that by choosing a JPG-in-a-PDF, they had "freedom" to fully exploit that "tailored search" without worrying about "breaking" the PDF. I think what I'm trying to ask is if the "very complex structure [of an X.509 certificate] that may embed a lot of fields" can give that same freedom, without having to worry about the validity of the certificate as a whole. $\endgroup$ – TripeHound Jul 9 '18 at 12:52
  • 2
    $\begingroup$ OK, added an example that shows a similar MD5 based attack on certificates... It's fine to question if an attack can be mounted on a specific protocol, but please err on the safe side when it comes to crypto :) $\endgroup$ – Maarten Bodewes Jul 9 '18 at 12:58
  • $\begingroup$ Thanks ... I'll explore that MD5 link and see if it answers the heart of my question. As I've said: I'm not in any way suggesting anyone continues using a SHA1-signed cert, and fully support erring on the side of safety. $\endgroup$ – TripeHound Jul 9 '18 at 13:06
  • $\begingroup$ The attack on a md5 certificate involved a distinct chosen prefix collision attack and a CA with bad issuance practices. $\endgroup$ – Peter Green Jul 9 '18 at 15:44
  • 1
    $\begingroup$ @Hamsterrific & immibis: Yes, this is directly tied to the 80 bits of security that a hash with an output of 160 bits is able to deliver. Note that MD5 only has 64 / 128 bits, so to bruteforce it is in the same ballpark as creating a SHA-1 collision using the attack vectors used for SHAttered. In other words, it is insecure even without the attacks on it. $\endgroup$ – Maarten Bodewes Jul 10 '18 at 10:38
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ what is the difference between distinct chosen prefix and a simple collision? $\endgroup$ – adi Jul 10 '18 at 4:15
  • $\begingroup$ @adi I think (but I'm still learning) a simple collision is finding/crafting any two files that hash to the same (but the contents may be entirely different, and you have little or not control over them). Identical prefix is finding/crafting two files that start the same, then differ, but hash the same (the Shattered attack). Chosen prefix is being able to take two files with arbitrary prefixes and then bring their hashes back into line by crafting follow-on data. See Collision Attack. $\endgroup$ – TripeHound Jul 10 '18 at 6:51
  • $\begingroup$ @adi To clarify TripeHound's great comment even further: a simple collision means that it's possible to make two different files with the same hash, but a chosen-prefix collision is what allows me to take an existing file, and figure out how to produce a file with different contents but the same hash. This is important because it means I can take your file - say, a digitally-signed legal document, or an SSL certificate - and craft a file that will look like your file to anything that relies on the hash, but is actually my version. This is obviously very useful for malicious purposes. $\endgroup$ – anaximander Jul 10 '18 at 9:05
  • $\begingroup$ No, a distinct chosen prefix collision attack lets you construct a pair of files with the same hash and distinct chosen prefixes. To construct a file with the same hash as an existing file would be a preimage attack. $\endgroup$ – Peter Green Jul 10 '18 at 10:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.