SECCON Beginners CTF 2024 crypto writeup

SECCON Beginners CTF 2024に顔をだして、cryptoの問題を解きました。全5問を解くのに5時間程度かかって多分これは一番*1。Safe Prime以外の4問はSecond Bloodでした。

crypto分野でまだある程度の実力を維持できていることに安心した一方で、他のカテゴリの問題に取り組む前に満足してしまって最終的なスコアや順位としてはイマイチというのはあとから見れば残念です。

Safe Prime (12分)
Math (17分)
ARES (1時間16分)
bless (59分)
Try hard in my style (2時間)

Safe Prime (12分)

RSA暗号の問題で、公開鍵 $e, n$ と暗号文 $c$ が分かっているほか、 $n$ が次のように作られていることがわかります。

while True:
    p = getPrime(512)
    q = 2 * p + 1
    if isPrime(q):
        break

n = p * q

問題名の通り、 $q$ はある素数 $p$ を用いて $q = 2p + 1$ と表せる形の素数（safe prime）です。 $p, q$ それぞれが別々のsafe primeならば問題になることはないのですが、この問題の場合は $q$ を構成するために使用した $p$ がそのまま $n$ にも使われてしまっていて、 $n$ が $n = pq = p(2p + 1) = 2p^2 + p$ と $p$ だけで表せてしまいます。

$n$ から $p$ を求めることができ、秘密鍵が手に入るので $c$ が復号できフラグが手に入ります。方程式は素直に解いたりしてもよいのですが、今回は横着してSageMathで解きました

n = 2929...
c = 4079...
PR.<x> = PolynomialRing(ZZ)
f = x*(2*x + 1) - n
p = int(f.roots()[0][0])
q = n // p

d = pow(65537, -1, (p-1)*(q-1))
m = pow(c, d, n)
print(bytes.fromhex(hex(m)[2:]).decode())

久々のCTFで環境を構築するのに時間を取られて12分かかっています。

Math (17分)

こちらもRSAの問題です。 $p, q$ に対して $a = p - x, b = q - x$ とそれぞれ表せる $a, b, x$ が存在していて、 $a, b, x$ は平方数であることが分かっていて、 $n, e, c$ に加えて $ab$ と $a, b$ のある約数 $a_f, b_f$ が渡されています。

まず、 $a, b$ は平方数なので $a_f^2, b_f^2$ もそれぞれ $a, b$ の約数になりそうです。 $\frac{ab}{a_f^2b_f^2}$ を計算してみたところ、十分小さい値になってこの値は素因数分解できました。それぞれの素因数が $a, b$ どちらに由来するものかを探索すれば、 $a, b$ は求められたと言って良いでしょう。

$a, b$ がわかれば $n = pq = (a + x)(b + x) = x^2 + x(a + b) + ab$ は未知変数が $x$ だけなのでこれも解くことができて $x$ が求まり、芋づる式に $p, q$ も求められて $c$ が復号できます。

solution scriptはこちら。なんかずいぶん汚くなってしまった。もうちょっと上手にかけると思います

n = 2834...
e = 65537
cipher = 2158...
ab = 2834...

af = 4701...
bf = 3576...

