[💠 Platinum 3] getrandbits 가 흘린 비트로 MT19937 상태를 되찾다 — DreamHack Unbreakable 풀이

file extracted/test.py extracted/output && ls -l extracted && wc -l extracted/output

cat extracted/test.py

TOTAL_BITS = 624 * 37
def challenge(num_bit, previous, current):
    random.seed(os.urandom(16))
    num_task = (TOTAL_BITS + num_bit - 1) // num_bit
 
    output = ""
    for _ in range(num_task):
        output += format(random.getrandbits(num_bit), f"0{num_bit}b")
 
    print(output)
 
    key = previous
    for _ in range(100):
        key += format(random.getrandbits(num_bit), f"0{num_bit}b").encode()
        key = sha256(key).digest()
 
    cipher = AES.new(key, AES.MODE_CBC, iv=b'iluvredblacktree')
    print(cipher.encrypt(pad(current, 16)).hex())
 
challenge(32, b'iloveredblacktree', iflags[0])
challenge(16, iflags[0], iflags[1])
challenge(8, iflags[1], iflags[2])
challenge(4, iflags[2], iflags[3])
challenge(2, iflags[3], iflags[4])
challenge(1, iflags[4], final_flag)

#!/usr/bin/env python3
"""output 파일의 구조를 확인한다 - 어느 줄이 어느 challenge() 호출인지."""
TOTAL_BITS = 624 * 37
lines = open('extracted/output').read().split('\n')
print(f"TOTAL_BITS = 624 * 37 = {TOTAL_BITS}")
for idx, k in enumerate([32, 16, 8, 4, 2, 1]):
    bits, ct = lines[idx * 2], lines[idx * 2 + 1]
    num_task = (TOTAL_BITS + k - 1) // k
    print(f"k={k:2d}  num_task={num_task:5d}  expect={num_task*k:6d}  "
          f"got={len(bits):6d}  {'OK' if len(bits)==num_task*k else 'MISMATCH'}"
          f"   ct={len(ct)//2:2d}B = {len(ct)//32} AES block(s)")

python3 inspect_output.py

#!/usr/bin/env python3
"""getrandbits(k) (k<=32) 가 32비트 워드 하나를 통째로 소비하고 상위 k비트만 준다는 것을
같은 상태에서 두 갈래로 뽑아 대조해 확인한다."""
import random, os
 
seed = os.urandom(16)
for k in (16, 8, 4, 2, 1):
    a = random.Random(); a.seed(seed)
    b = random.Random(); b.seed(seed)
    full = [a.getrandbits(32) for _ in range(8)]
    part = [b.getrandbits(k) for _ in range(8)]
    top = [w >> (32 - k) for w in full]
    print(f"k={k:2d}  getrandbits(k)={part}")
    print(f"      genrand>>{32-k:2d} ={top}   match={part == top}")

python3 probe_getrandbits.py

y ^= y >> 11;
y ^= (y << 7)  & 0x9d2c5680;
y ^= (y << 15) & 0xefc60000;
y ^= y >> 18;

TEMPER_BITS = [[j for j in range(32) if (temper(1 << j) >> b) & 1] for b in range(32)]

#!/usr/bin/env python3
"""tempering 이 (1) 가역이고 (2) GF(2) 위에서 선형이라는 것을 무작위 입력으로 확인한다."""
import os
import mt
 
n = 20000
bad_inv = bad_lin = 0
for _ in range(n):
    v = int.from_bytes(os.urandom(4), 'little')
    if mt.untemper(mt.temper(v)) != v:
        bad_inv += 1
    t = 0
    for b in range(32):                      # TEMPER_BITS 로 재조립
        acc = 0
        for j in mt.TEMPER_BITS[b]:
            acc ^= (v >> j) & 1
        t |= acc << b
    if t != mt.temper(v):
        bad_lin += 1
print(f"random inputs        : {n}")
print(f"untemper(temper(x))!=x : {bad_inv}")
print(f"XOR-basis != temper(x) : {bad_lin}")
x, y = int.from_bytes(os.urandom(4), 'little'), int.from_bytes(os.urandom(4), 'little')
print(f"temper(x^y) == temper(x)^temper(y) : {mt.temper(x ^ y) == mt.temper(x) ^ mt.temper(y)}")
print(f"TEMPER_BITS[31] = {mt.TEMPER_BITS[31]}   (MSB 는 원본 4비트의 XOR)")

python3 check_linear.py

x[i+624] = x[i+397] ^ ((x[i] & 0x80000000 | x[i+1] & 0x7fffffff) >> 1)
                    ^ (0x9908b0df if x[i+1] & 1 else 0)

