Description

The VerifyWithPrecompute function handles verification of ECDSA signatures. Signatures consist of a pair (r, s) of integers $0<r,s<n$, where $n$ is the order of the elliptic curve secp256r1. The signature is ultimately accepted if and only if the x-coordinate x of a computed point on the elliptic curve satisfies x == r, as can be seen in the code snippet below.

(x, y) = ShamirMultJacobian(points, u1, u2);
return (x == r);

However, the elliptic curve secp256r1 is defined over the finite field ${\mathbb{F}}_p$, so the x-coordinate x will be an element of ${\mathbb{F}}_p$ and be represented by an integer satisfying $0\le x<p$. Specifications state that a signature should be accepted if x % n == r. As $n<p$, it can happen that x % n == r but x != r, so some signatures that should be accepted are not.

Impact

That a properly generated valid signature will hit this bug by accident is extremly unlikely (it will happen roughly once every 10^39 signatures). The Project Wycheproof test vector shows, however, that it is possible to generate such signatures on purpose. The impact on the security of projects making use of the Secp256r1 library for signature verification is highly dependent on how signatures are otherwise used. See section ref↗ for a discussion of this as well as the reason for our severity rating.

This bug is the root cause of the failure of test case ID 285: k*G has a large x-coordinate from Project Wycheproof.

Recommendations

Replace return (x == r); by return ((x % nn) == r);.

Remediation

This issue has been acknowledged by Biconomy Labs, and a fix was implemented in commit 983b699d↗.