1478698 - FFDHE key exchange sometimes fails with decryption failure

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P2)

Description

[Alicja Kario]

Version: be5c5d3ad5f6 from tip

When the tlsfuzzer or gnutls is run against NSS server with negotiation selecting FFDHE key exchange, the handshake sometimes fails with decryption failure on Encrypted Extensions message.

I'm guessing that NSS does not left pad the shared secret in TLS 1.3 connections; see https://tools.ietf.org/html/draft-ietf-tls-tls13-28#section-4.2.8.1

Reproducer:

git clone https://github.com/tomato42/tlsfuzzer.git
pushd tlsfuzzer
git checkout ffdhe-test-script
git clone https://github.com/warner/python-ecdsa .python-ecdsa
ln -s .python-ecdsa/ecdsa ecdsa
git clone https://github.com/tomato42/tlslite-ng.git .tlslite-ng
ln -s .tlslite-ng/tlslite tlslite
popd
openssl req -x509 -newkey rsa -keyout localhost.key -out localhost.crt -nodes -batch -subj /CN=localhost
openssl pkcs12 -export -passout pass:  -out localhost.p12 -inkey localhost.key -in localhost.crt
mkdir nssdb
certutil -N -d sql:nssdb --empty-password
pk12util -i localhost.p12 -d sql:nssdb -W ''
selfserv -n localhost -p 4433 -d sql:./nssdb -V tls1.0: -H 1 -U 0 -G

# in another terminal, same directory
export PYTHONPATH=tlsfuzzer
while python scripts/test-tls13-ffdhe-sanity.py ; do echo $i; i=$(($i+1)); done


Unexpected result:
Error encountered while processing node <tlsfuzzer.expect.ExpectEncryptedExtensions object at 0x7fa64c3563d0> (child: <tlsfuzzer.expect.ExpectCertificate object at 0x7fa64c356410>) with last message being: None
Error while processing
Traceback (most recent call last):
  File "scripts/test-tls13-ffdhe-sanity.py", line 185, in main
    runner.run()
  File "/home/hkario/dev/tlsfuzzer/tlsfuzzer/runner.py", line 180, in run
    header, parser = self.state.msg_sock.recvMessageBlocking()
  File "/home/hkario/dev/tlsfuzzer/tlslite/messagesocket.py", line 101, in recvMessageBlocking
    for res in self.recvMessage():
  File "/home/hkario/dev/tlsfuzzer/tlslite/messagesocket.py", line 83, in recvMessage
    for ret in self.recvRecord():
  File "/home/hkario/dev/tlsfuzzer/tlslite/recordlayer.py", line 888, in recvRecord
    data = self._decryptAndUnseal(header, data)
  File "/home/hkario/dev/tlsfuzzer/tlslite/recordlayer.py", line 785, in _decryptAndUnseal
    raise TLSBadRecordMAC("Invalid tag, decryption failure")
TLSBadRecordMAC: Invalid tag, decryption failure

Note:
the test case is non deterministic - fails about once every 20-50 iterations

Comment 1

[Alicja Kario]

Indeed it looks like the problem is with zero padding, I've run the test few times, and always the connection failed when the shared secret needed to be zero padded.

Example connection:

for ffdhe4096, the private value selected by client is
0xefca446cd9bbb5ee8afcdc5cf286bb0e350364535f4c52bf4f06f9e6dfa84d651cb6b03047e8

