CTF をやり始めたので、解いた問題の記録を書いていく

ding-dong-ting-ping (CakeCTF 2023)

AlpacaHack で解いた。

問題

サーバーに対して次の操作ができる

1. register: {PREFIX}|user={username}|{timestamp} を暗号化したものを教えてくれる。username は base64 で渡すので、任意のバイト列を渡すことができる。PREFIX は不明。username に root が入っていたらだめ
2. login: register で作ったものを渡すと、username を返してくれる。これが root ならフラグがもらえる。解いてるときは気にしていなかったが、decode() しているので UTF-8 じゃないバイト列になってしまうとエラーらしい

暗号化は 16 byte block の AES-CBC みたいなものだが、通常の CBC では前の block の暗号文と現在の block の平文の XOR をとるのに対し、この問題では前の block の暗号文 の MD5 と現在の block の平文の XOR をとる。

解法

{PREFIX}|user=root|(なにか) を暗号化したものが得られれば勝ち。

block 境界がわからないと何もできないので、まず PREFIX の長さを求めることを考える。
usernameに aaaabaaaaaaa... みたいなものを b の位置を変えて渡して、どのブロックまで暗号文が一致しているかを観察することで、{PREFIX}|user= 部分の長さがわかる。今回の場合これが 23 であるとわかる。特に、PREFIX の長さは 17 である。

block 境界がわかったので、username に適当に長いバイト列を渡して、適当な block を見ると、その block の暗号文は AES(md5(その前の block の暗号文) xor (その block の平文)) となる。なので、その block の平文を細工することで、任意の 16 byte block に対して AES(block) を直接求めることができる。

{PREFIX}|user=root|(なにか) を暗号化することを考える。これは次のようにブロックに分割できる:

1. PREFIX の先頭 16 文字
2. ? を PREFIX の末尾の文字として、?|user=root|...
3. (なにか) の後ろのほう

1 を暗号化した結果はわかっているので、2 の ? が分かれば先ほどの手続きにより全体を暗号化した結果も求められることになる。? は 1 バイトで、あり得るものは高々 256 通りしかないので、適当に長い username に対して ? を全通り試して先ほどの手続きで正しい暗号化結果になるものを選べばよい。

janken vs yoshiking 2 (CakeCTF 2023)

AlpacaHack で解いた。

問題

素数 p と、mod p でのランダムな 5 \times 5 行列 M が与えられる。適当な整数 r に対して M^r \pmod p が与えられるので、r \bmod 3 を決定せよ。

解法

