CPCTF 2024 writeup

久しぶりにCTFに参加しました。cryptoのある程度以上の難易度の問題を解いたら満足してしまって、昔CTFを開催していたときに「この人いつも特定のジャンルの問題だけ解いて帰るな～」と思って見ていた人の気持ちってこういうことだったんだろうな、と思いました。

取り組んだ問題は面白かったし、解いていて楽しかったです。

[Crypto] AAAA
[Crypto] CES

[Crypto] AAAA

ほぼ全てがマスクされたOpenSSH形式のRSAの秘密鍵を見せてもらえます。わかるのは鍵の一部のBASE64がTOKYO+INSTITUTE+OF+TECHNOLOGY+DIGITAL+CREATORS+CLUB+TRAPAAAA を含むということだけ。

しかしそれ以外にも、公開鍵と暗号文、それから $ed / \phi(n)$ を貰えます。

RSAの $e, d$ には $ed \equiv 1 \mod \phi(n)$ という関係があり、適当な整数 $k$ を用いて $ed = 1 + k\phi(n)$ と書いて両辺 $\phi(n)$ で割ると、与えられている $ed / \phi(n)$ はほとんど $k$ と一致する事がわかります。

今回の問題設定では $e$ が大きく、ほとんど $n$ くらいの大きさがあることと合わせて考えると

$ed = 1 + k\phi(n) = 1 + k(n - s + 1)$

について $\mod e$ を取ると $1 + k(n - s + 1) \equiv 0 \mod e$ という式が立ち*1、未知数は $s$ のみで、 $e$ の半分程度の大きさになるはずなので、この剰余多項式の小さい根を求めれば $s$ が求まります。 $s$ がわかれば $\phi(n)$ が求められるのであとは $d$ を求めて暗号文を復号すればよいです。

問題に与えられていた文字列は $d$ のbase64結果のようでした

from base64 import b64decode, b64encode

e = 506184338...
n = 12339326...
k = 6649705358687...

PR.<x> = PolynomialRing(Zmod(e))
f = 1 + k*n - k*x + k
f = f.monic()

s = int(f.small_roots(X=floor(3 * n**0.5), beta=0.5)[0])
phi = n - s + 1

d = int(pow(e, -1, phi))
c = 91909831...

m = pow(c, d, n)
print(bytes.fromhex(hex(m)[2:]))

[Crypto] CES

以下のいずれかを合計2回だけ行えるサーバに接続できます。

任意の平文をCES-CBCで暗号化する
フラグをCES-CBCで暗号化する

CESはAESに手を加えたブロック暗号で、subbytesの実装が次のようになっていること以外はオリジナルのAESの実装と同じです。

def concat(a, b):
    tmp = int("{:064b}".format(a) + "{:064b}".format(b), 2)
    tmp_bin_list = [int(n) for n in bin(tmp)[2:]]
    irreducible_poly = [1, 0, 0, 0, 1, 1, 0, 1, 1]
    res = np.polydiv(tmp_bin_list, irreducible_poly)[1]
    res = list(map(int, res))
    res = [x % 2 for x in res]
    res = "".join(map(str, res))
    res = int(res, 2)
    return res

def sub_bytes(s, round_key):
    for i, line in enumerate(s):
        for j, x in enumerate(line):
            k = bytes_to_long(matrix2bytes(round_key))
            res = concat(k, s[i][j])
            assert concat(k, res) == s[i][j]
            s[i][j] = res

    return s

このconcat, subbytes がどういう実装になっているのかはわかりませんでしたが、assert の条件をながめていると「このsubbytesの実装は線形な変換になっているのでは」と思いました。

AESの各種ステップのうち非線形な変換はsubbytesだけですから、この実装が線形になればCESによる暗号化は線形な変換になります。つまり、平文 $m$ を鍵 $k$ で暗号化したとき、暗号文 $c$ の各ビットが $m$ と $k$ の何らかのビットのXORで表せます。鍵の足し方は平文によりませんから、異なる平文 $m, m'$ を同一の鍵 $k$ で暗号化した $c, c'$ について $m \oplus m' = c \oplus c'$ となるはずです。

ということを実験したらまさにそうなったので、サーバの実装では1, 2で同じ鍵が使われることを利用して、2で得た暗号化された平文を1で作った適当な平文の暗号文を用いて復号するコードを書きました

from ptrlib import Socket, chunks, xor
import ast
from problem import bytes2matrix, matrix2bytes, N_ROUNDS, inv_shift_rows, inv_mix_columns

def my_decrypt(ciphertext):
    state = bytes2matrix(ciphertext)

    for i in range(N_ROUNDS - 1, -1, -1):
        inv_shift_rows(state)
        if i > 0:
            inv_mix_columns(state)

    plaintext = matrix2bytes(state)
    return plaintext


sock = Socket("ces.web.cpctf.space 30008")
sock.sendlineafter("option: ", "2")
f_enc = ast.literal_eval(sock.recvlineafter("flag: ").decode()) 
iv = ast.literal_eval(sock.recvlineafter("iv: ").decode())

sock.sendlineafter("option: ", "1")
payload = "A" * len(f_enc)
sock.sendlineafter("encrypt: ", payload)
enc = ast.literal_eval(sock.recvlineafter("message: ").decode()) 
iv2 = ast.literal_eval(sock.recvlineafter("iv: ").decode())

flag = b""

for c1, c2 in zip(chunks(f_enc, 16), chunks(enc, 16)):
    c_wo_k = my_decrypt(xor(c1, c2))
    

    flag_i = xor(xor(c_wo_k, xor(b"A" * 16, iv2)), iv)
    flag += flag_i
    print(flag)

    iv = c1
    iv2 = c2

AESがそれっぽく改造されており一見難問にみえるものの、assertで性質をさりげなく表現することで難易度が調節されており、良い問題だったと思います。

*1:s = p + qとおいてます