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.