What do we know about the lattice attack?

To begin with, the  elliptic curve digital signature algorithm (ECDSA)  is a common digital signature scheme that we see in many of our code reviews. It has some desirable properties, but can also be very fragile to recover the private key with a side-channel attack that reveals less than one bit of the secret nonce.

ECDSA is a special form of the digital signature algorithm  (DSA)DSA is a fairly common digital signature scheme, which is defined by three algorithms: key generation, signature, and verification. The key generation algorithm generates private and public keys;  the private key is responsible for creating signatures;  and the public key is responsible for verifying signatures.  The signature algorithm takes a message and a private key as input and generates a signature. The verification algorithm takes a message, a signature, and a public key as input and returns a value of  true or  false, indicating whether the signature is valid.

DSA is defined for any mathematical group, and this scheme is safe as long as the discrete logarithm problem is hard for that group. A commonly used group is the integers modulo a prime number p.

Along with this group, we will have a group generator g and some cryptographically secure  hash  function  H. We can assume that  p , g and  H will be common knowledge.

Key generation works by first randomly selecting a value  x from modulo integers  p . Then the value is calculated y = g^x mod p

The private key of the signature is  x , and the public key is  y . The signing key must be kept secret, as it is what allows signatures to be made.

The signature algorithm creates a signature from the message  m and the secret key x . First, a random group element is generated  k . This is known as a nonce, which is important when it comes to attacks.

Then the values ​​are calculated  r = g^k mod p and s = ( k^-1 ( H ( m ) + xr )) mod p

Here  k^- 1 , is the inverse group, and  H ( m ) is the result of computing the hash m, and interpreting the result as an integer modulo p .

The signature is defined as a pair of  ( r , s ). (Note: if one of the  r or  values s​​is equal to  0, the algorithm restarts with the new value of  k ).

The verification algorithm receives a signature  ( r , s ), a message  m and a public key y as input. Let  ŝ = s^-1 , then the algorithm returns true if and only if  r , s ≠ 0 и r = ( g H ( m ) y r ) ŝ .

This validation check works because  g^H( m ) y^r = g^H(m)+ xr = g^ks, and therefore (g^H(m)y^r)^ŝ = g^k = r

A digital signature scheme is considered secure if it cannot be counterfeited.

Immutability has a formal cryptographic meaning, but at a high level it means that you cannot create signatures without knowing the secret key (unless you have copied an already existing signature created from the secret key). Proven to be  DSAimpossible to fake under the assumption of a discrete log.

The digital signature is defined over the mathematical group. When  DSA used with the group of elliptic curves as this mathematical group, we call it  ECDSAThe elliptic curve group  consists of elliptic curve points, which are pairs of  ( x , y ), which satisfy the equation  y^2 = x^3 + ax + b for some  a , b . For this blog post, all you need to know is that using elliptic curves you can define a finite group, which means you get a group generator,  g (elliptic curve point) , and  addition  and  dot multiplication operations  exactly like this the same as you can with integers. Since they form a finite group, generator,g , will have a finite order,  p. This blog post will not explain or require you to know how these  elliptic curve operations work .

The secret key x  will still be a random value modulo integers  p . ECDSA works the same as  DSA, but with a different group. Now the public key  y is still computed as  y = g^x , except that g is now a point on the elliptic curve. This means that y will also be a point on the elliptic curve (previously y was an integer modulo p ). Another difference is how we calculate the value of r . We still generate a random nonce k as an integer modulo p as before. We will calculate  g^k , but again, g is a point of an elliptic curve, and, therefore,  g^k also. Therefore, we can calculate  ( x^k , y^k ) = g^k and set  r = x^k . Now the meaning s can be computed as before, and we get our signature  ( r , s ), which is still an integer modulo  p , as before. To check, we need to correct for the fact that we computed  r a little differently.

So, as before, we  compute  the value of  ( g^H(m)y^r)^ŝ , but now that value is a point on the elliptic curve, so we take  xthe -coordinate of that point and compare it to our value of  r .

Recovery  of secret keys  from reused nonces NONCES

