SECCON CTF 2022 国内決勝 writeup - チョコラスクのブログ

SECCON CTF 2022 国内決勝にチームchocoruskで参加し、2位を取ることができました！

国内チームの中では唯一、Jeopardyのcrypto問を全完できてとても嬉しいです。

参加記が全然書き進まないので、まず自分が解いたJeopardy問 (cryptoのみ) のwriteupを公開します。

authenticator (crypto)
hell (crypto)
not new PRNG (crypto)

authenticator (crypto)

次のソースコードが与えられます。

import secrets
import time
import sys
import os

flag = os.environ.get("FLAG", "neko{neko neko kawaii}")
key = secrets.randbits(64)


def crc64(data: bytes, init: int) -> int:
    g = 0xcd8da4ff37e45ec3
    crc = init

    for x in data:
        crc = crc ^ x
        for _ in range(8):
            crc = ((crc >> 1) ^ (g * (crc & 1))) & 0xffffffffffffffff
    return crc


def auth(code: int, t: int) -> bool:
    return crc64((key ^ t).to_bytes(8, "little"), code) == code


while True:
    print("[A]uthenticate yourself")
    print("[H]int for pre-shared key")
    choice = input("> ").strip()
    if choice == "A":
        code = int(input("code: "), 16)
        assert 0 <= code < 2**64

        # key is changed in every 5 seconds
        t = int(time.time()) // 5 * 5
        if auth(code, t):
            print(flag)
            sys.exit(0)
        print("WRONG code")

    elif choice == "H":
        t = int(time.time()) // 5 * 5
        hint = crc64(b"hint", crc64((key ^ t).to_bytes(8, "little"), 0))
        print(f"hint: {hint:x}")

    else:
        sys.exit(0)

CRCというアルゴリズムに関する問題のようです。秘密鍵 key に関する情報 crc64("hint", crc64(key, 0)) が与えられ、crc64(key, code) == code を満たす code を計算できればフラグが得られます。

まず、data がわかっているときに、crc64(data, init) から init を復元することを考えてみます。

crc = ((crc >> 1) ^ (g * (crc & 1))) & 0xffffffffffffffff

において、g の最上位ビットは1であり、crc >> 1 の最上位ビットは0なので、最終結果の最上位ビットが1ならば最後の更新で g がXORされており、0ならばされていないことがわかります。このことより、次のように init を復元することができます。

def rev_crc64(data, crc):
    y = crc
    for i in range(len(data)-1, -1, -1):
        for j in range(8):
            if y>=2**63:
                y^=g
                y<<=1
                y^=1
            else:
                y<<=1
        y^=data[i]
    return y

これで、crc64(key, 0) を復元できました。次に、key を復元したいです。key は64bitなので、上の復元アルゴリズムにおいて、y^=1 の部分や y^=data[i] の部分は if y>=2**63: の判定に干渉することはなく、分離することができます。

def rev_crc64(data, crc):
    y = crc
    z = 0
    for i in range(len(data)-1, -1, -1):
        for j in range(8):
            if y>=2**63:
                y^=g
                y<<=1
                z<<=1
                z^=1
            else:
                y<<=1
                z<<=1
        z^=data[i]
    return y^z

よって、data は最後にXORすると考えてよいので、rev_crc64(key, x) == 0 ならば rev_crc64(0, x) == key です。これで key を復元できました。

最後に、crc64(key, code) == code を満たす code を計算します。ここで、CRCで検索して出てくる記事を色々眺めていると、多項式というキーワードがよく出てきていたことに気づきました。 $i$ ビット目の数を $t^{i}$ の係数とする $\mathbb{F}_{2}$ 上の多項式に翻訳すると、x = rev_crc64(0, y) は、

$\displaystyle{ y(t)t^{64}+x(t)=tz(t)g(t)+z(t) }$

と表現できます。crc64(key, code) == code は rev_crc64(0, code) == code ^ key と同値なので、

