Update entropy requirements to 64-bits mandatory in serial number

[gerv]

Currently, the policy says:

all new end-entity certificates must contain at least 20 bits of unpredictable random data (preferably in the serial number).

We should require the random data to be in the serial number, and perhaps also update the number of bits required.

There was a discussion in m.d.s.policy: https://groups.google.com/d/msg/mozilla.dev.security.policy/3avqmSF4MVU/ZPFE0rIuAQAJ

[gerv]

BRs 1.3.7 and later say:

Effective September 30, 2016, CAs SHALL generate non‐sequential Certificate serial numbers greater than zero (0) containing at least 64 bits of output from a CSPRNG.

That's exactly the text I would use in this policy. So updating the BR version (issue #30) and removing the above text as redundant would resolve this issue.

[gerv]

Actually, no it wouldn't, because not all certificates which chain up to Mozilla roots are covered by the BRs. We should take the BR text and add it verbatim to our policy, but making it clear that it applies to all certificates chaining up to Mozilla roots.

[briansmith]

Does this requirement even necessary any more if SHA-256 or better is being used to sign the certificate?

Does it even make sense to restrict it to end-entity certificates? If CAs are regularly issuing (name-constrained) intermediate certificates, then it would be equally important or unimportant for the CA certificates.

[gerv]

Does this requirement even necessary any more if SHA-256 or better is being used to sign the certificate?

If we'd imposed the requirement when MD5 was a thing, you might have said the very same thing about "if we are using SHA-1"... It seems to me that it's better to keep the requirement, and better to keep CAs doing this as a matter of course, than trying to reimpose it every time the crypto gets weak.

Why shouldn't serial numbers have a random component? What problems does it cause?

Yes, we could extend to all certs.

[briansmith]

We should take the BR text and add it verbatim to our policy, but making it clear that it applies to all certificates chaining up to Mozilla roots.

When it comes to things that involve hash collisions, even "certificates chaining up to Mozilla roots" isn't sufficient. Instead it would be "anything ever signed by a key that belongs to a CA certificate chaining up to Mozilla's roots" since there could be a collision between a non-certificate thing and a certificate.

Why shouldn't serial numbers have a random component? What problems does it cause?

In general it adds complexity to the certificate issuance process that IMO is unwarranted with better hash algorithms, and also it requires serial numbers to be ~8 bytes larger than necessary and also OCSP responses to be ~8 bytes larger than necessary. In particular, the EdDSA signature algorithm already has additional protections against collisions, so it seems quite unnecessary for EdDSA if EdDSA is allowed. Also, Ed25519 is targeted toward applications where size is a significant issue.

[gerv]

When it comes to things that involve hash collisions, even "certificates chaining up to Mozilla roots" isn't sufficient. Instead it would be "anything ever signed by a key that belongs to a CA certificate chaining up to Mozilla's roots" since there could be a collision between a non-certificate thing and a certificate.

Wouldn't that be best addressed by some sort of requirement against key reuse? Keys used inside the Web PKI may not be used outside it?

[briansmith]

Wouldn't that be best addressed by some sort of requirement against key reuse? Keys used inside the Web PKI may not be used outside it?

It is hard to do. For example "incide the Web PKI" wouldn't include S/MIME but surely some CAs are using the same keys for S/MIME and server certificates. Also, even within the Web PKI, there are various possibilities for key reuse: Certificates, CT precert signing, OCSP, CRLs, RoughTime, etc. Some of these are the signing of things that are less likely to be under as much attacker control as certificates.

Also, it will not be easy (or possible?) to enforce that in any way.

[gerv]

In general it adds complexity to the certificate issuance process that IMO is unwarranted with better hash algorithms

Symantec had to retire an entire issuance system because it only supported sequential serial numbers. If we don't make this a requirement everywhere, if we did make it a requirement for a particular algorithm in the future this might happen again - someone makes a system which doesn't support it, and it has to be replaced with one which does.

Also, the BRs require it for all certs, so it's a bit of a moot point.

[briansmith]

Also, the BRs require it for all certs, so it's a bit of a moot point.

No it's not, because the BRs can be changed. Especially when EdDSA support is added to the BRs, it makes sense to carve out an exception for EdDSA since it is already collision-resistant and the purpose of the randomized serialized numbers is to ensure collision-resistance.

[gerv]

Well, the SHA-1 issue will be dealt with in the section specifically on SHA-1, being drafted in issue #25. So if we only want this to apply to SHA-1, there is nothing to do here.

[briansmith]

So if we only want this to apply to SHA-1, there is nothing to do here.

Just to be clear, I see three options:

1. Do nothing more than resolve #25. That is, don't require randomness in any non-SHA-1-signed certs.
2. Require randomness in all RSA- and ECDSA- signed certificates, but not Ed25519 (EdDSA) certificates, since EdDSA includes hash collision countermeasures already.
3. Require randomness in all certs, regardless of the algorithm used.

Note that this issue's description says "EE certificates" but because of the nature of collision attacks, it's not reasonable to restrict this to EE certs only. I think the idea that the randomness should be required in all certificates, except maybe certificates generated internally by the CA without any outside influence.

[gerv]

Do CAs regularly generate intermediate certificates using CSRs sent by customers? Surely all intermediate certificates fall into the category of "generated internally by the CA without any [significant] outside influence"?

[briansmith]

Do CAs regularly generate intermediate certificates using CSRs sent by customers? Surely all intermediate certificates fall into the category of "generated internally by the CA without any [significant] outside influence"?

That would happen with any externally-operated name-constrained intermediates.

Also, what matters is not if they regularly do it, but if they ever do it.

[gerv]

Would "any certificate signed based on a CSR not generated by the CA itself" be a good way of covering it?

[briansmith]

Would "any certificate signed based on a CSR not generated by the CA itself" be a good way of covering it?

Better, but keep in mind that one may request a certificate my means other than a CSR, in theory. Your wording would not require randomness in such certificates. Also consider that a CA may generate a cross-signing certificate for another party where the CSR is generated internally by the issuing CA, but where the contents of the cross-signing certificate are almost completely chosen by the contents of the cross-signed certificate.

It seems the requirement is that all of the contents of the certificate, including in particular every component of the name components and key components, must be independently chosen by the CA with no outside influence, in order to fully prevent collision attacks by third parties.

However, when you consider CT, it makes sense to assume that the issuing CA is also an attacker, in which case their own certificates shouldn't be treated any differently than customers' certificates.