SECCON BeginnersCTF 2018 Writeup (Crypto - Streaming) - ようじょのおえかきちょう

プログラムを書くのが苦手な Beginner なので Excel で解きました。

問題

# encrypt.py

import os
from flag import flag


class Stream:
    A = 37423
    B = 61781
    C = 34607
    def __init__(self, seed):
        self.seed = seed % self.C

    def __iter__(self):
        return self

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

g = Stream(int(os.urandom(8).encode('hex'), 16))

encrypted = ''
for i in range(0, len(flag), 2):
    a = int(flag[i:i+2].encode('hex'), 16) ^ g.next()
    encrypted += chr(a % 256)
    encrypted += chr(a / 256)

open('encrypted', 'wb').write(encrypted)

# hexdump encrypted

0000000 ce 1e 65 0c 06 5f 94 3a 57 49 1d 17 f5 17 59 3f
0000010 9c 40 9d 4a 19 31 8d 26 3e 51 fd 03 ce 52 56 16
0000020

乱数パート

urandom(8)... でめっちゃでかい数字を一番最初の seed にしている
$X_{n+1} = (AX_n + B) \, \% \, C$ の形で新しい乱数を生成している

最初の seed はでかすぎて、残念ながら知りようもありません。

次に漸化式を見るとこれは線形なので周期性を持ち（擬似乱数列）、 $\% C$ しているので周期は高々 $C$ （34607）と分かります。Excel で =MOD((37423*A1+61781), 34607) のようにしてみると実際に確認できます。このことから、一番最初の seed が分からなくても、任意の $n$ に対する $X_n$ が分かれば帰納的に $X_{n+1}, \, X_{n + 2}, \, \cdots$ を知ることができます。

n: X_n
1: 1
2: 29990
3: 3327
4: 17509
...
34604: 6402
34605: 24959
34606: 24901
34607: 1

暗号化パート

ストリーム暗号というらしい。速くてやさしそう
flag を2文字ずつみて、2桁/文字の16進数にする。2文字ずつなので4桁の16進数が得られる（以下 hex）
int(hex, 16) する（以下 int）
hex と生成した乱数（以下 random）の XOR をとる（以下 a）
a を元に2文字を生成する（以下 chr1 chr2）
16進数で書き込む（以下 encrypted）
flag の prefix は ctf4b{ だと分かっている

encrypted から逆算して flag に辿り着くことを考えます。以下、flag の最初の2文字 "ct" について例を示します。

`encrypted` → `chr1` `chr2`

16進数を10進数に直してやればいいので chr1 = HEX2DEC("ce") = 206 chr2 = HEX2DEC("1e") = 30 です。

`chr1` `chr2` → `a`

a = chr1 + chr2 * 256 の関係があるので a が復元できます。206 + 30 * 256 = 7886 です。

`a` → `random`

a = int ^ random の形になっており、XOR の性質より random = a ^ int です。hex =DEC2HEX(CODE("c")) & DEC2HEX(CODE("t")) = 6374 より int = int(hex, 16) = 25460 なので random = BITXOR(a, int) = 32186 と求められます。

乱数パートで確認した疑似乱数列から 32186 を探して、以降 flag の長さぶんだけ取り出せば g.next() で使用した値が分かります。念の為 flag "ct" の続きである "f4" についても同様に確認してみると、ちゃんと random = 27217 が求まります。

既知→ `flag`

さて、現在分かっている値は以下の通りです（灰色は固定値）。ここからint → hex → flag の順に求めていきます。

f:id:yamasy1549:20180527121916p:plain

random と a が既知なので、XOR の性質より int = random ^ a（=BITXOR(random, a)）で求まります。続いて hex = DEX2HEX(int) で16進数に戻します。hex は16進数4桁ですが、flag にするときは2桁ずつ読みます。=CHAR(HEX2DEC(LEFT(hex, 2))) =CHAR(HEX2DEC(RIGHT(hex, 2))) で2桁ずつ2文字を読みます。

f:id:yamasy1549:20180527124912p:plain

できました。線形合同法は値を予測されやすいから乱数としてはあまり良くないよ、ということみたいです。

感想

過去何回か CTF に参加して {1, 2} 問解けたり解けなかったりしていて、今回初めて Writeup というかメモを公開しました。途中参加だったのでこの問題しか解けてないんですが、前に興味持って調べてた乱数の知識がちょっとだけ活用できて楽しかったです。誘ってくれてありがとうね。

これは変なこだわりなんですが、いつか Crypto 問を Excel の表だけで解きたいという気持ちがあって、今回それができたので嬉しいです。Excel 関数の勉強になりました。

問題

乱数パート

暗号化パート

encrypted → chr1 chr2

chr1 chr2 → a

a → random

既知→ flag

感想

`encrypted` → `chr1` `chr2`

`chr1` `chr2` → `a`

`a` → `random`

既知→ `flag`