ECDSA verify succeeds when it should fail
guidovranken opened this issue · 14 comments
The following program performs ECDSA verification on the following parameters:
ecc curve: secp256k1
public key X: 83121579216557378445487899878180864668798711284981320763518679672151497189239
public key Y: 35702972027818625020095973668955176475740885849864829235584237564223564379706
cleartext: {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b, 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41} (32 bytes)
signature R: 83121579216557378445487899878180864668798711284981320763518679672151497189239
signature S: 83121579216557378445487899878180864668798711284981320763518679672151497189239
digest: NULL
#include <relic_conf.h>
#include <relic.h>
int main(void)
{
if ( core_init() != RLC_OK ) abort();
bn_t r, s;
ec_t pub;
/* noret */ ep_param_set(SECG_K256);
bn_null(r); bn_new(r);
bn_null(s); bn_new(s);
const char* r_str = "83121579216557378445487899878180864668798711284981320763518679672151497189239";
const char* s_str = "83121579216557378445487899878180864668798711284981320763518679672151497189239";
/* noret */ bn_read_str(r, r_str, strlen(r_str), 10);
/* noret */ bn_read_str(s, s_str, strlen(s_str), 10);
const unsigned char pub_bytes[] = {0x04, 0xB7, 0xC5, 0x25, 0x88, 0xD9, 0x5C, 0x3B, 0x9A, 0xA2, 0x5B, 0x04, 0x03, 0xF1, 0xEE, 0xF7, 0x57, 0x02, 0xE8, 0x4B, 0xB7, 0x59, 0x7A, 0xAB, 0xE6, 0x63, 0xB8, 0x2F, 0x6F, 0x04, 0xEF, 0x27, 0x77, 0x4E, 0xEF, 0x2A, 0x82, 0x6F, 0x1E, 0x6D, 0x13, 0xA4, 0xDD, 0xE4, 0xE5, 0x48, 0x00, 0xED, 0x6A, 0x01, 0x2F, 0xCF, 0x21, 0x00, 0xEE, 0x64, 0xD5, 0x3C, 0x61, 0x62, 0x21, 0xEA, 0xE5, 0x76, 0x3A};
/* noret */ ec_new(pub);
/* noret */ ec_read_bin(pub, pub_bytes, sizeof(pub_bytes));
unsigned char in[] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b, 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41};
printf("cp_ecdsa_ver: %d\n", cp_ecdsa_ver(r, s, in, sizeof(in), 1, pub));
return 0;
}All libraries return false for these parameters, but relic returns true.
This is interesting and amounts to the case where H(m) = 0 (mod n).
RELIC is being called in "prehashed" mode, where H(m) = 0 triggers a special case. Are the other libraries also being called in "prehashed" mode?
Some libraries allow passing an arbitrary (unhashed) array, others do not (they sha256-hash the input themselves).
For example libsecp256k1's secp256k1_ecdsa_verify function takes the unhashed input (though it must be 32 bytes). This is useful if you don't want to use a predefined hash function (like SHA256), and for testing to find corner cases like this one.
Is this something you'd like to address in relic, or should I work around it?
But to answer your question, yes all libraries which support prehashed mode return false or error for this input.
Nice, thanks! Then it's something I should address. :)
Ok great.
Unrelated but should code that calls bn_get_bit or bn_set_bit check if the bit position is within bounds? If I don't do that check myself I get out-of-bounds access.
I added some bounds checking for the bit functions as well.
I should take all opportunities to harden the library.
@dfaranha Fix confirmed for the initial parameter set.
However here is another one:
ecc curve: secp256k1
public key X: 55066263022277343669578718895168534326250603453777594175500187360389116729240
public key Y: 32670510020758816978083085130507043184471273380659243275938904335757337482424
cleartext: {0x00, 0x00, 0x00} (3 bytes)
signature R: 104546003225722045112039007203142344920046999340768276760147352389092131869133
signature S: 96900796730960181123786672629079577025401317267213807243199432755332205217369
digest: NULL
This verifies in OpenSSL, Botan, wolfCrypt and probably others, but relic returns false.
Please let me know if you need a compilable reproducer for this.
#include <relic_conf.h>
#include <relic.h>
int main(void)
{
if ( core_init() != RLC_OK ) abort();
bn_t r, s;
ec_t pub;
/* noret */ ep_param_set(SECG_K256);
bn_null(r); bn_new(r);
bn_null(s); bn_new(s);
const char* r_str = "104546003225722045112039007203142344920046999340768276760147352389092131869133";
const char* s_str = "96900796730960181123786672629079577025401317267213807243199432755332205217369";
/* noret */ bn_read_str(r, r_str, strlen(r_str), 10);
/* noret */ bn_read_str(s, s_str, strlen(s_str), 10);
const unsigned char pub_bytes[] = {0x04, 0x79, 0xBE, 0x66, 0x7E, 0xF9, 0xDC, 0xBB, 0xAC, 0x55, 0xA0, 0x62, 0x95, 0xCE, 0x87, 0x0B, 0x07, 0x02, 0x9B, 0xFC, 0xDB, 0x2D, 0xCE, 0x28, 0xD9, 0x59, 0xF2, 0x81, 0x5B, 0x16, 0xF8, 0x17, 0x98, 0x48, 0x3A, 0xDA, 0x77, 0x26, 0xA3, 0xC4, 0x65, 0x5D, 0xA4, 0xFB, 0xFC, 0x0E, 0x11, 0x08, 0xA8, 0xFD, 0x17, 0xB4, 0x48, 0xA6, 0x85, 0x54, 0x19, 0x9C, 0x47, 0xD0, 0x8F, 0xFB, 0x10, 0xD4, 0xB8};
/* noret */ ec_new(pub);
/* noret */ ec_read_bin(pub, pub_bytes, sizeof(pub_bytes));
unsigned char in[] = {0x00, 0x00, 0x00};
printf("cp_ecdsa_ver: %d\n", cp_ecdsa_ver(r, s, in, sizeof(in), 1, pub));
return 0;
}Here's a reproducer for OpenSSL for the same parameters that you can compare against
#include <openssl/ecdsa.h>
#include <openssl/obj_mac.h>
#define CF_CHECK_EQ(expr, res) if ( (expr) != (res) ) { goto end; }
#define CF_CHECK_NE(expr, res) if ( (expr) == (res) ) { goto end; }
static void verify(const unsigned char* in, const size_t insize, const char* X, const char* Y, const char* R, const char* S) {
EC_GROUP* group = NULL;
EC_POINT* pub = NULL;
ECDSA_SIG* signature = NULL;
EC_KEY* key = NULL;
BIGNUM *pub_x = NULL, *pub_y = NULL, *sig_r = NULL, *sig_s = NULL;
CF_CHECK_NE(key = EC_KEY_new(), NULL);
CF_CHECK_NE(group = EC_GROUP_new_by_curve_name(NID_secp256k1), NULL);
CF_CHECK_EQ(EC_KEY_set_group(key, group), 1);
/* Signature */
CF_CHECK_NE(signature = ECDSA_SIG_new(), NULL);
CF_CHECK_NE(BN_dec2bn(&sig_r, R), 0);
CF_CHECK_NE(BN_dec2bn(&sig_s, S), 0);
CF_CHECK_EQ(ECDSA_SIG_set0(signature, sig_r, sig_s), 1);
/* Key */
CF_CHECK_NE(pub = EC_POINT_new(group), NULL);
CF_CHECK_NE(BN_dec2bn(&pub_x, X), 0);
CF_CHECK_NE(BN_dec2bn(&pub_y, Y), 0);
CF_CHECK_NE(EC_POINT_set_affine_coordinates_GFp(group, pub, pub_x, pub_y, NULL), 0);
CF_CHECK_EQ(EC_KEY_set_public_key(key, pub), 1);
printf("Verify result: %d\n", ECDSA_do_verify(in, insize, signature, key));
end:
return;
}
int main(void)
{
{
const unsigned char in[] = {0x00, 0x00, 0x00};
verify(
in,
sizeof(in),
"55066263022277343669578718895168534326250603453777594175500187360389116729240",
"32670510020758816978083085130507043184471273380659243275938904335757337482424",
"104546003225722045112039007203142344920046999340768276760147352389092131869133",
"96900796730960181123786672629079577025401317267213807243199432755332205217369");
}
return 0;
}Apparently fixed, but this is also a case where H(m) = 0. The other libraries are thus accepting 0-value hashes that are shorter than a digest.
I don't think that the hash size is of any importance to these libraries. I know that OpenSSL will take any hash size, truncate it to the curve size (32 bytes in this case), and interpret it as a bignum.
With the first parameter set, it seems that fails upon setting the pubkey to 831215..., 357029....
Eg. in this program, nothing is printed:
#include <openssl/ecdsa.h>
#include <openssl/obj_mac.h>
#define CF_CHECK_EQ(expr, res) if ( (expr) != (res) ) { goto end; }
#define CF_CHECK_NE(expr, res) if ( (expr) == (res) ) { goto end; }
static void verify(const unsigned char* in, const size_t insize, const char* X, const char* Y, const char* R, const char* S) {
EC_GROUP* group = NULL;
EC_POINT* pub = NULL;
ECDSA_SIG* signature = NULL;
EC_KEY* key = NULL;
BIGNUM *pub_x = NULL, *pub_y = NULL, *sig_r = NULL, *sig_s = NULL;
CF_CHECK_NE(key = EC_KEY_new(), NULL);
CF_CHECK_NE(group = EC_GROUP_new_by_curve_name(NID_secp256k1), NULL);
CF_CHECK_EQ(EC_KEY_set_group(key, group), 1);
/* Signature */
CF_CHECK_NE(signature = ECDSA_SIG_new(), NULL);
CF_CHECK_NE(BN_dec2bn(&sig_r, R), 0);
CF_CHECK_NE(BN_dec2bn(&sig_s, S), 0);
CF_CHECK_EQ(ECDSA_SIG_set0(signature, sig_r, sig_s), 1);
/* Key */
CF_CHECK_NE(pub = EC_POINT_new(group), NULL);
CF_CHECK_NE(BN_dec2bn(&pub_x, X), 0);
CF_CHECK_NE(BN_dec2bn(&pub_y, Y), 0);
CF_CHECK_NE(EC_POINT_set_affine_coordinates_GFp(group, pub, pub_x, pub_y, NULL), 0);
CF_CHECK_EQ(EC_KEY_set_public_key(key, pub), 1);
printf("X\n");
printf("Verify result: %d\n", ECDSA_do_verify(in, insize, signature, key));
end:
return;
}
int main(void)
{
{
const unsigned char in[] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b, 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41};
verify(
in,
sizeof(in),
"83121579216557378445487899878180864668798711284981320763518679672151497189239",
"35702972027818625020095973668955176475740885849864829235584237564223564379706",
"83121579216557378445487899878180864668798711284981320763518679672151497189239",
"83121579216557378445487899878180864668798711284981320763518679672151497189239");
}
return 0;
}So for the first parameter set, it seems the pubkey is not valid.
And for the second parameter set, it seems the other libraries allow H(m) = 0.
Botan agrees that the pubkey is invalid (this prints 0).
#include <botan/system_rng.h>
#include <botan/ecdsa.h>
int main(void)
{
::Botan::System_RNG rng;
::Botan::EC_Group group("secp256k1");
const ::Botan::BigInt pub_x("83121579216557378445487899878180864668798711284981320763518679672151497189239");
const ::Botan::BigInt pub_y("35702972027818625020095973668955176475740885849864829235584237564223564379706");
const ::Botan::PointGFp public_point = group.point(pub_x, pub_y);
auto pub = std::make_unique<::Botan::ECDSA_PublicKey>(::Botan::ECDSA_PublicKey(group, public_point));
printf("%d\n", pub->check_key(rng, true));
return 0;
}Ah yes, I misunderstood the error conditions! Just pushed a commit sorting this out.
Public key validation was always assumed to be done off-band in RELIC, but the cost is small enough to give a try here.
Thanks, I've tested again and I can't detect find other discrepancies with other libraries anymore.