P2PKH Address Pairs with Reused Nonce k

[peakyclin77]

Hello everyone,

I recently discovered several P2PKH address pairs created in a cloned and biased virtual environment, leading to the reuse of the same nonce r between them.

Observed Transactions:
TX 1

r = 5c16a3fbafc1ef0
Public Key = 956fb654bcb2e061

TX 2 (3 days later)

r = 5c16a3fbafc1ef0
Public Key = 4b20eabe93918281

These transactions send funds to the same address, which itself reuses the nonce k with the same private key.

Potential Security Implications
In a standard ECDSA scheme, using the same r with different private keys resembles a system of equations with two private keys and one common unknown, which typically cannot be solved directly.

However, is it possible that these private key pairs are derived from a shared structure (e.g., k + ?), potentially exposing a vulnerability?

Questions:
Has a similar case been solved before?
Are the private keys in this scenario vulnerable?
Any insights or analysis would be greatly appreciated.

[ABCbits]

I recently discovered several P2PKH address pairs created in a cloned and biased virtual environment, leading to the reuse of the same nonce r between them.

I don't know your goal. But this won't happen if you use RFC 6979. Since different key with same message hash always leads to different k value.

However, is it possible that these private key pairs are derived from a shared structure (e.g., k + ?), potentially exposing a vulnerability?

I believe this StackExchange answer partially answer answer your question, https://crypto.stackexchange.com/a/72112.

[mcdouglasx]

Are the private keys in this scenario vulnerable?

Without knowing the nonce, if there are two signatures for two different private keys sharing the same nonce k, it is not possible to derive the private keys from the two signatures, even if it is known that the same nonce was used in both.

In cases where two signatures with identical nonces are used for the same private key:

https://bitcointalk.org/index.php?topic=5495568


If the nonce k is known, you can solve these equations to find the respective private keys

Code:

Pcurve = 115792089237316195423570985008687907853269984665640564039457584007908834671663
N = 115792089237316195423570985008687907852837564279074904382605163141518161494337

def modinv(a, b):
    lm, hm = 1, 0
    low, high = a % b, b
    while low > 1:
        ratio = high // low
        nm, new = hm - lm * ratio, high - low * ratio
        lm, low, hm, high = nm, new, lm, low
    return lm % b

k = 64338999543366  # Example of a known nonce

# msg 1
hash1 = int("6eb1db1a144d94df76be0d2d2721df7839aff7b5899873a1ed9013f3fbbbd0d0", 16)
r1 = int("bda653c3ebcbbfd1d550462d4030c140bafc4ed9ca17d32ac598a7cedb942947", 16)
s1 = int("7ebff2f8199f0700e80297659424ca7eda26dde1afc1d226c08c377896b0ebda", 16)

# msg 2
hash2 = int("619e86eb7f8689b2b1ed260be14fcab2b2b31ae5e6a7df5e393ec4e272bd6f37", 16)
r2 = int("bda653c3ebcbbfd1d550462d4030c140bafc4ed9ca17d32ac598a7cedb942947", 16)
s2 = int("f37ba9033df153303c893a029b7aa80b3eb0e1d6099b14133661658455375487", 16)

privKey1 = ((s1 * k - hash1) * modinv(r1, N)) % N
privKey2 = ((s2 * k - hash2) * modinv(r2, N)) % N

print("Private Key 1:", privKey1)
print("Private Key 2:", privKey2)

[peakyclin77]

more context:

Ax: 1AxP2pkhFakeAddressExample1111
a1: 1A1P2pkhFakeAddressExample2222
a2: 1A2P2pkhFakeAddressExample3333
a3: 1A3P2pkhFakeAddressExample4444
a4: 1A4P2pkhFakeAddressExample5555
a5: 1A5P2pkhFakeAddressExample6666
a6: 1A6P2pkhFakeAddressExample7777
a7: 1A7P2pkhFakeAddressExample8888
a8: 1A8P2pkhFakeAddressExample9999

Transactions executed:
Multiple addresses (a1, a2, a3, ...) sent funds to Ax.
Ax reused the same nonce 𝑘 twice with the same private key → Ax is compromised.
Ax also shared the same nonce 𝑘 with some addresses (a1, a2, a3), meaning these addresses are compromised as well.

