Crew CTF 2022 - signsystem

TL;DR

SECP112r1曲線を用いたECDSAで署名の生成と検証が出来、指定されたメッセージの署名を生成出来たらフラグが開示される
112個のメッセージと署名の組を入手出来ると、以降のnonceがこれら112個の署名で用いられたnonceの線形結合で表す事が出来る
これを利用してNonceが同じ時のECDSAに対する攻撃と同じ要領で線形連立方程式を立てて解くと、署名鍵を導出出来るので任意のメッセージに対する署名を生成出来る

Prerequisite

ECDSA

Writeup

問題のスクリプトは次の通り

import sys
import random
from hashlib import sha256
from Crypto.Util.number import inverse
import ecdsa

from secret import FLAG

curve = ecdsa.curves.SECP112r1
p = int(curve.curve.p())
G = curve.generator
n = int(curve.order)

class SignSystem:
    def __init__(self):
        self.key = ecdsa.SigningKey.generate(curve=curve)
        self.nonce = [random.randint(1, n-1) for _ in range(112)]

    def sign(self, msg):
        e = int.from_bytes(sha256(msg).digest(), 'big') % n
        h = bin(e)[2:].zfill(112)
        k = sum([int(h[i])*self.nonce[i] for i in range(112)]) % n
        r = int((k * G).x()) % n
        s = inverse(k, n) * (e + r * self.key.privkey.secret_multiplier) % n
        
        return (int(r), int(s))

    def verify(self, msg, sig):
        (r, s) = sig
        e = int.from_bytes(sha256(msg).digest(), 'big')
        if s == 0:
            return False
        w = inverse(s, n)
        u1 = e*w % n
        u2 = r*w % n
        x1 = int((u1*G + u2*self.key.privkey.public_key.point).x()) % n
        return (r % n) == x1

if __name__ == '__main__':
    HDR = 'Welcome to sign system.'
    print(HDR)
    MENU = "1:sign\n2:verify\n3:getflag\n"
    S = SignSystem()
    try:
        while(True):
            print('')
            print(MENU)
            i = int(input('>> '))
            if i == 1:
                msghex = input('msg(hex): ')
                sig = S.sign(bytes.fromhex(msghex))
                print(f'signature: ({hex(sig[0])}, {hex(sig[1])})')
            elif i == 2:
                msghex = input('msg(hex): ')
                sig0hex = input('sig[0](hex): ')
                sig1hex = input('sig[1](hex): ')
                result = S.verify(bytes.fromhex(msghex), (int(sig0hex, 16), int(sig1hex, 16)))
                if result:
                    print('Verification success.')
                else:
                    print('Verification failed.')
            elif i == 3:
                target = random.randint(2**511, 2**512-1)
                print(f'target: {hex(target)}')
                sig0hex = input('sig[0](hex): ')
                sig1hex = input('sig[1](hex): ')
                result = S.verify(bytes.fromhex(hex(target)[2:]), (int(sig0hex, 16), int(sig1hex, 16)))
                if result:
                    print('OK, give you a flag.')
                    print(FLAG.decode())
                    break
                else:
                    print('NG.')
                    break
    except KeyboardInterrupt:
        print('bye')
        sys.exit(0)
    except:
        print('error occured')
        sys.exit(-1)

次の3つのコマンドを実行出来る

署名: 任意のメッセージの署名を得られる
検証: 署名とメッセージを与えて検証出来る
フラグ要求: ランダム生成されたメッセージの署名を与えるチャレンジが発生し、もし署名提出出来ればフラグが開示される。なお、成否に関わらずこのコマンドの実行後にプログラムは終了する。

問題のインスタンス起動時に乱数ベクトル$\boldsymbol x \in \mathbb F_p^{112}$が定義される。 (ハッシュ化済みの)メッセージを$z$とおく。これに対してベクトル$\boldsymbol h \in \mathbb F_p^{112}$を$z$のビット列をそのまま用いることで定義し、ECDSAに使うnonceを$k \coloneqq \boldsymbol x\cdot \boldsymbol h$で生成する。

該当箇所はk = sum([int(h[i])*self.nonce[i] for i in range(112)]) % nであり、これを見るとベクトルの内積で表すことが出来る事がわかる。

基底メッセージの取得

nonceの生成において都合が良い事にメッセージと乱数の内積を利用していることから、もし1次独立なメッセージを112個集めて基底とすれば、任意のメッセージのnonceをこの基底の線形結合で表すことが出来る。

具体的には基底となるメッセージのビット列を$\boldsymbol h_1, \boldsymbol h_2, \dots, \boldsymbol h_{112}$とし、あるメッセージのビット列を$\boldsymbol h$として、この基底に対する係数ベクトルを$(a_1, a_2, \dots, a_{112})$とおくと、$\boldsymbol h = (a_1, a_2, \dots, a_n) \cdot (\boldsymbol h_1, \boldsymbol h_2, \dots, \boldsymbol h_{112})$であるから、次のようになる。

$$ \begin{aligned} k &= \boldsymbol h \cdot \boldsymbol x \cr &= \left((a_1, a_2, \dots, a_{112})\begin{pmatrix}\boldsymbol h_1 \cr \boldsymbol h_2 \cr \vdots \cr \boldsymbol h_{112}\end{pmatrix}\right) \boldsymbol x^T \cr &= (a_1, a_2, \dots, a_{112}) \begin{pmatrix} \boldsymbol h_1 \cdot \boldsymbol x \cr \boldsymbol h_2 \cdot \boldsymbol x \cr \vdots \cr \boldsymbol h_{112}\cdot \boldsymbol x \end{pmatrix}\cr &= (a_1, a_2, \dots, a_{112}) \begin{pmatrix} k_1 \cr k_2 \cr \vdots \cr k_{112} \end{pmatrix}\cr &= \sum_{1 \leq i \leq 112} a_ik_i \end{aligned} $$

