## 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 $α$ and $β$ of $F_{n}$, where $n$ is the (prime) order of the elliptic curve, such that $α⋅G+β⋅Q=0$ and $(α,β)=(0,0)$. Should we have $Q=0$, then the corresponding private key is $d=0$, so we assume $Q=0$ from now on. Then we must have $β=0$ so we can define $d=−αβ_{−1}$, which will then satisfy $d⋅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≤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:

One summand is $Q$; the other is $2⋅Q$ (for

`points[3]`

).One summand is $G$; the other is $2⋅G$ (for

`points[12]`

).One summand is $α⋅G$; the other is $β⋅Q$ for $α,β∈{1,2,3}$ (for

`points[i]`

with $i∈{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}⋅G+u_{2}⋅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α⋅G+4β⋅Q$ where $α=(u1 >> (256-2*bits)) & ((1 << (256 - 2*bits)) - 1)$ and $β=(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≤γ,δ<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α,4β<n$. This implies that $(4α−γ)⋅G+(4β−δ)⋅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.