[Servercert-wg] Updating BR 6.1.1.3

[Corey Bonnell]

> I disagree. We point to the algorithm for determining a Debian weak key. A CA should be capable of determining whether or not that particular key meets that requirement. I think a similar discussion would be related to ROCA and
> which primes the CA has to consider.

The Debian weak key detection algorithm for a given RSA Public Key as described on the Wiki page [1] that you refer to is as follows:
1)            Obtain vulnerable version of OpenSSL running on the platform where the Public Key under test was generated.
2)            On that system, perform RSA key generation operations matching the modulus length and exponent of the Public Key, iterating over all of the following:
a.            Seeding the PRNG with values 0-32767 (each of the possible process IDs)
b.            Making the random file readable (rnd), unreadable (noreadrnd), and deleting it (nornd)
3)            With the list of 98,304 keys generated from step 2, check to see if the Public Key under test matches one of the generated keys. If there is a match, then the key is weak.

The algorithm above takes significant CPU time to execute, on the order of several CPU-hours to potentially hundreds of thousands at larger key sizes [2]. Additionally, it is not possible to determine the platform on which a given Public Key/CSR was generated and platforms may produce different outputs, so the above algorithm must be executed on each of the platforms affected by the vulnerability, so there are up to 11 different platforms to generate such lists for [3]. As such, execution of the algorithm above on an ad-hoc basis is not feasible, so such lists must be pre-computed and the results presumably hashed and stored in some lookup table for efficiency. This contrasts sharply with the ROCA vulnerability check that you mentioned, as that can be done relatively quickly with no significant performance degradation to the CSR submission workflow.

The Baseline Requirements in section 6.1.6 lists the requirements for RSA keys. CAs that implement the SHOULD for the upper bound for exponents may support up to ~2^255 exponent values. There is a lower bound for modulus lengths (2048 bits), and Mozilla Policy requires a modulus length divisible by 8, and while there is no upper bound for modulus length specified by policy, OpenSSL supports key lengths of up to “only” 16,384 bits. Additionally, at modulus lengths 3072 and above, OpenSSL supports only up to 64-bit exponents [4].

With all of this in mind, the number of tables that must be pre-computed by a CA faithfully following the SHOULDs in section 6.1.6 of the Baseline Requirements and Mozilla Policy and allowing modulus lengths of 2048-4096 must compute and store the following number of tables:

For modulus lengths 2048-3064 (128 key sizes in this range): 2^255 * 128 = 2^262
For modulus lengths 3072-4096 (129 key sizes in this range): 2^63 * 129 = ~2^70

Additionally, as mentioned above, they must repeat this process for each of the platforms.


> But there are always trade-offs. If the CA can't support a key size securely, not issuing seems like a reasonable path.

Another reasonable path for CAs would be to realize that it is not physically possible to check all supported RSA keys for the Debian vulnerability and instead check for a subset that would be the most commonly encountered, taking into account the popularity of the platforms at the time (2006-2008) and default values for modulus lengths and exponents in the primary software tooling. One large CA that has their CA implementation open-source has done exactly that [5], where a blocklist of the subset of all possible weak keys is consulted and the other key quality checks prescribed in section 6.1.6 are performed. Another popular open-source CA implementation has taken a virtually identical path [6].

Thanks,
Corey

[1] https://wiki.debian.org/SSLkeys
[2] https://github.com/g0tmi1k/debian-ssh
[3] https://www.debian.org/security/2008/dsa-1571
[4] https://github.com/openssl/openssl/issues/6130
[5] https://github.com/letsencrypt/boulder/blob/master/goodkey/good_key.go#L216
[6] https://github.com/rgorosito/ejbca/blob/master/modules/cesecore-common/src/org/cesecore/keys/validation/RsaKeyValidator.java#L355 (apologies, I wanted to link to the official SVN repository but it looks like it’s down)

This transmission may contain information that is privileged, confidential, and/or exempt from disclosure under applicable law. If you are not the intended recipient, you are hereby notified that any disclosure, copying, distribution, or use of the information contained herein (including any reliance thereon) is STRICTLY PROHIBITED. If you received this transmission in error, please immediately contact the sender and destroy the material in its entirety, whether in electronic or hard copy format.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cabforum.org/pipermail/servercert-wg/attachments/20200413/a3eff246/attachment.html>