Step 235. DH 키 교환과 MITM 시뮬레이션 — 도청당하는 채널에서 비밀을 만드는 법, 그리고 그 한계

Level 3 — CTF 실전과 공격 스킬 심화 | 난이도 ★★★☆☆ | 예상 소요 시간 4시간

전제: Step 227(암호 수학 기초)의 pow(a, b, n). 그 한 줄이 오늘 챕터의 전부입니다.

⚠️ 이 챕터의 실습은 내 랩·합법 플랫폼 전용입니다. 허가 없는 시스템에 적용하면 범죄입니다.

준비물: 파이썬 3(실측: 3.12.14), 종이와 펜(Alice·Eve·Bob 3열 표용).
주의: 오늘 실습은 100% 안전합니다. 네트워크 없이 내 컴퓨터 안에서 역할극만 합니다.

지금까지의 암호(대칭키)에는 치명적인 선행 문제가 있었습니다 — 키를 먼저 어떻게 나누는가? 디피-헬먼(Diffie-Hellman) 키 교환은 그 문제를 수학으로 해결합니다: 도청당하는 채널에서 공개값만 주고받고도, 두 사람만 아는 공통 비밀이 생깁니다. 그런데 이 마법에는 조건이 하나 빠져 있습니다 — "상대가 진짜 그 사람인가?"라는 인증입니다. 오늘은 DH를 직접 구현하고, 중간자 공격(MITM)이 왜 성립하는지 시뮬레이션으로 증명합니다.

1. 학습 목표

이 챕터를 끝내면 다음을 할 수 있습니다:

DH 키 교환의 절차(g^a mod p 교환 → g^ab mod p 공유)를 코드로 구현한다
이산 대수 문제가 DH의 안전성 근거임을 설명한다
작은 p에서 전수 탐색으로 DH가 깨짐을 실측한다
MITM 시나리오에서 중간자가 양쪽과 각각 키를 공유하는 구조를 시뮬레이션한다
"키 교환"과 "인증"이 왜 분리된 문제인지, TLS가 둘을 어떻게 묶는지 말할 수 있다

2. 배경 지식 — 오늘의 도구와 개념

오늘의 도구 한눈에 보기

구분	내용
언어·환경	파이썬 3 (실측: 3.12.14) — 표준 라이브러리만, 설치 없음
오늘의 명령어	`pow(g, a, p)`, 전수 탐색 루프, 간단한 XOR 암호(메시지 시연용)
필요한 개념	이산 대수 문제, 공개값/비밀 지수, 공유 비밀, MITM, 인증
오늘의 산출물	DH 구현 코드 + 작은 p 공격 출력 + MITM 시뮬레이션 출력

2-1. DH의 절차 — 다섯 줄의 마법

절차는 이것이 전부입니다. Alice와 Bob이 공개 파라미터 소수 p와 생성원 g에 합의한 뒤:

Alice: 비밀 a 선택 → A = g^a mod p 를 공개
Bob:   비밀 b 선택 → B = g^b mod p 를 공개
Alice는 B^a mod p 계산, Bob은 A^b mod p 계산
둘의 결과 = g^(ab) mod p 로 동일 → 이것이 공유 비밀

도청자는 p, g, A, B를 전부 봅니다. 그런데 공유 비밀을 만들려면 a나 b가 필요하고, A에서 a를 복구하는 문제가 바로 이산 대수 문제(discrete logarithm problem) — g^a mod p는 빠르게 계산되지만 그 역은 큰 p에서 사실상 불가능합니다.

2-2. 이산 대수 문제 — 가기는 쉽고 돌아오기는 어렵다

Step 227에서 pow(a, b, n)이 빠른 이유를 봤습니다. 방향을 바꾸면 이야기가 달라집니다 — "A = g^a mod p이고 g, A, p를 안다. a는?"에 대한 범용 고속 알고리즘이 없습니다. p가 2048비트면 전수 탐색은 우주 나이로도 부족합니다.

