Show Posts
|
Pages: [1] 2 3 4 »
|
Can anyone explain in a more simple way how to run this lattice attack? Thanks
|
|
|
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/issuesps 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.
|
|
|
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/issuesps 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.
|
|
|
This is some random code I have o my PC, it coverts HEX to WIF in python import codecs import hashlib PK0 = "00000000000000000000000000000008000000000000000000FFFFFFFFFFFFFFFF" PK1 = '80'+ PK0 PK2 = hashlib.sha256(codecs.decode(PK1, 'hex')) PK3 = hashlib.sha256(PK2.digest()) checksum = codecs.encode(PK3.digest(), 'hex')[0:8] PK4 = PK1 + str(checksum)[2:10] def base58(address_hex): alphabet = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz' b58_string = '' leading_zeros = len(address_hex) - len(address_hex.lstrip('0')) address_int = int(address_hex, 16) while address_int > 0: digit = address_int % 58 digit_char = alphabet[digit] b58_string = digit_char + b58_string address_int //= 58 ones = leading_zeros // 2 for one in range(ones): b58_string = '1' + b58_string return b58_string
WIF = base58(PK4) print(WIF) #keyint = int(PK0, 16) #print(keyint) #print(hex(keyint)) #print(keyint)
|
|
|
what will be time for kangaroo to find privkey on ranges:
2**115 bit 2**110 bit 2**105 bit 2**95 bit
?
Just run the tool 4 times and there's your answer
|
|
|
Someone with tons of computing power, what's the average time your kangaroo is showing for solving #120?
I honestly don't think this is necessarily the case, i mean if you had 1000 people looking in micro random 64 bit ranges, inevitably, one of them is gonna land on the right range and solve the key.. Although no one really knows if that was what happened, but you have to know that the bigger the range, the more it's gonna be about luck than about computing power .. you need couple hundred Telsa 100 to solve puzzle #120 within two months . If such computing power was available to a single person already, he would have sold more than just #120 .. he would have used them to crack open small range puzzles as well .. so i guess those who have huge computing power are busy doing something else making them way more money than our beloved puzzle would .. Lucky for us though, otherwise we stand no chance with our teeny tiny personal rigs So how many years is your rig showing? for example I;m getting around 1000 years on a laptop
|
|
|
Thanks, but there is only an .exe and no source code to look at unfortunately, only the readme inside the zip.
It's closed-source I believe, so it only works for Windows. Were you looking to run it on Linux? If you're just running CPU search, WINE is going to be super slow but it should work under it correctly. Ok, thanks. Yeah, running on Ubuntu 20.04. Even without the --continue option you can use the last found key position as starting range on your next search. Just look for shorter pattern so the software will dump keys every 20-30min, that way you will always know "where you are".
|
|
|
Someone with tons of computing power, what's the average time your kangaroo is showing for solving #120?
|
|
|
Here is my modified version of "gen_data.py": #!/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 <https://www.gnu.org/licenses/>. #
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. Thanks for sharing, but I this code is too much for me, can't get it to work. I hope someone will sort it out soon and explain the attack in a understandable way
|
|
|
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. Can you share your modified code?
|
|
|
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.
That's true, but GitHub repository of this tool ( lattice-attack) already state what kind of attack it perform. It uses linear matrices and lattice basis reduction to solve a Shortest Vector Problem from a Hidden Number Problem.
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/. Did you even read this thread buddy? Both no working OP script and the article you shared is already there and it's useless. Still waiting for working script...thanks in advance!
|
|
|
Can someone post a working python script for basic lattice attack? Thanks
|
|
|
Just a lazy solution: import java.math.BigInteger;
public class K { public static void main(String[] args) { BigInteger start = new BigInteger("0552e025571c01bcd9eda59365a2fb3ae0bd7547dfeeeb13d971d848bcbf0467", 16); BigInteger stride = BigInteger.valueOf(58L).pow(32);//depends on the position of most-right unknown character BigInteger range = BigInteger.valueOf(58L).pow(5);//5=number of unknown characters BigInteger end = start.add(range); System.out.println("START: "+start.toString(16)); System.out.println("END: "+end.toString(16)); System.out.println("STRIDE: "+stride.toString(16)); } } Going back to this version of Kangaroo: I think there is still something wrong with calculations with checksum - for longer ranges (>6 unknown characters) it does not return result, while when there is case without checksum (just a stride) it works good. how do i run this java. i have a question, does this work with missing chars at the end of the wif, really want to know, stuck on reading here past 2 days. He has a java one that will work pretty well and fast for 7-8 characters missing off the end. For the method in this topic, it won't do any good because your stride will be "1"...meaning check every key, in order. Here is a python script I threw together real quick if you are more familiar with it: #First, enter the start range as start = "starting range like example below" start = "552e025571c01bcda0297c22731d74becbd2cc13a750046ca49b5e9006a2c72" # <<<<------ enter starting range in hex startrange = int(start, 16) #leave alone
#This determines the range that determines the start and end range; depends on the number of unknown characters; enter that number in ukchar = int(x) ukchar = int(5) # <<<<------ enter the number of unknown characters addtostart = int(pow(58, ukchar)) endrange = hex(startrange + addtostart).rstrip("L").lstrip("0x")
#This determines the stride which is based on the position of the most right unknown character; enter that number in mostright = int(x) mostright = int(32) # <<<<------ enter the position of the most right unknown character stride = int(pow(58, mostright))
#This prints out starting range, ending range, and stride; leave alone print ("Starting range: " + hex(startrange).rstrip("L").lstrip("0x")) print ("Ending range : " + endrange) print ("Stride : " + hex(stride).rstrip("L").lstrip("0x"))
What exactly are we doing with this tool? I am using WP's python script with PawGo's Kangaroo to get the range & stride and it's all working as it supposed to, but I don't understand this tool at all tbh How can I begin solving #120 for example by using it's public key and some random WIF within the range? I don't get it
|
|
|
How can I search part of address using bitcrack, for example search for "16jY7" or how can I do a linear search instead of random using vanity?
BitCrack can not search "16jY7" , you use vanity to find is correct tools I think vanitysearch tools are not random but seed start is random and continue unfortunate can not custom seed start search try using other modify/fork of vanitysearch like bit crack many developers modify https://github.com/WanderingPhilosopher/VanBitCrakcenShttps://github.com/Telariust/VanitySearch-bitcrackThese tools can search "16jY7" in the range you want Thanks! in case anyone else needs it VanBitCrakcenS works perfectly, haven't tried the other tool Edit: After some more testing I found that it does random search after all not linear.
|
|
|
How can I search part of address using bitcrack, for example search for "16jY7" or how can I do a linear search instead of random using vanity?
|
|
|
So there are 2^96 different private keys in the entire 2^256 space that can "unlock" for example this address: 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN (Puzzle 64)? Can anyone confirm this?
Yes exactly and for a simple fact : 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN (and every other wallet address of this type) is encoded on 160 bits (and not on 256 bits like the majority of other crypto parameters in bitcoin protocol) 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN is base58 encoded and is 3ee4133d991f52fdf6a25c9834e0745ac74248a4 (20*8bytes = 160bits) in hexadecimal ( Unlike public keys that are encoded on 256 bitsa simple wallet address (p2pkh) is simply obtained by the function hash160(public_key) So if you have the possibility to browse the entire 1-2^256 space and to compute the hash160 function for every hash160(public_key) derived from 1-2^256 private keys you will find an average of 2^(256-160) = 2^96 public key with hash160=16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN . But even if 2^96 seems big its far away smaller from 2^256. And it's pretty impossible to have a collision between two random public key in the using age of bitcoin. But theoretically if you find any public key derived from a private key with hash160(public_key)= '16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN' or = to any other non zero wallet address you will able to unlock the coins. Because the verification in the bitcoin protocol to prove that you are the owner of the private key is simply "have you signed the transaction with the private key associated to a public key that gives 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN (or any other target address) with hash160 function Thanks for the reply! I'm missing something...So these addresses will have different public keys or not? Can one private key control 2^96 different wallets? For example when I import some random private key in Electrum wallet and click on "sweep funds" am I sweeping one wallet or 2^96 different wallets? You simply got it backwards .. One private key does NOT open 2^96 addresses instead, One address can be opened by 2^96 private keys See the difference? Yeah I get it thanks. Still the odds of finding one remain almost the same if you scan through 2^255
|
|
|
So there are 2^96 different private keys in the entire 2^256 space that can "unlock" for example this address: 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN (Puzzle 64)? Can anyone confirm this?
Yes exactly and for a simple fact : 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN (and every other wallet address of this type) is encoded on 160 bits (and not on 256 bits like the majority of other crypto parameters in bitcoin protocol) 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN is base58 encoded and is 3ee4133d991f52fdf6a25c9834e0745ac74248a4 (20*8bytes = 160bits) in hexadecimal ( Unlike public keys that are encoded on 256 bitsa simple wallet address (p2pkh) is simply obtained by the function hash160(public_key) So if you have the possibility to browse the entire 1-2^256 space and to compute the hash160 function for every hash160(public_key) derived from 1-2^256 private keys you will find an average of 2^(256-160) = 2^96 public key with hash160=16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN . But even if 2^96 seems big its far away smaller from 2^256. And it's pretty impossible to have a collision between two random public key in the using age of bitcoin. But theoretically if you find any public key derived from a private key with hash160(public_key)= '16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN' or = to any other non zero wallet address you will able to unlock the coins. Because the verification in the bitcoin protocol to prove that you are the owner of the private key is simply "have you signed the transaction with the private key associated to a public key that gives 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN (or any other target address) with hash160 function Thanks for the reply! I'm missing something...So these addresses will have different public keys or not? Can one private key control 2^96 different wallets? For example when I import some random private key in Electrum wallet and click on "sweep funds" am I sweeping one wallet or 2^96 different wallets?
|
|
|
So there are 2^96 different private keys in the entire 2^256 space that can "unlock" for example this address: 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN (Puzzle 64)? Can anyone confirm this?
|
|
|
NEW PRICE!
$20 ONLY!
BID NOW!
|
|
|
|