Step 231. Cryptopals Set 1 완주 — XOR 공격의 교과서를 내 코드로
Level 3 — CTF 실전과 공격 스킬 심화 | 난이도 ★★★☆☆ | 예상 소요 시간 6시간
전제: Step 90(XOR과 인코딩), Step 229~230의 파이썬 수치 감각. AES 라이브러리가 처음 등장합니다.
⚠️ 이 챕터의 실습은 내 랩·합법 플랫폼 전용입니다. 허가 없는 시스템에 적용하면 범죄입니다.
- 준비물: 파이썬 3(실측: 3.12.14),
pip install pycryptodome(AES용), 인터넷 접속(원본 문제 확인용). - 주의: Cryptopals(cryptopals.com)는 공개된 합법 학습 문제집입니다 — 제작자들이 공격 연습을 권장하기 위해 만든 사이트입니다. 다만 원본 문제 파일 다운로드가 필요한 문제(챌린지 4, 6, 7, 8)는 외부 데이터라, 이 챕터의 코드는 같은 알고리즘을 직접 만든 데이터로 실측합니다. 출력은 전부 실측입니다.
Cryptopals는 "암호 공격을 코드로 배우는" 최고의 커리큘럼으로 꼽힙니다. Set 1의 8문제는 XOR 공격의 교과서입니다 — 단일 바이트 XOR을 빈도 분석으로 깨고, 반복키 XOR은 키 길이를 해밍 거리로 추정한 뒤 열(column)별 단일키 문제로 분해합니다. 오늘 목표는 "정답을 아는 것"이 아니라 "점수 함수 하나로 256개 후보를 자동 채점하는 기계"를 갖는 것입니다. 이 기계는 Set 2와 이후 모든 Crypto 문제에서 재사용됩니다.
1. 학습 목표
이 챕터를 끝내면 다음을 할 수 있습니다:
- hex ↔ bytes ↔ base64 변환을 자유롭게 하고 각 형식의 역할을 설명한다
- 해밍 거리를 구현하고 "비트 차이 개수"로서의 의미를 안다
- 영어 빈도 점수 함수로 단일 바이트 XOR 암호문을 자동 해독한다
- 정규화 해밍 거리로 반복키 XOR의 키 길이를 추정하고, 열 분리로 키를 복구한다
- AES-ECB 복호화를 라이브러리로 수행하고, 반복 블록 탐지로 ECB 암호문을 식별한다
2. 배경 지식 — 오늘의 도구와 개념
오늘의 도구 한눈에 보기
| 구분 | 내용 |
|---|---|
| 언어·환경 | 파이썬 3 (실측: 3.12.14) + pycryptodome(AES-ECB 복호화용) |
| 오늘의 명령어 | bytes.fromhex(), base64.b64encode(), bin(x).count("1"), AES.new(key, AES.MODE_ECB) |
| 필요한 개념 | XOR(Step 90), 해밍 거리, 빈도 분석, 반복키 XOR의 열 분해, 블록 암호와 ECB |
| 오늘의 산출물 | xorlib.py — 점수 함수 + 단일키 해독기 + 키 길이 추정기(이후 챕터에서 재사용) |
2-1. 세 가지 표현 — hex, bytes, base64
같은 데이터의 세 얼굴입니다. bytes가 본체(실제 0과 1), hex는 사람이 읽기 위한 16진수 표기(바이트당 2글자), base64는 텍스트만 통과하는 채널(이메일, JSON)을 위한 64문자 인코딩(바이트 3개당 4글자)입니다. 암호 문제는 데이터를 hex나 base64로 주는데, 계산은 항상 bytes로 변환한 뒤에 합니다.
2-2. 해밍 거리 — 두 바이트열이 몇 비트 다른가
해밍 거리(hamming distance)는 두 바이트열의 다른 비트 수입니다. 각 바이트를 XOR하면 다른 비트만 1이 되니, bin(x ^ y).count("1")의 합이 곧 거리입니다. 유명한 검증 벡터: "this is a test"와 "wokka wokka!!!"의 거리는 37입니다 — 구현이 맞는지 확인하는 척도로 오늘도 씁니다.
2-3. 빈도 분석 — 언어는 통계를 새긴다
영어 문장은 글자 빈도가 편향돼 있습니다 — e, t, a, 공백이 압도적으로 많습니다. 단일 바이트 XOR은 평문의 통계를 그대로 옮길 뿐 지우지 못합니다. 그래서 "256개 키를 전부 시도하고, 결과가 가장 영어다운 것을 고르는" 것으로 키를 몰라도 해독됩니다. 점수 함수가 성패를 가릅니다 — 공백과 알파벳 비율만으로도 꽤 되고, 출력 불가 문자에 페널티를 주면 훨씬 안정됩니다.
2-4. 반복키 XOR의 분해 — 길이를 찾으면 게임이 끝난다
키 K를 반복해 XOR하면, 같은 위치의 평문 글자들은 같은 키 바이트로 암호화됩니다. 암호문을 키 길이 L 단위로 잘라 열을 만들면 각 열은 단일 바이트 XOR 문제입니다. 문제는 L을 모른다는 것 — 여기서 해밍 거리가 씁니다. 올바른 L로 자른 인접 블록들은 "영어 XOR 영어"라 다른 비트가 적고(정규화 거리 ~2~3), 틀린 L은 무작위에 가까워집니다(~4). L 후보 2~40의 정규화 거리를 비교해 특정합니다.
3. 따라 하기
이 챕터의 모든 출력은 2026-09-09 파이썬 3.12.14 실측입니다. 문제 데이터는 같은 알고리즘으로 직접 생성한 것입니다 — 원본 문제는 cryptopals.com에서 받아 같은 코드에 넣으면 됩니다.
3-1. hex ↔ base64 (챌린지 1)
import base64
raw = bytes.fromhex("43727970746f20747261636b21")
print("hex -> bytes:", raw)
print("bytes -> base64:", base64.b64encode(raw).decode())
print("base64 -> hex 왕복:", base64.b64decode(base64.b64encode(raw)).hex())
hex -> bytes: b'Crypto track!'
bytes -> base64: Q3J5cHRvIHRyYWNrIQ==
base64 -> hex 왕복: 43727970746f20747261636b21
출력 읽는 법: 세 표현이 한 데이터를 왕복합니다. 끝의 ==는 base64의 채움 문자 — 원본 바이트 수가 3의 배수가 아닐 때 붙습니다. 원본 챌린지 1은 훨씬 긴 hex를 주지만, 변환 코드는 이 세 줄이 전부입니다.
3-2. 해밍 거리 (챌린지 6의 예열)
def hamming(a, b):
return sum(bin(x ^ y).count("1") for x, y in zip(a, b))
print("해밍 거리:", hamming(b"this is a test", b"wokka wokka!!!"))
해밍 거리: 37
출력 읽는 법: 공개 검증 벡터 37과 일치 — 구현이 정확합니다. 이 함수 하나가 뒤의 키 길이 추정 전부를 받칩니다.
3-3. 단일 바이트 XOR 해독 (챌린지 3)
점수 함수와 "256개 전수조사" 해독기를 만듭니다.
FREQ = "etaoin shrdlu" # 영어에서 흔한 글자(공백 포함)
def score(bs):
s = 0
for x in bs.lower():
c = chr(x)
if c in FREQ: s += 2
elif c.isalpha() or c in " .,'!?": s += 1
elif x < 32 or x > 126: s -= 5 # 출력 불가 문자 페널티
return s
def break_single_xor(ct):
best = (-10**9, None, None)
for k in range(256):
pt = bytes(x ^ k for x in ct)
sc = score(pt)
if sc > best[0]:
best = (sc, k, pt)
return best
plain = b"The quick brown fox jumps over the lazy dog, again and again."
ct = bytes(x ^ 0x42 for x in plain)
sc, k, pt = break_single_xor(ct)
print("복구 키: 0x%02x, 점수: %d" % (k, sc))
print("복구 평문:", pt.decode())
복구 키: 0x42, 점수: 104
복구 평문: The quick brown fox jumps over the lazy dog, again and again.
출력 읽는 법: 키를 모르는 상태에서 256개 후보를 채점해 0x42를 찾았습니다. 비밀은 brute force가 아니라 채점입니다 — 틀린 키는 제어 문자를 쏟아내 페널티(-5)에 걸리고, 맞는 키만 영어 통계를 되살립니다.
3-4. 여러 줄에서 암호문 찾기 (챌린지 4)
60개의 무작위 줄 중 하나만 단일키 XOR로 암호화된 영어입니다. 점수 함수를 재사용해 "가장 영어다운 줄"을 찾습니다.
import secrets
lines = [secrets.token_bytes(30) for _ in range(60)]
lines[37] = bytes(x ^ 0x35 for x in b"Now that the party is jumping and the bass kicked in")
best = max((score(break_single_xor(l)[2]), i, break_single_xor(l)[2])
for i, l in enumerate(lines))
print("가장 영어다운 줄: #%d, 점수 %d" % (best[1], best[0]))
print("내용:", best[2].decode())
가장 영어다운 줄: #37, 점수 93
내용: Now that the party is jumping and the bass kicked in
출력 읽는 법: 60줄 × 256키 = 15,360번의 채점을 파이썬이 순식간에 끝냅니다. 챌린지 4의 원본(325줄 파일)도 이 코드 그대로입니다 — 파일을 open으로 읽어 lines에 넣기만 하면 됩니다.
3-5. 반복키 XOR 완전 해독 (챌린지 6)
키 길이 추정 → 열 분리 → 열별 단일키 해독, 세 단계입니다.
def rep_xor(data, key):
return bytes(b ^ key[i % len(key)] for i, b in enumerate(data))
def guess_keysize(ct, lo=2, hi=15):
out = []
for ks in range(lo, hi + 1):
blocks = [ct[i:i+ks] for i in range(0, ks * 6, ks)]
pairs = [(blocks[i], blocks[j]) for i in range(6) for j in range(i + 1, 6)]
d = sum(hamming(a, b) / ks for a, b in pairs) / len(pairs)
out.append((d, ks))
return sorted(out)[:3]
text = (b"Back in the lab again, cooking up the same old plaintext. "
b"The rhythm of English repeats itself like a drum machine. "
b"Letter frequencies leak through every single column we split. "
b"Split the ciphertext into columns and each one is a single key puzzle. "
b"Drums keep pounding rhythm to the brain, la de da de dee. ")
rct = rep_xor(text, b"ICE")
print("키 길이 후보:", [(ks, round(d, 2)) for d, ks in guess_keysize(rct)])
ks = guess_keysize(rct)[0][1]
key_bytes = bytearray()
for col in range(ks):
_, k, _ = break_single_xor(rct[col::ks]) # col 열만 추출해 단일키 해독
key_bytes.append(k)
print("복구된 키:", bytes(key_bytes))
print("복구 평문 앞 60자:", rep_xor(rct, bytes(key_bytes))[:60].decode())
키 길이 후보(정규화 해밍 거리 오름차순): [(3, 2.27), (7, 2.4), (12, 2.4)]
복구된 키: b'ICE'
복구 평문 앞 60자: Back in the lab again, cooking up the same old plaintext. Th
출력 읽는 법: 정규화(키 길이로 나누기)를 빼먹으면 긴 키 길이가 무조건 불리해져 오판합니다 — 반드시 / ks. 키 길이 3이 2.27로 가장 낮게 나왔고, 열 분리 공격이 키 ICE를 정확히 복구했습니다. rct[col::ks]라는 슬라이스 한 줄이 "열 추출"의 전부입니다.
3-6. AES-ECB 복호화와 반복 블록 탐지 (챌린지 7~8)
from Crypto.Cipher import AES
aes_key = b"YELLOW SUBMARINE"
msg = b"yellow submarine" * 4 + b"all my friends are" # 16B 블록 4개 반복
cipher = AES.new(aes_key, AES.MODE_ECB)
pad = bytes([16 - len(msg) % 16]) * (16 - len(msg) % 16)
ct = cipher.encrypt(msg + pad)
print("ECB 복호화 앞 46바이트:", cipher.decrypt(ct)[:46])
blocks = [ct[i:i+16] for i in range(0, len(ct), 16)]
print("전체 %d블록 중 고유 %d개" % (len(blocks), len(set(blocks))))
print("-> 반복 있음이면 ECB 의심:", len(set(blocks)) < len(blocks))
ECB 복호화 앞 46바이트: b'yellow submarineyellow submarineyellow submari'
전체 6블록 중 고유 3개
-> 반복 있음이면 ECB 의심: True
출력 읽는 법: ECB는 같은 평문 블록이 언제나 같은 암호문 블록이 됩니다 — yellow submarine 네 개가 암호문에서도 동일하게 반복됐습니다(고유 3개 = 반복 4개 + 잔여 + 패딩). 이 성질이 Set 1의 마지막 문제(암호문 파일에서 ECB 줄 찾기)의 해법이자, 다음 챕터의 본격 공격 소재입니다.
4. 미션과 연습문제
미션 — xorlib.py 완성과 Set 1 자가 검증
- 오늘의 함수들을
xorlib.py로 정리합니다 —hamming,score,break_single_xor(반환(점수, 키, 평문)),rep_xor,guess_keysize,detect_ecb_blocks(ct, bs=16)(반복 블록 수 반환) - 자가 검증 스크립트를 씁니다: ① hamming 검증 벡터(37) 통과 ② 직접 만든 단일키·반복키 암호문을 키를 지운 채로 복구 ③ ECB 반복 블록 탐지 성공
- cryptopals.com에서 Set 1의 실제 문제(챌린지 1~8)를 받아 같은 함수로 풀어 봅니다 — 특히 챌린지 4와 6의 파일은
open(...).read().splitlines()만 추가하면 됩니다 - (선택) 점수 함수를 개선해 보세요 — 글자 빈도표(
etaoin가중치 차등)를 넣으면 짧은 문장에서 정확도가 오릅니다
연습문제
문제 1. hex와 base64는 둘 다 "텍스트 표현"입니다. 바이트 12개가 각각 몇 글자가 되는지 계산하고, 왜 base64가 전송 효율에서 유리한지 답해 보세요.
문제 2. 단일 바이트 XOR 해독에서 "출력 불가 문자 페널티(-5)"가 없으면 어떤 오류가 생기나요? 틀린 키가 높은 점수를 받는 시나리오를 설명해 보세요.
문제 3. 반복키 XOR의 키 길이 추정에서 정규화(hamming / ks)를 하지 않으면 어떤 방향으로 오판하나요? 3-5의 수치를 근거로 설명해 보세요.
문제 4. ECB의 "같은 블록 = 같은 암호문" 성질이 왜 발생하는지, 블록 암호의 정의(고정 키 아래 블록 단위 치환)에서 설명해 보세요. 그리고 이 성질 하나로 공격자가 평문 없이 알 수 있는 것을 한 가지 답해 보세요.
5. 모범 답안과 완료 기준
미션 모범 답안
핵심은 함수 반환값의 통일입니다 — break_single_xor이 항상 (점수, 키, 평문) 튜플을 반환하면 챌린지 3, 4, 6이 모두 같은 함수 위에서 돌아갑니다.
def detect_ecb_blocks(ct, bs=16):
blocks = [ct[i:i+bs] for i in range(0, len(ct), bs)]
return len(blocks) - len(set(blocks)) # 반복된 블록 수
판정 기준: ① 세 자가 검증이 전부 통과(키를 지워도 복구됨) ② 원본 챌린지 데이터에 같은 함수가 동작 ③ xorlib.py 임포트만으로 재사용 가능할 것. "문제마다 새로 짜는 코드"가 아니라 "모든 문제에 쓰이는 도구상자"가 완성 조건입니다.
검증하는 법: 암호문 생성 코드와 해독 코드를 분리해, 생성에 쓴 키를 해독 쪽에서 보지 않는지 확인하세요. 복구된 키가 생성 키와 우연히 같아지는 것(하드코딩)이 가장 흔한 자기기만입니다.
연습문제 해답
문제 1 해답. 12바이트는 hex로 24글자(바이트당 2글자), base64로 16글자(3바이트당 4글자)입니다. base64는 바이트당 4/3글자라 hex의 2글자보다 33% 짧습니다 — 텍스트 채널에서 대역을 덜 씁니다. 대신 직접 계산은 못 하니, 둘 다 계산 전에 bytes로 되돌리는 전처리일 뿐입니다.
문제 2 해답. 틀린 키로 XOR하면 평문의 공백(0x20) 같은 바이트가 제어 문자(0x00~0x1F)로 바뀌는 경우가 많습니다. 페널티가 없으면 이들이 0점이라, 우연히 흔한 글자가 몇 개 나온 틀린 키가 정답을 이길 수 있습니다. 실측의 점수 함수에서 페널티 항을 빼면 짧은 문장에서 오답률이 눈에 띄게 올라갑니다 — 점수 함수는 "영어에 가산점"이 아니라 "비영어에 감점"이 본질입니다.
문제 3 해답. 정규화가 없으면 해밍 거리는 블록 길이에 대략 비례해 커지므로, 긴 키 길이일수록 원시 거리가 큽니다. 즉 짧은 키 길이(2, 3)가 실제 정답과 무관하게 유리해지는 방향으로 오판합니다. 3-5에서 ks=3의 정규화 거리는 2.27로 영어 통계 범위(2~3)에 있고, 이 값이 후보들 사이에서 최소였습니다.
문제 4 해답. 블록 암호는 고정된 키 아래 16바이트 블록을 16바이트 블록으로 치환하는 결정론적 함수입니다. ECB는 각 블록을 독립적으로 이 함수에 넣으므로, 입력 블록이 같으면 출력 블록도 필연적으로 같습니다. 공격자는 평문을 몰라도 "평문의 어디가 반복되는지" — 구조와 패턴을 알 수 있습니다. 이것이 이미지 윤곽 유출(다음 챕터의 펭귄 실험)과 바이트 앳 어 타임 공격의 뿌리입니다.
완료 기준 체크리스트
- [ ] hex/bytes/base64 변환 세 줄을 외워 쓸 수 있다
- [ ] 해밍 거리 구현이 검증 벡터 37을 통과했다
- [ ] 점수 함수로 단일 바이트 XOR을 키 없이 해독했다
- [ ] 여러 줄에서 암호문 줄을 자동 탐지했다
- [ ] 정규화 해밍 거리로 키 길이를 추정하고 열 분리로 반복키를 복구했다
- [ ] AES-ECB 복호화를 pycryptodome으로 수행했다
- [ ] 반복 블록 수로 ECB 암호문을 식별했다
- [ ] 미션: xorlib.py 완성 + 원본 Set 1 데이터에 적용 성공
6. 흔한 실수와 해결
벽 1. ValueError: non-hexadecimal number found in fromhex() arg at position 0
증상: ValueError: non-hexadecimal number found in fromhex() arg at position 0 (2026-09-09 실측).
원인: hex 문자열에 0~9a-f가 아닌 문자(공백, 줄바꿈, 접두어 0x)가 섞였습니다. 문제 파일을 읽을 때 줄바꿈이 대표적입니다.
해결: .strip()으로 줄바꿈을 제거하고, 파일 전체를 읽을 때는 "".join(f.read().split())로 공백류를 통째로 제거하세요.
벽 2. binascii.Error: Only base64 data is allowed
증상: binascii.Error: Only base64 data is allowed (2026-09-09 실측, validate=True 사용 시).
원인: base64 문자열에 줄바꿈 등이 섞였거나, hex 문자열을 base64 디코더에 넣는 착오입니다. 챌린지 7처럼 파일이 base64 여러 줄인 경우가 대표적입니다.
해결: base64.b64decode("".join(lines))로 줄을 합친 뒤 디코드하세요. hex인지 base64인지 문제 설명을 다시 확인하는 것도 빠릅니다.
벽 3. 점수 함수가 틀린 키를 고른다
증상: 복구 평문이 깨진 문자열인데 점수는 높습니다.
원인: 문장이 짧아 통계가 불안정하거나, 페널티 항이 없어 제어 문자가 무득점으로 통과했습니다(연습문제 2 참조).
해결: 3-3의 세 계층(흔한 글자 +2 / 문자 +1 / 출력 불가 -5)을 유지하고, 짧은 입력에는 상위 3개 후보를 눈으로 비교하세요. 완전 자동보다 "후보 압축 + 인간 판독"이 실전형입니다.
벽 4. 키 길이 추정이 정답의 배수를 고른다
증상: 실제 키가 3인데 6이나 9가 1위로 나옵니다.
원인: 정상입니다 — 키 길이 L의 배수로 잘라도 같은 키 패턴이 반복되므로 거리가 낮게 나옵니다.
해결: 후보 상위 2~3개를 모두 열 분리 공격에 돌리고, 복구된 키가 짧은 주기의 반복(예: ICEICE)이면 앞부분만 취하세요. 3-5처럼 후보 리스트 전체를 보는 습관이 해결책입니다.
벽 5. pip install pycryptodome인데 import crypto가 된다/안 된다
증상: 설치했는데 ModuleNotFoundError: No module named 'Crypto'.
원인: 패키지명은 pycryptodome, 임포트명은 Crypto(대문자)입니다. 예전 pycrypto와 충돌하면 임포트가 꼬입니다.
해결: python -m pip install --quiet pycryptodome 후 from Crypto.Cipher import AES로 확인하세요. 구형 pycrypto가 있으면 제거 후 재설치합니다.
7. 정리
오늘의 개념
| 개념 | 한 줄 설명 |
|---|---|
| hex / base64 | bytes의 텍스트 표현 둘 — 계산 전엔 항상 bytes로 |
| 해밍 거리 | 다른 비트의 개수 — 키 길이 추정의 자 등 |
| 빈도 분석 | 영어 통계(etaoin)로 256 후보 자동 채점 |
| 반복키 XOR 분해 | 키 길이 추정(정규화 해밍) → 열 분리 → 열별 단일키 |
| ECB 반복 탐지 | 같은 평문 블록 = 같은 암호문 블록 — 고유 블록 수 비교 |
오늘의 명령어·코드
| 명령 | 하는 일 |
|---|---|
bytes.fromhex(s) / b.hex() |
hex ↔ bytes |
base64.b64encode(b) / b64decode(s) |
base64 ↔ bytes |
bin(x ^ y).count("1") |
비트 차이 — 해밍 거리의 원자 |
ct[col::ks] |
반복키 XOR의 col번째 열 추출 |
AES.new(key, AES.MODE_ECB) |
ECB 모드 AES(학습용) |
len(set(blocks)) < len(blocks) |
ECB 반복 블록 탐지 |
명령어보다 중요한 감각
Set 1의 진짜 완주품은 코드가 아니라 점수 함수입니다 — "정답이 어떻게 생겼는지를 수치로 표현하는 능력"이 모든 고전 암호 공격의 엔진입니다. 그리고 마지막 두 문제가 남긴 것, "같은 블록은 같은 암호문"이라는 ECB의 결함이 다음 챕터의 시작입니다. 오늘 만든 xorlib.py는 버리지 마세요 — Set 2에서 그대로 이어집니다.
전부 체크되면 Step 231 완료입니다. 사이드바의 체크박스를 눌러 진도를 저장하세요.