ECDSA producing unverifiable or incorrect signatures for some curves

[guidovranken]

#include <botan/ecdsa.h>
#include <botan/pubkey.h>
#include <botan/system_rng.h>
#include <botan/hash.h>
#include <botan/ber_dec.h>

static void sign_verify(const std::string& curve) {
    ::Botan::System_RNG rng;
    const std::vector<uint8_t> msg{0xFF};
    std::unique_ptr<::Botan::PK_Signer> signer;
    ::Botan::EC_Group group(curve);
    const ::Botan::BigInt priv_bn("1");
    const auto priv = std::make_unique<::Botan::ECDSA_PrivateKey>(::Botan::ECDSA_PrivateKey(rng, group, priv_bn));
    signer.reset(new ::Botan::PK_Signer(*priv, rng, "EMSA1(SHA-256)", ::Botan::DER_SEQUENCE));
    const auto signature = signer->sign_message(msg, rng);
    ::Botan::BER_Decoder decoder(signature);
    ::Botan::BER_Decoder ber_sig = decoder.start_sequence();

    size_t count = 0;

    ::Botan::BigInt R;
    ::Botan::BigInt S;
    while(ber_sig.more_items())
    {
        switch ( count ) {
            case    0:
                ber_sig.decode(R);
                break;
            case    1:
                ber_sig.decode(S);
                break;
            default:
                printf("Error: Too many parts in signature BER\n");
                abort();
        }

        ++count;
    }

    const auto pub_x = priv->public_point().get_affine_x();
    const auto pub_y = priv->public_point().get_affine_y();

    const ::Botan::PointGFp public_point = group.point(pub_x, pub_y);
    const auto pub = std::make_unique<::Botan::ECDSA_PublicKey>(::Botan::ECDSA_PublicKey(group, public_point));
    const auto sig = ::Botan::BigInt::encode_fixed_length_int_pair(R, S, group.get_order_bytes());
    auto hash = ::Botan::HashFunction::create("SHA-256");
    hash->update(msg);
    const auto _msg = hash->final();
    printf("%s; verified: %d\n", curve.c_str(), ::Botan::PK_Verifier(*pub, "Raw").verify_message(_msg, sig));

    return;
}
int main(void)
{
    const std::vector<std::string> curves{
        "brainpool160r1",
            "brainpool192r1",
            "brainpool224r1",
            "brainpool256r1",
            "brainpool320r1",
            "brainpool384r1",
            "brainpool512r1",
            "frp256v1",
            "gost_256A",
            "gost_512A",
            "secp160k1",
            "secp160r1",
            "secp160r2",
            "secp192k1",
            "secp192r1",
            "secp224k1",
            "secp224r1",
            "secp256k1",
            "secp256r1",
            "secp384r1",
            "secp521r1",
            "sm2p256v1",
            "x962_p192v2",
            "x962_p192v3",
            "x962_p239v1",
            "x962_p239v2",
            "x962_p239v3",
    };

    for (const auto& c : curves) {
        sign_verify(c);
    }
}

prints:

brainpool160r1; verified: 1
brainpool192r1; verified: 1
brainpool224r1; verified: 1
brainpool256r1; verified: 1
brainpool320r1; verified: 1
brainpool384r1; verified: 1
brainpool512r1; verified: 1
frp256v1; verified: 1
gost_256A; verified: 1
gost_512A; verified: 1
secp160k1; verified: 0
secp160r1; verified: 0
secp160r2; verified: 0
secp192k1; verified: 1
secp192r1; verified: 1
secp224k1; verified: 0
secp224r1; verified: 1
secp256k1; verified: 1
secp256r1; verified: 1
secp384r1; verified: 1
secp521r1; verified: 1
sm2p256v1; verified: 1
x962_p192v2; verified: 1
x962_p192v3; verified: 1
x962_p239v1; verified: 0
x962_p239v2; verified: 0
x962_p239v3; verified: 0

[randombit]

Initially I wonder if the private key being 1 was triggering some corner case but using random integers instead changes nothing.

If I change this

printf("%s; verified: %d\n", curve.c_str(), ::Botan::PK_Verifier(*pub, "Raw").verify_message(_msg, sig));

to this

printf("%s; verified: %d\n", curve.c_str(), ::Botan::PK_Verifier(*pub, "EMSA1(SHA-256)").verify_message(msg, sig));

everything works.

Also it is probably not a coincidence that the effected curves all have an order of unusual size (161 bits for the secp160r{1,2}, 225 for secp224k1, and 239 for the x962_p239v curves)

I suspect there is a discrepancy between EMSA1 and EMSA_Raw with how the hash ends up getting truncated.

[randombit]

I suspect there is a discrepancy between EMSA1 and EMSA_Raw with how the hash ends up getting truncated.

Confirmed. Using EMSA1(SHA-256) the message representative is

e = 0x02A0402B9AA8650342D98EECC73519850BAEF6F5

but using "Raw" plus pre-hash the mr is

e = 0x01502015CD543281A16CC776639A8CC285D77B7AA3

[guidovranken]

Also it is probably not a coincidence that the effected curves all have an order of unusual size (161 bits for the secp160r{1,2}, 225 for secp224k1, and 239 for the x962_p239v curves)

I've run into such issues with Cryptofuzz myself. With these curves the size of the prime is not equal to the size of the curve (order is one bit larger than prime). So maybe you are using the prime size instead of the order size during truncation.

[randombit]

This bug turned out to be because we had two distinct pieces of code that were trying to shift the hash to fit into the group order, and they occasionally would get in each others way. This is fixed now on master