단, 전제가 있습니다 — p가 충분히 커야 한다는 것. 오늘 실습용 p = 23에서는 이산 대수가 전수 탐색 몇 줄로 깨집니다. 이것이 실전 공격(로그잼 등)의 씨앗이기도 합니다 — 약한 파라미터 협상을 강제하는 공격이 실제로 있었습니다.

2-3. MITM — "누구와 키를 교환했는가"라는 빈자리

DH는 도청에는 강하지만 중계에는 무방비입니다. Eve가 통신 중간에 앉아 Alice에게는 Bob인 척, Bob에게는 Alice인 척하면:

Alice ⇄ Eve : 공유 비밀 s1 (Alice는 Bob과 공유했다고 믿음)
Eve   ⇄ Bob : 공유 비밀 s2 (Bob은 Alice와 공유했다고 믿음)

이후 Alice가 보내는 암호문은 s1으로 암호화되니 Eve가 읽고, s2로 재암호화해 Bob에게 전달하면 — 양쪽 다 정상 대화로 인식합니다. DH 자체는 정상 작동했습니다. 무너진 것은 인증의 부재입니다. 이것이 TLS가 키 교환에 인증서와 서명을 반드시 묶는 이유입니다.

3. 따라 하기

이 챕터의 모든 출력은 2026-09-09 파이썬 3.12.14 실측입니다.

3-1. DH 구현 — 공유 비밀이 일치하는가

p, g = 23, 5            # 실습용 작은 파라미터 (실전은 2048비트 이상)
a, b = 6, 15            # Alice와 Bob의 비밀 지수
A = pow(g, a, p)        # Alice 공개값
B = pow(g, b, p)        # Bob 공개값
s_alice = pow(B, a, p)  # B^a = g^(ab) mod p
s_bob   = pow(A, b, p)  # A^b = g^(ab) mod p
print(f"Alice: a={a} -> 공개 A = {A}")
print(f"Bob  : b={b} -> 공개 B = {B}")
print(f"Alice의 공유 비밀 = {s_alice}")
print(f"Bob  의 공유 비밀 = {s_bob}")
print("일치 여부:", s_alice == s_bob)

Alice: a=6 -> 공개 A = 8
Bob  : b=15 -> 공개 B = 19
Alice의 공유 비밀 = 2
Bob  의 공유 비밀 = 2
일치 여부: True

출력 읽는 법: Alice는 b를 모르고, Bob은 a를 모릅니다. 그런데 둘 다 2에 도달했습니다 — B^a = (g^b)^a = g^(ab) = (g^a)^b = A^b (mod p)이기 때문입니다. 채널을 지난 것은 8과 19뿐입니다.

3-2. 도청자 관점 — 그리고 작은 p의 비극

Eve는 p=23, g=5, A=8, B=19를 봤습니다. p가 작으니 전수 탐색이 됩니다:

for x in range(1, 23):
    if pow(5, x, 23) == 8:
        print("Alice의 비밀 a =", x)   # A = g^a mod p 를 만족하는 x
        break
print("Eve의 공유 비밀:", pow(19, x, 23))

Alice의 비밀 a = 6
Eve의 공유 비밀: 2

읽는 법: 22번 안에 끝났습니다. p가 작다는 것 하나로 DH의 모든 보장이 사라집니다. 반면 127비트 소수(2**127 - 1)로 같은 계산을 하면 공개값은 정상 계산되지만, 전수 탐색은 최대 약 1.7×10³⁸ 회 — 초당 10억 회를 돌려도 우주 나이의 수십억 배입니다. 실전 파라미터(2048비트)가 왜 필요한지가 이 대비입니다.

3-3. MITM 시뮬레이션 — Eve의 이중 키 교환

이제 Eve가 중간에 앉습니다. Eve도 자기 비밀 지수 e = 13을 만들고, 양쪽의 공개값을 자기 것 E = 21로 바꿔치기합니다.

