DownUnderCTF 2023 lcg card gimmicks writeup

# はじめに
DownUnderCTF 2023 に参加しました．
去年の DownUnderCTF が人生初 CTF だったので，CTF を始めてこれでほぼ一年になります．
今回はいろいろ手をつけて，結果 31 問解いて，61 位でした．

Crypto の lcg card gimmicks について書こうと思います．

# 問題
```
Can you perform card tricks like a true magician?

Author: joseph

nc 2023.ductf.dev 30005
```

配布ファイル
```py
#!/usr/bin/env python3

from secrets import randbelow
import signal


DECK = [f'{val}{suit}' for suit in 'CDHS' for val in ['A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K']] + ['RJ', 'BJ']
M = 2**64


class LCG:
    def __init__(self, seed, A=None, C=None):
        self.M = M
        if A is None:
            self.A = randbelow(self.M) | 1
        else:
            self.A = A
        if C is None:
            self.C = randbelow(self.M)
        else:
            self.C = C
        self.seed = seed

    def __str__(self):
        o = f'A = {self.A}\n'
        o += f'C = {self.C}\n'
        o += f'M = {self.M}'
        return o

    def next(self):
        self.seed = (self.A * self.seed + self.C) % self.M
        return self.seed

    def between(self, lo, hi):
        r = self.next()
        return lo + (r >> 16) % (hi - lo)


def draw(rng, k):
    hand = []
    while len(hand) < k:
        r = rng.between(0, len(DECK)) 
        card = DECK[r]
        if card in hand:
            continue
        hand.append(card)
    return hand


def main():
    seed = randbelow(M)
    rng = LCG(seed)
    print(rng)

    hand = draw(rng, 13)
    print('My hand:', ' '.join(hand))

    guess = int(input('Show me a magic trick: '))
    if hand == draw(LCG(guess, A=rng.A, C=rng.C), 13):
        FLAG = open('flag.txt', 'r').read().strip()
        print(FLAG)
    else:
        print('Hmm not quite.')


if __name__ == '__main__':
    signal.alarm(10)
    main()
```

* 線形合同法で乱数が生成されていて，使われているのは LCG の各 state の真ん中あたりのビット
* $S_{i + 1} = (A \cdot S_i + C) \mod{M}$ で更新されて，$r_i = (S_i >> 16) \mod{54}$ が使われる
* $r_1, \dots, r_{13}$ が与えられるので，同じ $r_i$ の列を生成する $S_0$ を求める問題になっている

# 解法
* 更新式は上述の通りで，$r_i$ と $S_i$ の関係は以下の式のようになる
    $$
    S_i = (r_i + 54 (s_i + 2^{BIT})) \cdot 2^{16} + t_i + 2^{15}
    $$
    * $t_i + 2^{15}$ は $S_i >> 16$ と同じ演算の $S_i / 2^{16}$ の剰余
    * 小文字の $s_i$ を使って表記している $s_i + 2^{BIT}$ は，$S_i >> 16$ を $54$ で割ったときの商
        $BIT$ は，$(S_i >> 16) / 54$ の商のビット幅 $- 1$ のことなので，だいたい $40 \sim 43$ ぐらい
    * それぞれ，$v + 2^b$ としているのは，これらの値が正の値になるから
        なので，それぞれ $t_i, s_i$ のビット幅は，$15$ と $BIT$ になる
* $S_{i + 1} = (A \cdot S_i + C) \mod{M}$ に法をとる代わりに変数 $k_i$ を入れて，$S_i, S_{i+1}$ を $r_i, r_{i+1}$ を使った式に置き換えると，以下のようになる
    ```math
    \begin{align*}
    &54 \cdot 2^{16} \cdot (A \cdot s_i - s_{i + 1}) + (A \cdot t_i - t_{i + 1}) + k_i \cdot M \\
    &+ 2^{16} \cdot (A \cdot r_i - r_{i + 1}) + 54 \cdot 2^{16 + BIT} \cdot (A - 1) + 2^{15} \cdot (A - 1) + C = 0
    \end{align*}
    ```
* ここから行列を作る
    ```math
    M =
    \left(\begin{array}{cccc|c|ccc|ccc}
        54 \cdot 2^{16} \cdot A & 0 & \cdots & 0 & 0 & 1 & \cdots & 0 & 0 & \cdots & 0 \\
        -54 \cdot 2^{16} & 54 \cdot 2^{16} \cdot A & \cdots & 0 & 0 & 0 & \ddots & 0 & 0 & \cdots & 0 \\
        \vdots & \ddots & \ddots & \vdots & \vdots & \vdots & & \vdots & & \vdots & \\
        0 & 0 & \cdots & -54 \cdot 2^{16} & 0 & 0 & \cdots & 1 & 0 & \cdots & 0 \\ \hline
        A & 0 & \cdots & 0 & 0 & 0 & \cdots & 0 & 2^{BIT - 15} & \cdots & 0 \\ 
        -1 & A  & \cdots & 0 & 0 & 0 & \cdots & 0 & 0 & \ddots & 0 \\
        \vdots & \ddots & \ddots & \vdots & \vdots & & \vdots & & \vdots & & \vdots \\
        0 & 0 & \cdots & -1 & 0 & 0 & \cdots & 0 & 0 & \cdots & 2^{BIT - 15} \\ \hline 
        M & 0 & \cdots & 0 & 0 & 0 & \cdots & 0 & 0 & \cdots & 0 \\
        0 & M & \cdots & 0 & 0 & 0 & \cdots & 0 & 0 & \cdots & 0 \\
        \vdots & \vdots & \ddots & \vdots & \vdots & & \vdots & & & \vdots & \\
        0 & 0 & \cdots & M & 0 & 0 & \cdots & 0 & 0 & \cdots & 0 \\ \hline
        C_1 & C_2 & \cdots & C_{12} & 2^{BIT} & 0 & \cdots & 0 & 0 & \cdots & 0
    \end{array}\right)
    ```
    * $C_i$ は定数で，$C_i = 2^{16} \cdot (A \cdot r_i - r_{i + 1}) + 54 \cdot 2^{16 + BIT} \cdot (A - 1) + 2^{15} \cdot (A - 1) + C$
    * 構成的に線を引いてます
    * $(13 + 13 + 12 + 1) \times (12 + 1 + 13 + 13)$ の行列
    * 左 12 列は $0$ になってほしいので $N = 2^{1024}$ とかの適当な大きな値をかける
