1211403 - Unable to connect to SSl servers using a public key starting with more than two leading 0 bits

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Christian Boitel]

User Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:40.0) Gecko/20100101 Firefox/40.0
Build ID: 20150826023504

Steps to reproduce:

Use curl on redhat enterprise linux to connect to a server using a public key starting with more than 2 leading bits set to 0:
- Tested with NSS 3.18: all OK
- Tested with NSS 3.19-1: FAIL

You need a server presented such a public key:
- We used 4 Tomcat servers
- I use openssl to check server's public key contents
echo | openssl s_client -connect myserver:myport 2>/dev/null | openssl x509 -text -noout
- check the first bytes of the public key showed
- one of our 4 servers had a public starting with 0x11



Actual results:

Client sends a TLS alert reporting a "insufficient_security"


Expected results:

Connection should be granted: server presents a valid 1024 bits long public key and NSS allows connections to such servers.

Comment 1

[Christian Boitel]

I suspect the problem is located in SECKEY_BigIntegerBitLength commited during
https://hg.mozilla.org/projects/nss/rev/ae72d76f8d24#l2.58

From my understanding, we should remove trailing 0x00 as it is done. But noone can guarantee that first two most significant bits of a key isn't set to 0. After all, it is randomly generated.

Comment 2

[Christian Boitel]

Going a bit further, i found and confirmed in an SSL wireshark network dump that server sends public key using a BIT STRING (ASN/1) containing:
- a first byte stating how many bits have been padded at the end if key size in bits is not a multiple of height
- subjectPublicKey follows padded at the end

In the current code (SECKEY_BigIntegerBitLength in lib/cryptohi/seckey.c), we perform the following
- skip the first bytes being 0x00
- skip bits of the first non 0x00 byte that are 0
- evaluate remaining as key length

So if no padding has been made and public key starts with leading 0 bits, we wrongly calculate key length. We should instead assume first byte is padding indication (0x00 means 0 bits have been padded) and key length in bits is therefore (number -> len - 1) * 8 - padding.

Comment 3

[Christian Boitel]

Digging a bit further, i found this was not as easy as i thought.

First, ASN 1 decoding stubs are respecting the padding byte but somehow the padding byte information gets lost when key is copied to SECITEM. Since the padding byte is lost, there is no way later to find out the exact public key length sent by the server.

Second, SECKEY_BigIntegerBitLength is used in two opposite contexts:
a/ to calculate the server public key length in SECKEY_PublicKeyStrengthInBits
   => leading 0xx and leading 0 bits shall not be removed
   => instead, we should use the padding byte (if ASN 1 bit string encoding was used...) to determine exact key length in bits (len of key sent * 8 - padding byte)
b/ to calculate length of keys exchanged during key exchange steps (client/server key exchange)
   => i understand leading 0x00 and leading 0 bits shall be removed

So i believe:
- asn 1 decoding stubs (and maybe SECITEM) shall be updated to keep the padding byte when bit string is used
- SECKEY_PublicKeyStrengthInBits shall no longer use SECKEY_BigIntegerBitLength but calculate len*8-padding (or len*8 until padding byte isn't lost)
- other functions might still use SECKEY_BigIntegerBitLength as it is expected to 

This would more accurately calculate server public key length as quoted in NSS release notes.

Comment 4

[Martin Thomson [:mt:]]

Do you have an actual (public) key that is showing this problem?  I'm having trouble parsing your descriptions.  All the "ASN.1" dressing (it's DER actually) should have been removed before SECKEY_BigIntegerBitLength is called.

Note: 1024 bits is pretty small.  Even if this is a bug that we need to fix, I recommend getting a bigger key.

Comment 5

[Christian Boitel]

Attachment: Keystore that works

Keystore generated with Oracle JDK 8u60 using the following command line
$JAVA_HOME/bin/keytool -genkeypair -keysize 1024 -keystore ./keystore2 -storepass changeit -dname "CN=localhost, OU=test, O=test, L=Unknown, ST=Unknown, C=Unknown"

Configure a Tomcat 8 instance to use this keystore. It presents a public key that works with NSS (public key starts with x5e).

