chore(crypto): ecdsa uncompres_coords input check
What the developer wrote
Authored by M1nd3r
chore(crypto): ecdsa uncompres_coords input check
- Calling `uncompres_coords` will now return 0 (error) if the input `x` is a non-residue (has no sqrt) - as non-residue `x` results in an invalid `y` value. In case of failure, `y` is zeroed-out.
What changed, and why it matters
This commit hardens the Trezor firmware's elliptic-curve cryptography by making a low-level coordinate-decompression function validate its inputs. Previously, if a compressed public key or signature-recovery value pointed to an x-coordinate that does not correspond to any valid point on the curve, the function could silently produce a meaningless y-coordinate. The change now returns an error and clears the result, preventing downstream code from acting on invalid curve points. The commit message frames this as a routine code-quality improvement ('chore'), not as a security fix.
Treat this as a defensive hardening change worth including in security-focused release notes, even though the vendor labeled it as a chore. Review whether any other callers of `uncompress_coords()` (including in downstream forks or older branches) still ignore the return value, and ensure the new tests are run in CI. Consider whether invalid public keys could previously have reached `ecdsa_validate_pubkey()` with an unreduced or non-residue x and whether that had any exploitable consequence in higher-level protocols.
Security signals we found
Input validation added to elliptic-curve point decompression
Non-quadratic-residue x coordinates now rejected instead of producing invalid y
Out-of-range x coordinates (x >= p) now rejected
Failure path zeroes output y coordinate
Downstream callers updated to treat failure as an error condition
Commit message uses 'chore' label, not 'fix' or 'security'
Evidence from the diff
The patch changes uncompress_coords() in crypto/ecdsa.c from a void function to an int function that returns 0 on failure. It adds two checks: (1) the input x must be less than the curve prime, and (2) after computing a candidate y via bn_sqrt(), it verifies that y^2 equals x^3 + ax + b modulo p, catching cases where the right-hand side is a non-quadratic residue. On failure, y is zeroed. Callers ecdsa_read_pubkey() and tc_ecdsa_recover_pub_from_sig() now rely on this return value instead of calling ecdsa_validate_pubkey() separately. Tests are added for non-residue and out-of-range x values.
Changed components
crypto/ecdsa.c: uncompress_coords()crypto/ecdsa.c: ecdsa_read_pubkey()crypto/ecdsa.c: tc_ecdsa_recover_pub_from_sig()crypto/ecdsa.h: uncompress_coords() signaturecrypto/tests/test_check.c: compression/decompression testsInspect captured patch +94 / −19
### crypto/ecdsa.c
@@ -936,18 +936,45 @@ void compress_coords(const curve_point *cp, uint8_t *compressed) {
bn_write_be(&cp->x, compressed + 1);
}
-void uncompress_coords(const ecdsa_curve *curve, uint8_t odd,
- const bignum256 *x, bignum256 *y) {
+// Computes the y coordinate with the given parity of the curve point with the
+// given x coordinate. On success (x, y) is a valid public key, in case of
+// failure y is set to zero.
+int uncompress_coords(const ecdsa_curve *curve, uint8_t odd, const bignum256 *x,
+ bignum256 *y) {
+ bignum256 y_2 = {0}, y_2_check = {0};
+
+ // verify x is in range [0,p-1]
+ if (!bn_is_less(x, &curve->prime)) {
+ bn_zero(y);
+ return 0;
+ }
+
// y^2 = x^3 + a*x + b
- memcpy(y, x, sizeof(bignum256)); // y is x
- bn_multiply(x, y, &curve->prime); // y is x^2
- bn_subi(y, -curve->a, &curve->prime); // y is x^2 + a
- bn_multiply(x, y, &curve->prime); // y is x^3 + ax
- bn_add(y, &curve->b); // y is x^3 + ax + b
- bn_sqrt(y, &curve->prime); // y = sqrt(y)
+ memcpy(&y_2, x, sizeof(bignum256)); // y_2 is x
+ bn_multiply(x, &y_2, &curve->prime); // y_2 is x^2
+ bn_subi(&y_2, -curve->a, &curve->prime); // y_2 is x^2 + a
+ bn_multiply(x, &y_2, &curve->prime); // y_2 is x^3 + ax
+ bn_addmod(&y_2, &curve->b, &curve->prime); // y_2 is x^3 + ax + b
+ bn_mod(&y_2, &curve->prime);
+
+ bn_copy(&y_2, y);
+ bn_sqrt(y, &curve->prime); // y = sqrt(y_2)
+
+ // bn_sqrt() returns a meaningless value if y_2 is not a quadratic residue
+ bn_copy(y, &y_2_check);
+ bn_multiply(y, &y_2_check, &curve->prime); // y_2_check is y^2
+ bn_mod(&y_2_check, &curve->prime);
+ if (!bn_is_equal(&y_2_check, &y_2)) {
+ // x is invalid (x^3 + ax + b is a non-residue)
+ bn_zero(y);
+ return 0;
+ }
+
if ((odd & 0x01) != (y->val[0] & 1)) {
bn_subtract(&curve->prime, y, y); // y = -y
}
+
+ return 1;
}
int ecdsa_read_pubkey(const ecdsa_curve *curve, const uint8_t *pub_key,
@@ -962,8 +989,8 @@ int ecdsa_read_pubkey(const ecdsa_curve *curve, const uint8_t *pub_key,
}
if (pub_key[0] == 0x02 || pub_key[0] == 0x03) { // compute missing y coords
bn_read_be(pub_key + 1, &(pub->x));
- uncompress_coords(curve, pub_key[0], &(pub->x), &(pub->y));
- return ecdsa_validate_pubkey(curve, pub);
+ // uncompress_coords validates the resulting point
+ return uncompress_coords(curve, pub_key[0], &(pub->x), &(pub->y));
}
// error
return 0;
@@ -1045,13 +1072,9 @@ int tc_ecdsa_recover_pub_from_sig(const ecdsa_curve *curve, uint8_t *pub_key,
memcpy(&cp.x, &r, sizeof(bignum256));
if (recid & 2) {
bn_add(&cp.x, &curve->order);
- if (!bn_is_less(&cp.x, &curve->prime)) {
- return 1;
- }
}
- // compute y from x
- uncompress_coords(curve, recid & 1, &cp.x, &cp.y);
- if (!ecdsa_validate_pubkey(curve, &cp)) {
+ // compute y from x and validate the point
+ if (!uncompress_coords(curve, recid & 1, &cp.x, &cp.y)) {
return 1;
}
// e = -digest
### crypto/ecdsa.h
@@ -86,8 +86,8 @@ int scalar_multiply(const ecdsa_curve *curve, const bignum256 *k,
int ecdh_multiply(const ecdsa_curve *curve, const uint8_t *priv_key,
const uint8_t *pub_key, uint8_t *session_key);
void compress_coords(const curve_point *cp, uint8_t *compressed);
-void uncompress_coords(const ecdsa_curve *curve, uint8_t odd,
- const bignum256 *x, bignum256 *y);
+int uncompress_coords(const ecdsa_curve *curve, uint8_t odd, const bignum256 *x,
+ bignum256 *y);
int ecdsa_uncompress_pubkey(const ecdsa_curve *curve, const uint8_t *pub_key,
uint8_t *uncompressed);
### crypto/tests/test_check.c
@@ -10413,7 +10413,7 @@ static void test_compress_coord(const char *k_raw) {
bignum256 x = {0}, y = {0};
bn_read_be(compress + 1, &x);
- uncompress_coords(curve, compress[0], &x, &y);
+ ck_assert_int_eq(uncompress_coords(curve, compress[0], &x, &y), 1);
ck_assert(bn_is_equal(&expected_coords.x, &x));
ck_assert(bn_is_equal(&expected_coords.y, &y));
@@ -10438,6 +10438,57 @@ START_TEST(test_compress_coords) {
}
END_TEST
+static void test_uncompress_coord_invalid(const ecdsa_curve *curve,
+ const bignum256 *x) {
+ bignum256 y = {0};
+
+ for (uint8_t odd = 0x02; odd <= 0x03; odd++) {
+ bn_one(&y);
+ ck_assert_int_eq(uncompress_coords(curve, odd, x, &y), 0);
+ ck_assert(bn_is_zero(&y));
+ }
+}
+
+static void test_uncompress_coord_non_residue(const ecdsa_curve *curve,
+ uint32_t x_raw) {
+ bignum256 x = {0};
+ bn_read_uint32(x_raw, &x);
+ test_uncompress_coord_invalid(curve, &x);
+}
+
+static void test_uncompress_coord_out_of_range(const ecdsa_curve *curve) {
+ bignum256 x = {0};
+
+ // x == prime
+ bn_copy(&curve->prime, &x);
+ test_uncompress_coord_invalid(curve, &x);
+
+ // x == prime + 1
+ bn_addi(&x, 1);
+ test_uncompress_coord_invalid(curve, &x);
+
+ // x == 2^256 - 1
+ bn_read_be(
+ fromhex(
+ "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"),
+ &x);
+ test_uncompress_coord_invalid(curve, &x);
+}
+
+START_TEST(test_uncompress_coords_invalid) {
+ // x coordinates for which x^3 + a*x + b is not a quadratic residue,
+ // i.e. there is no curve point with the given x coordinate
+ test_uncompress_coord_non_residue(&secp256k1, 5);
+ test_uncompress_coord_non_residue(&secp256k1, 7);
+ test_uncompress_coord_non_residue(&nist256p1, 1);
+ test_uncompress_coord_non_residue(&nist256p1, 2);
+
+ // x coordinates which are not fully reduced modulo prime
+ test_uncompress_coord_out_of_range(&secp256k1);
+ test_uncompress_coord_out_of_range(&nist256p1);
+}
+END_TEST
+
START_TEST(test_zkp_bip340_sign) {
static struct {
const char *priv_key;
@@ -12461,6 +12512,7 @@ Suite *test_suite(void) {
tc = tcase_create("compress_coords");
tcase_add_test(tc, test_compress_coords);
+ tcase_add_test(tc, test_uncompress_coords_invalid);
suite_add_tcase(s, tc);
tc = tcase_create("zkp_bip340");Why this scored 59/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.