TLS interoperability issue in NSS based software

[Janne Snabb]

NSS (Netscape Security Services) module provides encryption services to many applications, such as Thunderbird, Firefox and Chromium. NSS has a hard coded maximum limit of 2236 bits for ephemeral Diffie-Hellman (DHE) keys. If the TLS server (such as a web server, SMTP server, IMAP server, etc) requests a bigger DHE key size, NSS based applications refuse to interoperate. They just close the connection and display a confusing error message (such as "Unknown error").

Recent versions of GnuTLS (as shipped by Ubuntu and other distributions) include a new library API which recommends and automatically selects the following key sizes:

Security level key bits

LOW 1248
LEGACY 1776
NORMAL 2432
HIGH 3248

See the following for more information: https://www.gnu.org/software/gnutls/manual/html_node/Selecting-cryptographic-key-sizes.html

As can be seen, NSS's maximum limit of 2236 bits can only interoperate with GnuTLS server which has been set at "LOW" or "LEGACY" security level.

This bug was discovered when Exim's GnuTLS interface was revamped recently. Thunderbird refused to complete TLS handshake with the Exim SMTP server any more, because the new GnuTLS interface was following the GnuTLS library's opinion on suitable key sizes.

Please patch the NSS library to accept reasonable key sizes: at the very least 3248 bits should be accepted to allow interoperability with GnuTLS at HIGH level. NSS is the only TLS library which has such a low hard limit on DHE key size.

The only reason people are not hitting this bug frequently yet is that most main stream server software still does not use GnuTLS library's new API or recommendations but instead hard codes the DHE key size to 1024 or 2048 bits.

I am attaching a patch which points out the relevant #define in blapit.h.

[Bsmith-mozilla (bsmith-mozilla)]

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).

[Nelson-bolyard (nelson-bolyard)]

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.

[Janne Snabb (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

[Ubuntu Foundations Team Bug Bot (crichton)]

The attachment "nss-dh-max-p-bits.patch" of this bug report has been identified as being a patch. The ubuntu-reviewers team has been subscribed to the bug report so that they can review the patch. In the event that this is in fact not a patch you can resolve this situation by removing the tag 'patch' from the bug report and editing the attachment so that it is not flagged as a patch. Additionally, if you are member of the ubuntu-reviewers team please also unsubscribe the team from this bug report.

[This is an automated message performed by a Launchpad user owned by Brian Murray. Please contact him regarding any issues with the action taken in this bug report.]

[Moz-bugs+5329 (moz-bugs+5329)]

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.

[Janne Snabb (snabb)]

Here are the relevant error messages from different NSS consumers.

Thunderbird:

Sending of message failed.
The message could not be sent using SMTP server localhost for an unknown
reason. Please verify that your SMTP server settings are correct and try
again, or contact your network administrator.

Firefox:

Secure Connection Failed
An error occurred during a connection to localhost.
Unable to generate public/private key pair.
(Error code: sec_error_keygen_fail)

Chromium:

This webpage is not available
The webpage at https://localhost/ might be temporarily down or it may
have moved permanently to a new web address.
Error 2 (net::ERR_FAILED): Unknown error.

[Janne Snabb (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.

[Janne Snabb (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.

[Micah Gersten (micahg)]

This needs to be accepted upstream before we take it in Ubuntu. Also, chromium uses the system NSS, but thunderbird doesn't anymore.

[Bsmith-mozilla (bsmith-mozilla)]

Our plan is to increase the limit to 16K.

[Janne Snabb (snabb)]

It appears that the limit has been already increased to 3072 bits in the newest NSS release 3.13.4, see diff at:

http://bonsai.mozilla.org/cvsview2.cgi?diff_mode=context&whitespace_mode=show&file=blapit.h&branch=&root=/cvsroot&subdir=mozilla/security/nss/lib/freebl&command=DIFF_FRAMESET&rev1=1.25&rev2=1.26

Increase to 16k has been targeted to next NSS release 3.13.5 (see the linked mozilla bug).

Could this be backported to precise as it is a LTS release?

[Wan-Teh Chang (wtc-google)]

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/

[Wan-Teh Chang (wtc-google)]

Created attachment 631576
Increase max RSA and DH key sizes to 16K bits. Adjust DH secret key size to group size

[Rrelyea (rrelyea)]

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

r+ rrelyea

[Wan-Teh Chang (wtc-google)]

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

[Matthew Haughton (snafu109)]

This was fixed in 3.14 release of NSS as shown at https://bugzilla.mozilla.org/buglist.cgi?list_id=4643675;resolution=FIXED;classification=Components;query_format=advanced;product=NSS;target_milestone=3.14 (see bug 636802). All currently supported Ubuntu releases are on 3.15+ so closing as this no longer affects any current Ubuntu versions.