lattice-attack || how to run without error

[casinotester0001]

And with these signatures, can you explain how the lattice-method works?

No, because I don't know that yet. Also because I don't think 100-bit keys were broken by lattice attacks. More probably they were beaten by Kangaroo or similar algorithms that don't require valid signatures.

I wanted to say, take the 100 bit puzzle data but show how it works with 256 bit. You can create signatures as there is a private key and explain how this lattice method works in the 256 bit range with examples. 

[casinotester0001]

here example:

1.) if we have 1 transaction with remarks:
 privatekey up to 128 bit : with nonce up to 128 bit -> lattice attack will show privatekey

2.) if we have 100 transaction with remarks:
 privatekey up to 2**20 bit : with nonce up to 253 bit -> lattice attack will show privatekey

3.) if we have 480 transaction with remarks:
 privatekey up to 2**10 bit : with nonce up to 254 bit -> lattice attack will show privatekey

4.) if we have 10 transaction with remarks:
 privatekey up to 2**200 bit : with nonce up to 240 bit -> lattice attack will show privatekey

For 256-bit ECDSA with 8-bit leakage, I guess 50 (even 40) is enough.
source: https://crypto.stackexchange.com/questions/98323/help-breaking-ecdsa-with-biased-nonces

[COBRAS]

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.

Lattice attack can be used only then if we define what we want to take as result. WE have a lot of "lattice attack" types like: CVP, SVP Doubled CVP, and of course mysthic "SLE method".  

all of this lattice attack is designed for something to find. YOU CANT USE "codes" and put there r,s,z without some "modification" to algorithm and waiting for good result.

 
here example:

1.) if we have 1 transaction with remarks:
 privatekey up to 128 bit : with nonce up to 128 bit -> lattice attack will show privatekey

2.) if we have 100 transaction with remarks:
 privatekey up to 2**20 bit : with nonce up to 253 bit -> lattice attack will show privatekey

3.) if we have 480 transaction with remarks:
 privatekey up to 2**10 bit : with nonce up to 254 bit -> lattice attack will show privatekey

4.) if we have 10 transaction with remarks:
 privatekey up to 2**200 bit : with nonce up to 240 bit -> lattice attack will show privatekey


what can we deduct? lattice attack is only bounded result depends the range of privatekeys.

second problem "if you will use" CVP againts SVP you will be have another values.

hi

You was show some yours  results of finding privkey.

i apologise you maybe has more knolage then others. But, no codes for test, and fxsniper , me, and other peoples try and has no results.... so lattice "attack" waste of time for 90% of pioples.


show working code for continue talk...

[BHWallet]

Can someone post a working python script for basic lattice attack? Thanks

[BHWallet]

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!

[PrivatePerson]

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

[garlonicon]

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.

[BHWallet]

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?

[garlonicon]

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

[BHWallet]

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

[COBRAS]

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

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

[BHWallet]

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.

[COBRAS]

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

[COBRAS]

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

and waht will be your new code doing ? generate sighnatures like original  scrypt without rial world use posibble ?

br

[BHWallet]

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.

[PrivatePerson]

If I understand correctly from the answers on github, the creator does not want to change his code.

[krashfire]

First, we look at signatures:

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:

Code:

z/r=random
r/s=random

But we can do more than that:

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.

Edit:

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

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?

[krashfire]

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.

[vhh]

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.

[Bglhn]

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.