$\displaystyle{ code(t)t^{64}+code(t)+key(t)=tz(t)g(t)+z(t) }$

を満たす $code(t)$ を求められればよいです。式変形すると、

$\displaystyle{ (t^{64}+1)code(t)\equiv key(t) \pmod{(tg(t)+1)} }$

となるので、 $t^{64}+1$ の $\bmod{(tg(t)+1)}$ における逆元をユークリッドの互除法で計算することで $code(t)$ が求まります。

g = 0xcd8da4ff37e45ec3

def rev_crc64(data, crc):
    y = crc
    z = 0
    for i in range(len(data)-1, -1, -1):
        for j in range(8):
            if y>=2**63:
                y^^=g
                z<<=1
                y<<=1
                z^^=1
            else:
                z<<=1
                y<<=1
        z^^=data[i]
    return y^^z

import socket

def recvuntil(client, delim=b'\n'):
    buf = b''
    while delim not in buf:
        buf += client.recv(1)
    return buf

host = 'authenticator.dom.seccon.games'
port = 8080

client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
client.connect((host, port))

recvuntil(client, b'> ')
client.send(b'H\n')
recvuntil(client, b'hint: ')
hint = int(recvuntil(client).strip(), 16)

x = rev_crc64(b'hint', hint)
key = rev_crc64(b'\x00'*8, x)

PR.<t> = PolynomialRing(GF(2))

def inv(a, mod):
    b, x, y=mod, 1, 0
    while b:
        t=a//b
        a-=t*b
        x-=t*y
        a, b=b, a
        x, y=y, x
    return x%mod

def to_poly(v):
    vp=0
    for i in range(64):
        vp+=((v>>i)&1)*t^i
    return vp

def to_int(vp):
    v = 0
    coeffs = vp.list()
    for i in range(len(coeffs)):
        v+=int(coeffs[i])*(2**i)
    return v

gp = to_poly(g)
f = inv((t^64+1)%(t*gp+1), t*gp+1) * to_poly(key) % (t*gp+1)
code = to_int(f)

recvuntil(client, b'> ')
client.send(b'A\n')
recvuntil(client, b'code: ')
client.send(hex(code)[2:].encode()+b'\n')
print(recvuntil(client))

Jeopardyのcrypto 3問の中で一番苦戦しました。CRCの有名度が高いせいか、多項式の計算と解釈できることを数式ではっきり解説している記事が検索でヒットしにくい*1点が難しかったです。

CRCを多項式の計算と解釈できることは初めて知りましたが、ビット演算を $\mathbb{F}_{2}$ 上の多項式の計算と解釈して解く問題は競技プログラミングでも出題されていて (これ)、かなり面白かったので、CTFでも出会えて嬉しいです。

hell (crypto)

次のソースコードとその出力結果が与えられます。

import os

flag = os.environ.get("FLAG", "neko{the_neko_must_fit_to_the_hyperelliptic}")
p = random_prime(2 ** 512)

xv = randint(0, p-1)
yv = int(flag.encode().hex(), 16)

assert yv < p

g = 2
PR.<x> = PolynomialRing(GF(p))
f = sum(randint(0, p-1)*x**i for i in range(2*g + 1 + 1))
F = f + (yv**2 - f.subs({x: xv}))

HC = HyperellipticCurve(F, 0)
J = HC.jacobian()(GF(p))

D = J(HC((xv, yv)))
print(f"p = {p}")
for i in range(2, 5):
    k = i*(i+1)
    print(k*D)

$\mathbb{F}_{p}$ 上の種数2の超楕円曲線 $HC$ があります。 $p$ は与えられますが、 $HC$ の方程式は未知です。 $HC$ 上の未知の点 $P(x_{v}, y_{v})$ の $y$ 座標 $y_{v}$ がフラグとなっており、この点に「対応する」 $HC$ のヤコビ多様体上の点を $D$ として、 $6D$ , $12D$ , $20D$ が「与えられます」。例えば $6D$ の出力結果は次のようになっています。