xxx@yyy> echo | openssl s_client -connect localhost:8443 2>/dev/null | openssl x509 -text -noout
Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number: 70458006 (0x4331a96)
    Signature Algorithm: dsaWithSHA1
        Issuer: C=Unknown, ST=Unknown, L=Unknown, O=test, OU=test, CN=localhost
        Validity
            Not Before: Nov 30 08:16:30 2015 GMT
            Not After : Feb 28 08:16:30 2016 GMT
        Subject: C=Unknown, ST=Unknown, L=Unknown, O=test, OU=test, CN=localhost
        Subject Public Key Info:
            Public Key Algorithm: dsaEncryption
                pub:
                    5e:08:c8:63:4c:c5:10:04:cf:ae:4b:d7:2e:d7:ae:
                    53:8d:77:39:72:05:5f:e1:f5:fb:37:7e:75:43:66:
                    1a:2a:24:ee:88:87:75:b0:41:60:28:3f:a8:f1:7b:
                    d6:6b:a7:f7:bf:0d:b4:d9:e2:95:d6:22:72:3b:1b:
                    96:b8:f1:a5:d5:b3:b9:16:7a:06:64:88:e4:29:97:
                    a7:c0:4f:ae:5e:61:90:2a:9b:f8:bb:b8:a0:0a:45:
                    a4:04:41:c5:90:be:0e:ad:9f:c8:10:d4:4d:ca:7c:
                    ae:6d:55:e1:30:f8:d9:70:4b:62:1a:d5:4b:88:35:
                    d2:65:c7:08:8f:68:c7:03

