Help breaking ECDSA with biased nonces

cn flag

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)

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

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

ph flag

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.

Katoptriss avatar
cn flag
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.

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.