⬅ BACK
IJCTF 2021 - ECSign

ECDSA is very popular recently...

ECSign

import hashlib
import random
from Crypto.Util.number import inverse, bytes_to_long, long_to_bytes
from Crypto.Random import get_random_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from ecdsa import NIST256p

from flag import FLAG

message = b"ECDSA prevents forging messages"

curve = NIST256p
G = curve.generator
n = curve.order

class Signature:
    def __init__(self):
        self.privkey = random.randrange(n)
        self.pubkey = self.privkey * G
        self.r = random.randrange(n)
        self.s = random.randrange(n)

    def sign(self, msg, k):
        hsh = int(hashlib.sha256(msg).hexdigest(), 16)
        p = k * G
        self.r = p.x() % n
        self.s = (inverse(k, n) * (hsh + (self.privkey * self.r) % n)) % n
        return (self.r, self.s)

    def f_sign(self, msg, k):
        hsh = int(hashlib.sha256(msg).hexdigest(), 16)
        self.s = (inverse(k, n) * (hsh + (self.privkey * self.r) % n)) % n
        return (self.r, self.s)

sig = Signature()
k = random.randrange(n)

sig1 = sig.sign(message, k)
sig2 = sig.f_sign(message, k^0xffffffff)
sig3 = sig.f_sign(message, k^0xffffffff00000000)

r = random.randrange(n)
pubkey2 = r*G
sharedkey = r*sig.pubkey

iv = get_random_bytes(16)
key = long_to_bytes(int(sharedkey.x()))
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(pad(FLAG, 16))

print("pubkey="+ str((int(sig.pubkey.x()), int(sig.pubkey.y()))))
print("sig1=" + str(tuple(map(lambda x:int(x), sig1))))
print("sig2=" + str(tuple(map(lambda x:int(x), sig2))))
print("sig3=" + str(tuple(map(lambda x:int(x), sig3))))

print("pubkey2="+ str((int(pubkey2.x()), int(pubkey2.y()))))
print("iv=" + "0x"+str(iv.hex()))
print("ct=" + "0x"+str(ct.hex()))
pubkey=(38745398585592404989617041657020362138123363380468846963780930586996547144750, 13643061224989896432264609612335708262502935494164515568037402963951605264829)
sig1=(77834524933954296097833315313842984664992628710802286706422333910202549804044, 106047115067349115009621212644299274382951056066902044358604548248126784117113)
sig2=(77834524933954296097833315313842984664992628710802286706422333910202549804044, 77856639655128453708803009032309618307780628811843761077611198123911335033581)
sig3=(77834524933954296097833315313842984664992628710802286706422333910202549804044, 113246340396800206689440828533000149451101779708634101475318788958650261939751)
pubkey2=(18408891362196717436082197656011814689561019672942300120844335017129989755383, 89780168462818288492260141231746707551390283872983535472764708240708422195758)
iv=0x1d828a4a93bc2026ae1c8ab1711a1991
ct=0x8c5350234cf12b0f4da1d344124fe76e29906fbf5a1ed45cc8c7a29009dc078a31a6150b8ec5be75e1f7cef7665f634b

Solution

We are given three ECDSA signatures of the same message. The only thing that changes is the nonce, and it only changes slightly. To decrypt the flag, we need to recover the secret signing key used to sign these messages.

Recall that in ECDSA a message mm is signed by choosing a random nonce kk and then computing

r=(kG)xs=k1(H(m)+rd)r = (kG)_x \qquad s = k^{-1}(H(m) + rd)

where dd is the secret signing key. Computations are performed modulo nn, where nn is the curve order. The signature is (r,s)(r, s).

In our case, the signatures all share the same rr value, but the ss values are different. We have

s1=k1(H(m)+rd)s2=(k(2321))(H(m)+rd)s3=(k(264232))(H(m)+rd)\begin{aligned} s_1 &= k^{-1} (H(m) + rd) \\ s_2 &= (k \oplus (2^{32} - 1)) (H(m) + rd) \\ s_3 &= (k \oplus (2^{64} - 2^{32})) (H(m) + rd) \end{aligned}

Since XOR is annoying to work with algebraically, we approximate the XOR operations with additions:

