[🥉 Bronze 2] LFSR 키스트림 32비트로 시드를 되감다 — DreamHack STREME REVERIE 풀이

ls -l extracted && cat extracted/output.txt

#!/usr/bin/env python3
from cipher import STREAM
import random
 
 
if __name__ == "__main__":
    with open("flag", "rb") as f:
        flag = f.read()
 
    assert flag[:3] == b'DH{' and flag[-1:] == b'}'
 
    seed = random.getrandbits(32)
    stream = STREAM(seed, 32)
 
    print(f"encrypted flag > {stream.encrypt(flag).hex()}")

class STREAM:
    def __init__(self, seed, size):
        self.state = self.num2bits(seed, size)
        # x^32 + x^22 + x^2 + x^1 + 1
        self.taps = (32, 22, 2, 1)
 
    def num2bits(self, num, size):
        assert num < (1 << size)
 
        return bin(num)[2:].zfill(size)
 
    def bits2num(self, bits):
        return int('0b' + bits, 2)
 
    def shift(self):
        new_bit = 0
        for tap in self.taps:
            new_bit ^= int(self.state[tap - 1])
        new_bit = str(new_bit)
        self.state = new_bit + self.state[:-1]
        return new_bit
 
    def getNbits(self, num):
        sequence = ""
        for _ in range(num):
            sequence += self.shift()
 
        return sequence
 
    def encrypt(self, plaintext):
        ciphertext = b""
        for p in plaintext:
            stream = self.bits2num(self.getNbits(8))
            c = p ^ stream
            ciphertext += bytes([c])
 
        return ciphertext

#!/usr/bin/env python3
"""LFSR 의 '출력 비트 = 다음 상태' 관계를 눈으로 확인한다.
 
32스텝을 돌린 뒤의 내부 상태가 그동안 뱉은 키스트림 32비트를 뒤집은 것과
같은지 직접 비교한다. 같다면 키스트림 32비트만 알아도 상태가 복원된다는 뜻이다.
"""
import sys
sys.path.insert(0, "extracted")
from cipher import STREAM
 
SEED = 0xFE5DB0A9
 
s = STREAM(SEED, 32)
print(f"[*] seed  = 0x{SEED:08x}")
print(f"[*] state = {s.state}   (state[0] 이 최신 비트 자리)")
print()
 
ks = ""
for step in range(1, 9):
    bit = s.shift()
    ks += bit
    print(f"  step {step:2d}: 출력={bit}  state={s.state}")
 
print()
ks += s.getNbits(24)          # 합쳐서 32비트
print(f"[*] 32스텝 키스트림      : {ks}")
print(f"[*] 32스텝 뒤 내부 상태  : {s.state}")
print(f"[*] 키스트림을 뒤집은 것 : {ks[::-1]}")
print(f"[+] 상태 == 뒤집은 키스트림 ? {s.state == ks[::-1]}")

python3 trace_lfsr.py

new  = prev[31] ^ prev[21] ^ prev[1] ^ prev[0]
cur  = new + prev[:-1]

prev[31] = new ^ prev[21] ^ prev[1] ^ prev[0]
         = cur[0] ^ cur[22] ^ cur[2] ^ cur[1]

def unshift(state):
    prev31 = int(state[0]) ^ int(state[22]) ^ int(state[2]) ^ int(state[1])
    return state[1:] + str(prev31)

#!/usr/bin/env python3
"""후보 256개가 각각 어떤 평문을 뱉는지, 어떤 조건에서 하나로 좁혀지는지 센다.
 
앞 3바이트는 어떤 후보를 넣어도 'DH{' 가 나온다 — 그걸로 상태를 만들었으니 당연하다.
그래서 4번째 글자부터가 판별 근거다.
"""
import string
import sys
 
sys.path.insert(0, "extracted")
from cipher import STREAM
from solve import load_ct, unshift
 
ct = load_ct()
ks = "".join(f"{c ^ p:08b}" for c, p in zip(ct, b"DH{"))
printable = set(string.printable[:-5].encode())
 
