Double-DES Meet-in-the-Middle — 왜 2DES가 아니라 3DES인가

DES 키가 56bit라 깨질 위험이 있으면 두 번 암호화하면 되지 않을까?

C = E_{K2}(E_{K1}(P))

키가 두 개면 112bit, 부르트포스 2^112 = 5×10^33 — 비현실적.

이 직관이 틀렸다. 실제 공격 비용은 2^57, 단일 DES보다 약간 높을 뿐.

---

Meet-in-the-Middle 공격

공격자가 plaintext-ciphertext 쌍 (P, C) 하나를 안다고 가정 (KPA).

목표: K1, K2를 찾기.

방법

중간값 M = E_{K1}(P) = D_{K2}(C)

이 등식을 양쪽에서 짠다.

Step 1: 모든 가능한 K1에 대해 M_i = E_{K1_i}(P) 계산. 2^56개 (M, K1) 쌍을 테이블에 저장.

Step 2: 모든 가능한 K2에 대해 M_j = D_{K2_j}(C) 계산. 매 결과에 대해 테이블 조회.

Step 3: 같은 M이 양쪽에 있으면 후보 (K1, K2). 확인용 두 번째 (P’, C’)로 검증.

비용

• 시간: 2^56 + 2^56 ≈ 2^57 (단일 DES와 같은 차원)
• 메모리: 2^56 × (8+7) byte ≈ 1 EB (실제론 못 함)

메모리가 진짜 병목이지만, 메모리 크기를 줄인 변형(Oechslin’s rainbow table 류)으로 시간/메모리 트레이드오프 가능.

핵심: 2DES는 부르트포스보다 메모리만 더 들지, 시간은 거의 같다. 키 두 배가 보안 두 배가 아니다.

---

미니어처 시연 (16bit 키)

실제 56bit는 못 돌리니 16bit DES (가상의 작은 블록 암호)로 시연.

def mini_encrypt(p: int, k: int) -> int:
    # 16bit 평문, 16bit 키, 단순 Feistel 4라운드
    L, R = (p >> 8) & 0xFF, p & 0xFF
    for i in range(4):
        rk = (k >> (i*4)) & 0xFFFF  # 4bit 슬라이딩
        L, R = R, L ^ ((R + rk) & 0xFF)
    return (L << 8) | R

# Double encryption
def double_enc(p, k1, k2):
    return mini_encrypt(mini_encrypt(p, k1), k2)

알려진 (P, C) 한 쌍으로 MITM:

P = 0x1234
C = double_enc(P, REAL_K1, REAL_K2)  # 가정

# Step 1: K1 후보 모두 → M_i 테이블
mid_table = {}
for k1 in range(0x10000):
    m = mini_encrypt(P, k1)
    mid_table.setdefault(m, []).append(k1)

# Step 2: K2 후보 모두 → 테이블 조회
candidates = []
for k2 in range(0x10000):
    m = mini_decrypt(C, k2)
    if m in mid_table:
        for k1 in mid_table[m]:
            candidates.append((k1, k2))

print(f"후보 {len(candidates)}개 (false positive 포함)")

16bit 키 두 개 → 단순 부르트포스 2^32 = 약 40억. MITM은 2^17 (16384 + 16384) = 약 13만번. 17만 배 빠르다.

---

그래서 3DES

3DES는 같은 공격을 회피한다.

C = E_{K3}(D_{K2}(E_{K1}(P)))

키 3개. MITM 적용하려면 좌우 어느 쪽이든 2개 키를 한꺼번에 처리해야 하므로:

• 시간: 2^112
• 실효 보안: 112bit (2-key 3DES) 또는 168bit (3-key 3DES)

가운데 D를 쓰는 이유: K1=K2=K3이면 단일 DES와 동일하게 동작 → 하위 호환성. 그 외엔 진짜 3중.

---

그러면 더 안전하지 않나? — Sweet32

3DES도 블록 크기 64bit 때문에 2016년 TLS에서 deprecated. 키 길이를 늘려도 블록 크기가 작으면 다른 길로 무너진다.

AES가 등장한 직후 3DES는 사실상 사양길로. 다만 아직도 일부 레거시 시스템(은행 ATM, 일부 임베디드)에 남아 있다.

---

만들면서 알게 된 것들

키 길이는 직선이 아니다. “키 두 배 = 보안 두 배”가 직관적이지만 MITM이 그 직관을 부순다. 블록 암호의 보안 비용은 항상 시간과 메모리의 곱으로 봐야 한다.

Storage 공격은 실제 위협. 1990년대엔 2^56 메모리가 농담이었지만 지금은 클라우드 빌리면 의외로 가능. 메모리 비용이 떨어지면 옛날 안전했던 알고리즘이 깨진다.

3DES의 D는 보안이 아니라 호환성. 시험에 자주 나오는 trivia. “왜 가운데가 D인가” → “K1=K2=K3일 때 단일 DES와 같게 만들기 위해”. 보안 강도와 무관.

미니어처 시연은 항상 통한다. 16bit 키로 56bit 알고리즘의 본질을 보일 수 있다. 학습 도구로 강력.

---

한 줄 결론

알고리즘	키 명목	키 실효	MITM 후 비용	블록
DES	56	56	2^56 (해당 없음)	64
2DES	112	112	2^57	64
3DES (3-key)	168	168	2^112	64
AES-128	128	128	2^128	128

키를 그냥 늘리지 마라. 보안 모델 자체를 바꿔야 한다.