1648822 - Add stricter validation of DH keys when in FIPS mode.

Status: RESOLVED FIXED

(NSS :: Libraries, enhancement, P1)

Description

[Robert Relyea]

When we have validated our DH code in FIPS mode we depend on the fact that our callers are (or can be configured to) restrict themselves to using NIST approved primes (which inclues the tls primes). This leads to some squishiness in our validation and it's cleaner if we enforce this in FIPS mode. At the same time we currently accept primes and keys that may be subject to small group attacks.

I'd like to add the following code:

If the subprime (q) is specified on the private key, verify that the public key (y) is in the subgroup of q by calculating y^q mod p = 1 and verifying that q and p are prime. This is called full validation by FIPS and we already do this in both FIPS and normal mode (except we currently aren't checking q and p for primality).

If subprime (q) has not been specified, and we are in FIPS mode then:

1. verify p is in the list of approved primes (either tls or ike)
2. if p is not in the list of approved primes then:
   (processing depends on a compile time flag and what is allowed officially in FIPS):
   PERMISSIVE: (This is a compile time flag that will give us more permissive than FIPS processing, but still defeat all potential subgroup issues and still have maximal compatibility)
   calculate q=(p-1)/2 verify q and p are primes.
   FULL VALIDATE on SAFE primes: (if FIPS allows)
   calculate q=(p-1)/2 verify q and p are primes. verify y^q mod p = 1.
   ONLY Approved primes:
   Reject all non-approved primes unless subprime (q) has been supplied.
3. in all cases the partial validation of y is done (1 < y < p-1 or equivalently 2 <= y <= p-2 ).

We already do 3 in all cases.

Since the new checks are in FIPS mode, there is no impact in FIPS mode.

In FIPS mode:
PERMISSIVE means we will reject primes with subprimes not equal to (p-1)/2 unless the subprime is somehow communicated. In the real world, that is not typical. These primes are dangerous to use without the subprime because it's not possible to detect small subgroup attacks with them. We will accept safe primes, where q is a sofie-germane prime (q*2+1 is prime == p). In this case the only small subgroups are 0, 1, -1 mod p and our partial validation of y is sufficient. Processing of primes that are not approved can be quite expensive, even being human perceivable for larger primes (4096, 6144, 8192). PERMISSIVE is not sufficient to meet the FIPS requirements, but is sufficient to defeat all subgroup attacks. This would be the default for NSS as shipped. (so user can put nss in FIPS mode and get completely safe handling of DH connections in their application with maximal compatibility with the real world).

FULL VALIDATE on SAFE primes: (if FIPS allows)
This would be the #else if it's allowed by FIPS (still getting recommendation from the lab).
This rejects all the primes that PERMISSIVE does, as well as several primes/generator groups that would otherwise be safe. If g^q mod p == -1 mod p, then if the private key x is odd, the y^q mod p == -1 mod p and will fail full validiation. openssl dhparam command will generate a g^q mod p == -1 mod p about half the time. Some early crypto descriptions recommended choosing a g^((p-1/2) mod p = -1 because g^k mod p will generate the maximal amount of public keys, y. Unfortunately the security isn't any better because even though you an use a longer k and get a unique y, you can also use y to determine bits of k. how many bits depends on how many factors of (p-1) there are. for (p-1) = 2*q, you can get 1 bit of k, so it's generally safe, but FIPS disallows it. Upshot about 50% (on average) of the primes/generators accepted by PERMISSIVE will be accepted unconditionally by FULL VALIDATE on SAFE primes. Of the reset about 50% of the public keys (those with even x) would be accepted. The same performance caveats for PERMISSIVE applies here.

ONLY Approved primes:
If we aren't allowed to validate q=(p-1)/2 is prime, if FIPS, then we will have to reject all primes that don't explicitly include a subprime, or isn't explicitly approved.

So the code would be:

if (subprime exists) {
/* full check /
else if (fips) {
#ifdef EXCLICIT
/ verify prime is safe /
#else
either: / verify prime is safe, full check / or / reject prime */ depending the results from the lab
#endif

Comment 1

[Robert Relyea]

Attachment: Bug 1648822 Add stricter validation of DH keys when in FIPS mode.

The new FIPS standard is dh operations must use approved primes. Approved
primes are those selected in the tls and ike RFCs. Currently tls and ike
have modes with checks whether the primes are approved, but the check may
not always happen. The safest thing to do in FIPS mode is only allow those
primes. In addition, FIPS requires 1< y < p-1 (or technically 2<=y<=p-2, since
y is an integer those two tests are identical).

While making changes I realized we would want a mode where we can do more strict
checks on the prime while not requiring that the prime be an approved prime. We
already allow for strict checking if q is supplied with the private key, but there
were a couple of issues with that check:

1. there was no way of actually setting q in the current NSS pk11wrap interfaces.
2. If the prime was a safe prime, but g was an actual generator, then we would fail the y^q mod p = 1 tests for 50% of the keys, even though those keys are safe.
3. We weren't checking primality of p and q.

So the old code:

if (q) {
check y^q mod p = 1
if not fail
}

check 1 <y < p-1 (done in DH_Derive).

New code

if (! p is approved prime) {
if (FIPS) fail;
if (q) {
y_test = y
if (p,q-> p is a safe prime) {
y_test = 1
}
check prime is prime Fail if not
check subprime is subprime fail if not
y_test^q mod p = 1
}
}
check 1 < y < p-1 (done in DH_Derive)

This means:
Existing code non-fips without setting the subprime continues to run as before.
Non-fips code which sets the subprime now runs slower, but p and q are checked
if p or q where not prime, the derive fails (which it should).
In FIPS mode only approved primes will succeed now.
Non-fips code can now set the subprime to q=(p-1)/2 if it doesn't have an
explicit q value (like in tls). If the derive succeeds, we know that p is a
safe prime. If p is approved, the checks are skipped because we already know
that p is a safe prime. Code can optionally do a test derive on a new p and
remember it's safe so that we know longer need to check ever call (though if
q is not (p-1)/2, you will need to continue to do the checks each call
because y could still be a small subgroup).

This patch:

gtests/softoken_gtest

1. Added New dh tests to softoken_gtests. The tests were added to softoken_gtests
   because we need to test both non-FIPS and FIPS mode. Test vectors include a
   category, so the same test vectors can be used in FIPS and non-FIPS even though
   each class may have different results. Most of the test vectors where created
   either by dhparams command in openssl, dsaparams in openssl, and the nss makepqg
   command. Each vector includes a label, prime, base, optional subprime, optional
   public key, test type, and key class (basically size).
2. If public key is not supplied, we use a generated public key.
3. If subPrime is supplied to wet it on the private key after generation.

lib/freebl/dh.c

1. add primality tests to KEA_VerifyKey().

lib/softokn/

1. Allow CKA_SUBPRIME to be set after key generation or import. This affects
   how we test for it's existance, since it is now always there on the key, we
   check it's length to make sure it's non-zero.
2. We implement the psuedocode above as real code.
3. We create two new functions:
   sftl_VerifyDH_Prime which return SECSuccess if Prime is an approved prime.
   sftk_IsSafePrime which returns SECSuess of both prime and subprime look
   reasonable, and sets a Bool to PR_TRUE is subprime -> prime is safe
   (subprime = (prime-1)/2. These functions are implemented in sftkdhverify.c
4. Cleanup incorrect nominclature on primes (safe primes are not strong primes).

Comment 2

[Kevin Jacobs [:kjacobs]]

https://hg.mozilla.org/projects/nss/rev/0be91fa2217a979feb33f0032957b929dd8831ca
https://hg.mozilla.org/projects/nss/rev/4014c075a31b8d076d638d610f99fedc18b53e76