문제: DreamHack — Basic of crypto 분류: Crypto 난이도: 🥉 Bronze 1 FLAG:
DH{Bruteforcing_is_the_fundamental_of_cracking_the_cryptography}
"기초로 돌아가 보자. 암호 시스템을 깨는 가장 근본적인 방법은 무엇일까?" 문제 설명부터 답(브루트포싱)을 암시한다. 플래그를 어떤 키스트림과 XOR해 flag.txt.enc로 남긴 문제다. 키스트림이 무작위처럼 보이지만, 실제로는 두 개의 작은 순열로 완전히 결정된다. 알려진 평문 조각이 그 순열을 특정해 준다.

문제 개요
| 항목 | 내용 |
|---|---|
| 문제명 | Basic of crypto |
| 난이도 | 🥉 Bronze 1 |
| 분류 | Crypto |
| 제공 파일 | chall.py, flag.txt.enc (64바이트) |
| 핵심 기법 | 키스트림 구조 + 알려진 평문 → 순열 전수조사 |
chall.py가 플래그의 형식(DH{로 시작, }로 끝, 내부는 대문자·소문자·밑줄)을 assert로 못박아 준다.
🧱 배경 — XOR 스트림 암호와 알려진 평문
이 문제는 스트림 암호의 골격이다. 평문 각 바이트를 키스트림 바이트와 XOR해 암호문을 만든다. XOR은 자기역원이라, 같은 키스트림을 다시 XOR하면 평문이 복원된다.

