ECDSA nonce reuse across multiple private keys (9 signatures / 7 keys / 3 nonces

[punchkun99]

Hello,

I would like to present an interesting ECDSA signature scenario involving what appears to be nonce reuse across different private keys.

Problem setup

Private keys:
d1, d2, d3, d4, d5, d6, d7

Nonces:
k1, k2, k3

Total: 9 signatures

Signature structure
   •   d1 signs three times, using the nonces k1, k2, k3 (or possibly their opposites -k1, -k2, -k3).
   •   Nonce k1 (or -k1) is used by: d1, d2, d3
   •   Nonce k2 (or -k2) is used by: d1, d4, d5
   •   Nonce k3 (or -k3) is used by: d1, d6, d7

So we clearly have nonce reuse between different private keys, with d1 acting as a pivot, since it signs once with each of the three nonces.

It also appears that RFC 6979 was not used, otherwise each signature would have a deterministic unique nonce.

ECDSA equation

s = k⁻¹ (z + r·d) mod n

which can be rewritten as:

k·s = z + r·d (mod n)

In this setup we therefore have:

9 equations for 10 unknowns

Unknowns:

Private keys:
d1, d2, d3, d4, d5, d6, d7

Nonces:
k1, k2, k3

Question

Even though the system appears underdetermined (9 equations for 10 unknowns), the particular structure — with nonce reuse across multiple keys and d1 acting as a pivot connecting the three groups — might allow some reduction of the system.

Is there any known method to solve this kind of system?

Thanks in advance for any insights.

[0bs3ssed]

Very interesting and yes retrievable.
Have you tried further reducing the unknowns down to 1 ?
Got a nice in-depth system I built which finish this extremely quickly if you would like any help... Just pop me a PM

Have also tried popping a DM but because I'm new I can't.

[BattleDog]

What you have there is basically a one-parameter family, not a uniquely solvable recovery. If you take d1 as the pivot, then its three signatures let you write k1, k2 and k3 as functions of d1, and once those are pinned in that form, every other di also collapses into a function of d1.

So yes, the algebra can be reduced hard, but that is not the same thing as saying that all keys are now recoverable. It just means the whole system folds down to one free variable unless you bring in one more independent constraint from somewhere else.

[vdog99]

Seems like this is instead of Nonce Re-Occurrence this is sk recurrence problem. Does this happen in real world would be unlikely but maybe a good math exercise.

If you can rewrite the sk maybe to multivariate polynomial equation, it could be solvable

Use this Paper for your analysis although it is for nonce recurrence https://eprint.iacr.org/2023/305.pdf

[punchkun99]

Thanks for your responses.

Analyzing other keys from the same environment, I noticed that many private keys share common factors. For example, some pairs have GCDs like 63, 225, etc. It is therefore possible that the keys in the d1–d7 set also have nontrivial GCDs between them.

Since the system admits a family of solutions, I was able to generate valid signatures for different solutions of the equation. Some of these valid signatures have relatively small S values.

Could the potential GCDs between private keys or the observation of small S values in these valid signatures provide an exploitable constraint to help reduce the solution space?

[vdog99]

Can you provide more Details and more analysis on your thinking? Unlikely to have GCD in EC 256 Bit Space

[mcdouglasx]

Have also tried popping a DM but because I'm new I can't.

Why don't you create a thread with your findings and methods? You're a new user, and this seems suspicious to people who have been here on the forum for a while. I'm not saying it's wrong, but be careful when you ask another user for a DM in contexts where it might seem suspicious.


I understand that you want to frame the problem as a Hidden Number Problem and solve it using base reduction, but as @BattleDog pointed out, you have 10 unknowns and 9 independent equations, so you need certain vulnerabilities to be met; otherwise, you would have to test the entire 256-bit range to obtain all the private keys.

[punchkun99]

Thank you for your responses. I understand that with 9 equations and 10 unknowns, the system cannot be solved without an additional constraint.

However, I have gathered 34 keys used in the same environment as keys D1 to D7, which provides information about these keys.
I would like to know if this data could help in solving the problem.

Here are the GCD results of the 34 keys I currently have:

======= KEY STRUCTURE ANALYSIS REPORT =======
Total keys analyzed: 34
=============================================

--- SHARED FACTOR (GCD): 817 ---
  KEY14 <-> KEY25
SUMMARY: Factor 817 links 1 specific pairs.

--- SHARED FACTOR (GCD): 212 ---
  KEY20 <-> KEY30
SUMMARY: Factor 212 links 1 specific pairs.

--- SHARED FACTOR (GCD): 89 ---
  KEY2 <-> KEY17
SUMMARY: Factor 89 links 1 specific pairs.

--- SHARED FACTOR (GCD): 82 ---
  KEY3 <-> KEY27
SUMMARY: Factor 82 links 1 specific pairs.

--- SHARED FACTOR (GCD): 57 ---
  KEY8 <-> KEY29
SUMMARY: Factor 57 links 1 specific pairs.

--- SHARED FACTOR (GCD): 53 ---
  KEY20 <-> KEY23
  KEY23 <-> KEY30
SUMMARY: Factor 53 links 2 specific pairs.

--- SHARED FACTOR (GCD): 38 ---
  KEY8 <-> KEY14
SUMMARY: Factor 38 links 1 specific pairs.

--- SHARED FACTOR (GCD): 37 ---
  KEY27 <-> KEY31
SUMMARY: Factor 37 links 1 specific pairs.

--- SHARED FACTOR (GCD): 36 ---
  KEY8 <-> KEY21
SUMMARY: Factor 36 links 1 specific pairs.

--- SHARED FACTOR (GCD): 28 ---
  KEY11 <-> KEY30
SUMMARY: Factor 28 links 1 specific pairs.

--- SHARED FACTOR (GCD): 27 ---
  KEY5 <-> KEY21
  KEY5 <-> KEY6
  KEY6 <-> KEY21
SUMMARY: Factor 27 links 3 specific pairs.

--- SHARED FACTOR (GCD): 26 ---
  KEY1 <-> KEY16
SUMMARY: Factor 26 links 1 specific pairs.

--- SHARED FACTOR (GCD): 25 ---
  KEY22 <-> KEY25
SUMMARY: Factor 25 links 1 specific pairs.

--- SHARED FACTOR (GCD): 24 ---
  KEY4 <-> KEY21
SUMMARY: Factor 24 links 1 specific pairs.

--- SHARED FACTOR (GCD): 23 ---
  KEY7 <-> KEY19
SUMMARY: Factor 23 links 1 specific pairs.

--- SHARED FACTOR (GCD): 19 ---
  KEY14 <-> KEY29
  KEY25 <-> KEY29
  KEY8 <-> KEY25
SUMMARY: Factor 19 links 3 specific pairs.

--- SHARED FACTOR (GCD): 17 ---
  KEY14 <-> KEY32
SUMMARY: Factor 17 links 1 specific pairs.

--- SHARED FACTOR (GCD): 15 ---
  KEY6 <-> KEY22
SUMMARY: Factor 15 links 1 specific pairs.

--- SHARED FACTOR (GCD): 14 ---
  KEY3 <-> KEY11
  KEY3 <-> KEY30
SUMMARY: Factor 14 links 2 specific pairs.

--- SHARED FACTOR (GCD): 13 ---
  KEY1 <-> KEY18
  KEY1 <-> KEY32
  KEY16 <-> KEY18
  KEY16 <-> KEY32
  KEY18 <-> KEY32
SUMMARY: Factor 13 links 5 specific pairs.

--- SHARED FACTOR (GCD): 12 ---
  KEY21 <-> KEY28
  KEY4 <-> KEY28
  KEY4 <-> KEY8
  KEY8 <-> KEY28
SUMMARY: Factor 12 links 4 specific pairs.

--- SHARED FACTOR (GCD): 9 ---
  KEY5 <-> KEY8
  KEY6 <-> KEY8
SUMMARY: Factor 9 links 2 specific pairs.

--- SHARED FACTOR (GCD): 8 ---
  KEY13 <-> KEY21
  KEY13 <-> KEY30
  KEY21 <-> KEY30
  KEY4 <-> KEY13
  KEY4 <-> KEY30
SUMMARY: Factor 8 links 5 specific pairs.

--- SHARED FACTOR (GCD): 7 ---
  KEY11 <-> KEY19
  KEY19 <-> KEY30
  KEY3 <-> KEY19
  KEY3 <-> KEY5
  KEY5 <-> KEY11
  KEY5 <-> KEY19
  KEY5 <-> KEY30
SUMMARY: Factor 7 links 7 specific pairs.

--- SHARED FACTOR (GCD): 6 ---
  KEY4 <-> KEY7
  KEY7 <-> KEY21
  KEY7 <-> KEY28
  KEY7 <-> KEY8
SUMMARY: Factor 6 links 4 specific pairs.

--- SHARED FACTOR (GCD): 5 ---
  KEY6 <-> KEY25
SUMMARY: Factor 5 links 1 specific pairs.

--- SHARED FACTOR (GCD): 4 ---
  KEY11 <-> KEY13
  KEY11 <-> KEY20
  KEY11 <-> KEY21
  KEY11 <-> KEY28
  KEY13 <-> KEY20
  KEY13 <-> KEY28
  KEY20 <-> KEY21
  KEY20 <-> KEY28
  KEY28 <-> KEY30
  KEY4 <-> KEY11
  KEY4 <-> KEY20
  KEY4 <-> KEY9
  KEY8 <-> KEY11
  KEY8 <-> KEY13
  KEY8 <-> KEY20
  KEY8 <-> KEY30
  KEY8 <-> KEY9
  KEY9 <-> KEY11
  KEY9 <-> KEY13
  KEY9 <-> KEY20
  KEY9 <-> KEY21
  KEY9 <-> KEY28
  KEY9 <-> KEY30
SUMMARY: Factor 4 links 23 specific pairs.

--- SHARED FACTOR (GCD): 3 ---
  KEY12 <-> KEY21
  KEY12 <-> KEY22
  KEY12 <-> KEY28
  KEY12 <-> KEY29
  KEY21 <-> KEY22
  KEY21 <-> KEY29
  KEY22 <-> KEY28
  KEY22 <-> KEY29
  KEY28 <-> KEY29
  KEY4 <-> KEY12
  KEY4 <-> KEY22
  KEY4 <-> KEY29
  KEY4 <-> KEY5
  KEY4 <-> KEY6
  KEY5 <-> KEY12
  KEY5 <-> KEY22
  KEY5 <-> KEY28
  KEY5 <-> KEY29
  KEY5 <-> KEY7
  KEY6 <-> KEY12
  KEY6 <-> KEY28
  KEY6 <-> KEY29
  KEY6 <-> KEY7
  KEY7 <-> KEY12
  KEY7 <-> KEY22
  KEY7 <-> KEY29
  KEY8 <-> KEY12
  KEY8 <-> KEY22
SUMMARY: Factor 3 links 28 specific pairs.

--- SHARED FACTOR (GCD): 2 ---
  KEY1 <-> KEY11
  KEY1 <-> KEY13
  KEY1 <-> KEY14
  KEY1 <-> KEY2
  KEY1 <-> KEY20
  KEY1 <-> KEY21
  KEY1 <-> KEY26
  KEY1 <-> KEY27
  KEY1 <-> KEY28
  KEY1 <-> KEY3
  KEY1 <-> KEY30
  KEY1 <-> KEY34
  KEY1 <-> KEY4
  KEY1 <-> KEY7
  KEY1 <-> KEY8
  KEY1 <-> KEY9
  KEY11 <-> KEY14
  KEY11 <-> KEY16
  KEY11 <-> KEY26
  KEY11 <-> KEY27
  KEY11 <-> KEY34
  KEY13 <-> KEY14
  KEY13 <-> KEY16
  KEY13 <-> KEY26
  KEY13 <-> KEY27
  KEY13 <-> KEY34
  KEY14 <-> KEY16
  KEY14 <-> KEY20
  KEY14 <-> KEY21
  KEY14 <-> KEY26
  KEY14 <-> KEY27
  KEY14 <-> KEY28
  KEY14 <-> KEY30
  KEY14 <-> KEY34
  KEY16 <-> KEY20
  KEY16 <-> KEY21
  KEY16 <-> KEY26
  KEY16 <-> KEY27
  KEY16 <-> KEY28
  KEY16 <-> KEY30
  KEY16 <-> KEY34
  KEY2 <-> KEY11
  KEY2 <-> KEY13
  KEY2 <-> KEY14
  KEY2 <-> KEY16
  KEY2 <-> KEY20
  KEY2 <-> KEY21
  KEY2 <-> KEY26
  KEY2 <-> KEY27
  KEY2 <-> KEY28
  KEY2 <-> KEY3
  KEY2 <-> KEY30
  KEY2 <-> KEY34
  KEY2 <-> KEY4
  KEY2 <-> KEY7
  KEY2 <-> KEY8
  KEY2 <-> KEY9
  KEY20 <-> KEY26
  KEY20 <-> KEY27
  KEY20 <-> KEY34
  KEY21 <-> KEY26
  KEY21 <-> KEY27
  KEY21 <-> KEY34
  KEY26 <-> KEY27
  KEY26 <-> KEY28
  KEY26 <-> KEY30
  KEY26 <-> KEY34
  KEY27 <-> KEY28
  KEY27 <-> KEY30
  KEY27 <-> KEY34
  KEY28 <-> KEY34
  KEY3 <-> KEY13
  KEY3 <-> KEY14
  KEY3 <-> KEY16
  KEY3 <-> KEY20
  KEY3 <-> KEY21
  KEY3 <-> KEY26
  KEY3 <-> KEY28
  KEY3 <-> KEY34
  KEY3 <-> KEY4
  KEY3 <-> KEY7
  KEY3 <-> KEY8
  KEY3 <-> KEY9
  KEY30 <-> KEY34
  KEY4 <-> KEY14
  KEY4 <-> KEY16
  KEY4 <-> KEY26
  KEY4 <-> KEY27
  KEY4 <-> KEY34
  KEY7 <-> KEY11
  KEY7 <-> KEY13
  KEY7 <-> KEY14
  KEY7 <-> KEY16
  KEY7 <-> KEY20
  KEY7 <-> KEY26
  KEY7 <-> KEY27
  KEY7 <-> KEY30
  KEY7 <-> KEY34
  KEY7 <-> KEY9
  KEY8 <-> KEY16
  KEY8 <-> KEY26
  KEY8 <-> KEY27
  KEY8 <-> KEY34
  KEY9 <-> KEY14
  KEY9 <-> KEY16
  KEY9 <-> KEY26
  KEY9 <-> KEY27
  KEY9 <-> KEY34
SUMMARY: Factor 2 links 108 specific pairs.