SECCON CTF 2021 Writeup

Sun Dec 12 2021

12/11-12 で開催していた SECCON CTF 2021 にチーム WreckTheLine で参加しました。結果は 14th/506 (得点のあるチームのみカウント) でした。

自分は Crypto に集中して取り組みました。どの Crypto 問もシンプルだけど非自明な感じがあって好きでした。ところで終了後の solves 数を改めて見ると、自分の解いた感覚の難易度と solves 数が結構違くて🤔 なんかシンプルな解法の見落としがあるのかな… (個人の感想としての難易度は難しいほうから oOoOoO > CCC > cerberus > Sign Wars > XXX > pppp でした)

以下、 Crypto の問題について writeup をまとめます。

Crypto

Sign Wars

8 solves

challenge.sage
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Util.Padding import pad
import random
from secret import msg1, msg2, flag

flag = pad(flag, 96)
flag1 = flag[:48]
flag2 = flag[48:]

# P-384 Curve
p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
a = -3
b = 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575
curve = EllipticCurve(GF(p), [a, b])
order = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
Z_n = GF(order)
gx = 26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087
gy = 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871
G = curve(gx, gy)

for b in msg1:
    assert b >= 0x20 and b <= 0x7f
z1 = bytes_to_long(msg1)
assert z1 < 2^128

for b in msg2:
    assert b >= 0x20 and b <= 0x7f
z2 = bytes_to_long(msg2)
assert z2 < 2^384

# prequel trilogy
def sign_prequel():
    d = bytes_to_long(flag1)
    sigs = []
    for _ in range(80):
        # normal ECDSA. all bits of k are unknown.
        k1 = random.getrandbits(128)
        k2 = z1
        k3 = random.getrandbits(128)
        k = (k3 << 256) + (k2 << 128) + k1
        kG = k*G
        r, _ = kG.xy()
        r = Z_n(r)
        k = Z_n(k)
        s = (z1 + r*d) / k
        sigs.append((r,s))

    return sigs

# original trilogy
def sign_original():
    d = bytes_to_long(flag2)
    sigs = []
    for _ in range(3):
        # normal ECDSA
        k = random.getrandbits(384)
        kG = k*G
        r, _ = kG.xy()
        r = Z_n(r)
        k = Z_n(k)
        s = (z2 + r*d) / k
        sigs.append((r,s))

    return sigs


def sign():
    sigs1 = sign_prequel()
    print(sigs1)
    sigs2 = sign_original()
    print(sigs2)


if __name__ == "__main__":
    sign()

ECDSA の鍵としてフラグの前半部 (sign_prequel) と後半部 (sign_original) が使われています。前半部→後半部とフラグを求めていきます。

sign_prequel $i$ 番目の署名について、 $k_1 2^{256} + k_3 = z_1 (s_i^{-1} - 2^{128}) + r_i s_i^{-1} d \mod N$ という式が成り立ちます。 $k_1, k_3$ は128 bitの乱数です。署名は80個得られています。

この式の両辺にある定数をかけることで左辺を小さい値にすることができれば、 Hidden Number Problem (HNP) として LLL で $d$ を求めることができます。まずはこのような定数を探しました。ソルバーとして rkm-san の実装を使いました。

# [x, k1, k2] mat
mat = matrix(ZZ, 3, 3)
mat[0, 0] = 2**256
mat[1, 0] = -order
mat[0, 1]
mat[2, 1] = -order
mat[0, 2] = 1
lb = [0, 0, 0]
ub = [2**190] * 3
res = solve(mat, lb, ub)
x = int(res[2][0])

↑で求めた $x$ を両辺にかけることで、左辺は $2^{190+128}$ 程度の大きさになります。あとは HNP を解きます。

# [z1, d, l1, l2, ...] mat
mat = matrix(ZZ, 82, 82)
for i in range(80):
    r, s = sigs1[i]
    mat[0, i] = (pow(s, -1, order) - 2**128) * x
    mat[1, i] = r * pow(s, -1, order) * x
    mat[i+2, i] = -order
