Description

The _jAdd(uint p1, uint p2, uint p3, uint q1, uint q2, uint q3) function's purpose is to calculate the sum of the two points (p1:p2:p3) and (q1:q2:q3) on the elliptic curve secp256r1. Both summands as well as the result are represented with Jacobian coordinates.

However, an issue arises when the represented points are equal: the function returns the incorrect result (0,0,0).

Impact

The value returned to an (indirect) caller of _jAdd will be invalid if the two summands passed to _jAdd represent equal points, with an impact depending on how the return value is used. Our analysis focused on the impact on the Secp256r1 library's Verify function, which is assumed to be the only function called by users of this library.

We came to the conclusion (detailed reasoning can be found in section ref↗) that an attacker could only make use of this bug through Verify in order to produce

1. Valid signatures for a key whose private key they know, which, however, get erroneously rejected by Verify

2. Invalid signatures for a key whose private key they know, which, however, get erroneously accepted by Verify

We thus believe that this bug does not help an attacker craft signatures that pass verification even though the attacker was not able to produce a legitimate valid signature.

That a properly generated valid signature triggers this bug is extremely unlikely.

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 345: extreme value for k and s^-1 from Project Wycheproof.

Recommendations

Consider adding a check for equality of the two summands in _jAdd and, in case of equality, calculate the result using _modifiedJacobianDouble instead, as that function implements the specialized formulas intended for precisely this case.

When checking whether the points represented by Jacobian coordinates (p1:p2:p3) and (q1:q2:q3) are equal, note that $(x:y:z)$ and $(a^{2}x:a^{3}x:az)$ represent the same point if $a$ is nonzero. One way to check equality is then to convert both points to affine coordinates, with a check like this:

(px, py) = _affineFromJacobian(p1, p2, p3);
(qx, qy) = _affineFromJacobian(q1, q2, q3);
if ((px == qx) && (py == qy)) {
    return _modifiedJacobianDouble(p1, p2, p3);
}

Alternatively, given that the code in _jAdd already calculates values u1, u2, s1, and s2 as in the following display, we can also check equality by checking whether (u1 == u2) && (s1 == s2) after having previously handled the case (p3 == 0) || (q3 == 0).

let
    pd
:= 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
let z1z1 := mulmod(p3, p3, pd) // Z1Z1 = Z1^2
let z2z2 := mulmod(q3, q3, pd) // Z2Z2 = Z2^2

let u1 := mulmod(p1, z2z2, pd) // U1 = X1*Z2Z2
let u2 := mulmod(q1, z1z1, pd) // U2 = X2*Z1Z1

let s1 := mulmod(p2, mulmod(z2z2, q3, pd), pd) // S1 = Y1*Z2*Z2Z2
let s2 := mulmod(q2, mulmod(z1z1, p3, pd), pd) // S2 = Y2*Z1*Z1Z1

Given that this bug cannot be used by an attacker to pass signature validation for a forged signature unless they could also have created a valid signature for it, it is also an option to not remediate this bug. In that case, it should be carefully considered whether an attacker could use the scenarios above maliciously when taking into account interaction with other components. See ref↗ for a discussion of this risk.

Remediation

This issue has been acknowledged by Biconomy Labs, and fixes were implemented in the following commits:

• 983b699d↗
• f7e03db2↗