(x^2 + 6106105760613229930922967928674194772311203495584899831908007722665915887604567524130011714211274238017162468796768873960998817929601626003988171559055311*x + 8353639222234371469381448272508733643135697105558047478854585109935480411915187137498318296437613301979306509039890224736362852436910491641294487128458694, y + 11174320243202866558065240046782750133803672540853882720989304292750647059310760847379190517566707897494367918287535024822914183996182344175519925897513754*x + 9117855201058206589443560045632239509110354537234084579277106131911457901329328843577651067905800695533557105057771128471218842605638620032058901751650682)

超楕円曲線の知識がなくても調べながら解けるように作られているはずだと信じて解いていきます。*2

自分の超楕円曲線に関する事前知識は次のような感じです。

5次以上の多項式 $f(x)$ を用いて $y^{2}=f(x)$ と表される曲線である
超楕円曲線 (というか一般の代数曲線？) に対し、そのヤコビ多様体というアーベル多様体を考えることができる (定義は見たことがあるけど忘れた)

調査が必要なのは次のポイントです。

超楕円曲線上の点に対応するヤコビ多様体の点の意味 (D = J(HC((xv, yv))) の部分)
ヤコビ多様体上の点のSagemathによる出力 ( $x$ の2次式と $x, y$ の1次式の組) の意味
ヤコビ多様体上の点の2倍を計算する公式、あるいは $2D$ から $D$ を復元するのに役立つSagemathの関数*3

Wikipediaを読んでいきます。まずヤコビ多様体の定義を思い出します。曲線のdivisorとは、 $D=\sum c_{P}\lbrack P\rbrack$ ( $c_{P}\in \mathbb{Z}$ , $P$ は曲線上の点) という形の形式的な有限和のことをいいます。 $\mathrm{deg}(D)=\sum_{P}c_{P}$ を $D$ のdegreeといい、degreeが0のdivisorのなす群を $\mathrm{Div}^{0}(HC)$ と表します。これを、「principal divisor」のなす $\mathrm{Div}^{0}(HC)$ の部分群 $\mathrm{Princ}(HC)$ で割ったもの $J(HC)=\mathrm{Div}^{0}(HC)/\mathrm{Princ}(HC)$ がヤコビ多様体です。ここまでで、D = J(HC((xv, yv))) は、 $HC$ 上の点 $P(x_{v}, y_{v})$ のみからなるdivisor $D=\lbrack P\rbrack$ (無限遠点で調節してdegree 0とする) のことっぽいことがわかります。

次に、ヤコビ多様体上の点の出力形式について、これはMumford representationというものっぽいです。Mumford representationでは、ヤコビ多様体上の点は $(u(x), v(x))$ ( $u(x), v(x)$ は多項式で $\mathrm{deg}(v)\lt\mathrm{deg}(u)\leq g$ および $u(x)|(v(x)^{2}-f(x))$ を満たす) と表せるようです。Sagemathの出力はこれっぽいです ( $(u(x), v(x))$ ではなく $(u(x), y-v(x))$ になっていますが)。

Mumford representationが満たすべき条件 $u(x)|(v(x)^{2}-f(x))$ から超楕円曲線の方程式 $y^{2}=f(x)$ を求めることができます。3つの点について $f(x)\equiv v_{i}(x)^{2}\pmod{u_{i}(x)}$ という制約があるので、中国剰余定理により $f(x)\equiv v(x)\pmod{\prod u_{i}(x)}$ という式が得られ、 $f(x)$ は5次、 $\prod u_{i}(x)$ は6次なので $f(x)$ が特定できます。

超楕円曲線の方程式がわかれば、 $2D=20D-3\times 6D$ で $2D$ がわかるので、 $2D$ から $D$ を復元すればよいです。まず、 $D=\sum \lbrack P_{i}\rbrack$ ( $P_{i}=(x_{i},y_{i})$ ) が「reduced」のとき、 $u(x)=\prod (x-x_{i})$ のようです。よって、今回の場合 $D=(x-x_{v}, y-y_{v})$ であることがわかります。