mod p での 5 \times 5 行列のうち可逆なものは、乗法に対して群をなすが、その位数は d = p^{10} (p^5 - 1)(p^4 - 1)(p^3 - 1)(p^2 - 1)(p - 1) である (cf. https://note.com/shiny_broom989/n/nb718170f755d) 。M はランダムかつ p は十分大きいので、ほとんどの場合 M は可逆である。

今回、d は 3 で 6 回割り切れる。ここで、M^{d/3^5} は（少なくとも）だいたいの場合 I となることが実験的に確かめられる。M^{d/3^6} = I となる事象は多分 1/3 くらいの確率でしか起きないので、そうなったらやりなおす。M^{d/3^6} \neq I ならば、M^{r \cdot d/3^6} は I, M^{d/3^6}, M^{2\cdot d/3^6} の 3 通りの値しかとらず、このどれになるかは r \bmod 3 によって決まることから、r \bmod 3 を決定できた。

ただ、この解法だと M^{d/3^6} = I とならなくても不正解になる場合がある。このとき何が起きているのかはよくわからない。

AlpacaHack Round 3 (Crypto)

14 位。

qrime

問題

P(n) を n より大きい最小の素数とする。n = pq, r は既知、p, q は素数、p = P(q)r + qP(r) のとき、n を素因数分解せよ。

解法

素数定理より、平均的に P(n) - n \sim O(\log n) なので、P(q) - q を全探索することができる。この値を決め打つと (r は既知なので) p は q の二次方程式の形で書けて、q を決定できる。

Rainbow Sweet Alchemist

問題

以下の手順で 1024 ビットの素数を作る。

1. 64 ビットの素数を 16 個作る。
2. その積の 2 倍 + 1 が素数かを判定する。素数ならばそれを返し終了する。
3. 素数でないならば、今持っている 16 個の素数のうち 1 個ランダムに選んで、それを新たに作った 64 ビット素数で置き換え、2 に戻る。

ただし、64 ビット素数を作る過程は deterministic である（i 回目に作った素数が何になるかは既知である）。16 個のうち 1 個選ぶ過程は non-deterministic である。

この過程を 2 回繰り返して素数 p, q を得る。n=pq を素因数分解せよ。

解法

実験すると、↑の過程で n を得るまでに、64 ビット素数を作る過程は 800 回程度しか実行されないと見積もれる。

p=2p_1 p_2 \dots p_{16} + 1, q=2q_1 q_2 \dots q_{16} + 1 (q_i は素数) と書けるので、
\phi(n) = (p-1)(q-1) = 4p_1 \dots p_{16} q_1 \dots q_{16} である。各 p_i, q_i は、800 回の素数生成過程で生成されるもののうちどれかである。

R = \{ r_1, \dots, r_m \} を素数の集合とするとき、2^{r_1 \dots r_m} \equiv 1 \pmod n と \{ p_1, \dots, p_{16}, q_1, \dots, q_{16} \} \subseteq \{ r_1, \dots, r_m \} はほぼ同値である（これに違反する確率は十分低いので無視する）。よって、2^{r_1 \dots r_m} \equiv 1 \pmod n である限り R から素数を 1 個ずつ除いていくことで、\{ p_1, \dots, p_{16}, q_1, \dots, q_{16} \} を求めることができる。こうして得られた 32 個の素数のうち、生成された巡目が早いほうから 16 個が p、残る 16 個が q を得るために使われる。

A Dance of Add and Mul

問題

暗号文をビット列で m_1, \dots, m_b とする。

楕円曲線 E: BLS12-381 を考える。Eが (G_1, G_2) によって生成されるとする（どのような G_1, G_2 をとったかは既知）。
このとき、o_1, o_2 を G_1, G_2 の位数、x_0, x_1, \dots, x_m を乱数とする。

c_i を、m_1=0 のとき x_{i-1} \cdot G_1 + x_i \cdot G_2、m_1=1 のとき x_{i-1} \cdot G_2 + x_i \cdot G_1 で定める。c_i が既知のとき、m を復元せよ。

思考過程

• 楕円曲線わからん。なんかアーベル群になることだけ知ってる
• o_1 \neq o_2 なら、o_i \cdot c_i で G_1 成分消して (o_i x_i) G_2 がわかって、隣り合うもので比較すると 01 や 10 の並びが特定できるんじゃね？どっちにもならなかったら前のビットと同じということで
• とりあえず SageMath をインストールしないと話にならん→インストール
• 動かしてみたところ o_1 = o_2 が判明。困る
• factor により、o_1 = 3 \cdot 11 \cdot 10177 \cdot 859267 \cdot 52437899 \cdot 52435875175126190479447740508185965837690552500527637822603658699938581184513 が判明する
• o_1, o_2、3 の倍数っぽいし、a G_1 + b G_2 の形で書いたときに a, b が 3 の倍数になっているかは \frac{o_1}{3} 倍することで判定できない？
• できなかった。↑は E が \langle G_1 \rangle , \langle G_2 \rangle の直和で書けることを前提としているが、そうではないため
• でも隣り合うものの差が G_1 ないし G_2 の整数倍かどうかって使いたいよな～
• \langle c_i - c_{i+1} \rangle \subseteq \langle G_1 \rangle かどうかの判定ができればよいが、一般にそんなことができるとは思えない
• （ライブラリのドキュメントを見て、そのような関数が存在しないかを探す）
• 10177 っていうちょうどいい素因数があるし、\frac{o_1}{10177} 倍してから生成される群を見ればいいんじゃね？→正解

解法

まず m_1, m_2 についてのみ考える。

d = c_1 - c_2 とおく。m_1=0, m_2=1 のとき、d = c_1 - c_2 = (x_1 - x_3) G_1 である。
同様に、m_1=1, m_2=0 のとき、d = c_1 - c_2 = (x_1 - x_3) G_2 である。
これ以外のときは、d は G_1 あるいは G_2 の整数倍とはならない。ゆえに、d が G_1 あるいは G_2 の整数倍かを判定する問題を考える。

G_1 についてのみ考える (G_2 も同様)。これは \langle d \rangle \subseteq \langle G_1 \rangle かを判定する問題となる。x_1 - x_3 の G_2 成分が偶然 10177 の倍数となってしまう場合を無視すれば、\langle \frac{o_1}{10177} d \rangle \subseteq \langle \frac{o_1}{10177} G_1 \rangle の比較である。また G_1 成分が偶然 10177 の倍数となってしまう場合も無視すると、\langle \frac{o_1}{10177} d \rangle = \langle \frac{o_1}{10177} G_1 \rangle かどうかの判定に帰着される。両辺の群の位数は 10177 要素なので、生成系の定義に従って群の元を列挙するのでも十分高速に判定ができる。

↑の手順により、隣り合うビットが同じか異なるかどうか、また異なるときは 0→1 か 1→0 のいずれか、というのもわかるため、全体のビットを決定可能である。

Hat Trick

問題

mod がランダムな 64 ビット素数、base が乱数なローリングハッシュが 3 つある。与えられた乱数 3 つ組に対して、ローリングハッシュ 3 個の値がそれになるような文字列を 1 個求めよ。文字列は英小文字 54 文字以下でなければならない。

ローリングハッシュが与えられてから 3 分以内に 3 組の乱数に対して解答する必要がある。

思考過程

• ローリングハッシュじゃん
• 競プロ的な構築か？
• 与えられる乱数が 192 bit くらいのエントロピーを持っていて、文字列のエントロピーが 253.8 bit くらいなので、そんなに余裕がない
• （ちょっと考える）→1 つのローリングハッシュの都合を合わせると他のローリングハッシュの値が壊れるので、直接構築を与えるのは難しそう
• CTF 典型？と思って調べる
• こんな記事が出てきた https://qiita.com/kusano_k/items/5509bff6e426e5043591
• LLL というアルゴリズムがあって、ナップサックを解くのに使えるらしい
• SageMath なら簡単に LLL を使える
• いろいろ試したら解けた

解法

文字列の長さを 54 に固定し、i 文字目を c_i とする。-12 \leq c_i \leq 13 として一般性を失わない。

i 番目のローリングハッシュの mod を p_i、base を b_i、目標の（乱数）値を t_i とすると、\sum_{j=0}^{53} {b_i}^j c_j \equiv r_i \pmod{p_i} なる c_j を求める問題となる。mod がちょっと邪魔なので、r_i に p_i の乱数倍を足して、mod を除去する。

この上で、↓のような行列を考える。S は十分大きい定数とする。

\left(\begin{matrix} 1 & 0 & 0 & \cdots & (-{b_1}^0 \bmod p_1) \cdot S & (-{b_2}^0 \bmod p_2) \cdot S & (-{b_3}^0 \bmod p_3) \cdot S \\ 0 & 1 & 0 & \cdots & (-{b_1}^1 \bmod p_1) \cdot S & (-{b_2}^1 \bmod p_2) \cdot S & (-{b_3}^1 \bmod p_3) \cdot S \\ 0 & 0 & 1 & \cdots & (-{b_1}^2 \bmod p_1) \cdot S & (-{b_2}^2 \bmod p_2) \cdot S & (-{b_3}^2 \bmod p_3) \cdot S \\ \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & r_1 S & r_2 S & r_3 S \end{matrix} \right)

これに LLL を適用すると、52 行目 (1-based) の左のほうに求める c_i が出てくる。-12 \leq c_i \leq 13 に違反しているかもしれないので、その場合は r_i の乱数を変えてやり直す。

LLL について

最初、得られる行列の各行が「元の行列の行ないし列の線形結合の係数」みたいなものを表しているのかと思って混乱した。実際には、行列に対して「行の整数倍の和として書けるベクトルからなるベクトル空間」を考えたとき、LLL はこのベクトル空間が一致するような行列であって、係数が小さいものを求めているのである。

特に、LLL の出力で得られる行列の各行は、元の行列の行の整数倍の和として書くことができる。

LLL で得られた行列の各行の左側 54 列の要素を非零とするには、元の行列での対応する行を選ぶほかない。このため、↑のような行列に対する LLL の結果の左側は、それぞれ c_j に対応しており、実際に \sum_{j=0}^{53} {b_i}^j c_j \equiv r_i \pmod{p_i} となっているならばナップサック問題の解として使えるのである。ただし、\sum_{j=0}^{53} {b_i}^j c_j = 0 なる解もたくさんあり、それらが 1～51 行目に入っているようである。なぜ求める解が 52 行目に入るのかはよくわからなかった。