LoginSignup
0
0
@toha

DownUnderCTF 2023 lcg card gimmicks writeup

Last updated at Posted at 2023-09-03

はじめに

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

配布ファイル

#!/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}$ を使った式に置き換えると，以下のようになる 
    \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*}
  • ここから行列を作る 
    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$ になっていれば正しい解の可能性が高い 
    \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

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
  • 結構失敗したりする
  • ビット幅の調整とかがも少しできるのかも
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0