ここでECDSAのnonceを$k$、署名を$r,s$、メッセージを$z$、署名鍵を$d$とおくと、$ks = z+rd$の関係があったことから、$ks - rd = z$と変形することで次のような行列に落とし込むことが出来る。

但し、事前に112個のビット列が一次独立なメッセージ($z_i$、ビット列は$\boldsymbol h_i$)とその署名$r_i,s_i$を入手し、メッセージ$z_0$のビット列$\boldsymbol h_0$が$\boldsymbol h_0 = \sum_{1 \leq i \leq 112} a_i \boldsymbol h_i$であり、これを署名した結果を$r_0,s_0$とする。

$$ \begin{pmatrix}s_1 & & & & -r_1 \cr & s_2 & & & -r_2 \cr & & \ddots & & \vdots \cr & & & s_{112} & -r_{112} \cr a_1s_0 & a_2s_0 & \dots & a_{112}s_0 & -r_0\end{pmatrix} \begin{pmatrix} k_1 \cr k_2 \cr \vdots \cr k_{112} \cr d\end{pmatrix} = \begin{pmatrix} z_1 \cr z_2 \cr \vdots \cr z_n \cr z_0 \end{pmatrix} $$

この式の左辺左側の行列の逆行列を両辺左側から掛ければ、$(k_1, k_2, \dots, k_{112}, d)^T$が求められるので署名鍵である$d$が求められる。よって任意のメッセージに対して署名が生成出来るようになるので3:getFlagコマンドで提示されたメッセージの署名を提出してフラグを得る。

Code

from pwn import remote
from hashlib import sha256


def choice(c):
    sc.recvuntil(b">> ")
    sc.sendline(str(c).encode())


def to_hex_bytes(msg):
    hex_msg = hex(msg)[2:]
    if len(hex_msg) % 2:
        hex_msg = "0" + hex_msg

    return hex_msg


def sign(msg):
    choice(1)
    sc.recvuntil(b"msg(hex): ")
    hex_msg = to_hex_bytes(msg)
    sc.sendline(hex_msg)
    sc.recvuntil(b"signature: (")
    r = int(sc.recvuntil(b",")[:-1], 16)
    s = int(sc.recvuntil(b")")[:-1], 16)

    return (r,s)


def hash(msg):
    msg = to_hex_bytes(msg)
    msg = bytes.fromhex(msg)
    return int.from_bytes(sha256(msg).digest(), 'big') % order


def to_line(msg):
    h = bin(hash(msg))[2:].zfill(112)
    return list(map(int,h))


def calc_kG(msg,r,s,Q):
    e = hash(msg)
    w = inverse_mod(s, order)
    u1 = e*w % order
    u2 = r*w % order

    return u1*G + u2*Q


p = 4451685225093714772084598273548427
order = 4451685225093714776491891542548933
a = 4451685225093714772084598273548424
b = 2061118396808653202902996166388514

gx = 188281465057972534892223778713752
gy = 3419875491033170827167861896082688

curve = EllipticCurve(GF(p), [a,b])
G = curve((gx, gy))

sc = remote("signsystem.crewctf-2022.crewc.tf", 1337)
# sc = remote("localhost", 13337)
msg = 0x114514
e = hash(msg)
r,s = sign(msg)

X = curve.lift_x(GF(p)(r))
w = inverse_mod(s, order)
u1 = e*w % order
u2 = r*w % order
Q = inverse_mod(u2, order) * ( X - u1 * G)
msg = 0x364364
r,s = sign(msg)
kG = calc_kG(msg,r,s,Q)
if r != int(kG.xy()[0]):
    Q = inverse_mod(u2, order) * ( -X - u1 * G)

m_list = []
h_and_kgs = []

for i in range(112):
    print(i)
    msg = randint(1, order)
    r,s = sign(msg)
    kG = calc_kG(msg, r, s, Q)
    assert r == int(kG.xy()[0])
    m_list.append(to_line(msg))
    h_and_kgs.append((hash(msg), (r,s), kG))

mat = matrix(GF(order), m_list)
mat_inv = mat^-1

msg = randint(1, order)
r,s = sign(msg)
target_line = to_line(msg)
v = vector(target_line, GF(order))
x = v * mat_inv

m_list = []
v_list = []
for i in range(112):
    l = [0 for _ in range(113)]
    l[i] = h_and_kgs[i][1][1]
    l[-1] = (-h_and_kgs[i][1][0]) % order
    v_list.append(h_and_kgs[i][0])
    m_list.append(l)

l = [0 for _ in range(113)]
for i in range(112):
    l[i] = x[i] * s % order
l[-1] = (-r) % order
m_list.append(l)
v_list.append(hash(msg))

mat = matrix(GF(order), m_list)
v = vector(v_list, GF(order))
x = (mat^-1) * v
d = int(x[-1])
print(x[-1])

choice(3)
sc.recvuntil(b"target: ")
target = int(sc.recvline(), 16)
k = randint(1, order)
R = k * G
r = R.xy()[0]
r = int(r)
s = inverse_mod(k, order) * (hash(target) + r * d) % order
s = int(s)
sc.recvuntil(b"sig[0](hex): ")
sc.sendline(hex(r)[2:].encode())
sc.recvuntil(b"sig[1](hex): ")
sc.sendline(hex(s)[2:].encode())
sc.interactive()

Flag

crew{w3_533_7h3_p0w3r_0f_l1n34r_4l63br4}