mat[0, 80] = 1
mat[1, 81] = 1
lb = [0] * 82
ub = [2**(190+128)] * 80 + [2**128, 2**(48*8)]
res = solve(mat, lb, ub)
z1 = int(res[2][0])
d1 = int(res[2][1])

これで前半部のフラグ (d1) が求まりました。

sign_original ECDSA の部分を見ると署名は3個しかなく、 $k$ の乱数も384 bitで生成しているので、前半の手法を使うことができません。普通だったらこの条件で $d$ を求めることはできません。

というわけで前半→後半と別れている意味を考えます。乱数生成に注目すると、前半の時点で $128 \times 2 \times 80 = 20480$ bits 分が getrandbits で生成されています。これは32 bit整数640個分に相当します。 getrandbits は Mersenne Twister を使用していますが、この乱数生成方法は32 bit整数が624個がわかっているとき後続の乱数が再現されます。つまり今回の問題のケースでは、後半部分の $k$ の値を乱数生成の観点からリークさせることができます。 $k$ がわかれば当然 $d$ も求まります。

rands = []
for i in range(80):
    r, s = sigs1[i]
    k = int((z1 * pow(s, -1, order) + r * pow(s, -1, order) * d1) % order)
    rands.append(k % 2**128)
    k = k // 2**256
    assert k < 2**128
    rands.append(k)

rands32 = []
for rand in rands:
    for i in range(4):
        rands32.append(int(rand % 2**32))
        rand = rand // 2**32


# https://inaz2.hatenablog.com/entry/2016/03/07/194147
def untemper(x):
    x = unBitshiftRightXor(x, 18)
    x = unBitshiftLeftXor(x, 15, 0xefc60000)
    x = unBitshiftLeftXor(x, 7, 0x9d2c5680)
    x = unBitshiftRightXor(x, 11)
    return x

def unBitshiftRightXor(x, shift):
    i = 1
    y = x
    while i * shift < 32:
        z = y >> shift
        y = x ^^ z
        i += 1
    return y

def unBitshiftLeftXor(x, shift, mask):
    i = 1
    y = x
    while i * shift < 32:
        z = y << shift
        y = x ^^ (z & mask)
        i += 1
    return y

mt_state = tuple([int(untemper(x)) for x in rands32[:624]] + [int(624)])
random.setstate((int(3), mt_state, None))
for _ in range(640 - 624):
    random.getrandbits(32)

k1 = random.getrandbits(384)
k2 = random.getrandbits(384)

kG1 = k1*G
kG2 = k2*G
r1, s1 = sigs2[0]
r2, s2 = sigs2[1]
assert kG1.xy()[0] == r1
assert kG2.xy()[0] == r2

d2 = int((s1 * k1 - s2 * k2) * pow(r1 - r2, -1, order))
long_to_bytes(d1) + long_to_bytes(d2)

SECCON{New_STARWARS_Spin-Off_The_Book_Of_Boba_Fett_Will_Premiere_On_December_29-107c360aab}

XXX

14 solves

task.sage
import os

flag = os.getenv("FLAG", "fake{fakeflag_blahblah}")
x = int.from_bytes(flag.encode(), "big")

p = random_prime(1 << int(x.bit_length() * 2.5))
Fp = GF(p)

params = []
while len(params) != 6:
    try:
        y = randint(2, x)
        a = randint(2, p-1)
        b = (y^2 - (x^3 + a*x)) % p

        EC = EllipticCurve(Fp, [a, b])
        EC(x, y)

        params.append([a, b])
    except ValueError:
        pass

print(p)
print(params)

フラグの値を $x$ をしたとき、ある $y$ をランダムに生成し、 $(x, y)$ が楕円曲線 $y^2 = x^3 + ax + b$ 上に乗るような $(a, b)$ がランダムに生成されます。 $(a, b)$ が6種類与えられています。

