CakeCTF 2022の振り返り - アロワナ飼いたい

■ 概要

9月3日から4日にかけて行われたCakeCTF 2022のメモ。辛うじて解けた2問に対するアプローチや解法などをまとめる。6時間ほど取り組んで、最終的に161位（チーム：4r0wana）に落ち着いた。

■ nimrev（warmup, rev）

タイトルからするに、Nimで作成されたと思われるプログラムが与えられる。Ghidraで中身を確認し、フラグの入力や正誤判定を行っているであろうNimMainModule関数を見つけた。

知識不足により、内部処理を読み解くことができなければ、angrでうまく解くこともできなかったので、NimMainModule関数内に書かれている0xbc, 0x9e, 0x94, 0x9a, … がフラグに該当すると仮定し、解析を進めることにした。

フラグフォーマットの先頭がCakeなので、ひとまず0xbc, 0x9e, 0x94, 0x9aが、それぞれC, a, k, eに対応すると考えた。さらに、2つ目の16進数0x9e（aと仮定したもの）から、1つ目の16進数 0xbc（Cと仮定したもの）を引いてみると、-0x1eが得られた。ここで、aのasciiコード0x61からCのasciiコード0x43を引くと、0x1eとなる（-(-0x1e)）。3つ目の16進数から2つ目の16進数においても同様の関係が確認でき、これをスクリプトに落としてみるとフラグが得られた。

flag = [0xbc, 0x9e, 0x94, 0x9a, 0xbc, 0xab, 0xb9, 0x84, 0x8c, 0xcf, 0x92, 0xcc, 0x8b, 0xce, 0x92, 0xcc, 0x8c, 0xa0, 0x91, 0xcf, 0x8b, 0xa0, 0xbc, 0x82]
c = 0x43
print(chr(c), end = "")
for i in range(len(flag)-1):
    c = c - (flag[i + 1]- flag[i])
    print(chr(c), end = "")

フラグ：CakeCTF{s0m3t1m3s_n0t_C}

■ frozen cake（warmup, crypto）

以下のようなスクリプトファイルが与えられる。

from Crypto.Util.number import getPrime
import os

flag = os.getenv("FLAG", "FakeCTF{warmup_a_frozen_cake}")
m = int(flag.encode().hex(), 16)

p = getPrime(512)
q = getPrime(512)

n = p*q

print("n =", n)
print("a =", pow(m, p, n))
print("b =", pow(m, q, n))
print("c =", pow(m, n, n))

$a = m^{p} \pmod {pq}, b = m^{q} \pmod {pq}, c = m^{pq} \pmod {pq}$ から $m$ を求める問題であることが分かる。始めはcommon modulus attackを使うのかと思ったが、指数が大きくうまくいかなかった。しばらく考えて、オイラーの定理（ $m^{\phi(n)}=1 \pmod n$ ： $\phi$ はオイラー関数）を使えば解けることに気付いた。

$\phi(pq) = (p-1)(q-1) = pq - (p + q) + 1$ であるから、以下が成り立つ。

$\displaystyle m^{pq - (p + q) + 1} = 1 \pmod {pq}$

上記の両辺に、 $m^{-1}$ をかけると、次のようになる。

$\displaystyle m^{pq - (p + q)} = m^{-1} \pmod {pq}$

ここで、 $\dfrac{c}{ab} = \dfrac{m^{pq}}{m^{p+q}} = m^{pq - (p+q)}$ であるから、結局は次が成り立つ。

$\displaystyle \frac{c}{ab} = m^{-1} \pmod {pq}$

これは、法 $pq$ の世界において、 $\dfrac{c}{ab}$ の逆元が $m$ と等しいことを表している。
この関係式を用いて、SageMathで $m$ の値を求めてみる。

$m$ が求められたので、あとは符号化処理を逆にたどればよい。

m = 8578537138843288659565828766182090884888045982768979615020663957703563826911332397091027325
print(bytes.fromhex(hex(m)[2:]))

フラグ：CakeCTF{oh_you_got_a_tepid_cake_sorry}

■ 感想

各ジャンルのwarmup問は解き切りたかったのですが、残念ながら無理でした。CakeGEAR（warmup, web）に関しては、sha1 ハッシュ値の解析を目指すという明らかに間違った方向に進んでしまったので、要復習です。運営の皆様、ありがとうございました。参加者の皆様、お疲れさまでした。