次に、 $D=(x-x_{v}, y-y_{v})$ のとき $2D$ を計算する公式がほしいです。超楕円曲線のヤコビ多様体上の点の和をMumford representationで計算する、Cantor's algorithmというものがあるようなので、これを追っていきます*4。 $D$ が1点の場合はかなり簡単になり、 $u=(x-x_{v})^{2}$ , $v=(f(x)+y_{v}^{2})/(2y_{v})$ に対し、 $(u', v')=((f-v^{2})/u, -v)$ , $(u'', v'')=((f-v'^{2})/u', -v')$ で得られる $(u'', v'')$ が $2D$ のMumford representationとなります。よって、 $x_{v}$ , $y_{v}$ を逆算することができて、解けます。

from Crypto.Util.number import *

p = 12022348156596660999966024805317365692214838036337325208414289984663889921502416753085931743030831771121692950289876216078866039507020072658832499672904927
PR.<x> = PolynomialRing(GF(p))

def inv(a, mod):
    b, x, y=mod, 1, 0
    while b:
        t=a//b
        a-=t*b
        x-=t*y
        a, b=b, a
        x, y=y, x
    return x%mod

def crt(r1, q1, r2, q2):
    g = inv(q2, q1)
    k = g*q2%q1
    g *= GF(p)(k)^(-1)
    return (g*(r1-r2)%q1)*q2+r2

u1,v1 = # 6Dの出力を"y+"を切り取って入れる
u2,v2 = # 12Dの出力を"y+"を切り取って入れる
u3,v3 = # 20Dの出力を"y+"を切り取って入れる
us = [u1,u2,u3]
vs = [v1,v2,v3]

f = (vs[0]^2)%us[0]
q = us[0]
for i in range(1, 3):
    f = crt(f, q, (vs[i]^2)%us[i], us[i])
    q *= us[i]

print(f'HC: y^2 = {f}')

HC = HyperellipticCurve(f, 0, 'x,y')
J = HC.jacobian()(GF(p))

D6 = J([u1,v1])
D12 = J([u2,v2])
D20 = J([u3,v3])
D2 = D20-3*D6
print(D2)

u0,v0 = # 2Dの出力を"y+"を切り取って入れる 

u01 = (f-v0^2)//u0
v01 = -v0
u02 = (f-v01^2)//u01
v02 = -v01