$i$ 番目の楕円曲線を $y^2 = x^3 + a_ix + b_i$ とおきます。 $i$ 番目と $j$ 番目の式の差を考えると、 $y_i^2 - y_j^2 = (a_i - a_j)x + (b_i - b_j)$ となります。ここで各項のbit数を見てみると、左辺が右辺の各項に対して小さいことがわかります。そのため、 LLL を使って $x$ が求められそうです。

solve.py
from itertools import combinations
from Crypto.Util.number import long_to_bytes


mat = matrix(ZZ, 17, 17)
for k, (i, j) in enumerate(combinations(range(6), 2)):
    ai, bi = params[i]
    aj, bj = params[j]
    mat[0, k] = ai - aj
    mat[1, k] = bi - bj
    mat[k+2, k] = -p
mat[0, 15] = 1
mat[1, 16] = p
res = mat.LLL()
C = mat.solve_left(res)

for c in C:
    print(long_to_bytes(abs(round(c[0]))))

SECCON{9dd4e461268c8034f5c8564e155c67a6}

cerberus

16 solves

problem.py
import base64
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.strxor import strxor
from flag import flag
import signal

key = get_random_bytes(16)
block_size = 16

# encrypt by AES-PCBC
# https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Propagating_cipher_block_chaining_(PCBC)
def encrypt(m):
    cipher = AES.new(key, AES.MODE_ECB)  # MODE_PCBC is not FOUND :sob: :sob:
    m = pad(m, 16)
    m = [m[i : i + block_size] for i in range(0, len(m), block_size)]

    iv = get_random_bytes(16)

    c = []
    prev = iv
    for m_block in m:
        c.append(cipher.encrypt(strxor(m_block, prev)))
        prev = strxor(c[-1], m_block)

    return iv, b"".join(c)


# decrypt by AES-PCBC
# https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Propagating_cipher_block_chaining_(PCBC)
def decrypt(iv, c):
    cipher = AES.new(key, AES.MODE_ECB)  # MODE_PCBC is not FOUND :sob: :sob:
    c = [c[i : i + block_size] for i in range(0, len(c), block_size)]

    m = []
    prev = iv
    for c_block in c:
        m.append(strxor(prev, cipher.decrypt(c_block)))
        prev = strxor(m[-1], c_block)

    return b"".join(m)


# The flag is padded with 16 bytes prefix
# flag = padding (16 bytes) + "SECCON{..."
signal.alarm(3600)
ref_iv, ref_c = encrypt(flag)
print("I teach you a spell! repeat after me!")
print(base64.b64encode(ref_iv + ref_c).decode("utf-8"))

while True:
    c = base64.b64decode(input("spell:"))
    iv = c[:16]
    c = c[16:]

    if not c.startswith(ref_c):
        print("Grrrrrrr!!!!")
        continue

    m = decrypt(iv, c)

    try:
        unpad(m, block_size)
    except:
        print("little different :(")
        continue

    print("Great :)")

AES の PCBC モードを使った Padding Oracle Attack 問題。 PCBC モード初めて知った… 少々困る制約として、復号してもらう暗号の前半部分は、フラグを暗号化したものである必要があります。フラグの暗号文が64bytesなことから4ブロックあることがわかります。

上記リンクの復号スキームの画像とにらめっこをしているとすぐわかることですが、 IV に対して何らかの値で xor をとると、復号結果の各ブロックそれぞれに対してその値の xor が加えられます。この特徴を使うことで暗号文の最後のブロックに対して Padding Oracle Attack が適用でき、復号することができます。

よくある Padding Oracle Attack の問題では、最後のブロックを一つ求めては削っていくことで全ブロックの復号ができます。しかしこの問題では送信する暗号の前半部がフラグの暗号と一致している必要があり、最後のブロックを削るということができません。ひと工夫必要です。

