SHA-1 – Why is it hard to find a certificate collision?

Question

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?

Answer 1

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.

Answer 2

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.