TSGCTF2023 WriteUp

友人に誘われて[TSGCTF2023](https://ctf.tsg.ne.jp/)に参加しました。人生初CTF。人生初なので開始10分前にCTFのイニシャリズムを調べてました。Capute The Flagというらしい。WriteUpなるものを書く文化があるようなので書きます。

結果は912点で32位でした。手取り足取り教えてくれてた友人に感謝感謝。

ネットワークとかメモリとかなんもわからんなので大半の時間を暗号(crypt)に費やしました。解けたのもcryptの2問のみ。
解きながら、「名前だけ知っているけど中身はよく知らん」技術要素が多く出てきたので、勉強になりました。ここでも適宜Wikipediaのリンクをくっつけておきます。

## ComplicatedFunction

### 問題の概要

公開鍵と暗号文が与えられるので、[RSA暗号](https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7)を解いて平文を求める問題でした。
サマーウォーズのアレです。言わずと知れた強力な暗号で、公開鍵(整数)$N$の素因数分解を求めることが本質ですが、$N$の大きさがちゃんと$10^{616}$ぐらいなので、簡単には求まりません。

### 解法
この問題の公開鍵生成の過程をよく見ると, 素数$p$を決める→それを使って素数$q$を決める→$N=p \times q$が作られる、となっており、怪しさを醸し出しています。はい、$q$が$p$に依存しています。

具体的には、$q$は次のように定められていました：

$q = \sqrt{p^2 + (2^{512}-6)p + \lceil \sqrt{p}\sin(p) \rceil} + 2 ^ {1023}$

この式をじっと睨むと, $q$が$p$に対して単調に増加することに気づきます。
（$\sin{p}$が負の値を取りうるため、単調性がないようにも思えますが、この部分の寄与のオーダーが$p^{1/2}$であるのに対して, それより強い$p^2$の項が足されているので、問題ありません。ちゃんと不等式で評価することもできます。）

単調性といえば二分探索です。鼻血を垂らして「よろしくお願いします」と叫びながらエンターキーを押します。

```python:solve.py
from math import isqrt, sin, ceil, lcm

N, c, e = (省略)

def f(p):
    return isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) + 2**1023

s = 2 ** 1023
t = 2 ** 1024

while s + 1 < t:
    mid = (s + t) // 2
    q = f(mid)
    if mid * q < N:
        s = mid
    else:
        t = mid

p = mid
q = f(p)
assert p * q == N

L = lcm(p-1, q-1)
D = pow(e, -1, L)
m = pow(c, D, N)

hex_string = m.to_bytes((m.bit_length()-1)//8 + 1, 'big')
print(hex_string)
```

```text:output
b'TSGCTF{From which angle did you solve this, binary search or convergence of f(p)-p?}'
```

flagを見るに、「$f(p)-p$の収束性」を使っても解けたようですね。

$f(p) - p = p \left( \sqrt{1 + \frac{2^{512}-6}{p} + \frac{\lceil \sqrt{p}\sin(p) \rceil}{p^2} } - 1 \right) + 2 ^ {1023} \simeq p\left(1 + \frac{2^{512}-6}{2p} - 1 \right) + 2 ^ {1023} = 2 ^ {1023} + 2^{511} - 3$

こんな感じの変形かな。ここから$q$を$p$の1次式で近似して$p$の2次方程式にするとか？

誤差の扱いが面倒そうなので実装はスキップで。

## Streamer
### 問題の概要
暗号文が与えられるので、今度は[ストリーム暗号](https://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%88%E3%83%AA%E3%83%BC%E3%83%A0%E6%9A%97%E5%8F%B7)を解いて平文を求めます。

### 解法
糸口は主に３つあります。

１つは、平文のフォーマットがあらかじめわかっていることです。具体的には,平文の形式は`TSGCTF{hogehoge@fugafuga}`として明示的に与えられており、さらに後述の3つ目の糸口も考慮することで、`hogehoge`と`fugafuga`の部分の文字の種類と文字数、および`fugafuga`の末尾２文字が`==`であることも分かります。

2つ目の糸口は、鍵は1byteの数字の要素数16の配列であるところです。304文字の平文の$n$文字目の暗号化の際の鍵は、配列の$n\text{%}16$番目の要素です。つまり鍵の要素は1つ当たり、$304 / 16 = 19$回暗号化に用いられています。


３つ目の糸口は、平文の`fugafuga`は`hogehoge`を[MD5](https://ja.wikipedia.org/wiki/MD5)でハッシュ化したのちに[Base64](https://ja.wikipedia.org/wiki/Base64)でエンコードしたものであるところです。

方針としては、１・２個目の糸口から鍵の候補を絞り込み、その中から３つ目の条件を満たすものをブルートフォースします。結果的には20万程度通りを調べればよく、手元のPCでも20秒ぐらいで実行できました。

```python:solve.py

import re
import hashlib
import base64

cipher, flag_length = (省略)

pattern_content = re.compile("[a-zA-Z0-9!-/:-?\[-`|~]")
pattern_hash = re.compile("[A-Za-z0-9+/]")

key = [-1] * 16

flag_head = b'TSGCTF{'
for i in range(len(flag_head)):
    key[i] = flag_head[i] ^ cipher[i]

flag_tail = b'==}'
for i in range(len(flag_tail)):
    key[-i-1] = flag_tail[-i-1] ^ cipher[-i-1]


possible_keys = [[] for _ in range(16)]

for i in range(16):
    if key[i] >= 0:
        continue
    for k in range(256):
        ok = True
        for j in range(19):
            idx = 16 * j + i
            char = chr(cipher[16 * j + i] ^ k)
            if 7 <= idx and idx <  278:
                if not pattern_content.fullmatch(char):
                    ok = False
            if 279 <= idx and idx < 301:
                if not pattern_hash.fullmatch(char):
                    ok = False
        if ok:
            possible_keys[i].append(k)


for key7 in possible_keys[7]:
    for key8 in possible_keys[8]:
        for key9 in possible_keys[9]:
            for key10 in possible_keys[10]:
                for key11 in possible_keys[11]:
                    for key12 in possible_keys[12]:
                        ans = b''
                        for i in range(flag_length):
                            m = i % 16
                            if key[m] >= 0:
                                ans += bytes([cipher[i] ^ key[m]])
                            else:
                                if m == 7:
                                    ans += bytes([cipher[i] ^ key7])
                                if m == 8:
                                    ans += bytes([cipher[i] ^ key8])
                                if m == 9:
                                    ans += bytes([cipher[i] ^ key9])
                                if m == 10:
                                    ans += bytes([cipher[i] ^ key10])
                                if m == 11:
                                    ans += bytes([cipher[i] ^ key11])
                                if m == 12:
                                    ans += bytes([cipher[i] ^ key12])
                        flag_content = ans[7:278]
                        flag_hash = ans[279:303]
                        if flag_hash == base64.b64encode(hashlib.md5(flag_content).digest()):
                            key[7:13] = [key7, key8, key9, key10, key11, key12]


for i in range(flag_length):
    print(chr(cipher[i] ^ key[i % 16]), end='')
```

```text:output
TSGCTF{The_l6n63|2_+|-|3_fla0_the_saf3|2_i+_k4`/_8e_as_lo|\|a_4$_you_use_a|\z_a|*pr0|*ria+3_5|\|cry|*+i0n._Tni$_ci|*|-|3r_i$Y4_0ne_+i|\/|e_|,a|)_ra+h3|2_t|-z4|\|_a_s+re4m_(oph3r,_but_it_i$Yins3(u|2e_be(auue_it_us3s_the_$2|\/|e_r4ndom_nuk83r$_re|*34+3|)jy._enjoy_hahahaY:-)-:)-:)@TWp6sWXidRLICfdhOMY+IG==}
```

読めるようで読めなかったのでやや自信がなかったけれど、正解でした。flagの内容からエスパーされないように読みにくくしているのかな。

## 所感
CTFってなんか難しいパソコン天下一武道会ってイメージで食わず嫌いしてましたが、楽しかったです。コンピュータサイエンスの総合格闘技ですね。初めて解けたときの脳汁がすごかった。