ok_close, ok_all, hits = 0, 0, []
for guess in range(0x100):
    state = (ks + f"{guess:08b}")[::-1]
    for _ in range(32):
        state = unshift(state)
    pt = STREAM(int(state, 2), 32).decrypt(ct)
 
    if guess < 3:
        print(f"  후보 {guess:3d}: {pt[:40]!r}")
    if pt[-1:] == b"}":
        ok_close += 1
    if set(pt) <= printable:
        ok_all += 1
        hits.append((guess, pt))
 
print()
print(f"[*] 'DH{{' 로 시작하는 후보 : 256 / 256   (상태를 그렇게 만들었으니 전부)")
print(f"[*] '}}' 로 끝나는 후보     : {ok_close} / 256")
print(f"[*] 전부 출력가능 문자     : {ok_all} / 256")
for guess, pt in hits:
    print(f"[+] 유일 후보 (4번째 글자 키스트림 {guess:08b}): {pt.decode()}")

python3 candidates.py

#!/usr/bin/env python3
"""STREME REVERIE (DreamHack #1923, Bronze 2, crypto) 풀이.
 
32비트 LFSR 의 출력 비트가 그대로 다음 상태로 들어가므로,
연속된 키스트림 32비트를 알면 그 시점의 내부 상태가 통째로 복원된다.
알려진 평문 "DH{" 는 24비트뿐이라 남은 8비트(=플래그 4번째 글자에 쓰인 키스트림)만
256가지로 훑고, 상태를 32스텝 되감아 시드를 얻는다.
 
사용법: python3 solve.py            (같은 폴더의 extracted/output.txt 를 읽는다)
"""
import re
import string
from pathlib import Path
 
HERE = Path(__file__).resolve().parent
TAPS = (32, 22, 2, 1)          # x^32 + x^22 + x^2 + x + 1
 
 
# ── 문제의 STREAM 을 그대로 옮긴 것 (검증용) ────────────────────────────────
class STREAM:
    def __init__(self, seed, size):
        self.state = bin(seed)[2:].zfill(size)
        self.taps = TAPS
 
    def shift(self):
        new_bit = 0
        for tap in self.taps:
            new_bit ^= int(self.state[tap - 1])
        new_bit = str(new_bit)
        self.state = new_bit + self.state[:-1]
        return new_bit
 
    def getNbits(self, num):
        return "".join(self.shift() for _ in range(num))
 
    def decrypt(self, ciphertext):
        out = b""
        for c in ciphertext:
            out += bytes([c ^ int(self.getNbits(8), 2)])
        return out
 
 
# ── LFSR 을 한 스텝 되감기 ────────────────────────────────────────────────
def unshift(state):
    """state = new_bit + prev[:-1] 이므로 prev[:31] 은 그대로 보이고,
    사라진 prev[31] 은 탭 관계식에서 되살린다."""
    prev31 = int(state[0]) ^ int(state[22]) ^ int(state[2]) ^ int(state[1])
    return state[1:] + str(prev31)
 
 
def load_ct():
    txt = (HERE / "extracted" / "output.txt").read_text()
    # "encrypted flag > ..." 의 앞부분도 [0-9a-f] 로 읽히므로 길이로 골라낸다
    return bytes.fromhex(max(re.findall(r"[0-9a-f]{2,}", txt), key=len))
 
 
def main():
    ct = load_ct()
    known = b"DH{"
    # 알려진 평문 3바이트 → 키스트림 24비트 (먼저 나온 비트가 MSB)
    ks = "".join(f"{c ^ p:08b}" for c, p in zip(ct, known))
    print(f"[*] 암호문 {len(ct)}바이트, 알려진 키스트림 {len(ks)}비트: {ks}")
 
    printable = set(string.printable[:-5].encode())
    for guess in range(0x100):
        bits = ks + f"{guess:08b}"          # k1..k32
        # 32스텝 뒤의 상태는 방금 나온 비트가 앞에 오도록 뒤집힌 순서다
        state = bits[::-1]
        for _ in range(32):
            state = unshift(state)
 
        seed = int(state, 2)
        flag = STREAM(seed, 32).decrypt(ct)
        if flag[:3] != known or flag[-1:] != b"}":
            continue
        if not set(flag) <= printable:
            continue
        print(f"[+] seed = {seed} (0x{seed:08x}), 4번째 글자 키스트림 = {guess:08b}")
        print(f"[+] FLAG: {flag.decode()}")
        return
 
    print("[-] 후보 256개 모두 실패")
 
 
