DES를 직접 구현하면서 부품을 망가뜨려보기 — '왜 16라운드인가'

암호 알고리즘 강의에서 DES를 배우면 보통 “16라운드”, “S-box 8개”, “Feistel 구조”라는 사실을 외운다. 외우긴 외우는데 — 왜 그래야 하는가는 안 외운다.

직접 만든 다음에 부품을 하나씩 망가뜨리면 보인다.

---

DES 사양 한 장 정리

항목	값
블록 크기	64 bit
키 크기 (명목)	64 bit
키 크기 (실효)	56 bit (8 bit는 패리티)
라운드 수	16
라운드 키	48 bit (PC-2 압축 출력)
S-box	8개, 각각 6 bit 입력 → 4 bit 출력
구조	Feistel

---

직접 구현

def des_encrypt(plaintext_64: bytes, key_64: bytes) -> bytes:
    # 1) IP (Initial Permutation)
    block = permute(plaintext_64, IP_TABLE)

    # 2) 키 스케줄: 56-bit → 16개 48-bit 라운드 키
    round_keys = key_schedule(key_64)

    # 3) 16 라운드 Feistel
    L, R = block[:32], block[32:]
    for k in round_keys:
        L, R = R, xor(L, f_function(R, k))

    # 4) 좌우 스왑 후 FP (Final Permutation)
    return permute(R + L, FP_TABLE)


def f_function(R32: bits, k48: bits) -> bits:
    # R(32) → 48 (Expansion E-box) → XOR 라운드 키 → S-box 8개 → P-box
    expanded = permute(R32, E_TABLE)        # 48 bit
    xored    = xor(expanded, k48)           # 48 bit
    s_out    = sbox_substitute(xored)       # 32 bit (6 → 4 ×8)
    return permute(s_out, P_TABLE)          # 32 bit

전체 구현은 ~250줄. 테이블(IP/FP/E/P/S-box 8개) 박는 게 제일 귀찮다.

---

실험 1 — 라운드를 줄이면?

Avalanche 효과: 평문 1비트가 바뀌면 암호문은 평균 50%(=32비트) 가량 바뀌어야 한다.

def avalanche(rounds: int, n: int = 1000):
    bits_changed = []
    for _ in range(n):
        p1 = random_64()
        p2 = flip_one_bit(p1, random_position())
        c1 = des_encrypt_n_rounds(p1, KEY, rounds)
        c2 = des_encrypt_n_rounds(p2, KEY, rounds)
        bits_changed.append(hamming(c1, c2))
    return mean(bits_changed)

라운드	평균 비트 변화 (이상값 32)
1	~6
2	~13
4	~22
8	~31
16	~32 ✓

8라운드면 거의 도달한다. 16라운드는 여유로 두는 마진이라기보다, 차분/선형 분석에 대한 안전 계수다. 1990년대 차분 공격이 2^47 chosen plaintext로 16라운드를 깰 수 있음이 알려졌으니, 사실 16라운드도 빠듯하다.

---

실험 2 — S-box를 항등함수로 바꾸면?

S-box는 DES의 유일한 비선형 구성요소다. 나머지(permutation, XOR, expansion)는 전부 선형.

# 정상 S-box 대신 입력의 lower 4 bits를 그대로 출력
def identity_sbox(input_6bits):
    return input_6bits & 0xF

이렇게 바꿔서 동일한 Avalanche 측정:

구성	16-round Avalanche
정상 S-box	~32 ✓
항등 S-box	~32 (겉으론 같음)

겉으론 비슷하다. 그런데 선형 공격 가능 여부를 확인하면:

# 선형 근사 식: input bits XOR == output bits XOR 의 확률을 1000개 샘플로 측정
def linear_bias(rounds):
    matches = 0
    for _ in range(1000):
        p, k = random_64(), KEY
        c = des_encrypt_n_rounds(p, k, rounds)
        if (p[5] ^ p[12]) == (c[3] ^ c[18]):  # 임의 비트 조합
            matches += 1
    return matches / 1000  # 0.5에 가까울수록 안전

구성	1라운드 bias	16라운드 bias
정상 S-box	0.51	0.50
항등 S-box	0.95	0.78

S-box를 항등으로 바꾸면 1라운드에서 거의 100% 예측 가능. 16라운드 누적 후에도 0.78로 충분히 깨짐. S-box가 비선형성의 유일한 출처임이 수치로 나온다.

---

실험 3 — IP/FP를 빼면?

Initial Permutation과 Final Permutation은 보안에 기여 안 한다는 게 정설이다. 직접 빼보면:

def des_no_ip_fp(p, k):
    # IP 생략, 라운드 진행, FP 생략
    L, R = p[:32], p[32:]
    for rk in key_schedule(k):
        L, R = R, xor(L, f_function(R, rk))
    return R + L  # 좌우 스왑만

같은 키/평문에 대한 차이:

구성	같은 키/평문에서 결과
정상 DES	c4 a3 7d ...
IP/FP 없음	1c b2 e5 ... (다른 비트지만)

둘 다 동일한 보안 강도다 (Avalanche, 선형 bias 동일). IP/FP가 들어간 이유는 하드웨어 회로 효율 — 70년대 IBM이 칩 배선을 단순화하려고 넣은 것이지 보안과 무관하다.

DES 시험에서 “IP는 왜 있나?” 물어보면 하드웨어 배선용이라고 답하면 된다. 보안 아니다.

---

실험 4 — 취약 키 (Weak Key)

DES에는 64개의 weak/semi-weak 키가 있다. 이 키들로 두 번 암호화하면 평문이 그대로 복원된다.

weak keys:
  0x0101010101010101
  0x1F1F1F1F0E0E0E0E
  0xE0E0E0E0F1F1F1F1
  0xFEFEFEFEFEFEFEFE

WEAK = bytes.fromhex('0101010101010101')
plaintext = b'helloDES'
c1 = des_encrypt(plaintext, WEAK)
c2 = des_encrypt(c1,        WEAK)
assert c2 == plaintext  # E(E(P)) == P

원인: 키 스케줄이 weak key에서 모든 라운드 키가 동일하게 되거나, 16라운드 키가 회문 패턴이 된다. 그래서 두 번 암호화하면 자기 자신이 역함수가 됨.

실무적 영향은 작지만 (2^56 키 공간에서 64개), 자체 구현하면 키 검증 단계에서 reject 해야 한다.

---

만들면서 알게 된 것들

S-box가 모든 것이다. 나머지 부품을 다 빼도 보안은 일부 유지되지만, S-box를 비선형이 아닌 걸로 바꾸면 즉시 무너진다.

16라운드는 마진이 아니라 빠듯한 수치. 차분 공격이 2^47이면 8라운드는 일상적 컴퓨터로 깬다. 16이 적당히 안전한 최소치.

IP/FP는 보안이 아닌 배선 편의. 70년대 하드웨어 컨텍스트가 알고리즘에 박혀 있다.

키 스케줄도 직접 짜봐야 weak key의 의미가 와닿는다. “왜 64개?”는 PC-1/PC-2 테이블 직접 다뤄야 보임.

---

한 줄 결론

알고리즘은 부품을 빼봐야 비로소 이해된다. 이 알고리즘이 왜 안전한가는 이 부품을 빼면 어떻게 깨지는가를 통해서만 보인다.