BigInt::BigInt(const uint8_t buf[], size_t length, size_t max_bits)

[Takarth]

This function is not working as intended.

It first limits the load length by cutting the excess most significant bytes. It then loads the array by binary decoding it. These 2 steps are fine

It then clears the least significant bits by shifting the BigInt 1-7 bits to the right. What it should actually be doing is clearing the most significant bits.

A simple solution would be something along the lines of: while(bits() > max_bits) clear_bit(bits() - 1); or with an AND-Operation.

I detected this bug when signing or verifying ECDSA/EMSA1(SHA-256) with a curve order smaller than 256. I can't verify signatures generated by botan in other crypto libs I can't verify signatures generated by other crypto libs in botan

[randombit]

That's most surprising as a few years ago we fixed a bug where in one particular corner case (#2415) we were incompatible here, which was fixed.

Can you be specific about which version of Botan you are using as well as which other libraries you are checking against (and their versions).

Additionally can you give examples of signatures generated by botan and rejected by other impls and also the inverse. Thanks

[Takarth]

I'm using the most current version 2.19.3 I use botan through softhsm2 as well as directly thorugh API calls. Verification is done using sun provider with java.

This test vector fails with botan2, while it is a valid ecdsa signature:

Botan::EC_Group grp(Botan::OID("1.2.840.10045.3.1.4"));

const auto publicKey(Botan::hex_decode("044991127577296a71a253aa378cff3fd81eed29210522fc03e45e256b9d0e6f7f1dedfaf8ebaf438143d5721cd47cde7ddddc6c72f880d35b7a7cad1a")); Botan::ECDSA_PublicKey key(grp, grp.OS2ECP(publicKey));

const auto msg(Botan::hex_decode("6d6573736167652d31313938623863342d386566352d343535302d623230382d")); const auto sig(Botan::hex_decode("662ebdcc2e8925c91fd15451ab83728063a048c203fc242bdcdc33264f060c833f36dc5799adc73b61fc007ee569d555ace73d31de4d8d4d8ec99946"));

Botan::PK_Verifier verifier(key, "EMSA1(SHA-256)"); verifier.verify_message(msg.data(), msg.size(), sig.data(), sig.size());

[randombit]

How was this signature generated? What implementations(s) accept it?

[Takarth]

Was tested with SUN JCE Java implementation & openSSL 1.0.2u cant adapt java code that easily but is also reproduceable with openssl (executed under Debian 11)

create key pair

openssl ecparam -name prime239v1 -genkey -noout -out private-key.pem openssl ec -in private-key.pem -pubout -out public-key.pem openssl ec -pubin -inform PEM -in public-key.pem -outform DER -out public-key.der

Extract public key (Extract public key in uncompressed format)

dumpasn1 public-key.der

Create test file

echo 1122334455 > test.txt

Sign

openssl dgst -sha256 -sign private-key.pem test.txt > signature.bin

Extract signature (concat R + S)

openssl asn1parse -in prime256v1.sig -inform der

Verify

openssl dgst -sha256 -verify public-key.pem -signature signature.bin test.txt

---

Copy output of extract public key & extract signature in previous code. Verification fails. Here expanded botan test code with correct msg.

Botan::EC_Group grp(Botan::OID("1.2.840.10045.3.1.4")); const auto publicKey(Botan::hex_decode("")); // Input extracted uncompressed public key (04.....) Botan::ECDSA_PublicKey key(grp, grp.OS2ECP(publicKey));

const auto msg(Botan::hex_decode("313132323333343435350A")); const auto sig(Botan::hex_decode("")); // Input extracted signature (R+S)

Botan::PK_Verifier verifier(key, "EMSA1(SHA-256)"); std::cout << (verifier.verify_message(msg.data(), msg.size(), sig.data(), sig.size()) ? "SUCCESS" : "FAIL") << std::endl;

This fails with current botan 2.19.3

---

Current implementation clears LSB instead of MSB which is incorrect.

if(8 length > max_bits) this >>= (8 - (max_bits % 8));

Replacing above snipet in the max bits function of BigInt with

while(bits() > max_bits) clear_bit(bits() - 1);

and it passes

[Takarth]

Thank you for solving the issue.

My solution was just wrong. I found the issue when I saw that the botan vectors failed with my solution, I think you came to the same conclusion:

EMSA1 shifting was applied multiple times when prime bit size is not a multiple of 8 and EMSA1 padding is used.

[randombit]

Thanks for reporting this and digging into the issue. This is fixed now in master, and so will be addressed in 3.0 which is expected for early April. I'm not sure how viable it is to backport the fix into 2.x. If nothing else I will not have time to look into a backport until after 3.0 ships.