Check for weak keys

[jsha]

We need to check for keys less than 2048 bits and known weak private keys, per CPS.

The automated process will also verify the Public Key of a Device that is requested has less than 2048 bit encryption and if it uses a known weak Private Key. If either or both are automatically detected in the secure session, the Applicant will be required to correct the determined issue before the DV-SSL Certificate can be issued.

[rmhrisk]

What about GCD test and what limits for ECC keys?

[jsha]

Good question. Can you provide a best practice recommendation or link to articles?

[rmhrisk]

BRs will require you to limit support to specific algorithms (https://cabforum.org/wp-content/uploads/BRv1.2.5.pdf Appendix A). For example you they will only allow you to issue NIST curves (NIST P-256, P-384, or P-521) and DSA with certain options. At a minimum this should be in this component.

You should also have a table of keys that are known to be exposed, for example https://code.google.com/p/littleblackbox/ or the Debian Keys.

You should also have some plan to do a GCD test looking for bad keys, https://www.cis.upenn.edu/~nadiah/ did some nice work here; it is computationally expensive and you probably cant do it in-line with your issuance but you can reasonably do it post issuance and revoke.

[jsha]

Here's what out CP currently says:

1.1.135 Public Key Parameters Generation and Quality Checking The CA shall generate Digital Signature Algorithm (DSA) parameters in accordance with FIPS 186-3.

RSA: The CA shall confirm that the value of the public exponent is an odd number equal to 3 or more. Additionally, the public exponent should be in the range between 216+1 and 2256-1. The modulus should also have the following characteristics: an odd number, not the power of a prime, and have no factors smaller than 752.

DSA: Although FIPS 800-57 says that domain parameters may be made available at some accessible site, compliant DSA certificates must include all domain parameters. This is to insure maximum interoperability among relying party software. The CA must confirm that the value of the Public Key has the unique correct representation and range in the field, and that the key has the correct order in the subgroup.

ECC: The CA should confirm the validity of all keys using either the ECC full Public Key validation routine or the ECC partial Public Key validation routine.

[schoen]

@jsha: @jhalderm should be able to provide good guidance on the resources available for doing this.

I guess the "not a power of a prime" is susceptible of fast verification by standard algorithms; gmpy and gmpy2 both have a built-in is_power function which is extremely fast.

>>> gmpy.is_power(112188567197465669**500)
1

I don't know offhand the super-fast way to do this in integer math without logarithms or successive approximations of nth roots, but gmp does, so if you have it available in Go, you could do the is_power check there.

[pde]

@jcb82 is working on an implementation of realtime GCD checking in Go.

[pde]

(We may want a simpler stand-in in the meantime).

[bifurcation]

For RSA:

• GCD checking does not seem worthwhile for pre-issuance. Add this to the list of analyses that third parties can do on our DB of certificates.
• +1 on checking the Debian list, but this seems unlikely to hit

For ECC: Seems like we should just check the curve asserted by the CSR, and use the Go elliptic.IsOnCurve method. http://golang.org/pkg/crypto/elliptic/#CurveParams.IsOnCurve