SHA-1 – Why is it hard to find a certificate collision? 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?
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.