In other transactions, a few days apart:

a4 and a5 used the same 𝑟 : r = 5c16a3fbafc1ef0
a7 and a8 also used the same 𝑟 : r = 4b20eabef45faf0


Questions:

Could Ax be considered a "master key" in this scenario?

Are a4, a5, a6, and a7 vulnerable?

Given that a4 and a5 shared the same 𝑟 and a7 and a8 also shared an 𝑟 is there an exploitable weakness here?


There are 4 BTC at risk in these addresses, so any in-depth analysis would be greatly appreciated.

[mcdouglasx]

snip

What are you using for the transactions? This practice of repeating nonces is insecure. If Ax made two signatures with the same nonce, its private key is exposed. From there, you can calculate the nonce, and once the nonce is obtained, you can get the private keys of all the addresses that share the same nonce. Transfer the funds to a secure location and stop using whatever you're using to send the transactions.

[peakyclin77]

Sometimes in the same transaction

Trx 1 :

Ax: 1AxP2pkhFakeAddressExample1111>>
A1: 1A1P2pkhFakeAddressExample2222>>
A2: 1A2P2pkhFakeAddressExample3333>>                Ax: 1AxP2pkhFakeAddressExample1111
A3: 1A3P2pkhFakeAddressExample4444>>
A4: 1A4P2pkhFakeAddressExample5555>>


⸻

The wallets I am interested in are those that have completely reused the nonce r between addresses in these transactions:

Trx 2:
A4: 1A4P2pkhFakeAddressExample5555 >>1AxP2pkhFakeAddressExample1111

Trx 3:
A5: 1A5P2pkhFakeAddressExample6666 >>1AxP2pkhFakeAddressExample1111

exemple:

TRX 2 :
R = 00b272eff27c410cd79b465a893d084ac0513e5cf43bff538c238e0247fc2a3dc6
S = 6d9b20df51a40139f080ced53f1bfd66c925979a886d0309f0407e3e283878cd
Z = c2b9a5609f88cdb943d3cf9cae1b284e187583a583ea9f8c39aac487779c003e
A4PublicKey = 037562e9f0388bc4499fa46111f59824355be953db0a3a016ee152a82059711fa2

TRX 3 :
R = 00b272eff27c410cd79b465a893d084ac0513e5cf43bff538c238e0247fc2a3dc6
S = 017b939c4cd9d8c648c69d36b6ba424c641d9afeea2fd06d62b273e15a688c6a
Z = ef64d2f01db818ab0b30e4674f6ede12c145b83784e46e7c0512a72f7c35469e
A5PublicKey = 025b511205afcd38e2f96294cb08cf78415999d78733ef84409293530a43f077c2

I already have Ax 1AxP2pkhFakeAddressExample1111 private key, Thanks for you answers by the way

[mcdouglasx]

Sometimes in the same transaction

Trx 1 :

Ax: 1AxP2pkhFakeAddressExample1111>>
A1: 1A1P2pkhFakeAddressExample2222>>
A2: 1A2P2pkhFakeAddressExample3333>>                Ax: 1AxP2pkhFakeAddressExample1111
A3: 1A3P2pkhFakeAddressExample4444>>
A4: 1A4P2pkhFakeAddressExample5555>>


⸻

The wallets I am interested in are those that have completely reused the nonce r between addresses in these transactions:

Trx 2:
A4: 1A4P2pkhFakeAddressExample5555 >>1AxP2pkhFakeAddressExample1111

Trx 3:
A5: 1A5P2pkhFakeAddressExample6666 >>1AxP2pkhFakeAddressExample1111

With r1 = r2, s1 ≠ s2, h1 ≠ h2.

I already have 1AxP2pkhFakeAddressExample1111 private key, Thanks for you answers by the way

If you know the private key for Ax, you know the private keys for the addresses that share a nonce with the signatures of Ax. Regardless of whether some keys have been affected or not, funds should be sent to a safe place. Even if they have not been affected, for example A6, you run the risk that the nonce of their signatures could be compromised at any moment when an insecure signature reuses one of its nonces or vice versa. Your method for build tx is vulnerable and should not be used.

