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 `DSA`

impossible 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 `ECDSA`

. *The 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

*exactly like this the same as you can with integers. Since they form a finite group, generator,*

__dot multiplication operations__`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

computethe value of`( g^H(m)y^r)^ŝ`

, but now that value is a point on the elliptic curve, so we take`x`

the -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

attackercan 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

, but all of their nonces they have ever generated are secret.private key secret

Even if the signer keeps each

nonce`NONCES`

secret , if he accidentally repeats onenonce`NONCES`

(even for different messages),can also bethe secret keyrecoveredimmediately .

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, thesecret keycan be immediately, whichrecovered.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`

.

**Let’s open bitaddress** and check:

__Private key found!__

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

```
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**