e = 13
E = pow(g, e, p)          # Eve의 공개값
s_ae = pow(E, a, p)       # Alice가 믿는 공유 비밀 (Eve와의 키)
s_ea = pow(A, e, p)       # Eve가 Alice와 공유하는 비밀
s_be = pow(E, b, p)       # Bob이 믿는 공유 비밀 (Eve와의 키)
s_eb = pow(B, e, p)       # Eve가 Bob과 공유하는 비밀
print(f"Alice 쪽: {s_ae} == {s_ea} -> {s_ae == s_ea}")
print(f"Bob   쪽: {s_be} == {s_eb} -> {s_be == s_eb}")
print(f"Alice 키와 Bob 키가 같은가? {s_ae == s_be}")

Alice 쪽: 18 == 18 -> True
Bob   쪽: 7 == 7 -> True
Alice 키와 Bob 키가 같은가? False

출력 읽는 법: 세 줄이 이 시나리오의 전부입니다. Alice와 Bob은 서로 다른 키(18과 7)를 쥐고 있고, 각각의 키는 둘 다 Eve와 공유된 것입니다. DH는 두 번 다 완벽하게 성공했습니다 — 잘못된 상대와.

3-4. Eve가 대화를 읽고 중계한다

공유 비밀을 간단한 XOR 암호 키로 써서 시연합니다:

def xor_msg(msg, key):
    return bytes(c ^ (key % 256) for c in msg)

plain = b"meet at 9pm"
c1 = xor_msg(plain, s_ae)          # Alice -> Eve 방향 암호문
read = xor_msg(c1, s_ea)           # Eve가 복호화해 읽는다
c2 = xor_msg(read, s_eb)           # Eve가 Bob용 키로 재암호화
print("Alice가 보낸 암호문:", c1.hex())
print("Eve가 읽은 평문:", read)
print("Bob이 받은 평문:", xor_msg(c2, s_be))

Alice가 보낸 암호문: 7f777766327366322b627f
Eve가 읽은 평문: b'meet at 9pm'
Bob이 받은 평문: b'meet at 9pm'

읽는 법: Bob은 정확한 메시지를 받았으므로 이상을 느낄 수 없습니다. Eve는 읽는 것뿐 아니라 내용을 바꿔 중계할 수도 있습니다 — "meet at 9pm"을 "meet at 3am"으로. 키 교환이 성공했다는 사실이 아무것도 보장하지 않는다는 것이 오늘의 핵심 데이터입니다.

3-5. 방어 — 인증된 키 교환

빈자리를 메우는 것은 전자서명입니다. Alice가 자기 공개값 A에 개인키로 서명해내면, Eve의 위조값 E에는 Alice의 서명을 만들 수 없으므로 Bob이 검증 단계에서 걸러냅니다. TLS가 DH 계열 키 교환(ECDHE)에 인증서·서명을 묶는 이유가 정확히 이것입니다 — 키 교환은 비밀을 만들고, 인증은 상대를 확인하고, 둘이 만나야 비로소 안전한 채널입니다.

4. 미션과 연습문제

미션 — 3자 역할극 완성

Alice, Bob, Eve를 각각의 코드 블록으로 분리해 MITM 시나리오 전체를 재현합니다 — 파라미터는 p=23, g=5, 각자의 비밀 지수는 자유 선택
Eve가 Alice의 메시지를 변조해 Bob에게 전달하는 단계를 추가합니다 (읽기만이 아니라 바꿔치기)
종이에 "Alice가 아는 것 / Eve가 아는 것 / Bob이 아는 것" 3열 표를 그리고, 각 공개값·공유 비밀이 어느 칸에 속하는지 배치합니다
마지막에 "서명을 붙였다면 어느 단계에서 공격이 끊기는가"를 표에 표시합니다

연습문제

문제 1. DH에서 도청자가 보는 네 값(p, g, A, B)을 적고, 공유 비밀 계산에 추가로 필요한 것이 무엇인지 답해 보세요.

문제 2. p=23, g=5에서 Bob의 공개값이 B=4였습니다. b를 전수 탐색으로 찾아 보세요 (코드 또는 손계산).

문제 3. MITM 공격에서 Alice와 Bob의 공유 비밀이 서로 다른데도(18 vs 7) 대화가 성립하는 이유를 설명해 보세요.

