Hypothetical adversaries that can trigger the addition bug through Verify can already recover the private key from the public key alone

The following claim is intended as a security reduction argument. Security of ECDSA over secp256r1 as a cryptographic scheme relies on the assumption that, given only a public key, it is computationally intractable to compute the private key from it. We assume that this is true. Then the below claim argues that if an attacker that only has the public key could use this to efficiently produce (r, s, e) that triggers the bug described in Finding ref↗, then this attacker would also be able to efficiently recover the private key from the public key alone. But this would contradict the assumption that this is computationally intractable. Hence, it must be in practice impossible for an attacker to produce such (r, s, e) if they only knew the public key.

Claim: An adversary, who knows arguments (passKey, r, s, e) that passed to Verify will cause a call to _jAdd in which the two summands are equal, can use them to efficiently compute the private key corresponding to the public key passKey.

Proof: The following diagram depicts the call graph between Verify and _jAdd.

We argue that along both branches, triggering the bug implies an efficiently computable, nontrivial linear relation in the elliptic curve between the generator $G$ and the public key, which we shall call $Q$. This means there are elements $\alpha$ and $\beta$ of ${\mathbb{F}}_n$, where $n$ is the (prime) order of the elliptic curve, such that $\alpha \cdot G+\beta \cdot Q=0$ and $(\alpha ,\beta )\ne (0,0)$. Should we have $Q=0$, then the corresponding private key is $d=0$, so we assume $Q\ne 0$ from now on. Then we must have $\beta \ne 0$ so we can define $d=-\alpha {\beta }^{-1}$, which will then satisfy $d\cdot G=Q$, so $d$ is the private key corresponding to $Q$.

Let us now consider the left part of the call graph. The function Verify calls _preComputeJacobianPoints, passing the public key passKey as the only argument. The function _preComputeJacobianPoints in turn calculates an array points of points on the elliptic curve represented in Jacobian coordinates, with , for $0\le i,j<4$.

points[0] = JPoint(0, 0, 0);
points[1] = JPoint(passKey.pubKeyX, passKey.pubKeyY, 1); // u2
points[2] = _jPointDouble(points[1]);
points[3] = _jPointAdd(points[1], points[2]);

points[4] = JPoint(gx, gy, 1); // u1Points[1]
points[5] = _jPointAdd(points[4], points[1]);
points[6] = _jPointAdd(points[4], points[2]);
points[7] = _jPointAdd(points[4], points[3]);

points[8] = _jPointDouble(points[4]); // u1Points[2]
points[9] = _jPointAdd(points[8], points[1]);
points[10] = _jPointAdd(points[8], points[2]);
points[11] = _jPointAdd(points[8], points[3]);

points[12] = _jPointAdd(points[4], points[8]); // u1Points[3]
points[13] = _jPointAdd(points[12], points[1]);
points[14] = _jPointAdd(points[12], points[2]);
points[15] = _jPointAdd(points[12], points[3]);

There are three types of _jAdd calls being made through the wrapper _jPointAdd when computing this table:

1. One summand is $Q$; the other is $2\cdot Q$ (for points[3]).

2. One summand is $G$; the other is $2\cdot G$ (for points[12]).

3. One summand is $\alpha \cdot G$; the other is $\beta \cdot Q$ for $\alpha ,\beta \in \{1,2,3\}$ (for points[i] with $i\in \{5,6,7,9,10,11,13,14,15\}$).

In each case, equality of the two summands implies a nontrivial linear relation between $G$ and $Q$.

Finally, let us consider the right part of the call graph, where we need to look into a call to ShamirMultJacobian(JPoint[16] memory points, uint u1, uint u2), where points is precisely the precomputed list of points discussed and where the concrete values of u1 and u2 are irrelevant for the following argument. This function uses Shamir's trick to efficiently compute $u_1\cdot G+u_2\cdot Q$ using the precomputed points. There is only one call to _jAdd in this function, namely

(x, y, z) = _jAdd(
    x,
    y,
    z,
    points[index].x,
    points[index].y,
    points[index].z
);

The arguments (x,y,z) to _jAdd will represent the point $4\alpha \cdot G+4\beta \cdot Q$ where $\alpha =\text{(u1 >> (256-2*bits)) \& ((1 << (256 - 2*bits)) - 1)}$ and $\beta =\text{(u2 >> (256-2*bits)) \& ((1 << (256 - 2*bits)) - 1)}$. The call to _jAdd will only be carried out if index is nonzero, and in that case, we know that we will have with $0\le \gamma ,\delta <4$, not both zero. As the values of u1 and u2 are the result of a computation modulo $n$ in VerifyWithPrecompute, they must be smaller than $n$; from which, it follows that we must have $4\alpha ,4\beta <n$. This implies that $(4\alpha -\gamma )\cdot G+(4\beta -\delta )\cdot Q=0$ is a nontrivial linear relation between $G$ and $Q$.

This ends the proof of the claim.

As an additional check on this argument, we produced a script that recovers the secret key from the public key and a test vector that triggers this bug.