[peakyclin77]

mcdouglasx I only have the private key for Ax; I didn't recover the ones that shared the nonce with Ax because they are empty. The addresses that interest me are those that shared between themselves sending to Ax, specifically A4 and A5, which had a three-day interval between their transactions. We know that we can't solve two equations with three unknowns, but in this case, we have Ax

[mcdouglasx]

mcdouglasx I only have the private key for Ax; I didn't recover the ones that shared the nonce with Ax because they are empty. The addresses that interest me are those that shared between themselves sending to Ax, specifically A4 and A5, which had a three-day interval between their transactions. We know that we can't solve two equations with three unknowns, but in this case, we have Ax

So far, the nonce shared between those 2 signatures is not shared with Ax. I don't know why you are inferring any relationship between Ax and (A4, A5). I suppose you want to explore the possibility that A4 and A5 are children of Ax. If that is the case, you shouldn't be concerned with the nonces between A4 and A5, but rather deriving keys from Ax. Another perspective would be to extract the nonces from the signatures you have access to and see if they follow some kind of pattern that allows you to predict the nonce used by A4 and A5.

[peakyclin77]

I suppose that A1, A2, A3, A4, A5, A6, A7, A8, etc. are children of Ax, as the transactions from A1, A2, and A3, which shared the same nonce as Ax, were made towards Ax on the same date, sometimes even within the same transaction, down to the millisecond. I would like to remind you that these are addresses discovered on the blockchain dating back to 2015, likely generated in a cloned VM.

[coolmib]

Let's dive right into the case that happened before. According to information from
https://christian-rossow.de/publications/btcsteal-raid2018.pdf
we are presented with the top 10 of most reused r value that have ever happened,
1st Rank:
0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 2,276,718.
Let's use some of it.
txid = 003bf42c785dc750ee5280a62c91bb0e32b2829b7f446c333aa346ea7972e80a (single Address)
txid = 0000ad6683b802442afcdd96743dc889c01ec978b0db2c92bd1e550ccda4b7c1(2 Addresses)

using tools from iceland2k14 : https://github.com/iceland2k14/rsz

Code:

python3 getz_input.py -tx 003bf42c785dc750ee5280a62c91bb0e32b2829b7f446c333aa346ea7972e80a

Result :