def build_equations(k, bitstr, nout):
    need = list(range(31, 31 - k, -1))          # top k output bit indices, MSB first
    rows, rhs = [], []
    win = deque(maxlen=N)
 
    def emit(i, w):
        base = i * k
        for p, b in enumerate(need):
            acc = 0
            for j in TEMPER_BITS[b]:
                acc ^= w[j]
            rows.append(acc)
            rhs.append(bitstr[base + p] == '1')
 
    for i in range(N):
        w = [1 << (i * 32 + j) for j in range(32)]
        if i < nout:
            emit(i, w)
        win.append(w)
    for i in range(N, nout):
        w = twist_sym(win[0], win[1], win[N - 227])
        emit(i, w)
        win.append(w)
    return rows, rhs

#!/usr/bin/env python3
"""MT19937 partial-bit state recovery over GF(2).
 
getrandbits(k) (k<=32) in CPython returns genrand_uint32() >> (32-k), i.e. the
TOP k bits of one tempered 32-bit output.  Both the twist and the tempering are
GF(2)-linear in the 624*32 = 19968 state bits, so every leaked bit is one linear
equation.  Collect enough of them and solve.
"""
import numpy as np
 
N = 624
M = 397
MATRIX_A = 0x9908B0DF
NUNK = N * 32          # 19968 unknowns
 
 
def temper(y):
    y ^= y >> 11
    y ^= (y << 7) & 0x9D2C5680
    y ^= (y << 15) & 0xEFC60000
    y ^= y >> 18
    return y & 0xFFFFFFFF
 
 
