botan RSA key with negative DER encoding modulus rejected

Botan cannot parse this certificate (openssl dump):

Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number:
            06:37:6c:00:aa:00:64:8a:11:cf:b8:d4:aa:5c:35:f4
        Signature Algorithm: md5WithRSAEncryption
        Issuer: CN = Root Agency
        Validity
            Not Before: May 28 22:02:59 1996 GMT
            Not After : Dec 31 23:59:59 2039 GMT
        Subject: CN = Root Agency
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
                Public-Key: (512 bit)
                Modulus:
                    00:81:55:22:b9:8a:a4:6f:ed:d6:e7:d9:66:0f:55:
                    bc:d7:cd:d5:bc:4e:40:02:21:a2:b1:f7:87:30:85:
                    5e:d2:f2:44:b9:dc:9b:75:b6:fb:46:5f:42:b6:9d:
                    23:36:0b:de:54:0f:cd:bd:1f:99:2a:10:58:11:cb:
                    40:cb:b5:a7:41
                Exponent: 65537 (0x10001)
        X509v3 extensions:
            commonName: 
                .GFor Testing Purposes Only Sample Software Publishing Credentials Agency
            2.5.29.1: 
                0>.....-...O..a!..dc..0.1.0...U....Root Agency...7l...d......\5.
    Signature Algorithm: md5WithRSAEncryption
    Signature Value:
        2d:2e:3e:7b:89:42:89:3f:a8:21:17:fa:f0:f5:c3:95:db:62:
        69:5b:c9:dc:c1:b3:fa:f0:c4:6f:6f:64:9a:bd:e7:1b:25:68:
        72:83:67:bd:56:b0:8d:01:bd:2a:f7:cc:4b:bd:87:a5:ba:87:
        20:4c:42:11:41:ad:10:17:3b:8c

here is the blob:

This throws:

void RSA_PublicKey::init(BigInt&& n, BigInt&& e) {
   if(n.is_negative() || n.is_even() || n.bits() < 5 /* n >= 3*5 */ || e.is_negative() || e.is_even()) {
      throw Decoding_Error("Invalid RSA public key parameters");
   }
   m_public = std::make_shared<RSA_Public_Data>(std::move(n), std::move(e));
}

Aug 26 '24 15:08 learn-more

It's unrelated to MD5, the public key is encoded with a negative modulus

  d= 3, l=  74:    BIT STRING
  d= 4, l=  71:     SEQUENCE
  d= 5, l=  64:      INTEGER                                -0x7EAADD46755B901229182699F0AA4328322A43B1BFFDDE5D4E0878CF7AA12D0DBB4623648A4904B9A0BD4962DCC9F421ABF03242E066D5EFA7EE34BF344A58BF
  d= 5, l=   3:      INTEGER                                0x010001

OpenSSL accepts it, and then uses the 2-s complement encoding :exploding_head:

Aug 26 '24 17:08 randombit

I guess the likely issue is is that the modulus is "accidentally" negative; the creating software was buggy and failed to account for the fact that the high bit being set in DER implies the integer is negative (thus to properly encode a positive integer that is a multiple of 8 bits, you must prepend a zero byte), OpenSSL then accounts for this bug in the creating software by using the 2-s complement encoding, which is actually the absolute value since the software didn't intentionally encode a negative value.

Aug 26 '24 17:08 randombit

I guess the likely issue is is that the modulus is "accidentally" negative; the creating software was buggy and failed to account for the fact that the high bit being set in DER implies the integer is negative (thus to properly encode a positive integer that is a multiple of 8 bits, you must prepend a zero byte), OpenSSL then accounts for this bug in the creating software by using the 2-s complement encoding, which is actually the absolute value since the software didn't intentionally encode a negative value.

Thanks for the quick analysis!

What would be the way forward here? Updating botan, or should I apply some workaround on this data before passing it to Botan?

Aug 26 '24 17:08 learn-more

There is no version that would accept this cert.

You would have to edit the key embedded within the cert to include the correct padding byte used to indicate a positive number. This would invalidate the self-signature, but fortunately (?) 512 bits can be factored in a day or two with CADO-NFS.

A patch to handle this is pretty simple, but I'm highly doubtful we'd want to do so. Can you give some context on what this cert is / why being able to use it matters? This seems like someone created an invalid test cert 20+ years ago, I'm not sure I'd want to permanently include a workaround that involves accepting manifestly invalid inputs to accommodate it.

Aug 26 '24 19:08 randombit

This is a certificate from Windows: certmgr.msc --> Intermediate Certification Authorities --> Certificates

Windows tells us: This certificate has an invalid digital signature. And for Public key parameters:

The only reference I found for this certificate (other than my own machines) was this: https://bugzilla.mozilla.org/show_bug.cgi?id=432802#c11

Aug 27 '24 11:08 learn-more

BTW for the record we can/do parse the certificate. The only thing that won't work is that you can't extract the public key as a Public_Key. The output of botan cert_info may have misled you here, because currently it prints the public key as the very last item, which may have made it look like parsing failed where it prints the exception message.

Aug 28 '24 00:08 randombit

BTW for the record we can/do parse the certificate. The only thing that won't work is that you can't extract the public key as a Public_Key. The output of botan cert_info may have misled you here, because currently it prints the public key as the very last item, which may have made it look like parsing failed where it prints the exception message.

I encountered this exception while using botan as static library in a tool I am writing. For this, I use botan to parse all fields of the certificate, and populate a custom type representing a certificate, so that it can be displayed to the user without depending on implementation-details like where the certificate is coming from.

Aug 29 '24 06:08 learn-more

botan botan copied to clipboard

RSA key with negative DER encoding modulus rejected

botan
botan copied to clipboard