Now that we understand what it is  ECDSA and how it works, let’s demonstrate its  fragility . Again, since this is a digital signature scheme, it is imperative that the  secret key  is never revealed to anyone other than the person signing the message.

However, if the signer ever issues the signature and also issues the used nonce, the  attacker  can immediately recover the  secret key .

Let’s say I release a signature  ( r , s ) for a message  m and accidentally discover that I’ve used a nonce  k .

Since  s = ( k^-1 ( H ( m ) + xr )), we can easily calculate the secret key:

s = (k^-1(H(m) + xr))

ks = H(m) + xr

ks – H(m) = xr

x = r^-1(ks – H(m))

Therefore, the signer must not only keep their  private key secret , but all of their nonces they have ever generated are secret.

Even if the signer keeps each  nonce NONCES secret , if he accidentally repeats one  nonce NONCES  (even for different messages),  the secret key  can also be  recovered immediately .

Let  ( r , s 1 ) and  ( r , s 2 ) be two signatures created on messages  m 1 and  m 2 (respectively) from the same nonce  k – since they have the same nonce, the r values ​​will be the same, so this is very easy for an attacker to detect:

s1 = k^-1(H(m1) + xr) and s2 = k^-1(H(m2) + xr)

s1 – s2 = k^-1(H(m1) – H(m2))

k(s1 – s2) = H(m1) – H(m2)

k = (s1 – s2)^-1(H(m1) – H(m2))

Once we have recovered the nonce  k using the above formula, we can recover the private key by performing the previously described attack.

Let’s digest this for a moment.

If  the signing nonce NONCES  is ever disclosed, the  secret key can be immediately  recovered , which  breaks our entire signature scheme .

Also, if two nonces ever repeat, no matter what the messages are,  an attacker  can easily detect this and immediately  recover the secret key , again breaking our whole scheme.

It’s pretty fragile and it’s only  light attacks !

But there is a  new  Lattice At tack  which has been described in great detail  (Joachim Breitner and Nadia Heninger)Йоахим Брайтнер и Надя Хенингер

Document  [PDF] :  Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies

In the Bitcoin blockchain, we found a certain transaction:

transaction:  08d917f0fee48b0d765006fa52d62dd3d704563200f2817046973e3bf6d11f1f

for Bitcoin Addresses:  15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E

and we managed to multiply the fake signatures and apply the lattice

where using the  Python script  algorithmLLL.py  with the installation of packages in  GOOGLE COLAB

INSTALL >> SAGE + ECDSA + BITCOIN + algorithm LLL

We managed to get  Private Key to  Bitcoin Wallet from one weak transaction in  ECDSA.

Installation
Installation
Run Bash script: lattice.sh
Run Bash script: lattice.sh
Result in HEX format Private key found!
Result in HEX format Private key found!
File: ONESIGN.txt (ECDSA Signature R, S, Z Value)
File: ONESIGN.txt (ECDSA Signature R, S, Z Value)
We propagated fake signatures for the Python script algorithmLLL.py
We propagated fake signatures for the Python script algorithmLLL.py
File: PRIVATEKEY.txt
File: PRIVATEKEY.txt
File: ADDRESS.txt
File: ADDRESS.txt

Let’s open bitaddress and check:

Checking the private key on the bitaddress website
Checking the private key on the bitaddress website

Private key found!

https://www.blockchain.com/btc/address/15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E

0.001 BTC
0.001 BTC
ADDR: 15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
WIF:  5JCAmNLXeSwi2SCgNH7wRL5qSQhPa7sZvj8eDwxisY5hJm8Uh92
HEX:  31AFD65CAD430D276E3360B1C762808D1D051154724B6FC15ED978FA9D06B1C1 

This video was created for the  CRYPTO DEEP TECH portal  to ensure the financial security of data and secp256k1 elliptic curve cryptography against weak ECDSA signatures in the BITCOIN cryptocurrency

https://youtu.be/YP4Xj6gUcf4 — Video footage

cryptodeeptech@gmail.com – Email for all questions

https://t.me/cryptodeep_tech — Technical support via Telegram

https://cryptodeeptech.ru/lattice-attack – Source

By

Leave a Reply

Your email address will not be published. Required fields are marked *