Failed in verify test cases of wycheproof

[LanfordCai]

For this case wycheproof ecdsa sha256 test case 218, the expected result is valid, however, it returns error.

public_key is 04b838ff44e5bc177bf21189d0766082fc9d843226887fc9760371100b7ee20a6ff0c9d75bfba7b31a6bca1974496eeb56de357071955d83c4b1badaa0b21832e9

Take test case 3 and test case 218 as examples:

the case 3 is

        {
          "tcId" : 3,
          "comment" : "valid",
          "msg" : "313233343030",
          "sig" : "3045022100813ef79ccefa9a56f7ba805f0e478584fe5f0dd5f567bc09b5123ccbc983236502206ff18a52dcc0336f7af62400a6dd9b810732baf1ff758000d6f613a556eb31ba",
          "result" : "valid",
          "flags" : []
        },

case 218 is:

        {
          "tcId" : 218,
          "comment" : "special case hash",
          "msg" : "37313338363834383931",
          "sig" : "3045022028f94a894e92024699e345fe66971e3edcd050023386135ab3939d550898fb25022100cd69c1a42be05a6ee1270c821479251e134c21858d800bda6f4e98b37196238e",
          "result" : "valid",
          "flags" : []
        },

msg = sha256(base16_decode(msg))
sig = base16_decode(sig)
pubkey = base16_decode(pubkey)

My program is:

#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include "include/secp256k1.h"

int verify(uint8_t msg[32], uint8_t* sig, uint8_t siglen, uint8_t pubkey[65], uint8_t pubkeylen) {
    secp256k1_context* ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY);

    secp256k1_ecdsa_signature signature;
    secp256k1_pubkey publickey;

    if (secp256k1_ecdsa_signature_parse_der(ctx, &signature, sig, siglen) != 1) {
        printf("signature parse failed\n");
        secp256k1_context_destroy(ctx);
        return 0;
    }

    if (secp256k1_ec_pubkey_parse(ctx, &publickey, pubkey, pubkeylen) != 1) {
        printf("pubkey parse failed\n");
        secp256k1_context_destroy(ctx);
        return 0;
    }

    if (secp256k1_ecdsa_verify(ctx, &signature, msg, &publickey) != 1) {
        printf("signature is not valid\n");
        secp256k1_context_destroy(ctx);
        return 0;
    }

    printf("signature is valid\n");
    secp256k1_context_destroy(ctx);
    return 1;
}

int main() {

    uint8_t wycheproof_pubkey[65] = {4, 184, 56, 255, 68, 229, 188, 23, 
                                    123, 242, 17, 137, 208, 118, 96, 130, 
                                    252, 157, 132, 50, 38, 136, 127, 201, 
                                    118, 3, 113, 16, 11, 126, 226, 10, 
                                    111, 240, 201, 215, 91, 251, 167, 179, 
                                    26, 107, 202, 25, 116, 73, 110, 235, 
                                    86, 222, 53, 112, 113, 149, 93, 131, 
                                    196, 177, 186, 218, 160, 178, 24, 50, 233};

    uint8_t wycheproof_msg3[32] = {187, 90, 82, 244, 47, 156, 146, 97, 237, 67, 97, 245, 148, 34, 161, 227, 0, 54, 231, 195, 43, 39, 12, 136, 7, 164, 25, 254, 202, 96, 80, 35};
    uint8_t wycheproof_sig3[71] = {48, 69, 2, 33, 0, 129, 62, 247, 156, 206, 250, 154, 86, 247, 186, 128, 95, 14, 71, 133, 132, 254, 95, 13, 213, 245, 103, 188, 9, 181, 18, 60, 203, 201, 131, 35, 101, 2, 32, 111, 241, 138, 82, 220, 192, 51, 111, 122, 246, 36, 0, 166, 221, 155, 129, 7, 50, 186, 241, 255, 117, 128, 0, 214, 246, 19, 165, 86, 235, 49, 186};

    uint8_t wycheproof_msg218[32] = {115, 0, 0, 0, 0, 33, 63, 42, 82, 92, 96, 53, 114, 82, 53, 194, 246, 150, 173, 62, 187, 94, 228, 127, 20, 6, 151, 173, 37, 119, 13, 145};
    uint8_t wycheproof_sig218[71] = {48, 69, 2, 32, 40, 249, 74, 137, 78, 146, 2, 70, 153, 227, 69, 254, 102, 151, 30, 62, 220, 208, 80, 2, 51, 134, 19, 90, 179, 147, 157, 85, 8, 152, 251, 37, 2, 33, 0, 205, 105, 193, 164, 43, 224, 90, 110, 225, 39, 12, 130, 20, 121, 37, 30, 19, 76, 33, 133, 141, 128, 11, 218, 111, 78, 152, 179, 113, 150, 35, 142};

    int result3;
    int result218;

    result3 = verify(wycheproof_msg3, wycheproof_sig3, sizeof(wycheproof_sig3), wycheproof_pubkey, sizeof(wycheproof_pubkey));
    result218 = verify(wycheproof_msg218, wycheproof_sig218, sizeof(wycheproof_sig218), wycheproof_pubkey, sizeof(wycheproof_pubkey));

    printf("result3 is %d\n", result3);
    printf("result218 is %d\n", result218);
    return 0;
}

The result of test case 3 is as expected, but the result of test case 218 is wrong.

BTW, A go-version secp256k1 library can verify case 218 correctly.

[gmaxwell]

Thank you so much for testing the library. However the result you are getting appears to be both expected and correct behaviour from the library.

Please see the documentation for secp256k1_ecdsa_verify: https://github.com/bitcoin-core/secp256k1/blob/master/include/secp256k1.h#L415

To avoid accepting malleable signatures, only ECDSA signatures in lower-S form are accepted. If you need to accept ECDSA signatures from sources that do not obey this rule, apply secp256k1_ecdsa_signature_normalize to the signature prior to validation, but be aware that doing so results in malleable signatures.

Adding a normalize call to your test case above the verify like this:

• secp256k1_ecdsa_signature_normalize(ctx, &signature, &signature);

results in:

signature is valid
signature is valid
result3 is 1
result218 is 1

To further confirm that the normailzation wasn't simply bypassing the test intent, I modified secp256k1_ecdsa_verify to remove the secp256k1_scalar_is_high call, left the normalization out, and the test still passes.

Any system which does not enforce a functionally equivalent normalization is vulnerable to malleation-- which may be irrelevant or serious vulnerabilities depending on the specific application. In OpenSSL this sort of malleation allows for trivial certificate blacklist bypassing, in Bitcoin before correction it resulted in moderately severe denial of service and in some cases could cause funds loss. Any implementation that does not do this would also now be consensus inconsistent with Bitcoin.

In libsecp256k1 since we don't know what protocols we may be used from we can't decide that it's simply safe to allow this behaviour (and, in our primary application of Bitcoin, it is very much not safe) our intentional and documented behaviour is to fix this vulnerability. If a particular callee wants to preserve it (or they know it is harmless in their application) they can get the conventional behaviour with a normalize call.

A quick look at the wycheproof vectors suggests to me that our existing tests already check most (all?) of those cases (and in some cases we have much stronger versions where curve specific magic made constructing them possible), but more tests is better so it it would probably be pretty nice if someone wanted to submit an addition to our tests that includes them, similar to your test harness.

[LanfordCai]

Thank for your patient explaination!