Challenge files



In sig.sage we can see nonces are generated by the generator:

nonce = self.lcg.next()


And it is cubic:

seed = (self.a*self.seed^3 + self.b*self.seed^2 + self.c*self.seed + self.d) % self.q



The challenge seemed to come from this paper https://eprint.iacr.org/2023/305.pdf
and I used the code linked in the appendix to solve it
https://github.com/kudelskisecurity/ecdsa-polynomial-nonce-recurrence-attack/blob/main/original-attack/recurrence_nonces.py


The paper also tells us to set N=6 for a Cubic Congruential Generator.


from pwn import remote
import hashlib
from Crypto.Util.number import *

def k_ij_poly(i, j):
    hi = Z(h[i])
    hj = Z(h[j])
    s_invi = Z(s_inv[i])
    s_invj = Z(s_inv[j])
    ri = Z(r[i])
    rj = Z(r[j])
    poly = dd*(ri*s_invi - rj*s_invj) + hi*s_invi - hj*s_invj
    return poly

def dpoly(n, i, j):
    if i == 0:
        return (k_ij_poly(j+1, j+2))*(k_ij_poly(j+1, j+2)) - (k_ij_poly(j+2, j+3))*(k_ij_poly(j+0, j+1))
    else:
        left = dpoly(n, i-1, j)
        for m in range(1,i+2):
            left = left*(k_ij_poly(j+m, j+i+2))
        right = dpoly(n, i-1, j+1)
        for m in range(1,i+2):
            right = right*(k_ij_poly(j, j+m))
        return (left - right)

def _hash(msg):
    return bytes_to_long(hashlib.sha1(msg).digest())


io = remote("crypto.csaw.io", "5002")
q = 115792089237316195423570985008687907852837564279074904382605163141518161494337

# send 7 msgs
for i in range(1, 8):
    print(io.readuntil(b": ").decode())
    io.sendline(b"1")
    print(io.readuntil(b": ").decode())
    io.sendline(f"{i:02x}".encode())

h = []
s = []
r = []
s_inv = []

# parse msg hashes and signatures
print(io.readuntil(b": ").decode())
io.sendline(b"2")
for i in range(7):
    io.readline()
    _m = bytes.fromhex(io.readline().split()[1].decode())
    exec("_r, _s = " + io.readline().decode()[10:])
    if i != 0:
        msg = previous_m + long_to_bytes(i)
        _h = _hash(msg)
        h.append(_h)
        s.append(_s)
        r.append(_r)
        s_inv.append(pow(_s, -1, q))
    previous_m = _m

# solve and send priv_key
N = 6
Z = GF(q)
R.<dd> = PolynomialRing(Z)
for priv_key, _ in dpoly(N-4, N-4, 0).roots():
    print(io.readuntil(b": ").decode())
    io.sendline(b"4")
    print(io.readline().decode())
    io.sendline(str(priv_key).encode())
    print(io.readline().decode())
    break