출처: Wikimedia Commons, public domain
핵심은 키스트림을 어떻게 복원하느냐다. 여기서 알려진 평문(known plaintext)이 결정적이다. 우리가 이미 아는 평문 바이트(D, H, {, })에서는 keystream = enc XOR plain으로 키스트림 값이 바로 나온다. 나머지는 키스트림의 구조와 형식 제약으로 좁힌다.
🔬 코드 정찰 — clock 키스트림은 두 순열이 전부
cat chall.py![클릭하여 확대 chall.py 전체 — clock()이 두 순열 H, M을 섞어 cal=8*H[h]+M[m]을 만들고, flag는 정해진 형식(DH로 시작, 대소문자·밑줄, 닫는 중괄호로 끝)으로 assert된다](/_next/image?url=%2Fimages%2Fblog%2Fdreamhack-basic-of-crypto-writeup%2F02_chall_source.png&w=3840&q=75)
clock()은 두 리스트 H, M(각각 07의 순열)을 섞은 뒤, 위치 7을 돌고 나서 i마다 cal = 8·H[h] + M[m]을 내놓는다. m이 0h가 증가하므로, 위치 i에서는 h = i//8, m = i%8이다. 정리하면 이렇다.
keystream[i] = 8·H[i//8] + M[i%8]즉 키스트림은 두 순열 H(8개), M(8개)로 완전히 결정된다. 값의 범위는 0..63(6비트). 같은 블록(i//8 고정)의 8개 키스트림 값은 8·H[b] + M[0..7] = 8·H[b] + (0..7의 순열)이라, 그 8개의 상위 3비트는 전부 H[b], 하위 3비트는 M이 배치한 0..7이다.
우리가 이미 아는 4바이트(D, H, {, })로 실제 키스트림 값을 직접 뽑아봤다.
enc = open('flag.txt.enc', 'rb').read()
known = {0: ord('D'), 1: ord('H'), 2: ord('{'), 63: ord('}')}
for i, p in known.items():
ks = enc[i] ^ p
b, c = i // 8, i % 8
print(f'i={i} (b={b},c={c}): keystream={ks} = 8*H[{b}]+M[{c}]')
i=0,1,2(모두 블록 0)의 키스트림이 60, 62, 63으로 전부 8×7대 — 즉 H[0] = 7이 이 세 값만으로 이미 확정된다. 마지막 바이트(i=63, 블록 7)는 키스트림 18 = 8×2+2라 H[7] = 2도 함께 확정된다. 딱 4바이트의 알려진 평문이 8개짜리 순열 H의 두 원소를 바로 못박아버린 셈이다. (나중에 나오지만, 실제 정답도 정확히 H[0]=7, H[7]=2다.)
🎯 풀이 — 순열 전수조사 + 형식 제약
H(8! = 40,320가지)를 전수조사한다. 각 후보 H에 대해, 각 열 c(즉 M[c])의 가능한 값들을 8개 블록 전부에서 형식 제약을 만족하는 값들의 교집합으로 좁힌다. 그 다음 각 열에서 서로 겹치지 않게 값을 하나씩 골라 M이 진짜 순열이 되는 조합을 찾는다(작은 매칭 문제라 재귀로 바로 풀린다).
# solve.py
from itertools import permutations
def valid(i, byte):
if i < 3: return byte == b'DH{'[i]
if i == 63: return byte == ord('}')
return (0x41<=byte<=0x5A) or (0x61<=byte<=0x7A) or byte==0x5F
def match(colM, used, c): # 열마다 서로 다른 값을 배정하는 매칭
if c == 8: return []
for m in colM[c]:
if m not in used:
rest = match(colM, used | {m}, c+1)
if rest is not None: return [m] + rest
return None
for H in permutations(range(8)):
colM = []
for c in range(8):
cand = set(range(8))
for b in range(8):
i = 8*b + c
cand &= {m for m in range(8) if valid(i, enc[i] ^ (8*H[b]+m))}
colM.append(cand)
if not cand: break
else:
M = match(colM, set(), 0)
if M: break
flag = bytes(enc[8*b+c] ^ (8*H[b]+M[c]) for b in range(8) for c in range(8))
H = (7, 5, 1, 4, 6, 0, 3, 2), M = [4, 6, 7, 5, 3, 1, 0, 2]에서 매칭이 완성된다. 앞서 known-plaintext로 손으로 확인한 H[0]=7, H[7]=2와 정확히 일치한다. 40,320가지 순열을 전부 시도하지 않고도(39,092번째에서 조기 종료), 0.14초 만에 끝났다 — 형식 제약이 워낙 강해서 대부분의 H 후보가 열 단위 교집합 단계에서 곧바로 걸러지기 때문이다.
복원된 플래그 DH{Bruteforcing_is_the_fundamental_of_cracking_the_cryptography}가 문제의 정신 그대로다.
![클릭하여 확대 keystream[i]=8·H[i//8]+M[i%8], 알려진 평문 제약으로 순열 H, M 을 전수조사](/_next/image?url=%2Fimages%2Fblog%2Fdreamhack-basic-of-crypto-writeup%2Fdiagram.png&w=3840&q=75)
FLAG: DH{Bruteforcing_is_the_fundamental_of_cracking_the_cryptography}
📝 결론
작은 상태에서 나온 키스트림은 그 상태만큼만 안전하다. 키스트림이 64바이트로 길어 보여도, 그 전체가 두 개의 8원소 순열에서 나온다면 실제 비밀 공간은 8! × 8! ≈ 16억이 아니라(순열이 독립이 아니라 서로 얽혀 있어서 실질적으로는 그보다 훨씬 작다), 형식 제약이 걸리면 순식간에 하나로 좁아진다. 스트림의 길이가 아니라 시드/상태의 엔트로피가 안전성을 정한다.
알려진 평문 한 조각이 전체를 연다. DH{와 }처럼 고정된 형식은 그 자리의 키스트림 값을 곧바로 알려 주고, 나머지 자리의 형식 제약은 후보를 대량으로 쳐낸다. 이번 문제에서는 단 4바이트의 알려진 평문만으로 8개짜리 순열의 원소 2개(H[0], H[7])가 바로 확정됐다. 플래그 형식은 방어자에게는 사소하지만 공격자에게는 강력한 지렛대다.
Comments
댓글
댓글을 남기려면 로그인이 필요해요. (네이버 · 구글 계정)
댓글 불러오는 중…