SECCON Beginners CTF 2023 作問者Writeup

# はじめに
SECCON Beginners CTF 2023のCryptoの作問(&review)を担当させていただきました。
Conquer, switchable_catの作問をしたのでそれぞれの作問者想定解法とお気持ちを書いていきます。
各作問者Writeupは[xryuseixさんのWriteup](https://qiita.com/xryuseix/items/1c03bcb43eee608dcb59)でまとめてあるのでそちらを参照してください。また作問者Writeupは正解というわけではないので、みなさまのWrirteupをぜひお待ちしております！運営一同エゴサします。
- 開催概要
    - スコアサーバURL：https://score.beginners.seccon.jp/
    - 開始時刻：2023/06/03（土）14:00 JST
    - 終了時刻：2023/06/04（日）14:00 JST

## [Easy] Conquer ( 84 points / 152 solves )
```python:problem.py
from Crypto.Util.number import *
from random import getrandbits
from flag import flag


def ROL(bits, N):
    for _ in range(N):
        bits = ((bits << 1) & (2**length - 1)) | (bits >> (length - 1))
    return bits


flag = bytes_to_long(flag)
length = flag.bit_length()

key = getrandbits(length)
cipher = flag ^ key

for i in range(32):
    key = ROL(key, pow(cipher, 3, length))
    cipher ^= key

print("key =", key)
print("cipher =", cipher)
```

暗号化部分に注目すると、

```python
for i in range(32):
    key = ROL(key, pow(cipher, 3, length))
    cipher ^= key
```
となっています。上のコードは、
```math
\begin{equation}
\left\{ \,
    \begin{aligned}
        & key_1 = ROL(key_0, cipher_{0}^3 \ \mathbb{mod} \ length) \\
        & cipher_1 = cipher_{0} \oplus key_{1}
    \end{aligned}
\right.
\\ \vdots \\
\left\{ \,
    \begin{aligned}
        & key_{32} = ROL(key_{31}, cipher_{31}^3 \ \mathbb{mod} \ length) \\
        & cipher_{32} = cipher_{31} \oplus key_{32}
    \end{aligned}
\right.
\end{equation}
```

と表すことができます。ここの$key_i$は`ROL()`で更新されているので、その関数について考えてみます。関数内のワンライナーで書かれている処理は以下のように分割できます。
    
```python
def ROL(bits, N):
    for _ in range(N):
        a = (bits << 1) & (2**length - 1)
        b = bits >> (length - 1)
        bits = a | b
    return bits
```
`a`には`bits`を1回左シフトして下位`length`bit分を抽出した値が代入され、`b`には`bits`のMSB(最高位bit)を抽出した値が代入されています。次の行の`a | b`では一番下に持ってきたMSBと、MSBを消して1bit左シフトした値を結合しています。それらの処理が`N`回ループしているので`ROL()`は`bits`を`N`bit左に循環させる関数となっています。

例えば`length=6`で`ROL(0b110101, 3)`を計算させると返り値は二進数で`10111`となります。この処理のことをビットローテーションや循環シフトといい、実際googleで「ROL 演算」と検索していただくとその解説記事が出てくるかと思います。

この`ROL()`は不可逆の処理ではなく例えば`length=10`で`ROL(x, 4)`の返り値が二進数で`10101100`だった場合、変数`x`は二進数で`1100001010`となります。ところでROLとはRotate Leftの略で、逆の処理はROR(Rotate Right)といいます。

ここで与えられている情報は$cipher_{32}$, $key_{32}$なので、それらからXOR演算で$cipher_{31}$を復元しRORで$key_{31}$を復元、$cipher_{31}$, $key_{31}$から$cipher_{30}$, $key_{30}$を……と復元していけば$cipher_{0}$を復元できると考えられます。これを実装すると次のようになります。

```python
for i in range(32):
    cipher ^= key
    key = ROR(key, pow(cipher, 3, length))
```

あとの未知情報は`length`だけですが、`key.bit_length()`や`cipher.bit_length()`ではビット演算の性質上必ずしもMSBが1とは限らないので、`cipher`,`key`,`flag`のビット長が同じとは限りません。ただ`key`が`getrandbits()`で初期化されていることから、頭のbitが連続して0で欠損している数は多くないと考えられるので、適宜手動でインクリメントさせるだけで十分特定可能です。

これらの考察を踏まえて以降にソルバを示します。

```python:solve.py
from Crypto.Util.number import *

def ROR(bits, N):
    for _ in range(N):
        bits = (bits >> 1) | ((bits & 1) << (length - 1))
    return bits

key = 364765105385226228888267246885507128079813677318333502635464281930855331056070734926401965510936356014326979260977790597194503012948
cipher = 92499232109251162138344223189844914420326826743556872876639400853892198641955596900058352490329330224967987380962193017044830636379
length = cipher.bit_length() + 3

for i in range(32):
    cipher ^= key
    key = ROR(key, pow(cipher, 3, length))

cipher ^= key

print(long_to_bytes(cipher))
```

## [Medium] switchable_cat ( 179 points / 27 solves )
```python:problem.py
from Crypto.Util.number import *
from secret import seed, flag
from random import getrandbits
from os import urandom


class LFSR:
    def __init__(self):
        self.bits = 128
        self.rr = seed
        self.switch = 0
    def next(self):
        r = self.rr
        if self.switch == 0:
            b = ((r >> 0) & 1) ^ \
                ((r >> 2) & 1) ^ \
                ((r >> 4) & 1) ^ \
                ((r >> 6) & 1) ^ \
                ((r >> 9) & 1)
        if self.switch == 1:
            b = ((r >> 1) & 1) ^ \
                ((r >> 5) & 1) ^ \
                ((r >> 7) & 1) ^ \
                ((r >> 8) & 1)
        r = (r >> 1) + (b << (self.bits - 1))
        self.rr = r
        self.switch = 1 - self.switch
        return r & 1
    
    def gen_randbits(self, bits):
        key = 0
        for i in range(bits):
            key <<= 1
            key += self.next()
        return key


lfsr = LFSR()

neko = urandom(ord("🐈")*ord("🐈")*ord("🐈"))
key = lfsr.gen_randbits(len(neko) * 8)
cipher = bytes_to_long(neko) ^ key

#   📄🐈💨💨💨💨
# ╭─^────────╮
# │  cipher  │
# ╰──────────╯

key = lfsr.gen_randbits(len(flag) * 8)
cipher = bytes_to_long(flag) ^ key

print("seed =", seed)
print("cipher =", cipher)
```

class名で定義されている通りこれは[線形帰還シフトレジスタ(LFSR:Linear Feedback Shift Register](https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E5%B8%B0%E9%82%84%E3%82%B7%E3%83%95%E3%83%88%E3%83%AC%E3%82%B8%E3%82%B9%E3%82%BF)というアルゴリズムをベースに作成した乱数生成器です。一見すると`seed`が与えられているので`problem.py`をそのまま実行することでフラグの暗号化に使用した乱数がそのまま手に入るように見えます。しかし、ねこちゃんの平文`neko`を暗号化するのに使用した乱数の大きさは2097545240576512*8bitなのでそのまま実行しても実行は終わりません。なのでLFSRの高速化を行列累乗により実装して復号します。

LFSRの行列累乗による高速化とは何か、簡単のために6bitで帰還多項式が以下のようなLFSRを考えます。

```python
b = ((r >> 1) & 1) ^ \
    ((r >> 2) & 1) ^ \
    ((r >> 3) & 1)
```


この乱数生成器から返される$n$番目の乱数$a_n$は初期シード$seed=s_0|s_1|s_2|s_3|s_4|s_5$を与えて

```math
\begin{pmatrix}
   a_n \\
   a_{n-1} \\
   a_{n-2} \\
   a_{n-3} \\
   a_{n-4} \\
   a_{n-5}
\end{pmatrix}
=
\begin{pmatrix}
   0 & 0 & 0 & 1 & 1 & 1 \\
   1 & 0 & 0 & 0 & 0 & 0 \\
   0 & 1 & 0 & 0 & 0 & 0 \\
   0 & 0 & 1 & 0 & 0 & 0 \\
   0 & 0 & 0 & 1 & 0 & 0 \\
   0 & 0 & 0 & 0 & 1 & 0
\end{pmatrix}^n
\cdot
\begin{pmatrix}
   s_{0} \\
   s_{1} \\
   s_{2} \\
   s_{3} \\
   s_{4} \\
   s_{5}
\end{pmatrix}
```

と計算することができます。問題文の帰還多項式は`switch`によって変わるので`switch == 0`, `switch == 1`の部分をそれぞれsagemathの`MatrixSpace()`を使用すると、

```python
bits = 128
M = MatrixSpace(GF(2), bits, bits)
vec1, vec2 = [], []
v1, v2 = [0] * (bits - 10), [0] * (bits - 10)
vec1 += v1 + [1, 0, 0, 1, 0, 1, 0, 1, 0, 1]
vec2 += v2 + [0, 1, 1, 0, 1, 0, 0, 0, 1, 0]
for i in range(bits - 1):
    v = [0] * bits
    v[i] = 1
    vec1 += v[:]
    vec2 += v[:]

A1, A2 = M(vec1), M(vec2)
```


と定義することができます。`flag`を暗号化し始めた乱数すなわち、2097545240576512*8+1番目の乱数`key_0`は前の`A`,`B`を使用して以下のように求めることができます。

```python
seed = 219857298424504813337494024829602082766
neko = 8*ord("🐈")*ord("🐈")*ord("🐈")

A = (A1*A2)^(neko // 2)*A1
B = vector(list(map(int, list(bin(seed)[2:]))))
B = A * B

key_0 = int(list(B)[-1])
```

あとは`switch`の値に気を付けながら内部状態を更新して`flag`の長さだけ`key`を復元していけばいいので最終的なソルバは以下のようになります。

```python:solve.sage
from Crypto.Util.number import *
from random import getrandbits


seed = 219857298424504813337494024829602082766
cipher = int(38366804914662571886103192955255674055487701488717997084670307464411166461113108822142059)

neko = 8*ord("🐈")*ord("🐈")*ord("🐈")
human = cipher.bit_length()+1
bits = 128
M = MatrixSpace(GF(2), bits, bits)
vec1, vec2 = [], []
v1, v2 = [0] * (bits - 10), [0] * (bits - 10)
vec1 += v1 + [1, 0, 0, 1, 0, 1, 0, 1, 0, 1]
vec2 += v2 + [0, 1, 1, 0, 1, 0, 0, 0, 1, 0]
for i in range(bits - 1):
    v = [0] * bits
    v[i] = 1
    vec1 += v[:]
    vec2 += v[:]

A1, A2 = M(vec1), M(vec2)
A = (A1*A2)^(neko // 2)*A1
B = vector(list(map(int, list(bin(seed)[2:]))))
B = A * B

switch = 1
key = 0
for i in range(human):
    key <<= 1
    key += int(list(B)[-1])
    if switch == 0:
        B = A1 * B
    if switch == 1:
        B = A2 * B
    switch = 1 - switch

flag = cipher ^^ key
print(long_to_bytes(flag))
```