Decoding_Error on Public_Key for RSA/EMSA3(MD5)

[learn-more]

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:

-----BEGIN CERTIFICATE-----
MIIByjCCAXSgAwIBAgIQBjdsAKoAZIoRz7jUqlw19DANBgkqhkiG9w0BAQQFADAW
MRQwEgYDVQQDEwtSb290IEFnZW5jeTAeFw05NjA1MjgyMjAyNTlaFw0zOTEyMzEy
MzU5NTlaMBYxFDASBgNVBAMTC1Jvb3QgQWdlbmN5MFswDQYJKoZIhvcNAQEBBQAD
SgAwRwJAgVUiuYqkb+3W59lmD1W8183VvE5AAiGisfeHMIVe0vJEudybdbb7Rl9C
tp0jNgveVA/NvR+ZKhBYEctAy7WnQQIDAQABo4GeMIGbMFAGA1UEAwRJE0dGb3Ig
VGVzdGluZyBQdXJwb3NlcyBPbmx5IFNhbXBsZSBTb2Z0d2FyZSBQdWJsaXNoaW5n
IENyZWRlbnRpYWxzIEFnZW5jeTBHBgNVHQEEQDA+gBAS5AktBh0dTwCNYSHcFmRj
oRgwFjEUMBIGA1UEAxMLUm9vdCBBZ2VuY3mCEAY3bACqAGSKEc+41KpcNfQwDQYJ
KoZIhvcNAQEEBQADQQAtLj57iUKJP6ghF/rw9cOV22JpW8ncwbP68MRvb2Savecb
JWhyg2e9VrCNAb0q98xLvYeluocgTEIRQa0QFzuM
-----END CERTIFICATE-----

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));
}

[randombit]

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 🤯

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

[learn-more]

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?

[randombit]

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.

[learn-more]

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

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

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

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.