0
$\begingroup$

I am currently trying to do the cryptopals challenge 62, breaking ECDSA with biased nonces, with the help of those two links (1 2) that describe accurately the attack. However, after around 15 hours, I still can't have it working, and I have absolutely no clue where I made a mistake.

Here is how I did it (using Python 3.6): First, to generate the signatures with faulty nonces (I took the same model as the one those links use, so the 8 LSB bits are zero):

import ecdsa
from random import randint

gen = ecdsa.SECP256k1.generator
order = gen.order()
d = randint(1, order)

pub = ecdsa.ecdsa.Public_key(gen, gen*d)
priv = ecdsa.ecdsa.Private_key(pub, d)

R = []
S = []

for i in range(100):
    nonce = randint(1, order)
    nonce ^= (nonce & 0xff)
    signed = priv.sign(h, nonce)
    R.append(signed.r)
    S.append(signed.s)

then the actual attack, which is quite short: we compute a few numbers, construct a matrix with them, call the LLL algorithm and we should find in the reduced basis the value -d*ct right next to a cu one, according to the links:

Constructing the matrix:

h = 1337
N_SIGNATURE = 100

M = [[0 for i in range(N_SIGNATURE + 2)] for j in range(N_SIGNATURE + 2)]

for i in range(N_SIGNATURE):
    M[i][i] = order

ct = gmpy2.invert(256, order) # 2**l with l = known bits
cu = order * ct
M[-2][-2] = int(ct)
M[-1][-1] = int(cu)

for i in range(N_SIGNATURE):
    M[-2][i] = int(R[i] * gmpy2.invert(S[i] * 256, order)) % order    # t_i
    M[-1][i] = int( -h  * gmpy2.invert(S[i] * 256, order)) % order    # u_i

Using the very efficient fplll lib (this part is a bit clunky and will be rewritten using Sage, but it works. Here, I mainly do formatting on the matrix so it can be inputted for fplll, and I convert the output back to a matrix):

str_M = str(M).replace(",", "")
os.system("echo " + str_M + " | fplll -a lll -m proved -f mpfr > result.txt")

new_matrix = [[0 for i in range(N_SIGNATURE+2)] for j in range(N_SIGNATURE+2)]

with open("result.txt", "r") as myfile:
    contents = myfile.read()
    contents = contents.replace("[", "").replace("]", "").replace("\n", "").split(" ")
    contents = contents[:-1] # there is one empty line at the end

    assert(len(contents) == pow(N_SIGNATURE + 2, 2))

    i = 0
    j = 0
    for v in contents:
        new_matrix[i][j] = int(v)
        j += 1
        if j == N_SIGNATURE + 2:
            j = 0
            i += 1

Getting d:

for row in new_matrix:
    if(row[-1] == cu):
        d2 = (-row[-2] * gmpy2.invert(ct, order)) % order
        
        if(d2 == d):
            print("Secret key recovered")


However, no matter how many variables I adjust and things I try, I can't get a result. I also tried scanning the whole matrix instead of the last elements, without success. Did I make a silly mistake I didn't notice, or is there something quite wrong in my code?

Note: the following line in link 2:

I forgot to mention: you'll want to write your implementation to work on vectors of rationals. If you have infinite-precision floats, those'll work too.

caught my attention, but the mpfr argument of fplll should fit what is needed here. And in case it doesn't, I also tried using a Sage matrix defined over QQ, but it doesn't work better.

$\endgroup$

1 Answer 1

3
$\begingroup$

You have to be a bit careful of several things:

  1. the fractional number $\frac{1}{2^l}$ is not the inverse of 2^l mod order.

  2. after lattice reduction, the entries of the basis matrix might be negative values, so the statement if(row[-1] == cu) might not be fully correct.

  3. note that order - d is also a solution of the HNP inequalities, so it might be safe to check both. Usually, lattice reduction will lead to the smaller one of d and order - d.

  4. the vector you want might not be the first vector of the reduced basis, so you can check all the rows.

For 256-bit ECDSA with 8-bit leakage, I guess 50 (even 40) is enough.

$\endgroup$
1
  • $\begingroup$ Thank you very much for your answer. Just fixing your point 1 made everything work right away. I never would have guessed a regular fraction was needed here, since everything is modulo the order and divisions are computed with the modular inverse. $\endgroup$
    – Katoptriss
    Jan 27, 2022 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.