NSS server share: 0x30910752e3072e6c1dfa71c795ccb5eb866683cca77350b87c0c249bd5946ce17893c8c3757aca8e45ccd4e9ba4c567b4e35a0f99bbf980d6bffb9624e5ed6dfe928cbd5b1d06ac00756ca64431343072e6c3d6a81d7415a32ed5548ca7613d82fc8e57a82eab84918be81731715ca2c79c20bd3803940cf1dcaa144517eabbfd46d9ba871a6a74e53e5e9b97c8a1a31791d7132d08d9c5d9fb074c076864e8fcc500e1d2be087ae3c7b9b9dd347ee1ac1a9cff9204ac993084a729ebfdd3df5823c6c75cee2090f671a0b3a57cccb9ebc524bdb33ecf4160368cf1d42e443d2c3360b4d13d74aa09f7b81350c6d5e1568191d120990753bfe334cadd64e3585c1c9af2cdf6b12ccfe3eee4db4615a14b36c875570fe1b1b8d779c7273c7a256389192e20863acb10abb833510a22f6dc14d1892e677fb0ce78fb989d849be66c520631763897b0d2c5cf62680c2770af094cef30898ff88f4c853bd0498449c7f3bc9047e11702eea792a0fbc4ab3e5f5db2dca329bd1662a70cd58f1d8beb01be9b6745375aafcece0562eab6b2ecb22fda007d085771f4b0532c33fb50ea74f5dd004b0fc8b35ea9c6dd26baf53a5905e9ab987d5bd88aed775c0fc4d23200c4631aa4d2bce4989efe2f302f446187f13a8d4737c94940207185615099f98e91b67c3f3f59c0f05ce62f8b4b74e8760c92e802a76421f01d89af346ab904b

calculated shared secret:
0x00ff331bec0c941ec641079ac2fe83138cffa8a289cd7c23905dcdb199d8f0c1336a86934d2465132b2a58f1ceda076ed0056174ac1688af654124bacf117655e674375b4514dbc760a346ce99bb0f9ad83b10a63be5ba1a1c38f53be359f5c7621768e2dd3cbc50ef7166c84a7dc44e5c6a32fb0de27bbcdf3b455fd645155d0d533690d74d13f1642146b41174a5876ee22c56d70fde177c21b8b2f920ad9f1e16050a402815c137fc6d2b2664c8406ec53a3797ab1bfffc7b69af5ebc1bb372bf273de335b50903cc9f4efa539ba179b9bf7319acb7b5301eedea89fd1ec5bb9ba62150bdfa6604aaa258e793975c25fee62a10f759955dc49bc7017e296342466d2b376ebb7fb3a1c46d31048602a68929998235ecc199376f161bb5b43742906ab92d3b15824d4e956538c0b2d3b1480cbeba35425fc2c48fb8c9efcb13540543d50b3e7d34b1f24f7e06ba3be957a04cd0d6686febde91613ae6e0c5573a834d8b5004cb058a941900d253cb07f7cade0c85cc8e5c9716326347c4b0d248b815489bf18913032f56be8b1613c2b8a04b22193befbee2d6906e74ee36aa80798717925397a89edfc7e9cfa04cbd7861ebd6f1c66e4ea9e9cfb63be57825832c5c56f00e6cbef6e98b8dcf87b43da04d5d0e28ffe22bece92531c6549c01ee5948f004c13b291334e35f28af0b04bd57ec1d9cc518fd69ef2782a20d8c0c


this is after applying the following diff to tlsfuzzer:
diff --git a/tlsfuzzer/expect.py b/tlsfuzzer/expect.py
index 0ae7c2f..76dd5fe 100644
--- a/tlsfuzzer/expect.py
+++ b/tlsfuzzer/expect.py
@@ -187,8 +187,10 @@ def srv_ext_handler_key_share(state, extension):
 
     kex = kex_for_group(group_id, state.version)
 
+    print("server share: {0}".format(b2a_hex(extension.server_share.key_exchange)))
     z = kex.calc_shared_key(cl_ext.private,
                             extension.server_share.key_exchange)
+    print("calculated shared secret: {0}".format(b2a_hex(z)))
 
     state.key['DH shared secret'] = z
 