# TEMPER_BITS[b] = which source bits of the raw state word feed output bit b.
# Derived by tempering the unit vectors, so no hand-transcribed shift masks.
TEMPER_BITS = [[j for j in range(32) if (temper(1 << j) >> b) & 1] for b in range(32)]
 
 
def _unshift_right(y, s):
    x = y
    for _ in range(32 // s + 1):
        x = y ^ (x >> s)
    return x & 0xFFFFFFFF
 
 
def _unshift_left(y, s, mask):
    x = y
    for _ in range(32 // s + 1):
        x = y ^ ((x << s) & mask)
    return x & 0xFFFFFFFF
 
 
def untemper(y):
    y = _unshift_right(y, 18)
    y = _unshift_left(y, 15, 0xEFC60000)
    y = _unshift_left(y, 7, 0x9D2C5680)
    return _unshift_right(y, 11)
 
 
def twist_sym(u, v, z):
    """Symbolic x[i] = x[i-227] ^ (((x[i-624]&0x80000000)|(x[i-623]&0x7fffffff))>>1)
                                ^ (0x9908b0df if x[i-623]&1 else 0)
    u = x[i-624], v = x[i-623], z = x[i-227]; each is a list of 32 GF(2) row vectors."""
    out = [0] * 32
    for j in range(32):
        t = z[j]
        if j <= 29:
            t ^= v[j + 1]          # (concat >> 1) bit j  == concat bit j+1 == v[j+1]
        elif j == 30:
            t ^= u[31]             # concat bit 31 is the UPPER bit of u
        if (MATRIX_A >> j) & 1:
            t ^= v[0]              # mag01[v & 1]
        out[j] = t
    return out
 
 
def build_equations(k, bitstr, nout):
    """Return (rows, rhs): one GF(2) equation per leaked bit.
 
    Unknown j*32+b is bit b of state word j, where word 0 is the word that
    produces the very first output (i.e. random.setstate index == 0)."""
    from collections import deque
 
    need = list(range(31, 31 - k, -1))          # top k output bit indices, MSB first
    rows, rhs = [], []
    win = deque(maxlen=N)
 
    def emit(i, w):
        base = i * k
        for p, b in enumerate(need):
            acc = 0
            for j in TEMPER_BITS[b]:
                acc ^= w[j]
            rows.append(acc)
            rhs.append(bitstr[base + p] == '1')
 
    for i in range(N):
        w = [1 << (i * 32 + j) for j in range(32)]
        if i < nout:
            emit(i, w)
        win.append(w)
    for i in range(N, nout):
        w = twist_sym(win[0], win[1], win[N - 227])
        emit(i, w)
        win.append(w)
    return rows, rhs
 
 
def solve_gf2(rows, rhs, nunk=NUNK):
    """Forward elimination to row echelon form, then back substitution.
    Free variables are pinned to 0.  Returns (solution_bits, free_columns)."""
    R = len(rows)
    W = (nunk + 1 + 63) // 64
    A = np.zeros((R, W), dtype=np.uint64)
    for i, (v, b) in enumerate(zip(rows, rhs)):
        if b:
            v |= 1 << nunk
        A[i] = np.frombuffer(v.to_bytes(W * 8, 'little'), dtype=np.uint64)
 
    piv = []
    r = 0
    for c in range(nunk):
        w = c >> 6
        msk = np.uint64(1 << (c & 63))
        nz = np.flatnonzero(A[r:, w] & msk)
        if nz.size == 0:
            continue
        p = r + int(nz[0])
        if p != r:
            A[[r, p]] = A[[p, r]]
            nz = np.flatnonzero(A[r:, w] & msk)
        tgt = r + nz[1:]
        if tgt.size:
            A[tgt, w:] ^= A[r, w:]
        piv.append(c)
        r += 1
 
    last = nunk >> 6
    lastbit = np.uint64(1 << (nunk & 63))
    if r < R and np.any(A[r:, last] & lastbit):
        raise ValueError("inconsistent system")
 
    x = np.zeros(W, dtype=np.uint64)
    for i in range(len(piv) - 1, -1, -1):
        c = piv[i]
        dot = int.from_bytes((A[i] & x).tobytes(), 'little').bit_count() & 1
        val = int(A[i][last] >> np.uint64(nunk & 63)) & 1
        if dot ^ val:
            x[c >> 6] |= np.uint64(1 << (c & 63))
    free = sorted(set(range(nunk)) - set(piv))
    return int.from_bytes(x.tobytes(), 'little'), free
 
 
def state_from_bits(sol):
    return [(sol >> (i * 32)) & 0xFFFFFFFF for i in range(N)]

#!/usr/bin/env python3
"""심볼릭 전개가 맞는지 검증한다.
 
로컬에서 직접 seed 한 MT19937 의 진짜 상태를 알고 있으므로, build_equations 가 만든
1차식에 그 상태를 대입해 실제 출력 비트와 한 개도 어긋나지 않는지 센다."""
import os
import random
import mt
 
r = random.Random(); r.seed(os.urandom(16))
clone = random.Random(); clone.setstate(r.getstate())
U = [mt.untemper(clone.getrandbits(32)) for _ in range(624)]   # 진짜 미지수 벡터
truth = 0
for i, w in enumerate(U):
    truth |= w << (i * 32)
 
for k, nout in ((16, 1443), (8, 2886), (2, 11544), (1, 23088)):
    rr = random.Random(); rr.setstate(r.getstate())
    bits = ''.join(format(rr.getrandbits(k), f'0{k}b') for _ in range(nout))
    rows, rhs = mt.build_equations(k, bits, nout)
    bad = sum(1 for row, b in zip(rows, rhs) if ((row & truth).bit_count() & 1) != b)
    print(f"k={k:2d}  nout={nout:5d}  equations={len(rows):5d}  unknowns={mt.NUNK}  "
          f"mismatch={bad}")

python3 check_symbolic.py

#!/usr/bin/env python3
"""문제 데이터를 건드리기 전에, 내가 만든 상태 복원이 정말 되는지 로컬에서 먼저 본다.
os.urandom(16) 으로 seed 한 MT19937 에서 k비트씩 23088비트를 받아 상태를 복원하고,
그 다음 나올 값 5개를 실제 값과 대조한다."""
import os
import random
import time
import mt
 
TOTAL_BITS = 624 * 37
for k in (16, 8, 4, 2, 1):
    nout = (TOTAL_BITS + k - 1) // k
    src = random.Random(); src.seed(os.urandom(16))
    outs = [src.getrandbits(k) for _ in range(nout)]
    bits = ''.join(format(v, f'0{k}b') for v in outs)
 
    t0 = time.time()
    rows, rhs = mt.build_equations(k, bits, nout)
    sol, free = mt.solve_gf2(rows, rhs)
    el = time.time() - t0
 
    rng = random.Random()
    rng.setstate((3, tuple(mt.state_from_bits(sol)) + (0,), None))
    replay = [rng.getrandbits(k) for _ in range(nout)]
    pred = [rng.getrandbits(k) for _ in range(5)]
    real = [src.getrandbits(k) for _ in range(5)]
    print(f"k={k:2d}  nout={nout:5d}  nullity={len(free):2d}  {el:5.1f}s  "
          f"replay={replay == outs}  next5={pred == real}  {pred}")

python3 selftest.py

#!/usr/bin/env python3
"""Unbreakable (DreamHack, Platinum 3, crypto) - full solve.
 
Six independent MT19937 instances leak 23088 bits each, k bits at a time
(k = 32, 16, 8, 4, 2, 1).  Recover every state, replay the 100 draws that build
the AES key, and unwind the flag chain.
 
    python3 solve.py extracted/output
"""
import random
import sys
import time
from hashlib import sha256
 
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
 
import mt
 
TOTAL_BITS = 624 * 37
IV = b'iluvredblacktree'
STAGES = [32, 16, 8, 4, 2, 1]
 
 
def recover_state(k, bitstr):
    """Return (624 state words that reproduce bitstr with index 0, nout, free cols)."""
    nout = (TOTAL_BITS + k - 1) // k
    if k == 32:
        # every output word is fully visible: untempering alone rebuilds the state
        words = [int(bitstr[i * 32:(i + 1) * 32], 2) for i in range(624)]
        return [mt.untemper(w) for w in words], nout, []
    rows, rhs = mt.build_equations(k, bitstr, nout)
    sol, free = mt.solve_gf2(rows, rhs)
    return mt.state_from_bits(sol), nout, free
 
 
def chain(path, log=None):
    """Walk the six challenge() calls in order.  Returns [(k, key, ct, plaintext)]."""
    lines = open(path).read().split('\n')
    prev = b'iloveredblacktree'
    result = []
    for idx, k in enumerate(STAGES):
        bitstr = lines[idx * 2]
        ct = bytes.fromhex(lines[idx * 2 + 1])
        t0 = time.time()
 
        state, nout, free = recover_state(k, bitstr)
        rng = random.Random()
        rng.setstate((3, tuple(state) + (0,), None))
 
        replay = ''.join(format(rng.getrandbits(k), f'0{k}b') for _ in range(nout))
        assert replay == bitstr, f'k={k}: replay mismatch'
 
        key = prev
        for _ in range(100):
            key += format(rng.getrandbits(k), f'0{k}b').encode()
            key = sha256(key).digest()
        pt = unpad(AES.new(key, AES.MODE_CBC, iv=IV).decrypt(ct), 16)
 
        if log:
            log(f'[k={k:2d}] {nout} outputs, nullity={len(free):2d}, '
                f'{time.time() - t0:5.1f}s  ->  {pt!r}')
        result.append((k, key, ct, pt))
        prev = pt
    return result
 
 
if __name__ == '__main__':
    path = sys.argv[1] if len(sys.argv) > 1 else 'extracted/output'
    stages = chain(path, log=lambda s: print(s, flush=True))
    print()
    print('FLAG:', stages[-1][3].decode())

python3 solve.py extracted/output

[k=32] Congratz! This is basic, right?
[k=16] Wow, possible to break with only 16 bits?
[k= 8] Mersenne Twister, 1-byte edition.
[k= 4] Nah, still possible to break RNGs.
[k= 2] You're very close! Go go go!
[k= 1] DH{now_you_love_Mersenne_twister_dont_ya?}

#!/usr/bin/env python3
"""마지막(k=1) 단계의 AES 키와 암호문을 파일로 떨궈, openssl 로 따로 복호해 볼 수 있게 한다."""
import solve
 
stages = solve.chain('extracted/output')
k, key, ct, pt = stages[-1]
open('key6.hex', 'w').write(key.hex())
open('ct6.bin', 'wb').write(ct)
print(f'stage k={k}')
print(f'key  = {key.hex()}')
print(f'ct   = {len(ct)} bytes -> ct6.bin')
print(f'pycryptodome 복호 결과 = {pt!r}')

#!/usr/bin/env bash
# 복원한 키가 진짜인지 pycryptodome 이 아닌 openssl 로 한 번 더 복호해 확인한다.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
python3 dump_key.py
IVHEX=$(printf 'iluvredblacktree' | xxd -p)
echo "iv   = $IVHEX  (= 'iluvredblacktree')"
echo "--- openssl enc -d -aes-256-cbc ---"
openssl enc -d -aes-256-cbc -K "$(cat key6.hex)" -iv "$IVHEX" -in ct6.bin
echo

./openssl_check.sh

#!/usr/bin/env bash
# Unbreakable (DreamHack, Platinum 3, crypto) — 한 방 재현.
# MT19937 상태를 6번 복원해 AES 키 체인을 되감고 flag 를 뽑는다. 오프라인 문제라 서버 불필요.
#   필요 패키지: numpy, pycryptodome  (pip install numpy pycryptodome)
#   소요: 약 30초 (19968 미지수 × 23088 식 GF(2) 소거를 5번)
set -eu
cd "$(dirname "$(readlink -f "$0")")"
EXPECT='DH{now_you_love_Mersenne_twister_dont_ya?}'
 
OUT=$(timeout 600 python3 solve.py extracted/output 2>&1) || true
echo "$OUT" | tail -10
 
FLAG=$(printf '%s' "$OUT" | grep -aoE 'DH\{[^}]+\}' | head -1)
if [ -n "$FLAG" ] && [ "$FLAG" = "$EXPECT" ]; then
  echo; echo "✅ PASS  $FLAG"; exit 0
fi
echo; echo "❌ FAIL (얻은 값: '${FLAG:-없음}' / 기대: '$EXPECT')"; exit 1

./reproduce.sh