1 package goodkey 2 3 import ( 4 "context" 5 "crypto" 6 "crypto/ecdsa" 7 "crypto/elliptic" 8 "crypto/rsa" 9 "errors" 10 "fmt" 11 "math/big" 12 "sync" 13 14 "github.com/letsencrypt/boulder/core" 15 16 "github.com/titanous/rocacheck" 17 ) 18 19 // To generate, run: primes 2 752 | tr '\n' , 20 var smallPrimeInts = []int64{ 21 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 22 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 23 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 24 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 25 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 26 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 27 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 28 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 29 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 30 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 31 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 32 719, 727, 733, 739, 743, 751, 33 } 34 35 // singleton defines the object of a Singleton pattern 36 var ( 37 smallPrimesSingleton sync.Once 38 smallPrimesProduct *big.Int 39 ) 40 41 type Config struct { 42 // WeakKeyFile is the path to a JSON file containing truncated modulus hashes 43 // of known weak RSA keys. If this config value is empty, then RSA modulus 44 // hash checking will be disabled. 45 WeakKeyFile string 46 // BlockedKeyFile is the path to a YAML file containing base64-encoded SHA256 47 // hashes of PKIX Subject Public Keys that should be blocked. If this config 48 // value is empty, then blocked key checking will be disabled. 49 BlockedKeyFile string 50 // FermatRounds is an integer number of rounds of Fermat's factorization 51 // method that should be performed to attempt to detect keys whose modulus can 52 // be trivially factored because the two factors are very close to each other. 53 // If this config value is empty (0), no factorization will be attempted. 54 FermatRounds int 55 } 56 57 // ErrBadKey represents an error with a key. It is distinct from the various 58 // ways in which an ACME request can have an erroneous key (BadPublicKeyError, 59 // BadCSRError) because this library is used to check both JWS signing keys and 60 // keys in CSRs. 61 var ErrBadKey = errors.New("") 62 63 func badKey(msg string, args ...interface{}) error { 64 return fmt.Errorf("%w%s", ErrBadKey, fmt.Errorf(msg, args...)) 65 } 66 67 // BlockedKeyCheckFunc is used to pass in the sa.BlockedKey functionality to KeyPolicy, 68 // rather than storing a full sa.SQLStorageAuthority. This allows external 69 // users who don’t want to import all of boulder/sa, and makes testing 70 // significantly simpler. 71 // On success, the function returns a boolean which is true if the key is blocked. 72 type BlockedKeyCheckFunc func(ctx context.Context, keyHash []byte) (bool, error) 73 74 // KeyPolicy determines which types of key may be used with various boulder 75 // operations. 76 type KeyPolicy struct { 77 AllowRSA bool // Whether RSA keys should be allowed. 78 AllowECDSANISTP256 bool // Whether ECDSA NISTP256 keys should be allowed. 79 AllowECDSANISTP384 bool // Whether ECDSA NISTP384 keys should be allowed. 80 weakRSAList *WeakRSAKeys 81 blockedList *blockedKeys 82 fermatRounds int 83 blockedCheck BlockedKeyCheckFunc 84 } 85 86 // NewKeyPolicy returns a KeyPolicy that allows RSA, ECDSA256 and ECDSA384. 87 // weakKeyFile contains the path to a JSON file containing truncated modulus 88 // hashes of known weak RSA keys. If this argument is empty RSA modulus hash 89 // checking will be disabled. blockedKeyFile contains the path to a YAML file 90 // containing Base64 encoded SHA256 hashes of pkix subject public keys that 91 // should be blocked. If this argument is empty then no blocked key checking is 92 // performed. 93 func NewKeyPolicy(config *Config, bkc BlockedKeyCheckFunc) (KeyPolicy, error) { 94 kp := KeyPolicy{ 95 AllowRSA: true, 96 AllowECDSANISTP256: true, 97 AllowECDSANISTP384: true, 98 blockedCheck: bkc, 99 } 100 if config.WeakKeyFile != "" { 101 keyList, err := LoadWeakRSASuffixes(config.WeakKeyFile) 102 if err != nil { 103 return KeyPolicy{}, err 104 } 105 kp.weakRSAList = keyList 106 } 107 if config.BlockedKeyFile != "" { 108 blocked, err := loadBlockedKeysList(config.BlockedKeyFile) 109 if err != nil { 110 return KeyPolicy{}, err 111 } 112 kp.blockedList = blocked 113 } 114 if config.FermatRounds < 0 { 115 return KeyPolicy{}, fmt.Errorf("Fermat factorization rounds cannot be negative: %d", config.FermatRounds) 116 } 117 kp.fermatRounds = config.FermatRounds 118 return kp, nil 119 } 120 121 // GoodKey returns true if the key is acceptable for both TLS use and account 122 // key use (our requirements are the same for either one), according to basic 123 // strength and algorithm checking. GoodKey only supports pointers: *rsa.PublicKey 124 // and *ecdsa.PublicKey. It will reject non-pointer types. 125 // TODO: Support JSONWebKeys once go-jose migration is done. 126 func (policy *KeyPolicy) GoodKey(ctx context.Context, key crypto.PublicKey) error { 127 // Early rejection of unacceptable key types to guard subsequent checks. 128 switch t := key.(type) { 129 case *rsa.PublicKey, *ecdsa.PublicKey: 130 break 131 default: 132 return badKey("unsupported key type %T", t) 133 } 134 // If there is a blocked list configured then check if the public key is one 135 // that has been administratively blocked. 136 if policy.blockedList != nil { 137 if blocked, err := policy.blockedList.blocked(key); err != nil { 138 return fmt.Errorf("error checking blocklist for key: %v", key) 139 } else if blocked { 140 return badKey("public key is forbidden") 141 } 142 } 143 if policy.blockedCheck != nil { 144 digest, err := core.KeyDigest(key) 145 if err != nil { 146 return badKey("%w", err) 147 } 148 exists, err := policy.blockedCheck(ctx, digest[:]) 149 if err != nil { 150 return err 151 } else if exists { 152 return badKey("public key is forbidden") 153 } 154 } 155 switch t := key.(type) { 156 case *rsa.PublicKey: 157 return policy.goodKeyRSA(t) 158 case *ecdsa.PublicKey: 159 return policy.goodKeyECDSA(t) 160 default: 161 return badKey("unsupported key type %T", key) 162 } 163 } 164 165 // GoodKeyECDSA determines if an ECDSA pubkey meets our requirements 166 func (policy *KeyPolicy) goodKeyECDSA(key *ecdsa.PublicKey) (err error) { 167 // Check the curve. 168 // 169 // The validity of the curve is an assumption for all following tests. 170 err = policy.goodCurve(key.Curve) 171 if err != nil { 172 return err 173 } 174 175 // Key validation routine adapted from NIST SP800-56A § 5.6.2.3.2. 176 // <http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf> 177 // 178 // Assuming a prime field since a) we are only allowing such curves and b) 179 // crypto/elliptic only supports prime curves. Where this assumption 180 // simplifies the code below, it is explicitly stated and explained. If ever 181 // adapting this code to support non-prime curves, refer to NIST SP800-56A § 182 // 5.6.2.3.2 and adapt this code appropriately. 183 params := key.Params() 184 185 // SP800-56A § 5.6.2.3.2 Step 1. 186 // Partial check of the public key for an invalid range in the EC group: 187 // Verify that key is not the point at infinity O. 188 // This code assumes that the point at infinity is (0,0), which is the 189 // case for all supported curves. 190 if isPointAtInfinityNISTP(key.X, key.Y) { 191 return badKey("key x, y must not be the point at infinity") 192 } 193 194 // SP800-56A § 5.6.2.3.2 Step 2. 195 // "Verify that x_Q and y_Q are integers in the interval [0,p-1] in the 196 // case that q is an odd prime p, or that x_Q and y_Q are bit strings 197 // of length m bits in the case that q = 2**m." 198 // 199 // Prove prime field: ASSUMED. 200 // Prove q != 2: ASSUMED. (Curve parameter. No supported curve has q == 2.) 201 // Prime field && q != 2 => q is an odd prime p 202 // Therefore "verify that x, y are in [0, p-1]" satisfies step 2. 203 // 204 // Therefore verify that both x and y of the public key point have the unique 205 // correct representation of an element in the underlying field by verifying 206 // that x and y are integers in [0, p-1]. 207 if key.X.Sign() < 0 || key.Y.Sign() < 0 { 208 return badKey("key x, y must not be negative") 209 } 210 211 if key.X.Cmp(params.P) >= 0 || key.Y.Cmp(params.P) >= 0 { 212 return badKey("key x, y must not exceed P-1") 213 } 214 215 // SP800-56A § 5.6.2.3.2 Step 3. 216 // "If q is an odd prime p, verify that (y_Q)**2 === (x_Q)***3 + a*x_Q + b (mod p). 217 // If q = 2**m, verify that (y_Q)**2 + (x_Q)*(y_Q) == (x_Q)**3 + a*(x_Q)*2 + b in 218 // the finite field of size 2**m. 219 // (Ensures that the public key is on the correct elliptic curve.)" 220 // 221 // q is an odd prime p: proven/assumed above. 222 // a = -3 for all supported curves. 223 // 224 // Therefore step 3 is satisfied simply by showing that 225 // y**2 === x**3 - 3*x + B (mod P). 226 // 227 // This proves that the public key is on the correct elliptic curve. 228 // But in practice, this test is provided by crypto/elliptic, so use that. 229 if !key.Curve.IsOnCurve(key.X, key.Y) { 230 return badKey("key point is not on the curve") 231 } 232 233 // SP800-56A § 5.6.2.3.2 Step 4. 234 // "Verify that n*Q == Ø. 235 // (Ensures that the public key has the correct order. Along with check 1, 236 // ensures that the public key is in the correct range in the correct EC 237 // subgroup, that is, it is in the correct EC subgroup and is not the 238 // identity element.)" 239 // 240 // Ensure that public key has the correct order: 241 // verify that n*Q = Ø. 242 // 243 // n*Q = Ø iff n*Q is the point at infinity (see step 1). 244 ox, oy := key.Curve.ScalarMult(key.X, key.Y, params.N.Bytes()) 245 if !isPointAtInfinityNISTP(ox, oy) { 246 return badKey("public key does not have correct order") 247 } 248 249 // End of SP800-56A § 5.6.2.3.2 Public Key Validation Routine. 250 // Key is valid. 251 return nil 252 } 253 254 // Returns true iff the point (x,y) on NIST P-256, NIST P-384 or NIST P-521 is 255 // the point at infinity. These curves all have the same point at infinity 256 // (0,0). This function must ONLY be used on points on curves verified to have 257 // (0,0) as their point at infinity. 258 func isPointAtInfinityNISTP(x, y *big.Int) bool { 259 return x.Sign() == 0 && y.Sign() == 0 260 } 261 262 // GoodCurve determines if an elliptic curve meets our requirements. 263 func (policy *KeyPolicy) goodCurve(c elliptic.Curve) (err error) { 264 // Simply use a whitelist for now. 265 params := c.Params() 266 switch { 267 case policy.AllowECDSANISTP256 && params == elliptic.P256().Params(): 268 return nil 269 case policy.AllowECDSANISTP384 && params == elliptic.P384().Params(): 270 return nil 271 default: 272 return badKey("ECDSA curve %v not allowed", params.Name) 273 } 274 } 275 276 // Baseline Requirements, Section 6.1.5 requires key size >= 2048 and a multiple 277 // of 8 bits: https://github.com/cabforum/servercert/blob/main/docs/BR.md#615-key-sizes 278 // Baseline Requirements, Section 6.1.1.3 requires that we reject any keys which 279 // have a known method to easily compute their private key, such as Debian Weak 280 // Keys. Our enforcement mechanism relies on enumerating all Debian Weak Keys at 281 // common key sizes, so we restrict all issuance to those common key sizes. 282 var acceptableRSAKeySizes = map[int]bool{ 283 2048: true, 284 3072: true, 285 4096: true, 286 } 287 288 // GoodKeyRSA determines if a RSA pubkey meets our requirements 289 func (policy *KeyPolicy) goodKeyRSA(key *rsa.PublicKey) (err error) { 290 if !policy.AllowRSA { 291 return badKey("RSA keys are not allowed") 292 } 293 if policy.weakRSAList != nil && policy.weakRSAList.Known(key) { 294 return badKey("key is on a known weak RSA key list") 295 } 296 297 modulus := key.N 298 299 // See comment on acceptableRSAKeySizes above. 300 modulusBitLen := modulus.BitLen() 301 if !acceptableRSAKeySizes[modulusBitLen] { 302 return badKey("key size not supported: %d", modulusBitLen) 303 } 304 305 // Rather than support arbitrary exponents, which significantly increases 306 // the size of the key space we allow, we restrict E to the defacto standard 307 // RSA exponent 65537. There is no specific standards document that specifies 308 // 65537 as the 'best' exponent, but ITU X.509 Annex C suggests there are 309 // notable merits for using it if using a fixed exponent. 310 // 311 // The CABF Baseline Requirements state: 312 // The CA SHALL confirm that the value of the public exponent is an 313 // odd number equal to 3 or more. Additionally, the public exponent 314 // SHOULD be in the range between 2^16 + 1 and 2^256-1. 315 // 316 // By only allowing one exponent, which fits these constraints, we satisfy 317 // these requirements. 318 if key.E != 65537 { 319 return badKey("key exponent must be 65537") 320 } 321 322 // The modulus SHOULD also have the following characteristics: an odd 323 // number, not the power of a prime, and have no factors smaller than 752. 324 // TODO: We don't yet check for "power of a prime." 325 if checkSmallPrimes(modulus) { 326 return badKey("key divisible by small prime") 327 } 328 // Check for weak keys generated by Infineon hardware 329 // (see https://crocs.fi.muni.cz/public/papers/rsa_ccs17) 330 if rocacheck.IsWeak(key) { 331 return badKey("key generated by vulnerable Infineon-based hardware") 332 } 333 // Check if the key can be easily factored via Fermat's factorization method. 334 if policy.fermatRounds > 0 { 335 err := checkPrimeFactorsTooClose(modulus, policy.fermatRounds) 336 if err != nil { 337 return badKey("key generated with factors too close together: %w", err) 338 } 339 } 340 341 return nil 342 } 343 344 // Returns true iff integer i is divisible by any of the primes in smallPrimes. 345 // 346 // Short circuits; execution time is dependent on i. Do not use this on secret 347 // values. 348 // 349 // Rather than checking each prime individually (invoking Mod on each), 350 // multiply the primes together and let GCD do our work for us: if the 351 // GCD between <key> and <product of primes> is not one, we know we have 352 // a bad key. This is substantially faster than checking each prime 353 // individually. 354 func checkSmallPrimes(i *big.Int) bool { 355 smallPrimesSingleton.Do(func() { 356 smallPrimesProduct = big.NewInt(1) 357 for _, prime := range smallPrimeInts { 358 smallPrimesProduct.Mul(smallPrimesProduct, big.NewInt(prime)) 359 } 360 }) 361 362 // When the GCD is 1, i and smallPrimesProduct are coprime, meaning they 363 // share no common factors. When the GCD is not one, it is the product of 364 // all common factors, meaning we've identified at least one small prime 365 // which invalidates i as a valid key. 366 367 var result big.Int 368 result.GCD(nil, nil, i, smallPrimesProduct) 369 return result.Cmp(big.NewInt(1)) != 0 370 } 371 372 // Returns an error if the modulus n is able to be factored into primes p and q 373 // via Fermat's factorization method. This method relies on the two primes being 374 // very close together, which means that they were almost certainly not picked 375 // independently from a uniform random distribution. Basically, if we can factor 376 // the key this easily, so can anyone else. 377 func checkPrimeFactorsTooClose(n *big.Int, rounds int) error { 378 // Pre-allocate some big numbers that we'll use a lot down below. 379 one := big.NewInt(1) 380 bb := new(big.Int) 381 382 // Any odd integer is equal to a difference of squares of integers: 383 // n = a^2 - b^2 = (a + b)(a - b) 384 // Any RSA public key modulus is equal to a product of two primes: 385 // n = pq 386 // Here we try to find values for a and b, since doing so also gives us the 387 // prime factors p = (a + b) and q = (a - b). 388 389 // We start with a close to the square root of the modulus n, to start with 390 // two candidate prime factors that are as close together as possible and 391 // work our way out from there. Specifically, we set a = ceil(sqrt(n)), the 392 // first integer greater than the square root of n. Unfortunately, big.Int's 393 // built-in square root function takes the floor, so we have to add one to get 394 // the ceil. 395 a := new(big.Int) 396 a.Sqrt(n).Add(a, one) 397 398 // We calculate b2 to see if it is a perfect square (i.e. b^2), and therefore 399 // b is an integer. Specifically, b2 = a^2 - n. 400 b2 := new(big.Int) 401 b2.Mul(a, a).Sub(b2, n) 402 403 for i := 0; i < rounds; i++ { 404 // To see if b2 is a perfect square, we take its square root, square that, 405 // and check to see if we got the same result back. 406 bb.Sqrt(b2).Mul(bb, bb) 407 if b2.Cmp(bb) == 0 { 408 // b2 is a perfect square, so we've found integer values of a and b, 409 // and can easily compute p and q as their sum and difference. 410 bb.Sqrt(bb) 411 p := new(big.Int).Add(a, bb) 412 q := new(big.Int).Sub(a, bb) 413 return fmt.Errorf("public modulus n = pq factored into p: %s; q: %s", p, q) 414 } 415 416 // Set up the next iteration by incrementing a by one and recalculating b2. 417 a.Add(a, one) 418 b2.Mul(a, a).Sub(b2, n) 419 } 420 return nil 421 } 422