diff --git a/tlsfuzzer/helpers.py b/tlsfuzzer/helpers.py
index 2b69b56..e8b3dcf 100644
--- a/tlsfuzzer/helpers.py
+++ b/tlsfuzzer/helpers.py
@@ -77,6 +78,7 @@ def key_share_gen(group, version=(3, 4)):
     """
     kex = kex_for_group(group, version)
     private = kex.get_random_private_key()
+    print("group: {1}, private value: {0}".format(hex(private), group))
     share = kex.calc_public_value(private)
     return KeyShareEntry().create(group, share, private)

Comment 2

[Franziskus Kiefer [:franziskus]]

Attachment: Bug 1478698 - make derived DH secret as long as the prime

Comment 3

[Franziskus Kiefer [:franziskus]]

Thanks for reporting Hubert. I attached a patch that should fix the issue. I still have to write a test but it should fix the issue.

Comment 4

[Alicja Kario]

as ekr said, r- on that: in TLS 1.2 the shared secret is explicitly null truncated, so that patch would break TLS 1.2

Comment 5

[Franziskus Kiefer [:franziskus]]

Well, the other option is to create a new PK11 mechanism. This can't be done purely in the TLS code without re-building the entire key.

Comment 6

[Alicja Kario]

can't it be padded after it is returned from the PK11?

Comment 7

[Eric Rescorla (:ekr)]

(In reply to Hubert Kario from comment #6)
> can't it be padded after it is returned from the PK11?

Note that this is what we do with the public keys.
https://searchfox.org/nss/source/lib/ssl/ssl3con.c#5809

Comment 8

[Robert Relyea]

You don't need to create a new mechanism. The existing mechanism takes a key length, which the key will be truncated/padded to.

Here's what I think should work:
TLS 1.3 need to use the key size. Probably this patch could work:

diff --git a/lib/ssl/tls13con.c b/lib/ssl/tls13con.c
--- a/lib/ssl/tls13con.c
+++ b/lib/ssl/tls13con.c
@@ -522,16 +522,17 @@ tls13_HandleKeyShare(sslSocket *ss,
                      TLS13KeyShareEntry *entry,
                      sslKeyPair *keyPair)
 {
     PORTCheapArenaPool arena;
     SECKEYPublicKey *peerKey;
     CK_MECHANISM_TYPE mechanism;
     PRErrorCode errorCode;
     SECStatus rv;
+    int keySize = 0;
 
     PORT_InitCheapArena(&arena, DER_DEFAULT_CHUNKSIZE);
     peerKey = PORT_ArenaZNew(&arena.arena, SECKEYPublicKey);
     if (peerKey == NULL) {
         goto loser;
     }
     peerKey->arena = &arena.arena;
     peerKey->pkcs11Slot = NULL;
@@ -546,28 +547,29 @@ tls13_HandleKeyShare(sslSocket *ss,
             mechanism = CKM_ECDH1_DERIVE;
             break;
         case ssl_kea_dh:
             rv = tls13_ImportDHEKeyShare(ss, peerKey,
                                          entry->key_exchange.data,
                                          entry->key_exchange.len,
                                          keyPair->pubKey);
             mechanism = CKM_DH_PKCS_DERIVE;
+	    keySize = peerKey->u.dh.publicValue.len;
             break;
         default:
             PORT_Assert(0);
             goto loser;
     }
     if (rv != SECSuccess) {
         goto loser;
     }
 
     ss->ssl3.hs.dheSecret = PK11_PubDeriveWithKDF(
         keyPair->privKey, peerKey, PR_FALSE, NULL, NULL, mechanism,
-        tls13_GetHkdfMechanism(ss), CKA_DERIVE, 0, CKD_NULL, NULL, NULL);
+        tls13_GetHkdfMechanism(ss), CKA_DERIVE, keySize, CKD_NULL, NULL, NULL);
     if (!ss->ssl3.hs.dheSecret) {
         ssl_MapLowLevelError(SSL_ERROR_KEY_EXCHANGE_FAILURE);
         goto loser;
     }
     PORT_DestroyCheapArena(&arena);
     return SECSuccess;
 
 loser:

Comment 9

[Robert Relyea]

NOTE: this does exactly what Franziskus's patch did, except just in the TLS 1.3 case.

bob

Comment 10

[Kai Engert [:KaiE:]]

Franziskus, what's your opinion on comment 8 ?

Comment 11

[Franziskus Kiefer [:franziskus]]

That should probably work

Comment 12

[Kai Engert [:KaiE:]]

Should we treat comment 11 as r+ and check it in?

Comment 13

[Eric Rescorla (:ekr)]

No. This needs a test.

Comment 14

[Robert Relyea]

Someone who can reproduce it should test it. If it's works, we should check it in.

I don't know if there's a practical test case we can include in NSS. This is the library compatibility issue, which we don't have a framework for adding new tests (IIRC). If we have such a test framework (particluarly testing against gnutls, openssl doesn't support this cipher suite), then we should add the testcase there.

Comment 15

[Alicja Kario]

Daiki was working on integrating tlsfuzzer with the treeherder, so we should be able to test it now with tlsfuzzer test case

Comment 16

[Martin Thomson [:mt:]]

Let's block this on bug 1485989 then.  I thought about this and can't think of a way to test this without it being very intrusive.  As far as I can tell, the patch is fine, but let's get the fuzzer integrated.

Comment 17

[Alicja Kario]

while there are few tests that use ffdhe already merged in tlsfuzzer, they need to be rerun multiple times to actually detect that FFDHE mismatch (any single run has a probability of about 1 in 256 to fail)

in https://github.com/tomato42/tlsfuzzer/pull/451 there are new scripts that can accept a parameter: `--repeat num` that sets the number of times any given test is repeated, so for verifying that this is fixed, and that it doesn't regress in the TLS 1.2 case, two tests need to be run:

test-dhe-key-share-random.py --repeat 256 'Protocol (3, 3)'
test-tls13-serverhello-random.py --repeat 256 'TLS 1.3 with ffdhe2048'

256 repetitions will give a false negative rate of about (1-1/256)^256 = 37% (as in "one in 3 runs will not fail even though bug is present"); increase it to 1200 to get (1-1/256)^1200 = 0.91% false negative rate

Comment 18

[Alicja Kario]

> any single run has a probability of about 1 in 256 to fail

that should be "any single connection has a probability of about 1 in 256 to fail"

Comment 19

[Martin Thomson [:mt:]]

ekr suggests a tweak.  Rather than rely on probabilities, just have each run report whether the secret was zero-padded and run handshakes until it happens.  Is that possible?

Comment 20

[Alicja Kario]

good idea, I can do that loop (connect, see if the secret was zero padded in TLS 1.3 or shorter in TLS 1.2, continue if it wasn't) inside the script, but that will require a new script

Filed https://github.com/tomato42/tlsfuzzer/issues/454 to track it

Comment 21

[Alicja Kario]

pull request ready: https://github.com/tomato42/tlsfuzzer/pull/458

Comment 22

[Daiki Ueno [:ueno]]

Attachment: nss-tls13-dhe-leading-zeros.patch

This enables the relevant tlsfuzzer test cases to cover the fix.

Comment 23

[Martin Thomson [:mt:]]

Comment on attachment 9011696 [details] [diff] [review]
nss-tls13-dhe-leading-zeros.patch

Review of attachment 9011696 [details] [diff] [review]:
-----------------------------------------------------------------

This is simple enough for splinter.  Thanks.

Comment 24

[Alicja Kario]

the test case designed for verifying this issue is test-tls13-dhe-shared-secret-padding.py, not test-tls13-ffdhe-sanity.py or test-tls13-unrecognised-groups.py (they will verify it only randomly, not deterministically)

also, I think that test-dhe-no-shared-secret-padding.py should be added to verify that this change does not introduce regression in TLS 1.2

Comment 25

[Daiki Ueno [:ueno]]

Attachment: nss-tls13-dhe-leading-zeros.patch

Oh, I didn't realize that those are separate tests; amended with them.

Comment 26

[Alicja Kario]

Comment on attachment 9012075 [details] [diff] [review]
nss-tls13-dhe-leading-zeros.patch

Review of attachment 9012075 [details] [diff] [review]:
-----------------------------------------------------------------

r+

Comment 27

[Martin Thomson [:mt:]]

Comment on attachment 9012075 [details] [diff] [review]
nss-tls13-dhe-leading-zeros.patch

Review of attachment 9012075 [details] [diff] [review]:
-----------------------------------------------------------------

Moar tests.  I'm not checking that Hubert is testing the right things, but we can do that analysis if/when something breaks.

Comment 28

[Daiki Ueno [:ueno]]

Pushed as https://hg.mozilla.org/projects/nss/rev/64de5aec1c11