assert ab % (af^2 * bf^2) == 0
factors = list(factor(ab // (af^2 * bf^2)))

PR.<x> = PolynomialRing(ZZ)

for i in range(0, 2**len(factors)):
    a = int(af**2)
    b = int(bf**2)
    for j in range(0, len(factors)):
        if (i >> j) & 1:
            a *= int(factors[j][0]) ** int(factors[j][1])
        else:
            b *= int(factors[j][0]) ** int(factors[j][1])

    f = (a + x) * (b + x) - n
    for ans in f.roots():
        xx = int(ans[0])**int(ans[1])
        if not is_square(xx):
            break

        p = a + xx
        q = b + xx

        d = pow(e, -1, (p-1)*(q-1))
        m = pow(cipher, d, n)
        print(bytes.fromhex(hex(m)[2:]))

ARES (1時間16分)

問題を解いていたときのメモを比較的丁寧に残していたので、そのまま貼ります。

RSA で暗号化したフラグ $c$ がまずもらえて、次のことが無限回できる

1: 任意の平文を RSAで暗号化 → CBCモードのAESで暗号化

2: 任意の暗号文を CBCモードのAESで復号 → RSAで復号

ただし、暗号文は alignされている必要がある

まず $n$ を求める。step 1 のassertは $m \lt n$ しかみてないので $m$ を-1にすれば $n - 1$ が暗号化される。これを2. で復号すればよい

次に2のstep2に頑張って $c$ を渡す

1: 適当な平文を 1 で暗号化

2: [Padding Oracle Attack]の要領で $k$ ブロック目の復号結果が $c$ に一致するように $k-1$ ブロック目の値を適当に変える

当然 $k-1$ ブロック目の値はめちゃめちゃになるが $n, e$ が分かってるので2. のオラクルで得られた結果をRSAで暗号化すれば、2. の AESでの復号結果が手に入る。これで $k-1$ ブロック目のめちゃめちゃな復号結果がわかるので、それが $c$ の対応する値になるように $k-2$ を操作すれば良い

これをそのまま実装すると次のようになります。

from ptrlib import Socket, xor, chunks

sock = Socket("nc ares.beginners.seccon.games 5000")

e = int(65537)
enc_flag = int(sock.recvlineafter("enc_flag: ").strip(), 16)

# find n
sock.sendlineafter("> ", "1")
sock.sendlineafter("m: ", "-1")
c = sock.recvlineafter("c: ")
sock.sendlineafter("> ", "2")
sock.sendlineafter("c: ", c)
n = int(sock.recvlineafter("m: ")) + 1

# create block which AES.decrypt(it) == enc_flag 
sock.sendlineafter("> ", "1")
sock.sendlineafter("m: ", str(2**1000))
c = bytes.fromhex(sock.recvlineafter("c: ").decode().strip())
c = chunks(c, 16)

target = int.to_bytes(enc_flag, 128, "big")
target = chunks(target, 16)

plaintext_block = chunks(int.to_bytes(int(pow(2**1000, e, n)), 128, "big"), 16)

for k in range(1, len(target)):
    c[-(k+1)] = xor(xor(c[-(k+1)], plaintext_block[-k]), target[-k])

    # check how k-1-th block is corruption
    sock.sendlineafter("> ", "2")
    sock.sendlineafter("c: ", b"".join(c).hex())
    m = int(sock.recvlineafter("m: "))
    d = pow(m, e, n)
    d = int.to_bytes(int(d), 128, "big")
    plaintext_block = chunks(d, 16)

# decrypt it
iv = xor(xor(c[0], plaintext_block[0]), target[0])
c = b"".join(c[1:]) # without iv
sock.sendlineafter("> ", "2")
sock.sendlineafter("c: ", (iv + c).hex())
flag = int(sock.recvlineafter("m: "))
print(int.to_bytes(flag, 128, "big"))

この問題はとてもおもしろかったです。シンプルな問題設定から、RSAの世界とAESの世界を行き来する一見複雑そうな解法をひねり出す必要がありますが、解いてみるとだいたいPadding Oracle Attackにうまく落ち着けられてそこそこきれいなスクリプトで解けました。ビギナー向けとしても良い問題だし、複数の暗号システムを組み合わせる問題としてもお手本のような問題だと思いました。

bless (59分)

BLS12-381という楕円曲線( $E_1$ )上の点 $G_1$ と、拡大体上の楕円曲線( $E_2$ )上の点 $G_2$ があって、 $P = sG_1, Q = tG_2, R = cstG_2$ から小さい $c$ を求めるという問題です。

問題の形式を一見するとペアリングのことが思い出され、BLS12-381はあまり馴染みのない楕円曲線ですがペアリングとなにか関連していたということも合わせて思い出されます。

ペアリングとは楕円曲線上の2点 $P, Q$ をある別の有限体に移すような演算 $e(P, Q)$ で、双線形性という性質を持っていて $e(aP, bQ) = e(P, Q)^{ab}$ が満たされます。

これをうまく使えば $e(sG_1, tG_2)^c = e(G_1, cstG_2)$ を満たすような $c$ を探索することで $c$ が求められそうです。

具体的にそのような操作を実現するために"ペアリング BLS12-381"などで検索し、以下の記事を発見できました。記事によると、BLS12-381を扱う上では $E_1, E_2$ のような楕円曲線と、さらに $E_2$ の6次双対(sextic twist)として定義される12次の拡大体上の楕円曲線 $E_{12}$ が登場し、 $E_1, E_2$ 上の点をうまく $E_{12}$ に移すことでペアリング演算が可能なようです。

project-euphoria.dev

この記事のもとになったyoshicampの講義には私も出ていたはずだけど、内容は忘れていたので、スクリプトキディして解きました。記事中で使われていたweil_pairingという関数は、ペアリング対象の点 $P, Q$ の両方が $q$ -torsion pointであることを要求しますが、問題中の $G_2$ は $qG_2 \ne 0$ でこの関数が使えず、かわりに $P$ が $q$ -torsion pointであることしか要求しないtate_pairingを使う必要がある、というのがハマりポイントでした。

import json

p = 0x1a01...
q = 0x73ED...

F1 = GF(p)
E1 = EllipticCurve(F1, (0, 4))
G1 = E1(0x17..., 0x08...)

F2 = GF(p^2, 'x', modulus=x^2+1)
E2 = EllipticCurve(F2, (0, 4*(1+F2.gen())))

F12.<w> = GF(p**12, "w", x**12 - 2*x**6 + 2)
i12 = w**6 - 1
z = w^-1
E12 = EllipticCurve(F12, [0, 4])

def F2_to_F12(coeffs):
    assert len(coeffs) == 2
    c, d = coeffs
    return c + d*i12


def sextic_twist(P):
    x = F2_to_F12(P.x().list())
    y = F2_to_F12(P.y().list())
    return E12(z^2*x, z^3*y)

def load(data):
    P = E1(data["P"]["x"], data["P"]["y"])
    Q = E2(F2(data["Q"]["x"]), F2(data["Q"]["y"]))
    R = E2(F2(data["R"]["x"]), F2(data["R"]["y"]))

    return P, Q, R

data = json.load(open("output.json"))

flag = []
for d in data:
    P, Q, R = load(d)

    a = E12(P).tate_pairing(sextic_twist(Q), q, 12)
    b = E12(G1).tate_pairing(sextic_twist(R), q, 12)
    for v in range(1, 256):
        if a**v == b:
            flag.append(v)
            break
    print(bytes(flag))

ペアリングに関して非常に入門的な、良い問題だったと思います。私もこの問題で初めてペアリングを扱う問題を解くことができて、ペアリングを扱う問題に対する準備ができたと思います。

Try hard in my style (2時間)

RSAの問題で、サーバに接続すると $n, e=17, t_1, t_2, c_1, c_2, c_3$ がもらえます。 $t_1, t_2$ はランダムな値で、 $c_1 = (m + s)^e \pmod n, c_2 = (m + st_1)^e \pmod n, c_3 = (mt_2 + s)^e \pmod n$ です（ただし $s$ はランダムな未知変数）。

暗号文が3つあって、いかにもなんらか暗号文同士の関係性を利用して解けそうです。

とりあえずこのままでは $m, s$ という２つの未知変数があって手も足もでないので、まずはCoppersmith's Short Pad Attack の要領で変数を消去することを考えます。

適当に $c_1, c_2$ に関して $f_1 = (m + s)^e - c_1, f_2 = (m + st_1)^e - c_2$ のような式を立てて、消去式で変数 $s$ を消去すると、 $m$ だけを変数に持つ1変数多項式 $g_1$ にできます。 $c_2, c_3$ についても同様に考えて $g_2$ を手に入れると、共通の根 $m$ を持つ２つの1変数多項式 $g_1, g_2$ が手に入った状態になりました。

あとはこれのGCDを取れば……と思ったのですが、 $g_1, g_2$ にはより大きな共通の根があるようで、 $\gcd(g_1, g_2)$ は $m^17 + \alpha$ という形になりました。どういう理屈でこうなるのかは全くわかりませんが、とにかくこの状態だとまだ解けないので困った。

困っていたのですが、 $f(x) = x^{17} + \alpha$ という式は $m$ を根に持つ17次多項式なので、実質 $m^e \mod n$ です。ここで、「サーバにつなぐたびに新しい値がもらえる」という問題の性質が活きてきて、同じ平文を暗号化していて異なる $n$ , 同じ $e$ をもつRSAの暗号文が $e$ 個集まるならHaståd's Broadcast Attack が可能です。

というわけでこの問題は以下のように解けました

from ptrlib import Socket, crt

def pgcd(a, b):
  while b:
    a, b = b, a % b
  return a.monic()


e = 17
def collect():
    sock = Socket("localhost", 9999)
    # sock = Socket("nc try-hard-in-my-style.beginners.seccon.games 5000")

    # e = int(sock.recvlineafter("e=").strip())
    n = int(sock.recvlineafter("n=").strip())
    t1 = int(sock.recvlineafter("t1=").strip())
    t2 = int(sock.recvlineafter("t2=").strip())
    c1 = int(sock.recvlineafter("c1=").strip())
    c2 = int(sock.recvlineafter("c2=").strip())
    c3 = int(sock.recvlineafter("c3=").strip())

    PR.<m, s> = PolynomialRing(Zmod(n))

    PRz = PolynomialRing(Zmod(n), ["mz", "sz"])
    f1 = (m + s)**e - c1
    f2 = (m + s*t1)**e - c2
    g1 = f1.change_ring(PRz).resultant(f2.change_ring(PRz), s)

    PRy = PolynomialRing(Zmod(n), ["my", "sy"])
    f3 = (m + s*t1)**e - c2
    f4 = (m*t2 + s)**e - c3
    g2 = f3.change_ring(PRy).resultant(f4.change_ring(PRy), s)

    PRn.<mn> = PolynomialRing(Zmod(n))
    h1 = PRn(g1.univariate_polynomial())
    h2 = PRn(g2.univariate_polynomial())

    k = pgcd(h1, h2)
    # m**e 
    c = int(-k.constant_coefficient())
    return c, n

pairs = []
for _ in range(e):
    c, n = collect()
    pairs.append((c, n))
x = crt(pairs)[0]
flag = Integer(x).nth_root(e)
print(bytes.fromhex(hex(flag)[2:]).decode())

考察と実験を繰り返しながら有効な方針を探るというアプローチができて満足度の高い問題でした。問題としても、Franklin-Reister's Related Message Attackを匂わせながら、Coppersmith's Short Pad Attackのような変数の消去と多項式のGCD、Haståd's Broadcast AttackとRSAや多項式への様々なアプローチを横断的に眺める構造になっていて、非常に綺麗だと思います。

Hardというタグに惑わされて変数の消去までに時間を書けてしまったことと、実験でバグらせまくったことで解くのが遅くなってしまったことだけは唯一すこし心残りです。

今年のSECCON Beginners CTFも、非常に面白くかつ教育的で次のCTFへのステップとなるような問題が提供されていて、良質なcryptoセットだと思いました。楽しかったです

*1:難しい2問を私より先に解いていたchocoruskさんが全部取り組んでいたら負けていたとは思いますが……

ふるつき

v('=')v かに