[🥉 Bronze 1] 두 순열로 만든 clock 키스트림 되맞추기 — DreamHack Basic of crypto 풀이

2026-07-14·1분 읽기·

[🥉 Bronze 1] 두 순열로 만든 clock 키스트림 되맞추기 — DreamHack Basic of crypto 풀이

플래그 64바이트를 clock 제너레이터가 만든 키스트림과 XOR한 문제. 키스트림 값은 두 순열 H, M으로 keystream[i] = 8·H[i//8] + M[i%8] 처럼 결정되는데, 알려진 평문(DH{, }, 대문자와 밑줄만) 제약이 강해 순열을 전수조사하면 유일한 플래그가 복원된다. 실제로 40320가지 H 순열 중 39092번째에서 정답이 나오고, 걸린 시간은 0.14초뿐이다.

문제: DreamHack — Basic of crypto 분류: Crypto 난이도: 🥉 Bronze 1 FLAG: DH{Bruteforcing_is_the_fundamental_of_cracking_the_cryptography}

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

Basic of crypto 문제 페이지 — "암호 시스템을 깨는 가장 근본적인 방법은 무엇일까?"
Basic of crypto 문제 페이지 — "암호 시스템을 깨는 가장 근본적인 방법은 무엇일까?"

문제 개요

항목내용
문제명Basic of crypto
난이도🥉 Bronze 1
분류Crypto
제공 파일chall.py, flag.txt.enc (64바이트)
핵심 기법키스트림 구조 + 알려진 평문 → 순열 전수조사

chall.py가 플래그의 형식(DH{로 시작, }로 끝, 내부는 대문자·소문자·밑줄)을 assert로 못박아 준다.



🧱 배경 — XOR 스트림 암호와 알려진 평문

이 문제는 스트림 암호의 골격이다. 평문 각 바이트를 키스트림 바이트와 XOR해 암호문을 만든다. XOR은 자기역원이라, 같은 키스트림을 다시 XOR하면 평문이 복원된다.

XOR 게이트 — 두 입력이 다를 때만 1, 같은 키로 두 번 XOR 하면 원래 값
XOR 게이트 — 두 입력이 다를 때만 1, 같은 키로 두 번 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된다
chall.py 전체 — clock()이 두 순열 H, M을 섞어 cal=8*H[h]+M[m]을 만들고, flag는 정해진 형식(DH로 시작, 대소문자·밑줄, 닫는 중괄호로 끝)으로 assert된다

clock()은 두 리스트 H, M(각각 07의 순열)을 섞은 뒤, 위치 i마다 cal = 8·H[h] + M[m]을 내놓는다. m이 07을 돌고 나서 h가 증가하므로, 위치 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}]')
알려진 평문 4바이트로 뽑은 키스트림 값 — 60,62,63(모두 87+m 꼴)과 18(82+2 꼴)
알려진 평문 4바이트로 뽑은 키스트림 값 — 60,62,63(모두 87+m 꼴)과 18(82+2 꼴)

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))
solve.py 실행 — 40320가지 H 순열 중 39092번째에서 매칭 성공, 0.14초 만에 플래그 복원
solve.py 실행 — 40320가지 H 순열 중 39092번째에서 매칭 성공, 0.14초 만에 플래그 복원

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 을 전수조사
keystream[i]=8·H[i//8]+M[i%8], 알려진 평문 제약으로 순열 H, M 을 전수조사

FLAG: DH{Bruteforcing_is_the_fundamental_of_cracking_the_cryptography}


📝 결론

작은 상태에서 나온 키스트림은 그 상태만큼만 안전하다. 키스트림이 64바이트로 길어 보여도, 그 전체가 두 개의 8원소 순열에서 나온다면 실제 비밀 공간은 8! × 8! ≈ 16억이 아니라(순열이 독립이 아니라 서로 얽혀 있어서 실질적으로는 그보다 훨씬 작다), 형식 제약이 걸리면 순식간에 하나로 좁아진다. 스트림의 길이가 아니라 시드/상태의 엔트로피가 안전성을 정한다.

알려진 평문 한 조각이 전체를 연다. DH{와 }처럼 고정된 형식은 그 자리의 키스트림 값을 곧바로 알려 주고, 나머지 자리의 형식 제약은 후보를 대량으로 쳐낸다. 이번 문제에서는 단 4바이트의 알려진 평문만으로 8개짜리 순열의 원소 2개(H[0], H[7])가 바로 확정됐다. 플래그 형식은 방어자에게는 사소하지만 공격자에게는 강력한 지렛대다.

이 글이 도움이 됐나요?

Comments

댓글

0개

댓글을 남기려면 로그인이 필요해요. (네이버 · 구글 계정)

댓글 불러오는 중…

Related

관련 글

3개
[🥉 Bronze 2] 두 번 쓴 일회용 패드 — DreamHack X-Time Pad 풀이
blog

[🥉 Bronze 2] 두 번 쓴 일회용 패드 — DreamHack X-Time Pad 풀이

One-Time Pad 를 흉내 낸 암호화 서버가 두 번째 패드를 첫 번째 패드에서 만들어 낸다. 소스에 박힌 512비트 상수 하나만 알면 내 평문 암호문에서 원래 키가 통째로 나오고, 그 키로 flag 암호문을 되돌린다. 평문 길이를 64자로 꽉 채워야 하는 이유는 bin() 과 문자열 슬라이스에 있다.
#dreamhack#ctf#crypto+5
2026-10-31#dreamhack +4
[🥉 Bronze 2] 세 겹으로 포장한 귤 상자 벗기기 — DreamHack 감귤 포장하기 풀이
blog

[🥉 Bronze 2] 세 겹으로 포장한 귤 상자 벗기기 — DreamHack 감귤 포장하기 풀이

플래그를 wrap(아핀 곱셈)·box(위치별 XOR)·truck(뒤집은 테이블 base64) 세 변환으로 포장한 문제. 문제 설명 자체가 4컷 만화로 "즙 짜고 양념 치기 → 마구잡이로 섞고 테이프로 감기 → 뒤죽박죽 글자 트럭에 싣기 → 배송 완료"를 그려 놓았다. 세 변환이 모두 가역이라, 적용된 역순으로 base64를 풀고 XOR를 되돌리고 아핀을 역산하면 플래그가 나온다.
#dreamhack#ctf#crypto+4
2026-07-14#dreamhack +4
[🥉 Bronze 2] 거듭제곱 차이 한 줄로 평문을 되돌리다 — DreamHack ICM2022 풀이
blog

[🥉 Bronze 2] 거듭제곱 차이 한 줄로 평문을 되돌리다 — DreamHack ICM2022 풀이

평문을 두 키의 거듭제곱 차이에 곱해 암호문 하나로 내보내는 crypto 문제. 키가 두 개지만 하나는 공개되고 다른 하나는 좁은 범위라, 암호문이 정수로 떨어지는 키를 전수조사하면 평문 정수 p가 그대로 복원된다. 그 p 자체가 플래그이며, ord 값을 이어 붙인 형태라 사람이 읽을 수도 있다.
#dreamhack#ctf#crypto+3
2026-07-14#dreamhack +4