* 以下のように行列 $M$ を考えたので，解のベクトルの先頭 12 要素が $0$ になっていれば正しい解の可能性が高い
    ```math
    \begin{align*}
    &(s_1,\; s_2,\; \cdots,\; s_{13},\; t_1,\; \cdots,\; t_{13},\; k_1,\; \cdots,\; k_{12},\; 1) \cdot M\\
    &= (0,\; \cdots,\; 0,\; 2^{BIT},\; s_1,\; \cdots,\; s_{13},\; 2^{BIT - 15} \cdot t_1,\; \cdots,\; 2^{BIT - 15} \cdot t_{13})
    \end{align*}
    ```

# Solver
```py
from pwn import *
from secrets import randbelow

DECK = [f'{val}{suit}' for suit in 'CDHS' for val in ['A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K']] + ['RJ', 'BJ']
M = 2**64

def main():
    io = remote('2023.ductf.dev', '30005')
    A = int(io.recvline().decode().strip().split()[-1])
    C = int(io.recvline().decode().strip().split()[-1])
    M = int(io.recvline().decode().strip().split()[-1])

    io.recvuntil(b'My hand: ')
    hand = io.recvline().decode().strip().split()
    print('target hand :', hand)
    r = [DECK.index(h) for h in hand]

    BIT = 42
    N = 2^256

    mat = []
    for i in range(13):
        mat.append([0] * 39)
        if i < 12:
            mat[-1][i] = 54 * (2^16) * A
        if 0 < i:
            mat[-1][i - 1] = -54 * (2^16)
        mat[-1][13 + i] = 1
    for i in range(13):
        mat.append([0] * 39)
        if i < 12:
            mat[-1][i] = A
        if 0 < i:
            mat[-1][i - 1] = -1
        mat[-1][26 + i] = (2^(BIT - 15))
    for i in range(12):
        mat.append([0] * 39)
        mat[-1][i] = M
    mat.append([(A * r[i] - r[i + 1]) * (2^16) + (A - 1) * (54 * (2^(16 + BIT))) + (A - 1) * (2^15) + C for i in range(12)] + [2^BIT] + [0] * 26)

    for i in range(len(mat)):
        for j in range(12):
            mat[i][j] *= N

    ans_mat = matrix(ZZ, mat).LLL()
    for ans in ans_mat:
        if all(a == 0 for a in ans[:12]) and all(a % (2^(BIT - 15)) == 0 and int(a // (2^(BIT - 15))).bit_length() < 16 and a != 0 for a in ans[26:]):
            seeds = [((r[i] + 54 * (int(ans[13 + i]) + 2^BIT)) * (2^16) + (2^15) + int((ans[26 + i] // (2^(BIT - 15))))) for i in range(13)]
            h = [DECK[(seeds[i] >> 16) % 54] for i in range(13)]
            if h == hand and all(seeds[i + 1] % M == (A * seeds[i] + C) % M for i in range(12)):
                seed0 = ((seeds[0] - C) * pow(A, -1, M)) % M
                if is_correct_seed(seed0, A, C, hand):
                    print(f'{seed0 = }')
                    io.sendlineafter(b'Show me a magic trick: ', str(int(seed0)).encode())
                    print(io.recvline())
                    return True
    return False

def is_correct_seed(seed, A, C, hand1):
    rng = LCG(seed, A, C)
    hand2 = draw(rng, 13)
    return hand1 == hand2

class LCG:
    def __init__(self, seed, A=None, C=None):
        self.M = M
        if A is None:
            self.A = randbelow(self.M) | 1
        else:
            self.A = A
        if C is None:
            self.C = randbelow(self.M)
        else:
            self.C = C
        self.seed = seed

    def __str__(self):
        o = f'A = {self.A}\n'
        o += f'C = {self.C}\n'
        o += f'M = {self.M}'
        return o

    def next(self):
        self.seed = (self.A * self.seed + self.C) % self.M
        return self.seed

    def between(self, lo, hi):
        r = self.next()
        return lo + int(r >> 16) % int(hi - lo)


def draw(rng, k):
    hand = []
    while len(hand) < k:
        r = rng.between(0, len(DECK)) 
        card = DECK[r]
        if card in hand:
            continue
        hand.append(card)
    return hand

if __name__ == '__main__':
    while not main():
        pass
```
* 結構失敗したりする
* ビット幅の調整とかがも少しできるのかも