xv = u02.list()[1]*((p-1)//2)%p
yv = f(x=xv)

g = x^2-yv
for r in g.roots():
    print(long_to_bytes(int(r[0])))

Wikipediaにかなり色々書いてあったので楽に解くことができました。

これに限らず、高度な整数論ネタがどんどん出題されてくれると、昔勉強したけれど忘れた数学や昔諦めた数学を勉強し直すモチベーションが上がるので嬉しいです。

not new PRNG (crypto)

次のソースコードとその出力結果が与えられます。

import os
import random
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad
from Crypto.Util.number import getPrime


p = getPrime(128)

xs = [random.randint(1, 2**64) for _ in range(4)]

a = random.randint(1, p)
b = random.randint(1, p)
c = random.randint(1, p)
d = random.randint(1, p)
e = random.randint(1, p)  # unknown

xs.append((a*xs[-4] + b*xs[-3] + c*xs[-2] + d*xs[-1] + e) % p)
xs.append((a*xs[-4] + b*xs[-3] + c*xs[-2] + d*xs[-1] + e) % p)
xs.append((a*xs[-4] + b*xs[-3] + c*xs[-2] + d*xs[-1] + e) % p)

outs = xs[-3:]


# encryption
FLAG = os.getenv("FLAG", "fake{the_flag_is_a_lie}")
key = 0
for x in xs[:4]:
    key <<= 64
    key += x
key = int(key).to_bytes(32, "little")
iv = get_random_bytes(16)  # public
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(pad(FLAG.encode(), 16))  # public

# output
print(f"p = {p}")
print(f"a = {a}")
print(f"b = {b}")
print(f"c = {c}")
print(f"d = {d}")
print(f"outs = {outs}")
print(f"iv = 0x{iv.hex()}")
print(f"ct = 0x{ct.hex()}")

素数 $p$ と整数 $a, b, c, d$ が与えられ ( $e$ は未知)、漸化式

$\displaystyle{ x_{n+4}\equiv ax_{n}+bx_{n+1}+cx_{n+2}+dx_{n+3}+e\pmod{p} }$

を満たす数列 $x$ について $x_{5}$ , $x_{6}$ , $x_{7}$ が与えられます。目標は $x_{1}$ , $x_{2}$ , $x_{3}$ , $x_{4}$ を復元することです。ここで、 $p$ は128bitなのに対し、 $x_{1}$ , $x_{2}$ , $x_{3}$ , $x_{4}$ は64bit以下であることが重要です。

$i=1, 2, 3$ に対し、

$\displaystyle{ x_{i+4}\equiv a'_{i}x_{1}+b'_{i}x_{2}+c'_{i}x_{3}+d'_{i}x_{4}+e'_{i}e\pmod{p} }$

を満たす $a'_{i}$ , $b'_{i}$ , $c'_{i}$ , $d'_{i}$ , $e'_{i}$ を計算できます。さらに $e$ を消去すると、

$\displaystyle{ y_{i}\equiv a_{i}x_{1}+b_{i}x_{2}+c_{i}x_{3}+d_{i}x_{4}\pmod{p} }$

という関係式が2つ得られます。

この2つの関係式を満たす $(x_{1}, x_{2}, x_{3}, x_{4})$ の個数を見積もります。 $(x_{1}, x_{2})$ は $2^{128}$ 通りあり、 $(x_{1}, x_{2})$ が決まると $(x_{3}, x_{4})$ が決まり、これらが $2^{64}$ 未満である確率は $1/2^{128}$ 程度なので、2つの関係式を満たす $(x_{1}, x_{2}, x_{3}, x_{4})$ の個数は1個程度になりそうです。

次のような行列について、LLLアルゴリズムを適用します。

$\begin{pmatrix} 2^{128}a_{1} && 2^{128}a_{2} && 1 && 0 && 0 && 0 && 0 \\ 2^{128}b_{1} && 2^{128}b_{2} && 0 && 1 && 0 && 0 && 0 \\ 2^{128}c_{1} && 2^{128}c_{2} && 0 && 0 && 1 && 0 && 0 \\ 2^{128}d_{1} && 2^{128}d_{2} && 0 && 0 && 0 && 1 && 0 \\ 2^{128}p && 0 && 0 && 0 && 0 && 0 && 0 \\ 0 && 2^{128}p && 0 && 0 && 0 && 0 && 0 \\ -2^{128}y_{1} && -2^{128}y_{2} && -2^{63} && -2^{63} && -2^{63} && -2^{63} && 2^{128} \end{pmatrix}$

想定している出力のベクトルは

$\displaystyle{ (0, 0, x_{1}-2^{63}, x_{2}-2^{63}, x_{3}-2^{63}, x_{4}-2^{63}, 2^{128}) }$

またはこの-1倍です。1, 2列目は0になってほしいので $2^{128}$ 倍の重みをつけており、7行目は1個だけ使ってほしいので7列目に $2^{128}$ 倍の重みをつけています。また、 $x_{i}$ より $x_{i}-2^{63}$ の方が絶対値が小さくなることが期待できるので、7行目の3〜6列目は0ではなく $-2^{63}$ としています。

このとき、得られる $(x_{1}, x_{2}, x_{3}, x_{4})$ は

[7556618114415270298, 8111946174900099316, 17896096178591467897, 9882114333904613878]

です。これは確かに条件に合う $2^{64}$ 未満の解ですが、残念ながらこの鍵を用いても暗号文の復号に失敗します。つまり、条件に合う $2^{64}$ 未満の解は他にもあるということです。

今得られた解は、 $x_{1}$ , $x_{2}$ が $2^{63}$ より小さく、 $x_{3}$ , $x_{4}$ は $2^{63}$ より大きいです。そこで、この解が出力されるのを避けるため、行列の7行目を次のようにずらしてみます。

$\displaystyle{ (-2^{128}y_{1}, -2^{128}y_{2}, -(2^{63}+\epsilon ), -(2^{63}+\epsilon ), -(2^{63}-\epsilon ), -(2^{63}-\epsilon ), 2^{128}) }$

試しに $\epsilon = 2^{64}/6$ としてみると、運良く欲しい解を得ることができました。

from Crypto.Cipher import AES
from Crypto.Util.number import *

p = 234687789984662131107323206406195107369
a = 35686285754866388325178539790367732387
b = 36011211474181220344603698726947017489
c = 84664322357902232989540976252462702046
d = 154807718022294938130158404283942212610
outs = [222378874028969090293268624578715626424, 42182082074667038745014860626841402403, 217744703567906139265663577111207633608]
iv = 0xf2dd287ca870eb9908bf52c44dfd9d2b
ct = 0x236a6aca059ae29056a23f5458c644abb74640d672dba1ee049eb956e629b7afb03ae33b2b2b419c24197d33baf6d88e2f0eedfa90c06e1a2be18b2fae2270f05ce39de5e0d59bb9a442d1b3eb392658e45cf721094543b13d35df8cf9ce420c

mat = [[a, b, c, d, 1], [(a*d)%p, (b*d+a)%p, (c*d+b)%p, (d*d+c)%p, (d+1)%p], [(a*d*d+c*a)%p, (b*d*d+a*d+c*b)%p, (c*d*d+b*d+c*c+a)%p, (d*d*d+c*d+c*d+b)%p, (d*d+d+c+1)%p]]
v1 = [0,0,0,0]
v2 = [0,0,0,0]
y1 = (mat[0][4]*outs[1]-mat[1][4]*outs[0])%p
y2 = (mat[0][4]*outs[2]-mat[2][4]*outs[0])%p
for i in range(4):
    v1[i]=(mat[0][4]*mat[1][i]-mat[1][4]*mat[0][i])%p
    v2[i]=(mat[0][4]*mat[2][i]-mat[2][4]*mat[0][i])%p

c1 = 2**128
c2 = 2**128
mat1 = [[0]*7 for _ in range(7)]
for i in range(4):
    mat1[i][0]=v1[i]*c1
    mat1[i][1]=v2[i]*c1
    mat1[i][i+2]=1
mat1[4][0]=p*c1
mat1[5][1]=p*c1
mat1[6][0]=(p-y1)*c1
mat1[6][1]=(p-y2)*c1
mat1[6][6]=c2

mids = [2**64//3*2, 2**64//3*2, 2**64//3, 2**64//3]
# mids = [2**63, 2**63, 2**63, 2**63]
for i in range(2,6):
    mat1[6][i]=-mids[i-2]

res = Matrix(mat1).LLL()
if res[-1][6]<0:
    xs = list([mids[i]-res[-1][i+2] for i in range(4)])
else:
    xs = list([mids[i]+res[-1][i+2] for i in range(4)])
print(xs)

e = (outs[0]-a*xs[0]-b*xs[1]-c*xs[2]-d*xs[3])%p
xs.append((a*xs[-4] + b*xs[-3] + c*xs[-2] + d*xs[-1] + e) % p)
xs.append((a*xs[-4] + b*xs[-3] + c*xs[-2] + d*xs[-1] + e) % p)
xs.append((a*xs[-4] + b*xs[-3] + c*xs[-2] + d*xs[-1] + e) % p)
assert xs[-3:] == outs

key = 0
for x in xs[:4]:
    assert x<2**64
    key <<= 64
    key += x
key = int(key).to_bytes(32, "little")
iv = long_to_bytes(iv)
ct = long_to_bytes(ct)
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
print(flag)