문제 4. "DH는 안전하므로 인증 없이 써도 된다"는 주장을 오늘 실측 결과를 인용해 반박해 보세요.

5. 모범 답안과 완료 기준

미션 모범 답안

역할 분리의 골격입니다 (3-3, 3-4 실측 코드의 재배열):

# --- Alice ---
a = 6; A = pow(g, a, p)
# --- Eve (중간에서 A를 가로채고 E로 바꿔치기) ---
e = 13; E = pow(g, e, p)
# --- Bob ---
b = 15; B = pow(g, b, p)

s_A = pow(E, a, p)    # Alice: Bob인 줄 알고 E를 받음
s_E_with_A = pow(A, e, p)
s_B = pow(E, b, p)    # Bob: Alice인 줄 알고 E를 받음
s_E_with_B = pow(B, e, p)

# 변조 시연
read = xor_msg(xor_msg(b"meet at 9pm", s_A), s_E_with_A)
forged = b"meet at 3am"
bob_gets = xor_msg(xor_msg(forged, s_E_with_B), s_B)
print("Eve가 읽음:", read, "/ Bob이 받음:", bob_gets)

Eve가 읽음: b'meet at 9pm' / Bob이 받음: b'meet at 3am'

검증하는 법: ① 양쪽 키 교환이 각각 성립하는가 (s_A == s_E_with_A, s_B == s_E_with_B). ② Alice 키 ≠ Bob 키인가. ③ 변조 후 Bob이 받은 평문이 원문과 다른가. ④ 3열 표에서 각 값의 소유자가 정확한가 — 특히 s_A는 Alice와 Eve 칸에만 있어야 합니다. 서명 방어 표시는 "E가 E인 채로는 Alice의 서명을 못 만든다 → Bob의 검증 실패" 지점입니다.

연습문제 해답

문제 1 해답. 도청자는 p, g, A, B를 봅니다. 공유 비밀 g^(ab) mod p를 만들려면 Alice의 비밀 a 또는 Bob의 비밀 b가 추가로 필요합니다 — 둘 다 채널에 나타나지 않으며, A에서 a를 구하는 것이 이산 대수 문제입니다.

문제 2 해답. pow(5, x, 23)을 x = 1부터 계산하면 5, 2, 10, 4 — x = 4에서 4가 나옵니다. 즉 b = 4입니다 (실측 확인 가능: pow(5, 4, 23) == 4).

문제 3 해답. 대화의 양 끝이 서로 직접 통신하는 것이 아니라 둘 다 Eve와 통신하기 때문입니다. Alice→Eve 구간은 키 18, Eve→Bob 구간은 키 7로 각각 정상 암호화되고, Eve가 중간에서 복호화·재암호화하며 이어 주므로 양쪽에는 "정상 대화"로 보입니다.

문제 4 해답. 3-3에서 DH는 두 번 다 수학적으로 정상 성공했고(각 쌍의 공유 비밀 일치), 그럼에도 3-4에서 대화 내용이 전부 노출·변조됐습니다. "키 교환이 성공했다"와 "올바른 상대와 교환했다"는 다른 명제이며, DH는 전자만 보장합니다. 후자는 인증(서명)의 영역입니다 — 그래서 실전 프로토콜(TLS)은 둘을 항상 묶습니다.

완료 기준 체크리스트

[ ] DH 절차 다섯 줄을 코드로 구현해 공유 비밀 일치를 확인했다
[ ] 이산 대수 문제가 DH 안전성의 근거임을 설명할 수 있다
[ ] 작은 p에서 전수 탐색으로 비밀 지수를 복구했다
[ ] p가 커지면 전수 탐색이 왜 불가능한지 수량 감각으로 말할 수 있다
[ ] MITM 시뮬레이션에서 양쪽 키가 다른 것을 출력으로 확인했다
[ ] Eve의 읽기·변조 중계를 재현했다
[ ] 미션: 3열 표 + 변조 단계 + 서명 차단 지점 표시 완료

6. 흔한 실수와 해결

벽 1. 공유 비밀이 서로 안 맞는다 (일반 DH)

