Nonce Reuse in ECDSA Signatures with Multiple Keys

Hey everyone, I want to share a cool scenario with ECDSA signatures that seems to involve reusing nonces across different private keys. Here's the setup: Private keys: d1, d2, d3, d4, d5, d6, d7 Nonces: k1, k2, k3 Total signatures: 9 Signature breakdown: d1 signs three times with nonces k1, k2, k3 (or maybe their negatives -k1, -k2, -k3). Nonce k1 (or -k1) is shared by: d1, d2, d3 Nonce k2 (or -k2) is shared by: d1, d4, d5 Nonce k3 (or -k3) is shared by: d1, d6, d7 So it's clear that we have some nonce reuse happening across different private keys, with d1 being the link since it signs with all three nonces. Also, it looks like RFC 6979 wasn't applied here, because otherwise, each signature would have a unique deterministic nonce. ECDSA formula: s = k⁻¹ (z + r·d) mod n We can also express it as: k·s = z + r·d (mod n) In this case, we’ve got: 9 equations and 10 unknowns. Unknowns: Private keys: d1, d2, d3, d4, d5, d6, d7 Nonces: k1, k2, k3 Now here’s my question: Even though it looks like we have one less equation than unknowns (9 equations for 10 unknowns), the way the structure is set up especially with the nonce reuse and d1 being the connector might let us reduce the system a bit. Is there any known method to tackle a system like this? Thanks for any thoughts you might have.

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.

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.

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

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?

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

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.

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.

Hey, interesting problem. and yes there is methods, let me walk through it. The linear algebra Write out all 9 ECDSA equations in the form k·s = z + r·d (mod n): Group 1 (shared nonce k1, so shared r-value r1): where each ε ∈ {+1, −1} accounts for the k vs −k ambiguity) All of these are linear in the unknowns. Now here's the key reduction Within each group, pair the d1-equation with the others to eliminate the shared nonce. For example, from (1) and (2) you eliminate k1 and get a direct linear relation between d1 and d2. Same trick with ( 1 )+( 3 ), ( 4 )+( 5 ), ( 4 )+( 6 ), ( 7 )+( 8 ), ( 7 )+( 9 ). That gives you 6 relations expressing d2, d3, d4, d5, d6, d7 each as an affine function of d1: where αi, βi are known constants derived from the observed (r, s, z) values. I think the 3 remaining equations (one per group) then express each nonce as an affine function of d1: So all 10 unknowns reduce to functions of a single free parameter d1. That's your 1 degree of freedom from the 9-equations-10-unknowns system. Can you close that last degree of freedom? Short answer, not from the linear equations alone, but possibly yes depending on what else you know. If you know any one value, any single private key or nonce, you plug it in and everything else falls out immediately. That's the classic nonce-reuse exploit, just extended across keys. If you know public keys (which are normally public), then you have the additional non-linear constraint that r = x(k·G). Since k1 = γ1·d1 + δ1, you need. That's one equation in one unknown, so conceptually the system is fully determined. The catch is that actually solving this equation head-on is equivalent to ECDLP, which is hard. However, and this is where it gets interesting having multiple such constraints (one per group) plus the lattice-friendly linear structure makes this a good candidate for lattice-based attacks (LLL/BKZ). You'd set up a lattice where short vectors correspond to valid (d1, k1, k2, k3) tuples consistent with all the signatures. With the kind of structure you've described, this has realistic chances of working, especially if the nonces have any bit-length bias or if the curve order isn't too large for practical lattice reduction. There's also the brute-force angle if you can narrow the range of d1 through any side-channel or structural info (say you know some bits of a key), the affine relationships let you verify candidates instantly. The sign ambiguity The ε signs (k vs −k) are not actually a big deal. Since k and −k produce the same r-value, you can observe from the signatures which r-values match. For each group you have at most 2 sign choices for each non-pivot signature, so worst case you try 2⁶ = 64 combinations of the linear system. Each is trivially cheap. Bottom line The system reduces cleanly to 1 free parameter thanks to the pivot structure of d1. The linear part is fully exploitable. Whether you can close the last degree of freedom depends on available side information. With public keys and a lattice approach, it's plausible. With any one leaked scalar, it's trivial. Without either, you're stuck at a parameterized family of solutions which is still a massive reduction from the original key space, and might be enough depending on your setting. Good luck with you're hunt.

Hello, thank you for your response, it’s starting to become much clearer. I have some background in lattice techniques like LLL/BKZ, but only in scenarios where there is a bit leakage on the nonces, not on the keys. Here, I’ve established all the equations linking the private keys d2 to d7 directly to d1, eliminating all the nonces k and testing all combinations of signs ±1. In the data below, the correct combination is (-1, 1, -1, 1, -1, -1) out of the 64 tested. My question is: can LLL/BKZ be combined with brute force to try to solve for the pivot d1? If so, how? P.S.: This is not directly related to the equations below, but I can forge any signature for d1 to d7 where R = Z, capable of solving the equation for k or d. However, I keep running into the same problem: I have neither. The signatures and keys used in the scheme below are valid TEST signatures. Here are the results of the equations linking the private keys d2 to d7 directly to d1, after eliminating all the nonces k and testing all combinations of signs. In the data below, the correct combination is