CakeCTF 2021 Writeup+感想
はじめに
ふるつきさん、yoshikingさん、ptr-yudaiさんの最強CTFerらによって開催されたCakeCTFにチームKUDoSとして参加しました。
自分はParty Ticket以外のcrypto4問を解き、全体としては結果は157チーム中6位でした。
最後のcrypto解いても順位変わんなかったから責任逃れできる
いつものように冗長writeup書こうかなとも思ったんですが、4問+αも書くモチベを維持できる気がしないのでflagに至るまでの脳内思考回路を振り返りつつ、ちょっとした感想を付け加えようかなと思います。
なお、自分が解くのにかかった時間を書いていますが、自分は念入りにデバッグしながらコーディングするタイプの人間なのでめちゃくちゃ遅いです。
他の問題と比較して難易度を見やすくするくらいの心持ちでお願いします。
問題一式はGitHubに置いておきます。
discrete log - 129pts (crypto, warmup, 所要時間25分)
People conclude discrete log is hard problem up to now.
from Crypto.Util.number import getPrime, isPrime, getRandomRange def getSafePrime(bits): while True: p = getPrime(bits - 1) q = 2*p + 1 if isPrime(q): return q with open("flag.txt", "rb") as f: flag = f.read().strip() p = getSafePrime(512) g = getRandomRange(2, p) r = getRandomRange(2, p) cs = [] for m in flag: cs.append(pow(g, r*m, p)) print(p) print(g) print(cs)
概要
\begin{align} G^{rm_1} \equiv C_1 \ {\rm mod} \ P \\ G^{rm_2} \equiv C_2 \ {\rm mod} \ P \\ \ \ \ \ \ \ \ \ ...\ \ \ \ \ \ \\ G^{rm_N} \equiv C_{N} \ {\rm mod} \ P \end{align}
大文字は既知で、$ m_i$を求めよという問題。
また$ N$はflagの長さ41で、$ m_i$は0から127までのいずれかです1。
簡易writeup
タイトルにもある離散対数問題は基本的に解けないです。
今回はflagフォーマットがCakeCTF{...}なので、8文字目と41文字目2がそれぞれ123と125とわかります。
この2つを取り出すと
\begin{align} G^{123r} \equiv C_8 \ {\rm mod} \ P \\ G^ {125r} \equiv C_{41} \ {\rm mod} \ P \end{align}
$ x$に対して$ xx^{-1} \equiv \ {\rm mod} \ P$となるモジュラ逆数$ x^{-1}$を考えると、
\begin{align} G^{-123r} \equiv C_8^{-1} \ {\rm mod} \ P \\ G^ {125r} \equiv C_{41} \ {\rm mod} \ P \end{align}
これらを乗算して
$$ G^ {2r} \equiv C_8^{-1} \cdot C_{41} \ {\rm mod} \ P $$
$ P$が4で割って3余る素数なので、$ x^{2} \equiv A \ {\rm mod} \ P$なる平方根$ x$は$x = \pm A^{(P + 1)/4}$で計算できます3。
以下は見やすさのためにあえて1/2乗の書き方をします。
$$ G^ {r} \equiv \left(C_8^{-1} \cdot C_{41}\right)^{1/2} \ {\rm mod} \ P $$
ここまでくれば、$ r$そのものを計算できなくても$ 1, G^{r}, G^{2r}, \cdots , G^{127r}$までが計算できるのでどれが$ C_i$に一致するかを確認するだけでOKです。
注意すべきは平方根は2つ存在することですかね。
ソルバはGitHubにあげるのでそちらを見てください。
感想
特に詰まることはなかったです。
何故か$ p$が4で割ると3余る条件を見落としていたせいで
「平方根求めるのにTonelli-Shanks使わないとしんどくない？Pythonで実装するか、まさかの初手からSage？」
となっていて、最初に解き切った時の感想としては初心者にこれをwarmupとして課すのはいささか鬼だなとは思ってました。
自分的に難易度は(当然)easyでしっかりwarmupだったかなという印象です。
improvisation - 161pts (crypto, 所要時間3時間)
I tried improvisation on making an easy crypto challenge :P
import random def LFSR(): r = random.randrange(1 << 64) while True: yield r & 1 b = (r & 1) ^\ ((r & 2) >> 1) ^\ ((r & 8) >> 3) ^\ ((r & 16) >> 4) r = (r >> 1) | (b << 63) if __name__ == '__main__': with open("flag.txt", "rb") as f: flag = f.read() assert flag.startswith(b'CakeCTF{') m = int.from_bytes(flag, 'little') lfsr = LFSR() c = 0 while m: c = (c << 1) | ((m & 1) ^ next(lfsr)) m >>= 1 print(hex(c))
概要
\begin{align} m_1 \oplus \ r_1 = C_1\\ \ \ \ \ \ \ \ \ ...\ \ \ \ \ \ \\ m_N \oplus \ r_N = C_N\\ r_1 \oplus r_2 \oplus r_4 \oplus r_5 = r_{65} \\ \ \ \ \ \ \ \ \ ...\ \ \ \ \ \ \\ r_{N-64} \oplus r_{N-63} \oplus r_{N-61} \oplus r_{N-60} = r_{N} \end{align}
大文字は既知で、$ m_i$を求めよという問題。
$ N$はflagのビット数300で4、$ m_i, r_i, C_i$は0か1のいずれかです。
また、少し$ m $と$ C $のインデックスの定義が(上のような書き方をしてしまったせいで)特殊になりますが、書くのが面倒なので 割愛。
簡易writeup
flagの先頭がCakeCTF{なので$ m_1$から$ m_{64}$まですぐ分かります。
なので、
\begin{align} m_1 \oplus \ C_1 = r_1\\ \ \ \ \ \ \ \ \ ...\ \ \ \ \ \ \\ m_{64} \oplus \ C_{64} = r_{64} \end{align}
から$ r_1$から$ r_{64}$までもすぐに求まり、
\begin{align} r_1 \oplus r_2 \oplus r_4 \oplus r_5 = r_{65} \\ \ \ \ \ \ \ \ \ ...\ \ \ \ \ \ \\ r_{N-64} \oplus r_{N-63} \oplus r_{N-61} \oplus r_{N-60} = r_{N} \end{align}
から残りの$r_{65}$以降も全て計算可能です。あとは
\begin{align} C_{65} \oplus \ r_{65} = m_{65}\\ \ \ \ \ \ \ \ \ ...\ \ \ \ \ \ \\ C_N \oplus \ r_N = m_N \end{align}
として全ての$ m_i$を復元可能です。やってることはこれだけ。
感想
「やってることはこれだけ」と言いつつ、思ったより時間取られました。理論上はスラスラいけてましたが、全ては$ m $と$ C $のインデックスをややこしく定義してしまった皺寄せがコーディングに来ました。
リトルエンディアンなのかビッグエンディアンなのか、LSBからとるのかMSBからとるのかで混乱しコーディング最弱マンには辛い作業。
この問題に限りflag = f.read()と、末尾にstrip()がついていないので改行が取り除かれません。
このせいで、flagの末尾は}だと思っていたら実は\nだったなんていうトンデモな罠に引っかかりました。
これで1時間溶かしています。なので実質2時間といったところ
また、最初はflagの末尾側から暗号化していくと思っていたので、$ r_{64} $までは非自明だからz3に解かせる系かなぁとも考えていました。
あとはLFSRとか完全に忘却の彼方にあって懐かしいなあと思ったり。
特に難しい知識は要求されないし、ちゃんとコーディングできるかだけですね。自分的に難易度はeasy。
Together as one - 200pts (crypto, lunatic, 所要時間2.5時間)
Stay safe everyone!!!
from Crypto.Util.number import getStrongPrime, bytes_to_long p = getStrongPrime(512) q = getStrongPrime(512) r = getStrongPrime(512) n = p*q*r x = pow(p + q, r, n) y = pow(p + q*r, r, n) m = bytes_to_long(open("./flag.txt", "rb").read()) assert m.bit_length() > 512 c = pow(m, 0x10001, n) print(f"{n = :#x}") print(f"{c = :#x}") print(f"{x = :#x}") print(f"{y = :#x}")
概要
大文字は既知で、$ m $を求めよという問題。
最後の行はただのRSAなので実質$ p, q, r $を求めれば十分です。
簡易writeup
二項展開から
$$ (p+q)^{r} = p^{r} + \ _rC_1p^{r-1}q + \cdots + \ _{r}C_{r-1} pq^{r-1} + q^{r} $$
で、右辺の最初と最後の項以外は$ N = pqr$の倍数となるので5
同様に
これらから
$$ Y-X \equiv q^{r} ( r^{r} - 1 ) \ {\rm mod} \ N $$
よって$ Y-X = q^{r} ( r^{r} - 1 ) + kN $と書け、これは$ q $の倍数となります。
なので$ q $の倍数である$ N $と$ Y-X $との最大公約数を考えれば$ q $が見つかります。
以下は全て$ {\rm mod} \ r$で考え、$ q $が判明しているので大文字で表記します。
Fermatの小定理から、$ r $の倍数ではない任意の$ a $に対して$ a^{r} \equiv a \ {\rm mod} \ r$となるので
$$ X \equiv p+Q \ {\rm mod} \ r $$
です(わからなくなったら二項展開して余分な項を消すと良いです)。同様にして
$$ Y \equiv p \ {\rm mod} \ r $$
これらから
$$ X-Y \equiv Q \ {\rm mod} \ r $$
よって$ X-Y-Q = kr $と書け、これは当然$ r $の倍数となります。
また、$ N, Q $がわかっているので当然$ pr $も計算可能で、これと先程の$X-Y-Q$との最大公約数を考えることで$ r $が求まります。
$ p, q, r $が全てわかれば、あとは$ \phi = (p-1)(q-1)(r-1) $として$ 65537d \equiv 1 \ {\rm mod} \ \phi$なる $ d $を求め、
$$ m = C^{d} \ {\rm mod} \ N $$
で復号可能です。
感想
他の人も評価しているように、シンプルな問題設定でここまでsolve数を絞るのはすごいと思います。
$ q $はすぐ求まりましたがここから結構苦戦しました。自分の思いついた方針としては
上の$ Y \equiv p \ {\rm mod} \ r $ という式と$ pr = N/Q $から$ p, r $が求まるのでは？
ひたすら$ {\rm mod} \ pr$ で考える
$ p, r $が求まらなくとも$\phi$が求まればよく、Eulerの定理から
$$ a^{pr-p-r+1} \equiv 1 \ {\rm mod} \ pr $$
で、$ p + r $や $ a^{p+r}$などが求まれば…
などと考えていました。
こういった感じのアプローチが複数思いつく問題はやりがいがありますね。
ただ、解いてしまっていうのもアレですが、(あとsolve数的に)lunaticは言い過ぎかなと…
気づくまでに時間がかかる系の問題で、個人的にはhardくらいでいいのではと思っています。
なお、解いている時は(というか解けたので)「シンプルなのにこの難易度は一周回って感動してる」となってました。
難易度lunatic表記もあってか、これ以上難しい問題はないだろうしCTF内での最優秀問の候補だろうと思ってましたが、この時はまだ真の絶望を知りませんでした…
Matrix Cipher - 239pts (crypto, 所要時間6時間)
Flag is multiplied and noised, then what should you do ...?
with open("flag.txt", "rb") as f: flag = list(f.read().strip()) def hadamard(M): d = M.determinant() x = 1.0 for row in M: x *= row.norm() return (d / x) ** (1.0/M.ncols()) def keygen(n, d): k = int(floor(sqrt(n) * d)) while True: R = k * Matrix.identity(ZZ, n) + random_matrix(ZZ, n, n, x=-d, y=d) if hadamard(R) >= 0.7: break B = R while True: U = random_matrix(ZZ, n, n, algorithm="unimodular") B = U * B if hadamard(B) <= 0.2: break return B, R def encrypt(B, m): assert B.nrows() == len(m) return vector(ZZ, m) * B + random_vector(ZZ, len(m), x=-50, y=50) B, R = keygen(len(flag), 100) c = encrypt(B, flag) print(list(B)) print(c)
概要
大文字は既知で、$ m_i$を求めよという問題(転置使った方が見やすかったかもしれませんが一応これで)。
また$ N$はflagの長さ46で、$ m_i$は0から127までのいずれか、$ e_i$は-50から50までのいずれかです。
簡易writeup
ソルバはGitHub見て、というスタイルで書いているのでコーディングに関することを省略すると、ここで言えるのはただ一言ですね。
LWE知ってる？？？？
この系統の問題をCVP(Closest Vector Problem)と扱う宗派の人もいるかもしれませんが、いずれにせよこのあたりのジャンル(格子、Latticeと言います)を知らなかったら解けない気がします。
ちなみに補足しておくと、LWE(Learning With Errors)は厳密には
です。素数$ q $のモジュラが追加されます。
ちなみに自分は「LWE CTF Writeup」とググって出てきた博多市さんのWriteupを参考にしました。
感想
まず言い訳をすると、時間がかかったのは朝5時からやり始めたのと、自分がLatticeに異常なまでの苦手意識を持っているからです。
最初プロトタイプで動かした時に全然違う答えが返ってきて、もしやhadaramd周りのフィルタに引っかかってるのでは？などと色々疑ったりしました。
まぁ解けてよかったです。マジで。余計Lattice嫌いを助長して負の連鎖に陥るところでした。
あと、(わかる人からすれば)すぐLWEに酷似していると見抜けて方針が立つので、運営チェックでよくOKでたなと思いますね。
まぁ見抜けたところで難しいには変わりない(solve数が物語っている)し、これ以上捻られると自分も苦しいんですが…
過去のLattice問のWriteup見て分かった 気になっている ので、個人的にはいい機会だと思いました。
難易度はそもそもLatticeという点も加味してやっぱりhardかなと。
Party Ticket - 256pts (crypto, 所要時間不明(12時間？))
Komachi is going to invite Moe and Lulu to the party. But... she is shy and she encrypted the invitations. Nanado's secret mission is to decrypt these tickets so Komachi won't get lonely.
from Crypto.Util.number import getPrime, isPrime from hashlib import sha512 import random def getSafePrime(bits): while True: p = getPrime(bits - 1) q = 2*p + 1 if isPrime(q): return q def make_inivitation(): with open("flag.txt", "rb") as f: flag = f.read().strip() m = int.from_bytes(flag + sha512(flag).digest(), "big") p = getSafePrime(512) q = getSafePrime(512) n = p * q assert m < n b = random.randint(2, n-1) c = m*(m + b) % n return c, n, b # print("Dear Moe:") print(make_inivitation()) # print("Dear Lulu:") print(make_inivitation())
簡易writeup
公式からどうぞ。自分は解いたわけではないのでリスペクトの意も込めて。
感想
Ticket受け取れず
諸悪の根源
Party Ticket被害者の会
作問者を許すな
Komachiも許すな
こんるる
今年度最良問題
以上です。ニコニコ動画に突如表示される赤文字も顔負けの怒涛のコメントラッシュ。
以下思考回路ですが、
Rabin暗号にも気づいていた
だから2回
make_invitaionが呼ばれているのも理解していたCRT(中国人剰余定理)などから絞っていくと踏んでいた
2回呼び出しするなら$ N_1N_2 $と同じくらい(2048 bits)の$ m $にするほうが自然なのに、その半分の長さしかない
だから近似使うのでは？末尾にSHA-2でハッシュ化したものがついているのはそのためか？
$ e=2 $だからLow Public Exponent Attackか？
などと色々考え抜いた末に爆発四散。対あり。
(Generalized) Håstad's Broadcast Attackに思い至らなかったのが全ての敗因ですね。
Together as oneの「このCTF内最優秀問題」なんて比じゃないレベルで、これが一気に今年度最優秀問題に決定しました。
おわりに
運営の御三方ありがとうございました。SECCON Beginners以来フルタイムで参加した大会になりました。CTF終了直後にTwitterが阿鼻叫喚TLになるくらい面白い大会だったと思います。というか作問スキルも高いって何？ cryptoは全て配布コードが短くて、それだけでもう印象最高です。
ここから関係ない話ですが、普段そこまでCTFやらない6同期がsetodaNoteCTFに参加しています。同じCTFerとして嬉しい限りです。期間が長いのとそこまで難しいわけではない(?)初心者向けらしいですね。まだ5日くらいあるらしいですので良ければ、という宣伝でした。
なお、自分は参加してないですがCTF初心者です7。死ぬまで言い続けます。参加しているみんな頑張って…！
