8
$\begingroup$

Why is it it’s so much harder to execute a successful collision on certificates than it is on text data?

I assume this has to do with the fact the certificate actually is a file that contains signed (and therefore encrypted) data. However, why does this complicate things? Of course an attacker doesn’t possess the private key but why would this make a difference from a technical point of view?

I already read there’s several ways to find collisions. The goal is to find the path of the least resistance (in "reasonable" amounts of time). The only successful MD5 certificate collision I was able to find is a “chosen-prefix” collision. In this case they were also depending on the probability of some of the functions of the CA, like the serial number counter, the time between request, processing and issuing and the amount of certificates issued on average.

In this scenario it’s necessary to have a CA that (unknowingly) cooperates in the process (which isn’t a requirement with non-signed files. If this is the case, then we should be safe. Because:

  • No collision can be made after the certificate has been generated;
  • All CA’s only issue SHA-2 certificates; (both are assumptions but in the ideal world scenario)

Does it actually work out like this?

$\endgroup$
2
  • $\begingroup$ "a file that contains signed (and therefore encrypted) data" One does not imply the other. There have been questions on this site discussing the differences both in terms of RSA specifically as well as more broadly in terms of public-key encryption in general, but I can't seem to find those at the moment. $\endgroup$
    – user
    Mar 7, 2017 at 7:23
  • $\begingroup$ @MichaelKjörling: I know several good Qs for sign-is-not-encrypt on security.SX but only one here: crypto.stackexchange.com/questions/15997/… $\endgroup$ Mar 7, 2017 at 16:23

2 Answers 2

16
$\begingroup$

Why is it it’s so much harder to execute a successful collision on certificates than it is on text data?

It's not. Actually, the attacker does have to worry about the sequence number that the CA will use, however as we seen from the successful MD5 attacks, that's a solvable problem.

What's more difficult is coming up with a useful (to the attacker) collision.

If all we want is to generate two colliding certificates signed with SHA-1, we can take advantage of the fact that RSA certificates have some random-looking data in the middle (the "RSA public key"), and a nontrivial percent of random moduli are easy to factor (and hence is easy to find the corresponding private key). So, all we'd need to do is a) guess the initial parts of the certificate (already solved problem), b) generate a collision in the initial parts of the RSA modulus, giving us two top portions and c) then search for a common lower section of the modulus where we can factor both. Then, we can have the CA sign one (which requires us to have the private key, which w do), and then we can use the other (which also requires us to have that private key, which we do). Bingo, we have a collision.

However, it's not a useful collision; all we've done is use one modulus with the CA, and another in practice; that doesn't allow the attacker to, well, attack anything.

What the attacker really wants is to have the CA sign one certificate for 'innocent1.com', and then have the certifcate for, say, 'microsoft.com' and hashes to the same value (and so they can use the same signature in that certificate). To do that, the attacker needs to form two certificate prefixes (one with innocent1.com, and the other with microsoft.com), and form a collision where the two hash states join together to form a common one.

So, what the collision method needs to do is, instead of starting from a common state (and finding two distinct sets of blocks that both result in a common state), start with two predetermined hash states, and find a set of blocks that shepherd them into a common state. We know how to do this with MD5; the current attacks on SHA-1 doesn't do this.

Now, it wouldn't be prudent to assume that the attacks on SHA-1 couldn't be extended to do that.

No collision can be made after the certificate has been generated

True (even for MD5 certificates); however the base SHA-1 attack was published 10 years ago. It's only now that someone has published that they actually performed the attack, however that doesn't mean that someone else didn't do it first.

All CA’s only issue SHA-2 certificates

I've been told (thanks Ajedi32) that CA's only issue SHA-2 (or better) certificates now; however that doesn't address certificates in the field that haven't expired yet. Yes, you can't attack them now; you could attack them a year ago...

Also:

I assume this has to do with the fact the certificate actually is a file that contains signed (and therefore encrypted) data.

Actually, a certificate does not include any encrypted data (ASN.1 encoding doesn't quite count as encryption :-). Because anyone is supposed to be able to parse a certificate, it can't include any encrypted (unintelligible without the key) data.

$\endgroup$
5
  • $\begingroup$ There has been a lot of push in the CA/Browser forum, so all "big" CA (the one that can produce EV certificates) indeed refuse to use SHA-1. Arguably, the whole point of the anathema on SHA-1 in certificates was really a plot to get rid of other, mostly governmental CA, that were not managed efficiently enough to be able to switch to SHA-2. $\endgroup$ Mar 6, 2017 at 17:41
  • 2
    $\begingroup$ Also, what really prevents making collisions on certificates with SHA-1 right now is that CA have learned to use random serial numbers, making the TBS contents unpredictable by attackers (the serial number occurs really early in the structure). Even Microsoft's AD CS, in its default configuration, uses about 30 bits of entropy in the serial number generation. Technically, even MD5 would still be safe under these conditions. $\endgroup$ Mar 6, 2017 at 17:44
  • 2
    $\begingroup$ "I suspect it'll be quite a while before all of them (including the smaller CA vendors) all move from SHA-1" FWIW, CAs have been explicitly prohibited from issuing SHA-1 certificates by the CAB Baseline Requirements for several months now. So any CA which does still issue SHA-1 certs risks getting distrusted by browsers. Not to mention it doesn't really matter anymore if CAs issue SHA-1 certs or not, as most modern browsers won't accept them. $\endgroup$
    – Ajedi32
    Mar 6, 2017 at 21:05
  • $\begingroup$ @Ajedi32: that's nice to know; I'll edit my answer accordingly... $\endgroup$
    – poncho
    Mar 6, 2017 at 21:05
  • $\begingroup$ IIRC at least one CA worked around the CAB forum rules by issuing SHA1 certs from an old root that is no longer trusted by modern browsers, but is trusted by legacy browsers. Servers that care more about supporting legacy browsers than about security can then use client detection techniques to decide which cert to serve up. $\endgroup$ Jun 24, 2019 at 23:19
4
$\begingroup$

Generating a collision is not the same as generating a useful collision.

The basic recipe for exploiting a collision looks like.

  1. Generate a pair of colliding files A and B. With B being more favorable to the attacker than A.
  2. Get someone the victim trusts to sign A
  3. Transplant the signature from A to B.

Now some key characteristics of the md5/sha1/sha2 hash functions.

  1. Choosing a common prefix has little impact on the difficulty of finding a collision but if you change the prefix you will need to go and find new collision blocks
  2. Adding a common suffix to an existing collision will result in a collision.

The attack on pdf goes something like

  1. Generate a common prefix containing a valid pdf header and which would skip over the "collision blocks".
  2. Generate the collision blocks.
  3. Generate a common suffix that contains the content for both versions of the document and decides which one to display based on the content of the collision blocks.

So back to the topic at hand, attacking CAs. The goal here is to get a CA to sign a "good" cert with a signature we can transplant to an "evil" cert. The "evil" cert needs to have different metadata to be useful, maybe a different domain, maybe flags that allow it to be used as an intermediate certificate rather than an end entity certificate.

This is fundamentally difficult for two reasons.

  1. CAs don't just take a certificate from their customer and sign it. They take a CSR, decide which parts of it they will ignore, add a serial number, build a certificate and then sign it. The customer can predict much of what the CA will do but they have limited scope to implement it.
  2. Certificates are relatively simple structures with little scope for tricky logic.

The net result is that the trick used for the colliding pdfs demo simply won't work against a CA.

Even a distinct chosen prefix collision can only be exploited if the CA uses sufficiently predictable serial numbers.

$\endgroup$
4
  • $\begingroup$ "Certificates are relatively simple structures with little scope for tricky logic." ... come again? $\endgroup$
    – Maarten Bodewes
    Mar 6, 2017 at 20:27
  • $\begingroup$ I wanted to point to the decoded certificate in an online ASN.1 decoder, but that link is rather too long. Instead I'll just point to Peter Gutman's Style Guide from 2000. Certificates have become more complex since then. Oh, wait: TinyURL link to the relatively simple StackExchange certificate. Note that you can also attack the ASN.1 / DER encoding itself. $\endgroup$
    – Maarten Bodewes
    Mar 6, 2017 at 20:36
  • $\begingroup$ Certificates do have structure but not enough to prevent attack given known serial (predicted) issuer (fixed) validity (predicted) subject (chosen) and some extensions, see Stevens et al win.tue.nl/hashclash/rogue-ca/#sec5 $\endgroup$ Mar 7, 2017 at 16:19
  • $\begingroup$ That attack relied on a "distinct chosen prefix" collision attack. $\endgroup$ Mar 7, 2017 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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