Negative RSA moduli from X509 parsing about ocaml-x509

[hannesm]

strange (I can reproduce this with ocaml-x509). so the ASN.1 encoding of the modulus of the public exponent is (in hex):

02 81 80 ac b2 45 c7 7e 95 57 1c a6 4a 03 67 7a
93 49 7c d4 36 5a 1e 91 52 87 b7 9f a6 1a 92 1b
4f 58 25 c7 46 f1 b0 34 1a fa 94 ea ad e5 b6 64
72 ca 8c d8 59 14 60 c0 1d 21 5d c3 4e f3 17 01
53 94 7f da b4 62 cd bb a0 80 e7 cb fd 21 d8 3f
2f 55 e8 63 21 27 18 ac ca e6 c4 f5 0b b9 5b a8
bc 55 b8 ab e5 4c bb ee 6f 32 9e d4 db d8 f4 cc
e1 df 9f fc 5e eb ce d7 ec 38 f2 68 c7 75 f5 e0
9c 1e 21

According to layman ASN.1 section 5.7, 02 indicates an Integer, 81 80 is its octet length in long form. The most significant bit is the sign (in this case ac, thus negative). This code path in ASN.1 is hit.

Did you create the certificate? If so, with which tool?

(I'm not the expert here, @pqwy certainly knows more)

NOTE: updated to clear up my length confusion

[hannesm]

related to this http://stackoverflow.com/questions/12860226/oddity-when-encoding-large-integers-using-asn-1

[NathanReb]

Hmm correct (even though the integer starts at AC and not 80 which is still part of the data size).
I got a positive integer cause I used zarith Z.of_string on the hex string "AC B2... 1E 21" prefixed with "0x".
Still this positive integer looks much more like a RSA modulus than the negative one, which can be divided by 3, for instance.

I did not generated the certificate, just got it from the zmap data set

[braibant]

As Nathan hint at, https://en.wikipedia.org/wiki/X.690#Length_Octets tend to indicate that 81 80 is the length of the key in long form. This bug report https://bugzilla.redhat.com/show_bug.cgi?id=1036385 shows that some tool generate such ill formed certificates.

[hannesm]

sorry for my length confusion, I updated my comment to reflect reality.

what to do: there are tools which produce wrong certificates. these certificates are in the wild. I believe we've to provide a non-negative integer decoder in asn1-combinators and use this for public keys.

[NathanReb]

That would be great, ty !

That's what openssl seems to do.
When I run openssl x509 -text I get the following result for the subject key :

Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
                Public-Key: (1024 bit)
                Modulus:
                    00:ac:b2:45:c7:7e:95:57:1c:a6:4a:03:67:7a:93:
                    49:7c:d4:36:5a:1e:91:52:87:b7:9f:a6:1a:92:1b:
                    4f:58:25:c7:46:f1:b0:34:1a:fa:94:ea:ad:e5:b6:
                    64:72:ca:8c:d8:59:14:60:c0:1d:21:5d:c3:4e:f3:
                    17:01:53:94:7f:da:b4:62:cd:bb:a0:80:e7:cb:fd:
                    21:d8:3f:2f:55:e8:63:21:27:18:ac:ca:e6:c4:f5:
                    0b:b9:5b:a8:bc:55:b8:ab:e5:4c:bb:ee:6f:32:9e:
                    d4:db:d8:f4:cc:e1:df:9f:fc:5e:eb:ce:d7:ec:38:
                    f2:68:c7:75:f5:e0:9c:1e:21
                Exponent: 65537 (0x10001)

It adds a leading 0 byte

[pqwy]

The central question in my mind is how widespread is this.

what to do: there are tools which produce wrong certificates. these certificates are in the wild.

In general, no. I am very reluctant to add warts to support other people's old bugs. These certificates are badly encoded, making them invalid. They should be replaced, not used, and definitely not worked around in newly written software.

Well, unless this is really common practice. We do have a precedent of bending the standard here. But that is not a work-around, in that case everyone other than the standard seems to agree on the encoding.

As a side-note, accepting this would violate the core DER property of uniqueness of representation. Thus we immediately lose the invariant that you can encode a certificate and arrive at the same byte sequence your parsed it from. This is not something to lose lightly. The fact that OpenSSL is always willing to add warts is one of the reasons OpenSSL is what it is, plus, they have a very relaxed interpretation of certificate usage flags and are generally eager to accept any byte stream that someone claims to contain a certificate.

To resolve this dilemma I downloaded Zenmap's sample of HTTPS certificates from two days ago. Of those, we parse 508723 and reject 4382 (which is most probably a bug I will now look into). I was wondering how many certificates had negative moduli under the current decoding?

Three.

Namely:

Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number: 115317803952574443 (0x199b0ee84df0feb)
    Signature Algorithm: sha1WithRSAEncryption
        Issuer: C=CZ, ST=CZ, L=Prague, O=2N Telecommunications, OU=Helios IP, CN=2N Telecommunications
        Validity
            Not Before: Jan  1 00:00:00 2010 GMT
            Not After : Dec 27 00:00:00 2029 GMT
        Subject: C=CZ, ST=CZ, L=Prague, O=2N Telecommunications, OU=Helios IP, CN=2N Telecommunications
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
                Public-Key: (1024 bit)
                Modulus:
                    00:cb:f8:90:f9:e8:16:6f:27:c9:a5:10:06:27:09:
                    89:31:15:34:90:5d:cb:3e:66:3e:92:96:5b:4f:d0:
                    df:da:b4:b1:4f:6a:a4:09:10:23:1e:91:f8:81:f7:
                    94:7e:2b:9b:87:a0:39:96:c3:26:12:80:d4:57:04:
                    e2:7f:38:9b:8d:86:8c:ad:bb:b0:67:e9:a7:cf:d8:
                    89:14:14:b8:97:cd:eb:86:7c:07:4f:c2:03:37:e7:
                    b4:30:32:ba:12:24:28:3c:0e:fa:be:a5:9f:4c:74:
                    89:44:76:f2:e1:52:a0:02:b0:56:9a:f1:1e:07:08:
                    17:ec:35:46:83:0e:03:27:8b
                Exponent: 65537 (0x10001)
    Signature Algorithm: sha1WithRSAEncryption
         0e:fc:59:f6:88:e3:b8:54:48:84:6b:7f:3d:4d:db:3e:7d:ed:
         58:78:1a:02:b2:df:ec:63:19:6f:8a:fe:af:97:ba:6b:8f:e1:
         5c:8e:04:45:59:9c:de:f1:c3:21:3f:44:d2:0e:a1:1e:b9:59:
         22:0f:7d:64:7f:26:ae:65:67:dd:5a:1e:bd:a5:b0:3d:56:07:
         40:e7:9b:9c:8e:34:29:e1:90:35:c0:1a:f6:2f:d9:b5:7b:a9:
         d9:46:18:5a:eb:a0:60:1e:fb:ad:84:2c:cc:3e:2c:fd:ce:bc:
         cc:31:30:cb:37:28:b5:4d:42:ba:4a:91:9e:a1:b2:5d:4a:29:
         14:01
-----BEGIN CERTIFICATE-----
MIICfDCCAeWgAwIBAgIIAZmw7oTfD+swDQYJKoZIhvcNAQEFBQAwfzELMAkGA1UE
BhMCQ1oxCzAJBgNVBAgTAkNaMQ8wDQYDVQQHEwZQcmFndWUxHjAcBgNVBAoTFTJO
IFRlbGVjb21tdW5pY2F0aW9uczESMBAGA1UECxMJSGVsaW9zIElQMR4wHAYDVQQD
ExUyTiBUZWxlY29tbXVuaWNhdGlvbnMwIhgPMjAxMDAxMDEwMDAwMDBaGA8yMDI5
MTIyNzAwMDAwMFowfzELMAkGA1UEBhMCQ1oxCzAJBgNVBAgTAkNaMQ8wDQYDVQQH
EwZQcmFndWUxHjAcBgNVBAoTFTJOIFRlbGVjb21tdW5pY2F0aW9uczESMBAGA1UE
CxMJSGVsaW9zIElQMR4wHAYDVQQDExUyTiBUZWxlY29tbXVuaWNhdGlvbnMwgZ4w
DQYJKoZIhvcNAQEBBQADgYwAMIGIAoGAy/iQ+egWbyfJpRAGJwmJMRU0kF3LPmY+
kpZbT9Df2rSxT2qkCRAjHpH4gfeUfiubh6A5lsMmEoDUVwTifzibjYaMrbuwZ+mn
z9iJFBS4l83rhnwHT8IDN+e0MDK6EiQoPA76vqWfTHSJRHby4VKgArBWmvEeBwgX
7DVGgw4DJ4sCAwEAATANBgkqhkiG9w0BAQUFAAOBgQAO/Fn2iOO4VEiEa389Tds+
fe1YeBoCst/sYxlviv6vl7prj+FcjgRFWZze8cMhP0TSDqEeuVkiD31kfyauZWfd
Wh69pbA9VgdA55ucjjQp4ZA1wBr2L9m1e6nZRhha66BgHvuthCzMPiz9zrzMMTDL
Nyi1TUK6SpGeobJdSikUAQ==
-----END CERTIFICATE-----

Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number: 79868500614503902 (0x11bbffa67deddde)
    Signature Algorithm: sha1WithRSAEncryption
        Issuer: C=CZ, ST=CZ, L=Prague, O=2N Telecommunications, OU=Helios IP, CN=2N Telecommunications
        Validity
            Not Before: Jan  1 00:00:00 2010 GMT
            Not After : Dec 27 00:00:00 2029 GMT
        Subject: C=CZ, ST=CZ, L=Prague, O=2N Telecommunications, OU=Helios IP, CN=2N Telecommunications
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
                Public-Key: (1024 bit)
                Modulus:
                    00:dc:74:26:f1:bf:ef:25:30:81:b7:21:ed:61:87:
                    f3:89:df:7d:2d:f3:8c:d2:4e:7d:f3:ac:f3:5d:18:
                    b0:0e:1e:18:e9:51:4e:00:ce:50:33:af:24:90:f5:
                    7b:a4:08:87:00:cf:12:fd:04:ff:00:71:31:3f:3f:
                    4a:e8:5a:1f:52:32:8f:85:b2:dd:dc:fc:f2:eb:37:
                    81:aa:26:2d:e5:b1:09:93:0f:bc:fb:83:05:d8:49:
                    df:8b:47:18:01:df:42:b6:21:ec:c5:4b:17:70:a5:
                    84:57:a3:83:14:82:6f:f3:df:76:20:77:e7:8b:ac:
                    7e:21:60:a6:bb:93:24:40:85
                Exponent: 65537 (0x10001)
    Signature Algorithm: sha1WithRSAEncryption
         90:9a:67:47:83:8f:3e:47:ea:bc:1a:88:00:d3:5d:52:19:18:
         04:a0:69:a2:a4:f8:c4:d9:74:e8:02:ba:94:1e:a9:63:e9:70:
         76:e7:ae:f1:c6:ed:e2:d3:74:ad:8c:64:3b:2d:56:73:0d:2b:
         dd:1b:ff:a6:b3:b9:f9:3e:74:cb:e4:b8:ae:94:36:5a:1b:b5:
         7b:97:d3:3e:52:29:db:d3:c8:0f:fd:eb:d7:da:34:3f:ca:d9:
         ff:36:48:16:e8:4b:8b:e6:ad:60:2e:ef:81:f6:0d:8a:90:27:
         bc:77:d1:69:8b:ce:29:59:c9:12:99:6a:bb:98:93:3c:a4:a4:
         73:19
-----BEGIN CERTIFICATE-----
MIICfDCCAeWgAwIBAgIIARu/+mfe3d4wDQYJKoZIhvcNAQEFBQAwfzELMAkGA1UE
BhMCQ1oxCzAJBgNVBAgTAkNaMQ8wDQYDVQQHEwZQcmFndWUxHjAcBgNVBAoTFTJO
IFRlbGVjb21tdW5pY2F0aW9uczESMBAGA1UECxMJSGVsaW9zIElQMR4wHAYDVQQD
ExUyTiBUZWxlY29tbXVuaWNhdGlvbnMwIhgPMjAxMDAxMDEwMDAwMDBaGA8yMDI5
MTIyNzAwMDAwMFowfzELMAkGA1UEBhMCQ1oxCzAJBgNVBAgTAkNaMQ8wDQYDVQQH
EwZQcmFndWUxHjAcBgNVBAoTFTJOIFRlbGVjb21tdW5pY2F0aW9uczESMBAGA1UE
CxMJSGVsaW9zIElQMR4wHAYDVQQDExUyTiBUZWxlY29tbXVuaWNhdGlvbnMwgZ4w
DQYJKoZIhvcNAQEBBQADgYwAMIGIAoGA3HQm8b/vJTCBtyHtYYfzid99LfOM0k59
86zzXRiwDh4Y6VFOAM5QM68kkPV7pAiHAM8S/QT/AHExPz9K6FofUjKPhbLd3Pzy
6zeBqiYt5bEJkw+8+4MF2Enfi0cYAd9CtiHsxUsXcKWEV6ODFIJv8992IHfni6x+
IWCmu5MkQIUCAwEAATANBgkqhkiG9w0BAQUFAAOBgQCQmmdHg48+R+q8GogA011S
GRgEoGmipPjE2XToArqUHqlj6XB2567xxu3i03StjGQ7LVZzDSvdG/+ms7n5PnTL
5LiulDZaG7V7l9M+Uinb08gP/evX2jQ/ytn/NkgW6EuL5q1gLu+B9g2KkCe8d9Fp
i84pWckSmWq7mJM8pKRzGQ==
-----END CERTIFICATE-----

Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number:
            42:e7:b2:0c:fe:e9:f9:bc:41:c6:3f:93:85:42:5f:1c
    Signature Algorithm: sha1WithRSAEncryption
        Issuer: CN=re-net.kosei-kai.or.jp
        Validity
            Not Before: Feb  4 06:11:26 2015 GMT
            Not After : Feb  4 00:00:00 2016 GMT
        Subject: CN=RKKDESKNETS-01.rkk.local
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
                Public-Key: (1024 bit)
                Modulus:
                    00:d8:40:8c:71:60:b0:0e:cd:f5:b5:51:d6:11:97:
                    21:cc:17:d7:26:b7:a8:c0:47:b2:fb:20:00:a8:40:
                    a2:df:07:32:c8:a3:13:fa:53:4e:8c:64:41:e5:e7:
                    8d:7b:4d:cd:10:26:b2:5f:40:ec:2d:a4:6e:fe:55:
                    24:da:47:d4:ae:7f:dc:f6:74:c0:de:3a:c2:12:e9:
                    43:18:7e:18:92:44:25:aa:d2:85:7e:42:b4:5c:a8:
                    3d:f0:32:dd:ed:86:1d:1f:d1:64:0b:23:ab:38:84:
                    17:e0:e3:ba:51:a1:ee:70:76:12:b6:8d:b1:d5:7a:
                    bf:32:da:81:4a:35:2b:18:85
                Exponent: 65537 (0x10001)
        X509v3 extensions:
            X509v3 Key Usage:
                Key Encipherment, Data Encipherment
            X509v3 Extended Key Usage:
                TLS Web Server Authentication
    Signature Algorithm: sha1WithRSAEncryption
         c3:8d:97:3e:e2:fd:be:92:fb:43:17:6a:af:2a:34:00:d8:a3:
         39:2b:2b:97:43:ea:0d:f9:35:cb:2a:82:30:ec:d0:27:e7:65:
         8b:67:31:c0:06:20:fc:88:5d:e4:85:f0:4e:97:c3:8d:d9:4c:
         13:dd:94:a4:42:5f:e2:4f:a0:59:35:0d:ea:27:b1:46:d2:05:
         ef:32:aa:b2:3b:f5:d6:a6:dc:c4:3b:f4:5b:61:4b:bc:ce:53:
         00:f2:52:57:fa:bb:c0:7d:c7:f5:7c:29:f7:a4:08:af:90:f3:
         e9:9a:e0:92:7f:64:49:71:94:75:65:73:82:d4:00:36:0a:d9:
         ae:8f:e5:0b:d6:26:8c:3d:5b:68:fb:8a:e3:dc:9a:79:9b:43:
         51:d2:7f:94:92:36:71:54:79:0b:1a:d5:f4:6e:ba:c6:20:e1:
         ad:88:a5:b5:08:59:4a:84:43:45:dc:11:12:e0:1c:85:f9:a3:
         cd:08:21:0e:eb:57:5d:73:d8:fc:70:f1:cb:84:0b:a1:42:b1:
         df:55:07:0d:75:55:8c:2c:d8:68:60:0e:ed:fa:6f:f1:62:2d:
         6b:c0:a3:e1:51:cb:55:6a:f0:b0:ba:d8:6a:8e:8a:a5:ce:1b:
         8c:2d:eb:c3:54:8f:0a:64:44:e6:51:80:64:99:66:40:77:8b:
         03:32:99:31
-----BEGIN CERTIFICATE-----
MIICbTCCAVWgAwIBAgIQQueyDP7p+bxBxj+ThUJfHDANBgkqhkiG9w0BAQUFADAh
MR8wHQYDVQQDExZyZS1uZXQua29zZWkta2FpLm9yLmpwMB4XDTE1MDIwNDA2MTEy
NloXDTE2MDIwNDAwMDAwMFowIzEhMB8GA1UEAxMYUktLREVTS05FVFMtMDEucmtr
LmxvY2FsMIGeMA0GCSqGSIb3DQEBAQUAA4GMADCBiAKBgNhAjHFgsA7N9bVR1hGX
IcwX1ya3qMBHsvsgAKhAot8HMsijE/pTToxkQeXnjXtNzRAmsl9A7C2kbv5VJNpH
1K5/3PZ0wN46whLpQxh+GJJEJarShX5CtFyoPfAy3e2GHR/RZAsjqziEF+DjulGh
7nB2EraNsdV6vzLagUo1KxiFAgMBAAGjJDAiMAsGA1UdDwQEAwIEMDATBgNVHSUE
DDAKBggrBgEFBQcDATANBgkqhkiG9w0BAQUFAAOCAQEAw42XPuL9vpL7Qxdqryo0
ANijOSsrl0PqDfk1yyqCMOzQJ+dli2cxwAYg/Ihd5IXwTpfDjdlME92UpEJf4k+g
WTUN6iexRtIF7zKqsjv11qbcxDv0W2FLvM5TAPJSV/q7wH3H9Xwp96QIr5Dz6Zrg
kn9kSXGUdWVzgtQANgrZro/lC9YmjD1baPuK49yaeZtDUdJ/lJI2cVR5CxrV9G66
xiDhrYiltQhZSoRDRdwREuAchfmjzQghDutXXXPY/HDxy4QLoUKx31UHDXVVjCzY
aGAO7fpv8WIta8Cj4VHLVWrwsLrYao6Kpc4bjC3rw1SPCmRE5lGAZJlmQHeLAzKZ
MQ==
-----END CERTIFICATE-----

IMHO this change is not justified.

@NathanReb

I did not generated the certificate, just got it from the zmap data set

Which file is it in? It's an old self-signed MatrixSSL Sample Server CA that expired in 2007, is probably no longer online, and not present in the Sonar HTTPS set.

EDIT:
9/766889 in the large IMAP set. DNs: 9fans.eu, kamalatta.ddnss.de, *.0xco.co, imap.buf.io, *.inri.net, 9.offblast.org, *.collyer.net, *.feline.systems, *.huygens.org.

[pqwy]

Speaking of newly written software:

gopherbot added workingasintended

[pqwy]

Some more results from digging around the Sonar set:

• 1644 certificates use RSASSA-PSS.
• 1344 have been hit by Langley's proposal that hash- and RSA-based algorithms must have an explicit NULL as parameter, as opposed to nothing.
• 811 use an unknown algorithm.
• 136 have Version 4.
• 24 are hit by an asn1 bug where a string encoded as constructed directly below a CHOICE is rejected. 22 of those seem to belong to the Government of Korea.
• 23 don't wrap an explicit [0] tag around the value field of AnotherName alternative of GeneralName. Those contain cryptic strings Qnx-NPM3-0000-1790-A0CD and Win-7B09-82EE-FFBB-7359.
• 6 use PrintableString for the same field.
• The rest have miscellaneous errors.

Unknown algorithms are:

• 1.3.14.3.2.29 sha-1WithRSAEncryption (677)
• 111 1.2.840.10040.4.3 - dsa-with-sha1 (111)
• 11 1.2.643.2.2.3 - GostR3411-94-with-GostR3410-2001 (11)
• 10 1.2.840.10045.4.1 - ecdsa-with-SHA1 (10)
• 1 1.3.14.3.2.15 - shaWithRSASignature (1)
• 1 1.2.840.113549.0.1.5 (1)

That last one, Baltimore CyberTrust Root, uses a signature algorithm so powerful that it must be kept secret.

-- Just wanted to share.

[hannesm]

thanks @pqwy, this is a great breakdown. and I agree that the number of certificates with negative moduli is so small that we shouldn't implement workarounds for them.
otoh, we should add decoding support for OID 1.3.14.3.2.29 in our registry.

[NathanReb]

I took my data set from https://scans.io/series/443-https-tls-full_ipv4 (the 2015-04-02 one).
The certificate is indeed not valid anymore but still seems to be available from several IP adress (more than 45k adress actually).

[hannesm]

closing since @pqwy and myself decided that we don't want to implement ugly hacks for broken software (which affects <2% of people)