636802 - Softoken & FreeBL cannot do Diffie-Hellman key agreement with keys larger than 2236 bits

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P2)

Description

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

See blapit.h:

#define DH_MAX_P_BITS         2236

I would expect some servers to want to use 3072-bit keys (to match AES-128) based on the NIST guidelines. I did not find any such limit in OpenSSL (though I looked only briefly).

Comment 1

[Nelson Bolyard (seldom reads bugmail)]

IIRC, that number was chosen after measuring execution time for various 
large primes and then choosing an upper bound on the acceptable amount of 
time, above which the operation would be considered a denial of service.

Numbers which are set in that way need to be better documented with respect 
to the criteria by which they were chosen, and then revisited from time to 
time to update them, provided that the criteria are still valid.

Comment 2

[Janne Snabb]

Yes, it is about time DH_MAX_P_BITS should be bumped.

Currently NSS has a serious emerging interoperability issue with GnuTLS:

GnuTLS 2.12.0 which was released a bit more than a year ago introduced a new function "gnutls_sec_param_to_pk_bits()" which offloads the burden of selecting suitable key sizes from individual software authors to GnuTLS library maintainers. See the following URL for more information on this:

https://www.gnu.org/software/gnutls/manual/html_node/Selecting-cryptographic-key-sizes.html

As can be seen, GnuTLS now suggests 2432 bits DHE key size on "NORMAL" security level and 3248 bits on "HIGH" security level. Neither of these settings can inter-operate with NSS with the current maximum key size of 2236 bits. Only security levels "LOW" and "LEGACY" can inter-operate with NSS.

The only reason people are not hitting this frequently right now is that this GnuTLS API call is new and not much of the mainstream software uses it yet (because they want to be compatible with the older API). Most software still uses hard-coded 1024 or 2048 key size.

Exim's (a very popular MTA) GnuTLS support was revamped just now, and as a result Thunderbird was not able to do STARTTLS any more. The Exim code had to be patched to clamp down the maximum key size to 2236 bits so that it can still interoperate with NSS based software. Such hacks are ugly and should not be needed.

The last time this maximum key size was increased is documented at the following bug:

https://bugzilla.mozilla.org/show_bug.cgi?id=259229

That was about 7.5 years ago. Any measured execution times 7.5 years ago are completely irrelevant today.

I propose bumping DH_MAX_P_BITS preferably to 8k or at the very least to 4k to allow interoperability for the next couple of years. The best would be to have a mechanism which allows NSS consumers to configure this.

Best Regards,
Janne Snabb

Comment 3

[Phil Pennock]

The GnuTLS folks state:
  That's very interesting. Our key sizes is according to recommendations like ECRYPT [0]

  [0] http://www.keylength.com/en/3/

The table at that link is enlightening.

Comment 4

[Janne Snabb]

How to test:

certtool --generate-privkey --outfile key.pem
certtool --generate-self-signed --load-privkey key.pem --outfile cert.pem
certtool --generate-dh-params --bits 2237 --outfile dh2237.pem
certtool --generate-dh-params --bits 2236 --outfile dh2236.pem

gnutls-serv --http --x509keyfile key.pem --x509certfile cert.pem --dhparams dh2237.pem --disable-client-cert --priority NONE:+VERS-TLS-ALL:+CIPHER-ALL:+MAC-ALL:+DHE-RSA:+SIGN-ALL:+COMP-ALL

Connect to https://localhost:5556/ (with firefox for example) and observe the failure.

gnutls-serv --http --x509keyfile key.pem --x509certfile cert.pem --dhparams dh2236.pem --disable-client-cert --priority NONE:+VERS-TLS-ALL:+CIPHER-ALL:+MAC-ALL:+DHE-RSA:+SIGN-ALL:+COMP-ALL

Connect to https://localhost:5556/ (with firefox for example) and observe the normal security warning about untrusted certificate.

gnutls-serv and certtool are part of GnuTLS tools. They can be installed on Debian and Ubuntu by running "apt-get install gnutls-bin".

The long priority string is there just to ensure that the TLS handshake negotiates DHE-RSA based key exchange (new GnuTLS versions negotiate ECDHE-RSA otherwise which masks the issue because DHE key will not be needed). With older GnuTLS versions (I think less than 3) priority string "NORMAL" is sufficient as the older GnuTLS library does not have support for elliptic curves.

Comment 5

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Our plan is to increase the limit to 16K.

Comment 6

[Wan-Teh Chang]

bsmith: the Diffie-Hellman private keys generated by NSS
are hardcoded to be 160 bits long:
http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/security/nss/lib/freebl/dh.c&rev=1.11&mark=24#24

The private key length should be the same as the length of the
q parameter.  So for a 2048-bit p, q should be either 224 or
256 bits.  A 160-bit q is only appropriate for a 1024-bit p.

Private key length should max out at 512 bits (at the 256-bit
security level).

We can come up with a step function that returns these discrete
private key lengths depending on the size of p:
160 bits
224 bits
256 bits
384 bits
512 bits

See NIST SP 800-57, Table 2 and http://www.keylength.com/en/4/

Comment 7

[Wan-Teh Chang]

Attachment: Increase max RSA and DH key sizes to 16K bits. Adjust DH secret key size to group size

Comment 8

[Robert Relyea]

Comment on attachment 631576 [details] [diff] [review]
Increase max RSA and DH key sizes to 16K bits. Adjust DH secret key size to group size

r+ rrelyea

Comment 9

[Wan-Teh Chang]

Patch checked in on the NSS trunk (NSS 3.14).

Checking in blapit.h;
/cvsroot/mozilla/security/nss/lib/freebl/blapit.h,v  <--  blapit.h
new revision: 1.29; previous revision: 1.28
done
Checking in dh.c;
/cvsroot/mozilla/security/nss/lib/freebl/dh.c,v  <--  dh.c
new revision: 1.12; previous revision: 1.11
done