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 sis 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 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 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.
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
https://cryptodeeptech.ru/lattice-attack — Source
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 sis 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 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 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.
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
https://cryptodeeptech.ru/lattice-attack — Source
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 sis 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 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 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.
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