今、 $C_0 || C_1 || C_2 || C_3 || C_0$ を ref_iv を使って復号してもらうことを考えます。最後のブロックの復号結果は $P_4 = \mathrm{Dec}_k(C_0) \oplus (C_3 \oplus P_3)$ となります。 $P_0 = \mathrm{IV} \oplus \mathrm{Dec}_k(C_0)$ であることを使うと $P_4 = P_0 \oplus \mathrm{IV} \oplus C_3 \oplus P_3$ となります。ここから最後のブロックの復号結果が $P_0$ と同じになるための iv を求めることができ、その状態から Padding Oracle Attack を使って $P_0$ を求められます。これを繰り返すことで全てのブロックの復号結果をリークできます。

solve.py
from pwn import remote

io = remote("cerberus.quals.seccon.jp", 8080)
_ = io.recvline()
c = b64decode(io.recvline().strip())
ref_iv = c[:16]
ref_c = c[16:]


def try_decrypt(iv, c):
    io.sendlineafter(b"spell:", b64encode(iv + c))
    ret = io.recvline().strip().decode()
    if "little" in ret:
        return False
    elif "Great" in ret:
        return True
    else:
        io.close()
        raise ValueError


dec = b""
iv = ref_iv
for idx in range(16)[::-1]:
    print(idx)
    for i in range(256):
        tmp_iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
        if (idx == 15 and i == 0) or not try_decrypt(tmp_iv, ref_c):
            continue
        dec = long_to_bytes((16 - idx) ^ i) + dec
        print(dec)
        iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
        iv = iv[:idx] + xor(iv[idx:], long_to_bytes(16-idx), long_to_bytes(16-idx+1))
        break
print(dec)
dec3 = dec
iv = xor(iv, b"\x11", ref_c[-16:], ref_iv)
dec = b""
for idx in range(16)[::-1]:
    print(idx)
    for i in range(256):
        tmp_iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
        if (idx == 15 and i == 0) or not try_decrypt(tmp_iv, ref_c+ref_c[:16]):
            continue
        dec = long_to_bytes((16 - idx) ^ i) + dec
        print(dec)
        iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
        iv = iv[:idx] + xor(iv[idx:], long_to_bytes(16-idx), long_to_bytes(16-idx+1))
        break
print(dec)
dec0 = dec
iv = xor(iv, b"\x11", ref_c[:16], ref_c[:16], dec)
dec = b""
for idx in range(16)[::-1]:
    print(idx)
    for i in range(256):
        tmp_iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
        if (idx == 15 and i == 0) or not try_decrypt(tmp_iv, ref_c+ref_c[:32]):
            continue
        dec = long_to_bytes((16 - idx) ^ i) + dec
        print(dec)
        iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
        iv = iv[:idx] + xor(iv[idx:], long_to_bytes(16-idx), long_to_bytes(16-idx+1))
        break
print(dec)
dec1 = dec
iv = xor(iv, b"\x11", ref_c[16:32], ref_c[16:32], dec)
dec = b""
for idx in range(16)[::-1]:
    print(idx)
    for i in range(256):
        tmp_iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
        if (idx == 15 and i == 0) or not try_decrypt(tmp_iv, ref_c+ref_c[:48]):
            continue
        dec = long_to_bytes((16 - idx) ^ i) + dec
        print(dec)
        iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
        iv = iv[:idx] + xor(iv[idx:], long_to_bytes(16-idx), long_to_bytes(16-idx+1))
        break
print(dec)
dec2 = dec
flag = dec0 + dec1 + dec2 + dec3
print(flag)

SECCON{v._.^v-_-v^._.^_S0und_oF_0rpHeUs_Aha~~}

日本のサーバーだからなのか、 Padding Oracle Attack 問なのに oracle が高速だったので待ち時間があまりなくストレスフリーでした。

CCC

17 solves

challenge.py
from Crypto.Util.number import bytes_to_long, getPrime, getRandomInteger, isPrime
from secret import flag


def create_prime(p_bit_len, add_bit_len, a):
    p = getPrime(p_bit_len)
    p_bit_len2 = 2*p_bit_len // 3 + add_bit_len
    while True:
        b = getRandomInteger(p_bit_len2)
        _p = a * p
        q = _p**2 + 3*_p*b + 3*b**2
        if isPrime(q):
            return p, q