- check public key (

Public key generated starts with 5e (check  echo | openssl s_client -connect localhost:8443 2>/dev/null | openssl x509 -text -noout

Comment 6

[Christian Boitel]

Attachment: Keystore that fails

Same as previous attachment but this keystore exhibit a public key with leading bits set to 0

xxxx@yyyy> echo | openssl s_client -connect localhost:8443 2>/dev/null | openssl x509 -text -noout
Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number: 1938574180 (0x738c4b64)
    Signature Algorithm: dsaWithSHA1
        Issuer: C=Unknown, ST=Unknown, L=Unknown, O=test, OU=test, CN=localhost
        Validity
            Not Before: Nov 30 08:20:25 2015 GMT
            Not After : Feb 28 08:20:25 2016 GMT
        Subject: C=Unknown, ST=Unknown, L=Unknown, O=test, OU=test, CN=localhost
        Subject Public Key Info:
            Public Key Algorithm: dsaEncryption
                pub:
                    2b:7d:f8:d5:b1:29:25:88:19:d7:35:d8:e6:44:83:
                    95:a8:f5:43:17:c6:c4:cb:58:45:07:79:6e:f8:6a:
                    3f:64:75:30:bb:4b:73:67:06:81:1f:80:ae:55:0a:
                    3a:6b:a9:9c:fc:06:d0:60:ba:59:6e:e0:12:ce:6c:
                    2e:3c:8d:b8:85:ac:6b:00:f8:9c:9d:a3:19:6b:81:
                    56:13:e4:a8:a1:0b:d0:e2:e9:21:78:f1:5b:22:65:
                    bc:3f:ef:ed:ba:e2:84:02:96:db:ac:7c:54:b1:b1:
                    e8:5b:dd:ed:ad:6a:e4:d5:97:d3:6d:f6:75:fe:5b:
                    f3:38:ec:e5:61:31:52:b8


Using this keystore and trying to connect with curl (which uses NSS) will result in an insufficient_security TLS alert from client (see ssltap infos below)

xxxx@yyy> ssltap -s localhost:8443
Looking up "localhost"...
Proxy socket ready and listening
Connected to localhost:8443
--> [
(133 bytes of 128)
SSLRecord { [Mon Nov 30 09:54:01 2015]
   type    = 22 (handshake)
   version = { 3,1 }
   length  = 128 (0x80)
   handshake {
      type = 1 (client_hello)
      length = 124 (0x00007c)
         ClientHelloV3 {
            client_version = {3, 3}
            random = {...}
            session ID = {
                length = 0
                contents = {...}
            }
            cipher_suites[17] = {
                (0x009e) TLS/DHE-RSA/AES128-GCM/SHA256
                (0x009c) TLS/RSA/AES128-GCM/SHA256
                (0x0039) TLS/DHE-RSA/AES256-CBC/SHA
                (0x006b) TLS/DHE-RSA/AES256-CBC/SHA256
                (0x0038) TLS/DHE-DSS/AES256-CBC/SHA
                (0x0035) TLS/RSA/AES256-CBC/SHA
                (0x003d) TLS/RSA/AES256-CBC/SHA256
                (0x0033) TLS/DHE-RSA/AES128-CBC/SHA
                (0x0067) TLS/DHE-RSA/AES128-CBC/SHA256
                (0x0032) TLS/DHE-DSS/AES128-CBC/SHA
                (0x002f) TLS/RSA/AES128-CBC/SHA
                (0x003c) TLS/RSA/AES128-CBC/SHA256
                (0x0005) SSL3/RSA/RC4-128/SHA
                (0x0004) SSL3/RSA/RC4-128/MD5
                (0x0016) SSL3/DHE-RSA/3DES192EDE-CBC/SHA
                (0x0013) SSL3/DHE-DSS/DES192EDE3CBC/SHA
                (0x000a) SSL3/RSA/3DES192EDE-CBC/SHA
            }
            compression[1] = {
                (00) NULL
            }
            extensions[49] = {
              extension type server_name, length [14] = {
   0: 00 0c 00 00  09 6c 6f 63  61 6c 68 6f  73 74        | .....localhost
              }
              extension type renegotiation_info, length [1] = {
   0: 00                                                  | .
              }
              extension type signature_algorithms, length [22] = {
   0: 00 14 04 01  05 01 06 01  02 01 04 03  05 03 06 03  | ................
  10: 02 03 04 02  02 02                                  | ......
              }
            }
         }
   }
}
]
<-- [
(1361 bytes of 1356)
SSLRecord { [Mon Nov 30 09:54:01 2015]
   type    = 22 (handshake)
   version = { 3,3 }
   length  = 1356 (0x54c)
   handshake {
      type = 2 (server_hello)
      length = 77 (0x00004d)
         ServerHello {
            server_version = {3, 3}
            random = {...}
            session ID = {
                length = 32
                contents = {...}
            }
            cipher_suite = (0x0032) TLS/DHE-DSS/AES128-CBC/SHA
            compression method = (00) NULL
            extensions[5] = {
              extension type renegotiation_info, length [1] = {
   0: 00                                                  | .
              }
            }
         }
      type = 11 (certificate)
      length = 823 (0x000337)
         CertificateChain {
            chainlength = 820 (0x0334)
            Certificate {
               size = 817 (0x0331)
               data = { saved in file 'cert.001' }
            }
         }
      type = 12 (server_key_exchange)
      length = 440 (0x0001b8)
      type = 14 (server_hello_done)
      length = 0 (0x000000)
   }
}
]
--> [
(7 bytes of 2)
SSLRecord { [Mon Nov 30 09:54:01 2015]
   type    = 21 (alert)
   version = { 3,3 }
   length  = 2 (0x2)
   fatal: insufficient_security
}
]
Read EOF on Client socket. [Mon Nov 30 09:54:01 2015]
Read EOF on Server socket. [Mon Nov 30 09:54:01 2015]
Connection 1 Complete [Mon Nov 30 09:54:01 2015]


xxxx@yyy> curl -v -1 --insecure https://localhost:1924
* About to connect() to localhost port 1924 (#0)
*   Trying 127.0.0.1... connected
* Connected to localhost (127.0.0.1) port 1924 (#0)
* Initializing NSS with certpath: sql:/etc/pki/nssdb
* warning: ignoring value of ssl.verifyhost
* skipping SSL peer certificate verification
* NSS error -12156
* Closing connection #0
* SSL connect error
curl: (35) SSL connect error

Comment 7

[Christian Boitel]

Hi all,

Provided two JDK keystore exhibiting the problem as well as ssltap debug information.

Martin,

You are right: DER encoding have been removed before SECKEY_BigIntegerBitLength is called. But one information has been lost during this DER decoding step: the number of bits in the last octet that have been used for padding purpose. As a consequence, SECKEY_BigIntegerBitLength has no way of correctly calculating the key length.

Comment 8

[Martin Thomson [:mt:]]

Thanks to the attachments, I've managed to reproduce this.  The problem here is that this isn't recognizably a 1024-bit key.  As shown, it's detected as being only 1022 bits.  This is intentional, though it may indeed be incorrect (a public key of just 75 is in theory possible).

Anyone generating an RSA certificate should generate a certificate that has the high bit set.  Yes, this reduces the entropy of the final key by one bit, but detecting that you genuinely selected from a 1024-bit group is difficult otherwise.  I've never seen an RSA key that doesn't do this.

However, DSA is different.  Because we always know the prime, we should probably just use that when calculating key strength.  From I can tell, that always has the top bit set.  The same applies to DH keys.

Comment 9

[Martin Thomson [:mt:]]

Attachment: bug1211403.patch

I'll mark this for review once I've checked that it passes tests.  It looks like this is a long-latent bug, just that the recent changes made the error visible with 1:4 probability, rather than 1:256.  (Assuming people were actually using both DSA and 1024-bit keys, both of which aren't exactly common.)

Comment 10

[Martin Thomson [:mt:]]

Comment on attachment 8695104 [details] [diff] [review]
bug1211403.patch

This seems to pass the basic tests we have.  I'm not sure that we have all the different key sizes, particularly those around the important bit lengths, fully picketed, but that doesn't bother me too much.

Comment 11

[Wan-Teh Chang]

Comment on attachment 8695104 [details] [diff] [review]
bug1211403.patch

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

r=wtc.

Comment 12

[Martin Thomson [:mt:]]

Comment on attachment 8695104 [details] [diff] [review]
bug1211403.patch

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

https://hg.mozilla.org/projects/nss/rev/075e80f679d1

Comment 13

[Wan-Teh Chang]

Martin: you set the target milestone to 3.22, but the version
number in lib/nss/nss.h is 3.21.1.

Is the version in lib/nss/nss.h wrong?

Comment 14

[Martin Thomson [:mt:]]

Well, probably, but Kai already fixed it: https://hg.mozilla.org/projects/nss/rev/f585b5e9c2a6