[Input Index #: 0]
     R: 3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
     S: 37241abae7c5160855be545f69b22652d0675394b2ec51c406c047481489bfad
     Z: 407267215a54d1c3a426af0c07adc82ca005cdbe78b93e1c541bacdbeb837930
PubKey: 0200a1541e7dd887595db87a5823e831608ff74cd3ac266e4d35bdea169ac1264a
======================================================================
[Input Index #: 1]
     R: 3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
     S: 17c51c7e43b18c11d24420bb2ac0d577db0f567b1cb8d7c906017e578af71752
     Z: d021e63fac5e96bee5e3c8de2726709978093abe9b774b37b464409a9867edfe
PubKey: 0200a1541e7dd887595db87a5823e831608ff74cd3ac266e4d35bdea169ac1264a
======================================================================
.
.
.

we just need 2 set of rsz pairs
Now.. Lets try to get the PrivKey and k-nonce

Code:

import secp256k1 as ice
G = ice.scalar_multiplication(1)
N = ice.N

def calculate_d_k(r,s1,s2,z1,z2):
    s_diff = (s1 - s2) % N
    z_diff = (z1 - z2) % N
    try:
        s_diff_inv = pow(s_diff, -1, N)
        r_inv = pow(r, -1, N)
    except ValueError:
        print("Modular inverse does not exist for given s_diff or r.")
        return None
    k = (z_diff * s_diff_inv) % N
    dA = ((s1 * k - z1) * r_inv) % N
    return k, dA

r = int('3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63',16)
s1 = int('37241abae7c5160855be545f69b22652d0675394b2ec51c406c047481489bfad',16)
z1 = int('407267215a54d1c3a426af0c07adc82ca005cdbe78b93e1c541bacdbeb837930',16)
s2 = int('17c51c7e43b18c11d24420bb2ac0d577db0f567b1cb8d7c906017e578af71752',16)
z2 = int('d021e63fac5e96bee5e3c8de2726709978093abe9b774b37b464409a9867edfe',16)
pubkey = '0200a1541e7dd887595db87a5823e831608ff74cd3ac266e4d35bdea169ac1264a'
Dk, privkey = calculate_d_k(r,s1,s2,z1,z2)
print(f"k-Nonce : {hex(Dk)}")
print(f"PrivKey : {hex(privkey)}")
print(ice.scalar_multiplication(privkey).hex() == ice.pub2upub(pubkey).hex()) 

Result :
k-Nonce : 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0
PrivKey : 0xa2df1308b53e3fac548c630d75715960a3a38eb0e2b920e5fbbb79ad9cbe4715
True

2nd txid

Code:

python3 .\getz_input.py -txid 0000ad6683b802442afcdd96743dc889c01ec978b0db2c92bd1e550ccda4b7c1

[Input Index #: 0]
     R: 3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
     S: 3530d87f6b67f398d9d3e3b4c74902b171f041b48be4f5b7e0cbeca4455533f0
     Z: 8b5c8a445b469f121131a5c72796a06ac7d8a1cff77bbb452837fb7e1d44ab39
PubKey: 030be93b33bf3126af00f79ab309676d47fb8b2e2c4cbbae76fd52b9d78bc8bcd7
======================================================================
[Input Index #: 1]
     R: 3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
     S: 64801f6a42e9fdeb21fe29c56c2d69e306fb6046a2a60d7b372c374bcaca2edf
     Z: b6125c89387fd212c6a2dd30ce55e0ed1d055cee85caf5f373dbb32c22f309c5
PubKey: 0225c072edb4f3112d769e8743bc46007664083b41331023c0be1630bac6870b76

Using the code from @mcdouglasx

Code:

Pcurve = 115792089237316195423570985008687907853269984665640564039457584007908834671663
N = 115792089237316195423570985008687907852837564279074904382605163141518161494337

def modinv(a, b):
    lm, hm = 1, 0
    low, high = a % b, b
    while low > 1:
        ratio = high // low
        nm, new = hm - lm * ratio, high - low * ratio
        lm, low, hm, high = nm, new, lm, low
    return lm % b

k = 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0  # Example of a known nonce

# msg 1
hash1 = int("8b5c8a445b469f121131a5c72796a06ac7d8a1cff77bbb452837fb7e1d44ab39", 16)
r1 = int("3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63", 16)
s1 = int("3530d87f6b67f398d9d3e3b4c74902b171f041b48be4f5b7e0cbeca4455533f0", 16)

# msg 2
hash2 = int("b6125c89387fd212c6a2dd30ce55e0ed1d055cee85caf5f373dbb32c22f309c5", 16)
r2 = int("3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63", 16)
s2 = int("64801f6a42e9fdeb21fe29c56c2d69e306fb6046a2a60d7b372c374bcaca2edf", 16)

privKey1 = ((s1 * k - hash1) * modinv(r1, N)) % N
privKey2 = ((s2 * k - hash2) * modinv(r2, N)) % N

print("Private Key 1:", hex(privKey1))
print("Private Key 2:", hex(privKey2))

Result :
Private Key 1: 0x33c9621cb97649655c78fdc38fdc8c4d1f4d6e8b25aca9bec93b39fec7866a74 <== Correct
Private Key 2: 0x8e1d9939700d8571ae5f869ab0cb33fe5ee8ca1001a45f9dc09457b7decdd7e8 <== incorrect

What I missed?

[amaclin1]

Let's dive right into the case that happened before. According to information from
https://christian-rossow.de/publications/btcsteal-raid2018.pdf
we are presented with the top 10 of most reused r value that have ever happened,
1st Rank:
0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 2,276,718.
Let's use some of it.
txid = 003bf42c785dc750ee5280a62c91bb0e32b2829b7f446c333aa346ea7972e80a (single Address)

As far as I remember, this 'technology' I used 10 years ago to consolidate spam/dust outputs.
https://bitcointalk.org/index.php?topic=1175321
My transactions had smaller size and were included in blocks before other steal bots.
Of course, I can sign a message with a private key of 1aamWKicYga3AN8UgywedHzEG12KbUUJJ ( recepient in tx https://www.blockchain.com/explorer/transactions/btc/003bf42c785dc750ee5280a62c91bb0e32b2829b7f446c333aa346ea7972e80a )

By the way, what do you think about this transaction?
Yes, this is not p2pkh, but p2wsh. Do you see R and S?  

[peakyclin77]

In the scenario I mentioned earlier in the thread, where the same nonce 𝑟 is reused between different public keys, I have noticed that sometimes we observe two instances of reuse between two keys, or even three instances of reuse among three different keys. Given this situation, is there a way to recover the private keys associated with these compromised addresses through a nonce reuse attack or any other method?

Since we have two equations and three unknowns in this case, it seems like it might be possible to solve for the private keys. I am aware that there are approximately 4 BTC at stake in this situation.

Any insights on how to approach this attack, or if there are existing tools or techniques to recover the private keys, would be highly appreciated.

Thanks!

[amaclin1]

Given this situation, is there a way to recover the private keys associated with these compromised addresses through a nonce reuse attack or any other method?

With any valid {R,S,Z,P} you are able to create a great number of valid {R,S,Z₁,P₁} but this knowledge can not help you to find privkey of P

[peakyclin77]

amaclin1, these P2PKH addresses are compromised no matter what—around 4 BTC is at risk. The transactions accidentally reused the R value between addresses due to a biased PRNG. I’m looking for a brute-force method to recover the nonce or any other approach. I already have a private key that might be the master key for all these

[amaclin1]

amaclin1, these P2PKH addresses are compromised no matter what—around 4 BTC is at risk. The transactions accidentally reused the R value between addresses due to a biased PRNG. I’m looking for a brute-force method to recover the nonce or any other approach. I already have a private key that might be the master key for all these

Do you understand me?
I can provide you a number of valid {R,S,Z_n,P_n} for any given R,S
Without knowledge how 'K' was choosen this information has no sense.
Just a math.

[peakyclin77]

amaclin1 Have you ever seen a similar exploitable case or an optimized brute-force method for this kind of situation?

[peakyclin77]

hello send me a message

[amaclin1]

Have a look:

Code:

void ECDSAtest::run ( )
{
  const MyKey32 r ( MyByteArray ( "correct horse" ).sha256 ( ) );
  const MyKey32 s ( MyByteArray ( "battery staple" ).sha256 ( ) );
  const QByteArray sig ( Crypto ( ).der ( r, s ) );
  for ( int i ( 0 ); i < 10; i++ )
  {
    const MyKey32 z ( MyByteArray ( ).putInt64 ( rand ( ) ).sha256 ( ) ); // message digest (random)
    const QByteArray p ( z.recover ( sig ) );                             // public key
    xassert ( z.verifyECDSA ( p, sig ) );
    printf ( "r = %s\n", r.toHex ( ).constData ( ) );
    printf ( "s = %s\n", s.toHex ( ).constData ( ) );
    printf ( "p = %s\n", p.toHex ( ).constData ( ) );
    printf ( "z = %s\n\n", z.toHex ( ).constData ( ) );
  }
}

and the output is:

Code:

r = 4104d36f8da2c254349f85836793ebe029e0c957063a34c91c2e9203187b5631
s = 11e2b7895e7b3dca8df8d0cf965fde793b82cd39242774277ca90d72d09bfd59
p = 033f4ba28ee3fef48745feeafeebed4c31ef88c76476967d54555c60d003c3b989
z = b8282e78d87c2a42f7c0f5b543c0d7760d3fe5a3860a25c20ec57ddaa4d80b81

r = 4104d36f8da2c254349f85836793ebe029e0c957063a34c91c2e9203187b5631
s = 11e2b7895e7b3dca8df8d0cf965fde793b82cd39242774277ca90d72d09bfd59
p = 02b4f7c02eddc95020c978367c417e786cd1a2d790d4b160814aa0e79cb2524318
z = 534ad60f6997e0e64bcc9a3fefebdb6e91132733afbbe73b22df4d09fafa2e5f

r = 4104d36f8da2c254349f85836793ebe029e0c957063a34c91c2e9203187b5631
s = 11e2b7895e7b3dca8df8d0cf965fde793b82cd39242774277ca90d72d09bfd59
p = 0371b1d0ea2942e7721f45c11b504fe772e7a96580bf1f690fb2977de03b1b93d1
z = ac1e5fe366116f29501c2d702dc50c7a22e930d89bd33ccc1ade2453a258d03b

r = 4104d36f8da2c254349f85836793ebe029e0c957063a34c91c2e9203187b5631
s = 11e2b7895e7b3dca8df8d0cf965fde793b82cd39242774277ca90d72d09bfd59
p = 020b0e8d33144b7eb145923b3a1351925a8c8a505db3fa7449f5e584709c94a44d
z = f09a861da05c0e34a4f2e389d394ed3315b2fdd8ac2fa99eb57c02e49b33b9d5

r = 4104d36f8da2c254349f85836793ebe029e0c957063a34c91c2e9203187b5631
s = 11e2b7895e7b3dca8df8d0cf965fde793b82cd39242774277ca90d72d09bfd59
p = 03cfaa7ed8c33610ffa7d5259a1ec6f4003d1c24f90aa2227c7227b7e0a53aa688
z = 154a3840fbdc243a8e2d52bb79c9b3d5165c49046534c7b3deb384ecf614bcbe

r = 4104d36f8da2c254349f85836793ebe029e0c957063a34c91c2e9203187b5631
s = 11e2b7895e7b3dca8df8d0cf965fde793b82cd39242774277ca90d72d09bfd59
p = 02017f1fd37181f1e182420e40a647c28d8fadd2443eeaa088573e9b95423994c5
z = bb52d7b4bc776729c8766870aa442376da952a3047c02f113728a6d1b4bd92f5

r = 4104d36f8da2c254349f85836793ebe029e0c957063a34c91c2e9203187b5631
s = 11e2b7895e7b3dca8df8d0cf965fde793b82cd39242774277ca90d72d09bfd59
p = 032d55b0f1cf15a0fcae739fde423d7f6e2cbc62318386ae414ea8cca013feec45
z = 94625d3d0f084c54f5e9c44c64ef4c4613a14580bff776b0d52451e977fb8e7e

r = 4104d36f8da2c254349f85836793ebe029e0c957063a34c91c2e9203187b5631
s = 11e2b7895e7b3dca8df8d0cf965fde793b82cd39242774277ca90d72d09bfd59
p = 039032f16bbb8843b7467371f0f257216852f7ac68f05c4a09e8aff4fb81d91b6f
z = 9c2071cebfd2c277d34c41f1f7872ee12d0a37c2738fdf18e3feaa8e9679c61b

r = 4104d36f8da2c254349f85836793ebe029e0c957063a34c91c2e9203187b5631
s = 11e2b7895e7b3dca8df8d0cf965fde793b82cd39242774277ca90d72d09bfd59
p = 020f66af536b042a29880f1e967ab25408abd5fa4eb77a7fcd801ee51aa1fc7a35
z = 24aa9e69d9381ddc4c39a5f1b78eb93d3ff446ceea74c1c4d2e9a65142e465aa

r = 4104d36f8da2c254349f85836793ebe029e0c957063a34c91c2e9203187b5631
s = 11e2b7895e7b3dca8df8d0cf965fde793b82cd39242774277ca90d72d09bfd59
p = 02260f3b4c1f525f47dc02832c534c7b96e317d4e342c9a0657d21766572e1d7b1
z = e5c2748fb249a4d2ebaaa5ed2b22a4d745a60e1256aecfacc6a82cd36e3ee685

[peakyclin77]

amaclin1,

Thanks, I understand now. As mentioned earlier, all these addresses are compromised. For one address containing just over 2 BTC, there are 6 RSZ signatures in total. The second signature for this address shared the same rr with two other empty addresses, but it was the first to use this rr. In these 6 signatures, there are similar patterns, such as prefixes and fixed bits.