s1=k1(H(m)+rd)s2=(k+t2)(H(m)+rd)s3=(k+t3)(H(m)+rd)\begin{aligned} s_1 &= k^{-1} (H(m) + rd) \\ s_2 &= (k + t_2) (H(m) + rd) \\ s_3 &= (k + t_3) (H(m) + rd) \end{aligned}

where t2<232|t_2| < 2^{32} and t3<264|t_3| < 2^{64}. Note that because we do not know kk, we do not immediately know t2t_2 and t3t_3. However, they are small values (compared to the curve order), and LLL is magical.

At the moment, we have three equations in four unknowns k,t2,t3,dk, t_2, t_3, d. We can combine these to get one equation in two unknowns. We choose to eliminate kk and dd so that we get a relation containing only t2t_2 and t3t_3. It turns out we get the equation

c2t2+c3t30(modn)    c2t2+c3t3=bn\begin{aligned} c_2 t_2 + c_3 t_3 &\equiv 0 \pmod n \\ \implies c_2 t_2 + c_3 t_3 &= bn \end{aligned}

For some coefficients c2c_2 and c3c_3 and some integer bb. And since the unknowns are small compared to nn, we have the perfect setting to use lattice techniques.

Consider the lattice generated by the rows of the following matrix:

M=[c210c301n00]M = \begin{bmatrix} c_2 & 1 & 0 \\ c_3 & 0 & 1 \\ n & 0 & 0 \end{bmatrix}

Denote by rir_i the iith row. Note that t2r0+t3r1bn=0t_2 r_0 + t_3 r_1 - bn = 0, so (0,t2,t3)(0, t_2, t_3) is a short vector in this lattice. We can find this exact vector by using the LLL algorithm and looking for a vector with 00 in the first entry. This gives us the values of t2t_2 and t3t_3.

Once we have recovered t2t_2 and t3t_3, we can substitute them into the expressions for s1,s2s_1, s_2 and s3s_3. We are then left with three equations and two unknowns. It is easy to solve for the private key dd, e.g. with Gröbner bases, resultants, rearranging by hand, etc.

import hashlib
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

from sage.matrix.matrix2 import Matrix
def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))

h = int(hashlib.sha256(b'ECDSA prevents forging messages').hexdigest(), 16)
pubkey = (38745398585592404989617041657020362138123363380468846963780930586996547144750, 13643061224989896432264609612335708262502935494164515568037402963951605264829)
r = 77834524933954296097833315313842984664992628710802286706422333910202549804044
s1 = 106047115067349115009621212644299274382951056066902044358604548248126784117113
s2 = 77856639655128453708803009032309618307780628811843761077611198123911335033581
s3 = 113246340396800206689440828533000149451101779708634101475318788958650261939751
pubkey2 = (18408891362196717436082197656011814689561019672942300120844335017129989755383, 89780168462818288492260141231746707551390283872983535472764708240708422195758)
iv = bytes.fromhex('1d828a4a93bc2026ae1c8ab1711a1991')
ct = bytes.fromhex('8c5350234cf12b0f4da1d344124fe76e29906fbf5a1ed45cc8c7a29009dc078a31a6150b8ec5be75e1f7cef7665f634b')

n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
P.<k,t2,t3,d> = PolynomialRing(Integers(n))

f1 = s1*k - h - r*d
f2 = s2*(k+t2) - h - r*d
f3 = s3*(k+t3) - h - r*d
h1 = resultant(f1, f2, d)
h2 = resultant(f1, f3, d)
g1 = resultant(h1, h2, k)

c2, c3 = map(ZZ, g1.coefficients())
M = matrix(ZZ, [
    [c2, 1, 0],
    [c3, 0, 1],
    [n, 0, 0]
])
M = M.LLL()
t2_ = M[0][1]
t3_ = M[0][2]

f2 = f2.subs({ t2: t2_ })
f3 = f3.subs({ t3: t3_ })
h1 = resultant(f2, f3, k)
d = h1.univariate_polynomial().roots()[0][0]

p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = -3
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
E = EllipticCurve(GF(p), [a, b])
sharedkey = int(d)*E(*pubkey2)

key = long_to_bytes(int(sharedkey.xy()[0]))
cipher = AES.new(key, AES.MODE_CBC, iv)
pt = unpad(cipher.decrypt(ct), 16)
print(pt.decode())