Breaking Linear Dependencies in ECDSA Nonce Reuse Systems

[peakyclin77]

Hello everyone,

I’m reposting my problem with a few updates, but I’m still stuck. Does anyone have a solution or insight?

Initial problem

We have 9 signatures and 7 private keys:
d1, d2, d3, d4, d5, d6, d7, and 3 nonces: k1, k2, k3.

d1 uses the nonces k1, k2, k3 (or their negatives: -k1, -k2, -k3)
d2 and d3 reuse k1 (or -k1)
d4 and d5 reuse k2 (or -k2)
d6 and d7 reuse k3 (or -k3)

So far, the ambiguity of the signs is not an issue, because by eliminating the nonces from the equations, we can derive relations between the keys and verify them through scalar multiplication by n. If a public key does not match, we simply flip S and the correct public key appears.

We obtain relations of the form:

Code:

Q2 = α2·Q1 + β2·G
Q3 = α3·Q1 + β3·G
Q4 = α4·Q1 + β4·G
Q5 = α5·Q1 + β5·G
Q6 = α6·Q1 + β6·G
Q7 = α7·Q1 + β7·G

Nonce structure

The nonces can even be expressed as affine functions of d1, with coefficients U1 and U2 (where U1 = γ and U2 = δ):

Code:

k1 = γ1·d1 + δ1
k2 = γ2·d1 + δ2
k3 = γ3·d1 + δ3

At this point, everything reduces to a single free unknown: d1. The system is underdetermined, and there is a missing constraint to fully close it.

I know that if d2 had used k1 and k2 with two independent relations like:

Code:

d2 = α2·d1 + β2
d2 = α2'·d1 + β2'

(with different coefficients), then the system would become solvable/closed.

Current issue

In this setup, for any key from d1 to d7, using the relation:

Code:

d2 = α2·d1 + β2

and the coordinates U1, U2 from a signature, I can generate a new signature for d2 using k2 (thus the same R value). The issue is that this leads to a valid-looking signature, but k2 still depends on d1, so I end up with a tautology like:

Code:

d2 = α2·d1 + β2 = α2·d1 + β2 = 0

Question

Does anyone have an idea on how to break this linear structure or introduce an additional constraint to close the system?

[BattleDog]

With ECDSA, the basic equation is still s*k = z + r*d mod n. When the same nonce is reused, you can eliminate the nonce and get a relation between private keys. That part is fine. But if all you ever get are relations like "this key is an affine function of d1", then you have not recovered the keys, you have just chosen d1 as the free variable for the whole family of possible solutions.

Does anyone have an idea on how to break this linear structure or introduce an additional constraint to close the system?

No, not from the data as you've described it. You can express everything relative to d1, but unless something pins d1 down, the system will stay open.

[NotATether]

There is an industrial way to run the lattice attack at scale and it's https://github.com/bitlogik/lattice-attack .

It requires that you know at least 4 bits of each nonce, with MSB and LSB being preferred as it simplifies things.

You also need at least 88 signatures. If you have more bits, you'll need less.

There are several solvers with increasingly long runtime and more accurate results, such as LLL, BKZ-15 BKZ-25, BKZ-35, etc

You must understand however, that even with a large signature set, finding a solution is not guaranteed. Because increasing the number of dimensions in the lattice via adding more signatures merely makes the problem space bigger, and it is possible that the algorithm fails to find a solution, similar to a given linear algebra system.