Actalis: Insufficient Serial Number Entropy

If the majority of outstanding certificates were held by the Italian government, major banks and hospitals, what are the CA supposed to do if they're just told "No, you won't revoke the certificates until we're ready, we don't think the risk is worth it"? Further, reading a comment below on the usage of these certificates by the Italian state for mandatory reporting: it sounds like revoking could be considered a criminal offense...

This very much reads like a private entity mandating that tens if not hundreds of thousands of Euros are spent by the Italian state over a very minor security risk.

* The baseline requirement is 64 bits of entropy and Actalis were providing 63 bits, i.e. only short by a single bit. It would seem unusual if the baseline requirements were a mere one bit of entropy from insecurity.

* The requirement for 64 bits of entropy is to reduce the risk of hash collision attacks [1] - which have only ever been demonstrated for MD5 and SHA-1, neither of which are used to sign certificates any more.

If web security was a tightrope, this would be like hearing that the second safety net, underneath the first believed-to-be-robust safety net, was found to be strong enough to catch a 900 lbs person, when it was specified for 1000 lbs.

[1] https://cabforum.org/2016/03/31/ballot-164/

In the 2008 attack, the CA was using sequential serial numbers. They weren't randomized at all.

The attackers had to do a large amount of computation to produce colliding certificates even when they knew exactly what the rest of the content of the certificate would be.

In the aftermath of that, we got MD5 deprecation and also a requirement that certificates include randomness that wouldn't be predictable to the subscriber, so that the subscriber doesn't know what the collision target is.

It's a little complicated to foresee the exact size of the benefit from this in different threat models, but in the model where the attacker has the capability to produce two related texts with the same SHA-256 hash, the current precaution means that the attacker has only a 1/2⁶⁴ probability that using that capability in conjunction with a certificate issuance will yield a matching certificate.

In 2008, certificate issuance usually cost money for the subscriber, where now it needn't, but there are still issuance rate limits and there's now Certificate Transparency, so all of the attempts will become public.

A bigger risk is presumably an n-way collision capability where an attacker can produce, not just 2, but n related plaintexts that all have the same SHA-256. In that case the attacker has an (n-1)/2⁶⁴ probability per certificate issuance that the issued certificate has the desired hash, assuming nothing unexpected or uncontrollable happens during the certificate issuance. (Another tricky problem, for example, is the time of issuance, which can be specified accurate to the second by the CA and appears in the certificate.)

Especially when nobody has demonstrated a SHA-256 collision or research that's close to producing one, and all attempts would be public in Certificate Transparency, and all CA issuance is rate-limited in some way, it doesn't seem like even 1/2⁶³ is that bad. Just five or ten bits of entropy in the certificate would probably have been enough to stop the 2008 researchers' attack from succeeding at all.

The attack would also have to have been carried out while the existing certificates were being issued (if there was no successful attack during certificate issuance, there won't be an attack after-the-fact).

I like tialaramex's brown M&M analogy: browser vendors are concerned with ensuring that CAs take rules and policies very seriously, even if there's no conceivable way that a particular problem could be related to an attack or vulnerability.