def encrypt(p_bit_len, add_bit_len, a, plain_text):
    p, q = create_prime(p_bit_len, add_bit_len, a)
    n = p*q
    e = 65537

    c = pow(plain_text, e, n)
    print(f"{n=}")
    print(f"{e=}")
    print(f"{c=}")
    print(f"{a=}")


if __name__ == "__main__":
    encrypt(1024, 9, 23, bytes_to_long(flag))

RSA の公開鍵 $n = pq$ について、 $q = a^2p^2 + 3abp + 3b^2$ が成り立ちます。 $a = 23$ で $b$ は乱数で生成されています。 $p$ は1024bitで $b$ は691bitです。

手計算をすると $an = (ap)^3 + 3b(ap)^2 + 3b^2(ap) = (ap + b)^3 - b^3$ と変形できます。 $b^3$ は十分小さいため無視して考えると $ap + b \simeq (an)^{1/3}$ と近似できます。試しに自分で生成した $p, b$ について以上の近似がどれだけ成り立つか確認してみると、 $2^{12}$ bit程度の誤差になりました。これは全探索するのに十分小さい値なので $ap + b$ の正確な値を探索させました。

solve.py
from gmpy2 import iroot


ap_b_approx = int(iroot(a * n, 3)[0])
for i in range(10000):
    tmp = ap_b_approx + i
    if tmp ** 3 - a * n < 0:
        continue
    root, exact = iroot(tmp ** 3 - a * n, 3)
    if exact:
        b = int(root)
        ap_b = tmp
        print(root)
p = (ap_b - b) // a
assert n % p == 0
q = n // p
phi = (p - 1) * (q - 1)
d = int(pow(e, -1, phi))
print(long_to_bytes(int(pow(c, d, n))))