if __name__ == "__main__":
    main()

python3 solve.py

#!/usr/bin/env python3
"""복원한 시드로 flag 를 다시 암호화해 배포된 output.txt 와 바이트 단위로 대조한다."""
import sys
 
sys.path.insert(0, "extracted")
from cipher import STREAM
 
SEED = 0xFE5DB0A9
FLAG = b"DH{855083595b1557aeb8f60e7422e49405672b8ddf793700d884dae710909f9d0f}"
 
ct = bytes.fromhex(open("extracted/output.txt").read().split(">")[1].strip())
mine = STREAM(SEED, 32).encrypt(FLAG)
 
print(f"[*] 배포된 암호문 : {ct.hex()[:48]}... ({len(ct)}바이트)")
print(f"[*] 재암호화 결과 : {mine.hex()[:48]}... ({len(mine)}바이트)")
print(f"[+] 완전 일치? {mine == ct}")
print(f"[+] 복호 결과   : {STREAM(SEED, 32).decrypt(ct).decode()}")

python3 verify.py

from sage.matrix.berlekamp_massey import berlekamp_massey
 
R.<x> = GF(2)[]
f = x^32 + x^22 + x^2 + x + 1          # cipher.py 주석의 다항식
g = f.reverse()                        # 코드가 실제로 도는 점화식
 
print("[1] 주석 다항식 f =", f)
print("    기약(irreducible)?", f.is_irreducible(), " 원시(primitive)?", f.is_primitive())
print("    → 주기 2^32-1 =", 2^32 - 1)
print()
print("[2] 역순 다항식 g =", g)
print("    원시(primitive)?", g.is_primitive())
print("    코드의 점화식: k_t = k_(t-1) + k_(t-2) + k_(t-22) + k_(t-32)")
print()
 
flag = b'DH{855083595b1557aeb8f60e7422e49405672b8ddf793700d884dae710909f9d0f}'
ct = bytes.fromhex(open('extracted/output.txt').read().split('>')[1].strip())
bits = ''.join(format(c ^^ p, '08b') for c, p in zip(ct, flag))
seq = [GF(2)(int(b)) for b in bits]
 
print("[3] 복원한 키스트림", len(seq), "비트에 Berlekamp-Massey")
bm = berlekamp_massey(seq)
print("    최소 다항식 =", bm, " (차수", bm.degree(), ")")
print("    == g ?", bm == g, "   == f ?", bm == f)

sage lfsr_poly.sage

#!/usr/bin/env bash
# STREME REVERIE (DreamHack #1923, Bronze 2, crypto) — 한 방 재현.
# 배포된 extracted/output.txt 만으로 flag 를 복원하고 정답과 대조한다. 서버 불필요.
set -eu
cd "$(dirname "$(readlink -f "$0")")"
EXPECT=$(python3 -c "import json;print(json.load(open('문제.json'))['flag'])" 2>/dev/null || echo '')
 
OUT=$(timeout 300 python3 solve.py "$@" 2>&1) || true
 
echo "$OUT" | tail -8
FLAG=$(printf '%s' "$OUT" | grep -aoE 'DH\{[^}]+\}' | head -1)
if [ -n "$FLAG" ] && { [ -z "$EXPECT" ] || [ "$FLAG" = "$EXPECT" ]; }; then
  echo; echo "✅ PASS  $FLAG"; exit 0
fi
echo; echo "❌ FAIL (얻은 값: '${FLAG:-없음}' / 기대: '$EXPECT')"; exit 1

./reproduce.sh