증상: pow(B, a, p) != pow(A, b, p).
원인: 공개값 계산에서 mod를 빼먹거나(g**a로 큰 수를 만든 뒤 % p는 되지만 순서 실수가 흔함), A와 B를 뒤바꿔 대입한 경우.
해결: 항상 세 개짜리 pow(g, a, p)를 쓰고, Alice는 "상대 공개값 ^ 내 비밀"이라는 문장으로 대입을 점검하세요.

벽 2. MITM인데 키가 하나만 나온다

증상: 시뮬레이션인데 Alice와 Bob의 키가 같습니다.
원인: Eve가 바꿔치기하지 않고 A, B를 그대로 전달하게 코딩한 경우 — 그것은 MITM이 아니라 도청입니다.
해결: Eve는 자기 공개값 E를 양쪽에 보내야 합니다. "Alice가 받는 값은 B가 아니라 E"인지 코드에서 확인하세요.

벽 3. 전수 탐색이 안 끝난다

증상: 이산 대수 복구 코드가 몇 분째 돌아갑니다.
원인: p를 크게 잡은 채 range(1, p)로 돌린 경우. 127비트 p면 영원히 안 끝납니다.
해결: 실습용 p는 1000 이하로. 큰 p는 "계산은 되지만 역산은 안 된다"를 보여 주는 시연에만 쓰세요.

벽 4. XOR 암호 키가 바이트 범위를 넘는다

증상: ValueError: bytes must be in range(0, 256) (키를 그대로 XOR에 쓴 경우).
원인: 공유 비밀 s는 mod p의 값이라 p가 크면 256을 넘습니다.
해결: 시연용으로는 key % 256으로 접고, 실제로는 공유 비밀을 해시(KDF)해 키를 만드는 것이 표준입니다 — 그 절차까지가 TLS의 "키 유도"입니다.

벽 5. 역할이 헷갈려 코드가 꼬인다

증상: 누가 어떤 값을 아는지 코드에서 섞입니다.
원인: DH MITM은 수학보다 역할 관리가 어렵습니다 — 원문 가이드가 지적한 그대로입니다.
해결: 코드 전에 종이에 Alice/Eve/Bob 3열 표를 그리고, 값이 나올 때마다 "아는 사람" 칸에 적으세요. 코드는 그 표의 사본입니다.

7. 정리

오늘의 개념

개념	한 줄 설명
DH 키 교환	공개값 `g^a mod p` 교환으로 도청 채널 위에서 공통 비밀 생성
이산 대수 문제	`g^a mod p`의 역산 — DH 안전성의 수학적 근거
공유 비밀	`g^(ab) mod p` — 양쪽만 도달하고 채널에는 나타나지 않는 값
파라미터 취약성	p가 작으면 이산 대수가 전수 탐색으로 깨짐
MITM	중간자가 양쪽과 각각 키 교환 — 인증 부재가 만드는 구멍
인증된 키 교환	DH + 서명(인증서) — TLS가 둘을 묶는 이유

오늘의 명령어·코드

명령	하는 일
`pow(g, a, p)`	공개값 계산 — DH의 기본 연산
`pow(B, a, p)`	상대 공개값으로 공유 비밀 계산
전수 탐색 루프	작은 p에서 이산 대수 풀기 (공격 시연용)
`bytes(c ^ (key % 256) for c in msg)`	시연용 XOR 암호 (실전 암호 아님)

명령어보다 중요한 감각

DH는 "비밀을 만드는 문제"를 풀었지만 "상대를 확인하는 문제"는 남겼습니다. 오늘 시뮬레이션의 세 출력 — 양쪽 키 교환 성공(True, True), 두 키의 불일치(False), 그리고 Eve가 읽은 평문 — 은 그 빈자리가 얼마나 치명적인지를 보여 줍니다. 암호 시스템을 평가할 때 "키 교환이 성공하는가" 다음에 반드시 물으세요 — "그런데 누구와?"

전부 체크되면 Step 235 완료입니다. 사이드바의 체크박스를 눌러 진도를 저장하세요.