298520 - Ensure that key establishment must be as secure as the strength of the key being transported for FIPS 140-2

Status: RESOLVED FIXED

(NSS :: Documentation, defect, P1)

Description

[glen beasley]

ensure the security of key establishment method is as strong as the crypto key
being transported for FIPS 140-2 see VE.07.19.01 

This requires a table of comparable key strengths between different 
algorithms, such as RSA and AES.

Comment 1

[Wan-Teh Chang]

Attachment: Proposed patch (except DH private key size)

What we need to for this requirement is to ensure
that the maximum strengths of our key establishment
methods must be comparable to the strength of AES-256.
From NIST SP 500-57, Part 1, Table 2:Comparable strengths,
these are:
- Finite Field Cryptography (e.g., DSA, D-H)
  L = 15360, N = 512, where L is the size of the public
  key and N is the size of the private key
- Integer Factorization Cryptography (e.g., RSA)
  k = 15360, where k is the size of the modulus n.
- ECC (e.g., ECDSA)
  f = 512+, where f is the size of n, the order of the
  base point G.

I searched for all the maximum values in our softoken
as follows:
1. In all directories, I searched in all headers for
lines that contain both "define" and "MAX".
2. In lib/freebl and lib/softoken, I searched in all
files for lines that contain both "define" and "MAX".

I found the following relevant macros:
- #define MAX_ECKEY_LEN      72 /* Bytes */
  This is unchanged.
- #define MAX_RSA_MODULUS  1024 /* bytes, 8k bits */
  This is replaced by RSA_MAX_MODULUS_BITS/8, where
  the new macro RSA_MAX_MODULUS_BITS is defined as
  #define RSA_MAX_MODULUS_BITS 15360
- #define MAX_RSA_EXPONENT    8 /* bytes, 64 bits */
  This is unchanged because I think public exponents
  are usually 3 or 0x10001 (65537).  Nelson, is this
  maximum okay?
- #define DH_MAX_P_BITS         2236
  This value is increased to 15360.
- #define MAX_KEY_LEN 256
  This is unchanged.  I just added a comment to explain
  what the macro means.

I didn't handle N = 512 (size of the private key) for FFC
(DSA, D-H).  In lib/freebl/dh.c, the size of the private
key is a hardcoded constant:
    #define DH_SECRET_KEY_LEN      20
which is 160 bits.  SP 800-57 Table 2 lists the following
(L, N) pairs:

L = 1024, N = 160
L = 2048, N = 224
L = 3072, N = 256
L = 7680, N = 384
L = 15360, N = 512

Our hardcoded N value of 160 is only suitable for a 1024-bit
public key.  PKCS #3 does not contain any "20" or "160"
strings.  So I may need to consult ANSI X9.42.  Nelson, do
you think we should modify DH_NewKey to make the private key's
size depend on the size of the prime P?  Anyone know why our
private key size is hardcoded at 160 bits?

Comment 2

[Julien Pierre]

Per our meeting today, retargetting to 3.11.1 .

Comment 3

[Wan-Teh Chang]

Attachment: Proposed patch v2 (except DH public and private key sizes)

The only real change in this patch is to increase the
maximum RSA modulus size from 8k bits to 15360 bits.
The rest of the changes are all code cleanup.  I
didn't change Diffie Hellman maximum key sizes at
all.

Nelson, let me know if you'd like the RSA maximum
modulus size to be a power of 2 (16 * 1024) rather
than this 15360 number from the NIST SP 800-57.

Comment 4

[Nelson Bolyard (seldom reads bugmail)]

I understand the rationale for this patch, but I am concerned about an 
unintended consequence, namely, renewed vulnerability to Denial of Service
attacks.  We chose the current limit specifically to bound the amount of 
time that a single RSA computation can take.  RSA computation time grows 
linearly with the size of the exponent, but geometrically with the size 
of the modulus, that is, RSA computation time is proportional to the square 
of the modulus size.  Doubling the modulus size limit will quadruple the 
maximum RSA computation time.   