SECCON{CCC_means_Cubic_root_and_the_CTF_I_learnt_a_lot_about_fermat's_factorization_method}

oOoOoO

26 solves

problem.py
import signal
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import random
from flag import flag

message = b""
for _ in range(128):
    message += b"o" if random.getrandbits(1) == 1 else b"O"

M = getPrime(len(message) * 5)
S = bytes_to_long(message) % M

print("M =", M)
print('S =', S)
print('MESSAGE =', message.upper().decode("utf-8"))

signal.alarm(600)
ans = input('message =').strip().encode()

if ans == message:
    print(flag)
else:
    print("🧙")

o か O で構成された128文字の文字列の数値に対して、ある素数 $M$ で mod を計算したもの $S$ が与えられます。元の文字列を当てられればフラグが手に入ります。

o は 0x6f、O は 0x4f です。この文字列を数値で表すと $\sum_{k=0}^{127}(79 + 32x_k)256^{k}$ となります。ここで $x_k$ は末尾から数えて $k$ 番目が O のとき0, o のとき1となります。 $M$ と $S$ の関係性は $\sum_{k=0}^{127}(79 + 32x_k)256^{k} = S \mod M$ と記せます。問題の見方を変えると、集合 $\{32 \times 256^k | 0 \le k < 128 \}$ のどの部分集合の和を取ると $S - 79\sum_{k=0}^{127} 256^k$ になるかを求める問題となります。これは部分和問題です。

自分はこの問題を $\sum_{k=0}^{127} 32\times 256^k x_k = S - 79\sum_{k=0}^{127}256^k \mod M$ となる $x_k$ を LLL のような格子基底簡約アルゴリズムを使って解くことにしました。 mod のぶんは全探索しました (最大でも20-30種類程度しかない)。しかし LLL だと答えが出ず、 BKZ を使ってみると答えが得られました。 BKZ よく知らないんだよな…

solve.py
from pwn import remote

io = remote("oooooo.quals.seccon.jp", 8000)
io.recvuntil(b"M = ")
M = int(io.recvline())
io.recvuntil(b"S = ")
S = int(io.recvline())

res = 0
for i in range(128):
    res += 0x4f * 256**i
res -= S
res %= M
target = -res % M
cands = []
for i in range(128):
    cands.append(int(0x20 * 256**i % M))

def check(res):
    for r in res[0]:
        if abs(r) != 0 and abs(r) != 1:
            return False
    return True

for j in range(20):
    print(j)
    mat = matrix(ZZ, 129, 129)
    for i in range(128):
        mat[i, i] = 1
    for i in range(128):
        mat[i, 128] = cands[i]
    mat[128, 128] = -(j*M+target)
    weights = diagonal_matrix([1] * 128 + [12])
    mat *= weights
    res = mat.BKZ()
    res /= weights
    if check(res):
        break
dec = b""
for i in range(128):
    if res[0][i] == 0:
        dec = b"O" + dec
    elif abs(res[0][i]) == 1:
        dec = b"o" + dec
print(dec)
io.sendlineafter(b"message =", dec)
print(io.recvline())

SECCON{Here_is_Huge-Huge_Island_yahhoOoOoOoOoOoO}

この問題がここまで解かれてるのすごい、 SECCON beginners でナップサック暗号が出たからなのだろうか。

pppp

70 solves

problem.sage
from Crypto.Util.number import *
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q

mid = len(flag) // 2

e = 65537

m1 = int.from_bytes(flag[:mid], byteorder='big')
m2 = int.from_bytes(flag[mid:], byteorder='big')

assert m1 < 2**256
assert m2 < 2**256

m = [[p,p,p,p], [0,m1,m1,m1], [0,0,m2,m2],[0,0,0,1]]

# add padding
for i in range(4):
    for j in range(4):
        m[i][j] *= getPrime(768)

m = matrix(Zmod(p*q), m)

c = m^e

print("n =", n)
print("e =", e)
print("c =", list(c))

上三角行列を RSA で暗号化した問題。

上三角行列なので対角項の暗号文 $C_{ii}$ は $C_{ii} = M_{ii}^e \mod n$ となります。 $M_{00} = k_{00}p$ ( $k$ は未知の素数) であることを考慮すると、 $\gcd(C_{00}, n)$ で $p$ が求まります。 $p$ が求まったので RSA の復号ができるようになり、もともとの行列の対角にある $M_{11} = k_{11}m_1, M_{22} = k_{22}m_2$ も求まります。これらの $M_{11}, M_{22}$ が素因数分解できればフラグは求まるのですが、流石にできないようになっていました ( $M_{11}$ のほうはできたけど $M_{22}$ はできなかった)。

次に $C_{12}$ や $C_{23}$ の値が $M$ の値を使ってどう表されるかを見てみると、 $C_{12} = M_{12}\sum_{i=0}^{e-1} M_{22}^i M_{11}^{e-1-i} \mod n$ となります。 $M_{11}, M_{22}$ は上記の方法で求まるので $M_{12}$ も求まります。 $M_{12} = k_{12} m_1$ という形なので、 $\gcd(M_{11}, M_{12})$ で $m_1$ が求まります。 $C_{23}$ に注目すると同様の方法で $m_2$ も求まります。

solve.py
p = gcd(c[0][0], n)
q = n // p
c1 = c[1][1]
c2 = c[2][2]
phi = (p - 1) * (q - 1)
d = int(pow(e, -1, phi))

m00 = int(pow(c[0][0], d, n))
m11 = int(pow(c1, d, n))
m22 = int(pow(c2, d, n))
m33 = int(pow(c[3][3], d, n))

tmp = 0
for i in range(e):
    tmp += pow(m22, i, n) * pow(m11, e-1-i, n)
m12 = int(c[1][2] / tmp)

tmp = 0
for i in range(e):
    tmp += pow(m33, i, n) * pow(m22, e-1-i, n)
m23 = int(c[2][3] / tmp)

print(long_to_bytes(gcd(m11, m12)) + long_to_bytes(gcd(m22, m23)))

SECCON{C4n_y0u_prove_why_decryptable?}