IIRC, we encountered a test case in which the RSA computation took very 
long (hours?) because it used a rather large modulus.  I think that may 
have been one of the NISCC tests.  (The details are in an old BugScape 
bug, not in bugzilla :-( .)  I am concerned that by raising the RSA 
modulus limit this far, we are making NSS vulnerable to that attack again. 

Having said that, I will review the patch for correctness without regard 
to the DOS potential.

Comment 5

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 203451 [details] [diff] [review]
Proposed patch v2 (except DH public and private key sizes)

This patch appears to correctly do what it was intended to do.
So, r=nelson, assuming we decide this will not create a DoS vulnerability.

BTW, should we do the same thing to MAX_RSA_EXPONENT that this patch does
to MAX_RSA_MODULUS, namely move it into blapit.h and convert it to a
count of bits?

Comment 6

[Nelson Bolyard (seldom reads bugmail)]

Hmm. Here's another thought.  Maybe the max RSA modulus length should depend 
on whether softoken is in FIPS mode or not.

Comment 7

[Julien Pierre]

Re: comment #6,

I think it would be reasonable to add optional arguments to softoken to configure the maximum key size. The default for the non-FIPS mode of operation should be to retain the limits we have now, and the default for the FIPS mode would be these higher limits.

Comment 8

[Wan-Teh Chang]

Nelson, Julien:

FIPS mode should be more secure than non-FIPS mode.
Your suggested change will make FIPS mode more
vulnerable to DoS attack, which doesn't make sense.

I am perfectly fine with keeping the current maximum
RSA modulus size and having our FIPS 140-2 certificate
annotated with the caveat that key establishment by
RSA key wrapping in our softoken has at most 192 bits
of security.

Could you tell me how to use bltest to perform an
RSA public key operation (such as RSA encryption)?
I'd like to measure the performance of RSA with
various modulus sizes.

Comment 9

[Julien Pierre]

rsaperf is much easier to use to test RSA performance . By default, it tests private key ops. Use the -e option to test public key ops. For example,
./rsaperf -n none -k 2048 -p 20 -e . This will generate a keypair, and then test the performance of public key ops for 20 seconds. With larger key sizes, the keygen is likely to take much longer than 20 seconds, though.

Comment 10

[Julien Pierre]

FYI, on my opteron 248 (2 ghz), the 15360 bits RSA keygen took just under 16 minutes, running 64-bit optimized code. After that, performance was 173 ops/s for public key operations. This is the best case, as the opteron is the CPU for which mpi is now the most optimized. Other CPUs, and 32-bit code, are going to be slower. My measurements on other key sizes show that on the same opteron, if I use 32-bit binaries, I get about 1/5th of the speed. Most CPUs from Intel are also much worse at multiplies than AMD. And the average clock speed is less than 2 GHz. So, I wouldn't be surprised if the average machine out there only does about 10 public key ops/s for the maximum RSA key size set in the patch.

Comment 11

[Robert Relyea]

The keygen should not be part of your worry about DOS, since the user can't force a keygen. The interesting number is how many public key ops can we do. 10 ops/sec isn't a DOS for a client, the biggest risk to servers is dealing with a nasty client Auth.

Does anyone measure the performance of the client auth case currently? It seems like the larger key size reduces the public key ops to roughly the level of private key ops for 1024 bit keys. It seems to me you would have to bring up several hundred attacking threads to bring down a server for a second or two. At what point does the standard DOS detection tools kick in? (you can always create a DOS by swamping the server with connection requests, independent of SSL).

bob

Comment 12

[Julien Pierre]

Attachment: test script. Checks RSA performance at the freebl layer

This is a test script which can be helpful in measuring performance of public keys (as well as private keys). Should be run overnight on slow machines.

Bob, I know the user never forces a keygen. The keygen is only necessary because rsaperf does not have built-in keys for sizes other than 1024 bits. We should add the larger keys to save the keygen time, which is huge for older 32-bit CPUs .

We have not measured the performance of SSL client authentication in the recent past at Sun. Last time I worked on it (3 years ago), the revocation check was the biggest problem by far. That was fixed, and I don't remember what the main bottleneck is now. It's probably in PKIX code somewhere else. There are possibly many other public key ops in the server than the one used in SSL, depending on the size of the cert chain.

Comment 13

[Wan-Teh Chang]

My PC (2.4GHz Pentium 4) can do 37 public key ops per
second with a 8K-bit RSA modulus.  (Key gen took at
least an hour, which is unacceptable.)

With that number, we can extrapolate that my PC should
be able to do 37/4 = 9 public key ops per second with a
16K-bit RSA modulus.  Does that make an NSS-based server
vulnerable to a DoS attack?

If 9 ops/sec is vulnerable to a DoS attack, is 37 ops/sec
also vulnerable?  What is our criterion for DoS vulnerability?

Comment 14

[Wan-Teh Chang]

Attachment: Proposed patch v3 (except DH public and private key sizes)

I moved the maximum RSA exponent size macro to
blapit.h as Nelson suggested.

Comment 15

[Julien Pierre]

I'm not sure we can come up with a general criterion for DoS here. Even with typical RSA keys (1024, 2048 bits), it's not hard to peak a server's CPU with full SSL handshakes - let alone client auth handshakes. In our labs, we need about 1.5 times the client CPU power compared to the server in order to fully peak SSL servers. Of course, the clients are multithreaded (strsclnt), otherwise, not much load is applied. Once you add more load, the latency of the server simply increases. To me this sounds like there is no one-size-fits-all, and the criterion may need to be application and hardware specific. Having the max key size configurable as an optional argument to C_Initialize is probably the best way to let the end-user decide . modutil would need to be enhanced to expose this setting and save/read it in secmod.db .

This still leaves the question of the default. I don't think we should make the limit higher than 8192 by default, given the finding on common hardware (2.4 GHz P4) that these keys take so long to process. Perhaps we can simply do the FIPS validation with the higher limit set in modutil, as part of the test environment ?

Comment 16

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 203564 [details] [diff] [review]
Proposed patch v3 (except DH public and private key sizes)

I like this patch even better than the previous version.  
The only remaining question is about the number 15360.  
If the very fastest CPU on which NSS runs can only do less than 10 ops/sec with a 15Kb key, 
Then other CPUs are going to do much less than 1 per second.  That seems clearly unacceptable.  

I'd like to suggest a floor of 20 ops/sec, and not allow a key size that is so large that we cannot do 20 ops/sec with that key size.  Of course, this will vary by CPU type and speed.  

I think it would be prudent for one of Sun's NSS developers to see how many ops/sec can be done with 2kb, 4kb, 8kb, and 15kb keys on a fairly modern US-3 or US-4 CPU.

Comment 17

[Julien Pierre]

Nelson,

I ran some tests with the 15360 bits key . I created a cert for it, to avoid the huge keygen time. rsaperf support running with a cert using -d dbdir and -n certnickname. In this mode, there is additional overhead because of softoken, as rsaperf doesn't go directly to freebl anymore . But the softoken overhead is negligible for the huge keys.

Here are the results :
US II/248 : 2.91 ops/s
US III/900 : 8.24 ops/s
Pentium 4/2800 : 9.10 ops/s
Opteron/2200 w/ x86 code : 30.09 ops/s
Opteron/2200 : 194 ops/s
PA-RISC/??? : 18.74 ops/s
PowerPC/??? : 7.77 ops/s

I don't know how to find out the exact type of chip and clock speed on HP-UX and AIX.

Comment 18

[Julien Pierre]

Attachment: cert db with certs of 512, 1024, 2048, 4096, 8192 and 15360 bits public keys

Comment 19

[Julien Pierre]

Attachment: key db containing 512, 1024, 2048, 4096, 8192 and 15360 bits private keys matching the cert db

Comment 20

[Julien Pierre]

Attachment: script that tests all the public and private keys from DBs in ~/certs . Uses PKCS#11 session objects for benchmarking.

Comment 21

[Nelson Bolyard (seldom reads bugmail)]

Julien, regarding your comment 17, were those public key ops or private?

Comment 22

[Julien Pierre]

Nelson,

Those were public keys ops. The private key ops were much slower - they varied between 0.02 and 0.98 ops/s depending on the CPU.

Comment 23

[Robert Relyea]

>It's probably in PKIX code somewhere else. There are
>possibly many other public key ops in the server than the one used in SSL,
>depending on the size of the cert chain.

Ah, you are right. I was thinking we verified the signature of the request before you handled the certificate chain, but we don't. We verify the cert chain first, then verify the signature. This leaves us open to worse attacks because you can multiply the effect of the verification by creating long chains of certificates.

If we verified the signature first, then we force the attacker to do a private key op before hand. That private key op must be completed in real-time, not pregenerated, so the attackers horsepower has to greatly outway the server's horsepower.

Now that I think about it, the best way to do this attack is to have your 'personal' key be something small (like 512 bytes), but the signatures on each cert in the chain should be the max you can get away with. In this senario you will do the most damage in both cases, since we will never really get to verifying the user's client auth signature because our chain won't connect to anyplace real? (I'm presuming that a real CA would not construct long chains of 16K key certificates to mount this attack).

bob

Comment 24

[Julien Pierre]

Does the SSL spec say anything about the ordering of the certs that are sent ?
The libpkix code has the capability to build from different directions, and to verify an actual chain as input, as opposed to a leaf cert as CERT_VerifyCert* do. 
If we start verifying the chain from a root cert trusted for client auth, then none of the large public key attacks would work. The main problem with this approach is that it also takes significant time for NSS to query the trusted root certs from all tokens. Unfortunately that information is dynamic over the liftime of a process.

Comment 25

[Nelson Bolyard (seldom reads bugmail)]

(In reply to comment #24)  Julien asked:
> Does the SSL spec say anything about the ordering of the certs that are sent ?

Yes, RFC 2246 says (page 39)

   certificate_list
       This is a sequence (chain) of X.509v3 certificates. The sender's
       certificate must come first in the list. Each following
       certificate must directly certify the one preceding it. Because
       certificate validation requires that root keys be distributed
       independently, the self-signed certificate which specifies the
       root certificate authority may optionally be omitted from the
       chain, under the assumption that the remote end must already
       possess it in order to validate it in any case.

Note, although the certs are sent leaf-to-root, that is not necessarily
the order in which the chain is validated.  However, if the chain is 
incomplete (lacking the root, as described in the RFC, quoted above),
then presumably the chain must be completed, and that presumably means
traversing it leaf-to-root.

Comment 26

[Nelson Bolyard (seldom reads bugmail)]

Wan-Teh, Glen, 
Is this bug intended to suggest that tests be added to SSL and/or CMS (libSMIME)
to ensure that the cipher suites and/or CMS messages use a key establishment
method as strong as the crypto key being transported?

Comment 27

[Julien Pierre]

Per our meeting, removing ECC from status whiteboard . No SSL code change is required, so changing category to documentation.

Comment 28

[Nelson Bolyard (seldom reads bugmail)]

What (if anything) does this requirement imply about the strength of the 
authentication algorithm used to authenticate the key used for key 
transport/agreement?

As you know, SSL/TLS cipher suites use both a key transport/agreement 
algorithm to communicate the "pre-master secret", and they also use an
algorithm to authenticate the server's key.  There *can* be huge disparity
between the strengths of the keys for the two algorithms.  The key 
transport key can be tiny, and the authentication key can be huge, 
or vice versa.

Does this requirement imply that the authentication key should be at least
as strong as the key transport key?  or at most as strong ? or ??

This question is particularly relevant in the case of ECDHE key agreement
and RSA authentication.  Are the strengths of the two keys permitted to 
be independently determined?  

Comment 29

[Wan-Teh Chang]

There are several FIPS 140-2 requirements of this sort.
The spirit of these requirements is that the security
of a system is only as strong as the security of its
weakest link.  It is possible that some of these
requirements, such as this one, may be worded
imprecisely or omit some details.  I would interpret
the imprecise requirements or fill in the blanks
with the "weakest link" philosophy in mind.

In any case, we have decided to not try to meet this
requirement.  Instead, we will just document that NSS
allows the security of key establishment method to be
weaker than the crypto key being transported.  This is
why this is now a documentation bug.  Our FIPS certificates
may be annotated with a caveat as I described in comment 8.

Comment 30

[Nelson Bolyard (seldom reads bugmail)]

In reply to comment 1:
> What we need to [snip] ensure that the *maximum* strengths of our key 
> establishment methods must be comparable to the strength of AES-256.

Are we only concerned with MAXIMUM strengths? 
Is there a requirement here to ensure that, for specific encryption keys
being transported, the tranport key used to transport it be as strong as 
the key being stransported, in each case?

Is the requirement limited to key transport?  
What about key agreement (e.g. DH, ECDH) and derivation?

In comment 29, you wrote:
> The spirit of these requirements is that the security of a system is 
> only as strong as the security of its weakest link.

I agree.  That's what was behind my question in comment 28.  Let me ask it
another way.  

Ought we prevent SSL/TLS from negotiating an AES 256 cipher suite when
the SIGNATURE key (used for authentication) is much weaker?  
Does it make sense to choose a really strong ECDHE key/curve to establish 
the PSM (from which the AES 256 key will ultimately be derived) when the 
signature key (e.g. in the server cert) is only 1024 bit RSA?

In cases of a mismatch of key sizes for various purposes, should be choose
ephemeral keys (from which others will be derived) according to the 
strongest key to be used in the entire handshake? or the weakest? 

Comment 31

[Wan-Teh Chang]

We decided to not change the maximum RSA or DH key sizes
allowed by NSS.  Instead, we decided to annotate the NSS
Cryptographic Module Security Policy with the caveats
required by Implementation Guidance for FIPS 140-2
(http://csrc.nist.gov/cryptval/140-1/FIPS1402IG.pdf),
IG 7.5 "Strength of Key Establishment Methods".

I have added the caveats to our Security Policy:
http://wiki.mozilla.org/Security_Policy#Specification_of_Security_Policy

  The FIPS PUB 140-2 cipher suite shall consist solely
  of ..., RSA (PKCS #1, key wrapping, key establishment
  methodology provides between 80 bits and 192 bits of
  encryption strength) and Diffie-Hellman (key agreement,
  key establishment methodology provides between 80 bits
  and 112 bits of encryption strength) for key
  establishment, ...

and our Key Management documentation:
http://wiki.mozilla.org/VE_07KeyMgmt

  Key Establishment Techniques

  NSS uses the following Approved key establishment
  techniques listed in Annex D to FIPS PUB 140-2:

    * Diffie-Hellman (key agreement, key establishment
      methodology provides between 80 bits and 112 bits
      of encryption strength)
    * Key Wrapping using RSA keys (PKCS #1, key wrapping,
      key establishment methodology provides between 80
      bits and 192 bits of encryption strength)

The caveats were written as specified in the Implementation
Guidance for FIPS 140-2.  The minimum 80 bits of encryption
strength are the minimum in FIPS mode, rather than the
minimum allowed by NSS.  The maximum 112 bits or 192 bits
of encryption strength come from the maximum DH key size of
2236 bits or the maximum RSA key size of 8192 bits allowed
by NSS.

Comment 32

[Wan-Teh Chang]

Attachment: Proposed patch v4 (code cleanup only)

Since we decided to not raise any maximum key size, the
only things left in the proposed patch are all code cleanup
changes.

1. Move the maximum RSA sizes from rsa.c to blapit.h.
2. Add a comment for MAX_KEY_LEN.

Comment 33

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 221396 [details] [diff] [review]
Proposed patch v4 (code cleanup only)

r=nelson

Comment 34

[Wan-Teh Chang]

Comment on attachment 221396 [details] [diff] [review]
Proposed patch v4 (code cleanup only)

I checked in this code cleanup patch on the NSS trunk (3.12) only.

Checking in pkcs11i.h;
/cvsroot/mozilla/security/nss/lib/softoken/pkcs11i.h,v  <--  pkcs11i.h
new revision: 1.44; previous revision: 1.43
done
Checking in blapit.h;
/cvsroot/mozilla/security/nss/lib/freebl/blapit.h,v  <--  blapit.h
new revision: 1.19; previous revision: 1.18
done
Checking in rsa.c;
/cvsroot/mozilla/security/nss/lib/freebl/rsa.c,v  <--  rsa.c
new revision: 1.37; previous revision: 1.36
done