0x03. 대칭키 암호화: DES, AES, 그리고 운용 모드

대칭키 암호화(Symmetric Key Cryptography)는 암호화와 복호화에 동일한 키를 사용하는 방식이다. 빠르고 효율적이어서 대용량 데이터 암호화에 널리 쓰인다.

이 글에서는 대칭키 암호의 구성요소, 대표 알고리즘인 DES와 AES, 그리고 다양한 운용 모드를 다룬다.

암호 알고리즘의 타입과 모드

암호화 알고리즘은 **타입(Type)**과 모드(Mode) 두 가지 측면으로 구분된다.

알고리즘 타입: 한 번에 암호화할 평문의 크기를 결정
알고리즘 모드: 타입이 정해진 후, 암호화의 세부 동작 방식을 결정

알고리즘 타입

스트림 암호 (Stream Cipher)

비트 단위로 암호화/복호화를 수행한다. 평문을 한 비트씩 처리하는 방식이다.

블록 암호 (Block Cipher)

블록 단위로 암호화/복호화를 수행한다. 일정 크기의 비트 블록을 한 번에 처리한다.

알고리즘 모드

알고리즘 모드는 블록 암호에 무작위성을 부여하기 위한 것이다. 모드 없이 블록 암호만 사용하면 동일한 평문 블록이 항상 동일한 암호문 블록으로 변환되어 예측 가능해진다.

주요 모드는 다음과 같다:

ECB (Electronic Code Book)
CBC (Cipher Block Chaining)
CFB (Cipher Feedback)
OFB (Output Feedback)
CTR (Counter)

대칭키 암호의 구성요소

대칭키 암호화는 암호화와 복호화에 동일한 키를 사용한다. 빠르고 효율적이며, 대표적인 알고리즘으로는 DES, AES, IDEA, Blowfish, RC4/5, ChaCha20 등이 있다.

대칭키 블록 암호

대칭키 블록 암호는 n비트 블록의 평문을 암호화하거나 암호문을 복호화한다. 이때 k비트 키를 사용한다.

현대 블록 암호의 구성요소

현대 블록 암호는 보통 P-Box(치환 유닛), S-Box(대체 유닛), 그리고 기타 유닛의 조합으로 구성된다.

예제: n = 64인 블록 암호가 있다고 가정하자. 암호문에 1이 10개 있을 때, Eve가 암호문을 복호화하기 위해 필요한 시도 횟수는?

A. 대체 암호(Substitution cipher)로 설계된 경우
- Eve는 평문에 1이 몇 개인지 알 수 없다. 가능한 모든 2^64개의 64비트 블록을 시도해야 한다.
B. 전치 암호(Transposition cipher)로 설계된 경우
- Eve는 평문에도 정확히 10개의 1이 있다는 것을 안다. 1이 정확히 10개인 64비트 블록만 시도하면 된다.

P-Box (Permutation Box)

P-Box는 문자에 대한 전통적인 전치 암호를 비트 수준에서 구현한 것이다. 비트의 위치를 바꾸는 역할을 한다.

Straight P-Box

입력과 출력의 비트 수가 같다. **n!**개의 가능한 매핑이 존재한다.

Compression P-Box

n개 입력, m개 출력 (m < n). 입력보다 출력이 적다.

Expansion P-Box

n개 입력, m개 출력 (m > n). 입력보다 출력이 많다.

P-Box의 역연산 가능 여부

Straight P-Box는 역연산이 가능하다. 아래 그림은 1차원 테이블로 표현된 순열 테이블을 역변환하는 방법을 보여준다.

Compression P-Box와 Expansion P-Box는 역연산이 불가능하다.

Compression P-Box: 암호화 시 입력이 버려질 수 있어, 복호화 시 해당 비트를 복원할 방법이 없다.
Expansion P-Box: 하나의 입력이 여러 출력에 매핑될 수 있어, 복호화 시 어떤 입력이 어떤 출력에 매핑되었는지 알 수 없다.

단, 일부 암호에서는 암호화에 compression이나 expansion P-Box를 사용하더라도 복호화에서 그 효과가 상쇄되도록 설계한다.

S-Box (Substitution Box)

S-Box는 소형 대체 암호로 볼 수 있다. m x n 대체 유닛으로, m과 n이 반드시 같을 필요는 없다.

예제: 3 x 2 크기의 S-Box. 입력의 가장 왼쪽 비트가 행을, 오른쪽 두 비트가 열을 결정한다.

이 테이블에 따르면, 입력 010은 출력 01을, 입력 101은 출력 00을 생성한다.

S-Box의 역연산 가능 여부

S-Box는 역연산이 가능할 수도, 불가능할 수도 있다. 역연산이 가능하려면 입력 비트 수와 출력 비트 수가 동일해야 한다.

아래는 역연산 가능한 S-Box의 예이다. 왼쪽 박스에 001을 입력하면 101이 출력되고, 오른쪽 테이블에 101을 입력하면 001이 출력되어 서로 역관계임을 알 수 있다.

XOR 연산

XOR(Exclusive-OR) 연산은 가역적이다. 두 번 적용하면 원래 값이 복원되므로, 대부분의 블록 암호에서 중요한 구성요소로 사용된다.

GF(2^n) 필드에서 XOR 연산의 다섯 가지 성질: 닫힘(closure), 결합법칙(associativity), 교환법칙(commutativity), 항등원 존재(existence of identity), 역원 존재(existence of inverse)

순환 시프트 (Circular Shift)

일부 현대 블록 암호에서 사용되는 연산이다.

Q: 순환 시프트는 역연산이 가능한가? YES

스왑 (Swap)

스왑은 k = n/2인 특수한 순환 시프트이다.

분할과 결합 (Split and Combine)

일부 블록 암호에서 사용되는 연산이다.

곱 암호 (Product Cipher)

Shannon이 S-P 네트워크 개념을 도입했다. 곱 암호는 대체(S), 순열(P), 그리고 앞서 다룬 구성요소들을 결합한 복합 암호이다.

곱 암호의 두 가지 핵심 특성: **확산(Diffusion)**과 혼동(Confusion)

확산 (Diffusion)

확산은 암호문과 평문 사이의 관계를 숨기는 것이다.

예제:

1라운드: 비트 8이 S-Box 4를 통해 비트 7과 8에 영향. 순열 후 비트 8은 비트 2와 4에 영향.
2라운드: 비트 2가 S-Box 1을 통해 비트 1과 2에 영향. 순열 후 비트 8은 비트 1, 3, 6, 7에 영향.

혼동 (Confusion)

혼동은 암호문과 키 사이의 관계를 숨기는 것이다.

예제: 암호문 비트 1, 3, 6, 7은 키의 세 비트(K1의 비트 8, K2의 비트 2와 4)에 의해 영향받는다. 암호문 비트와 키 비트 사이의 관계가 모호해진다.

라운드 (Rounds)

확산과 혼동은 S-Box, P-Box 등의 조합을 반복(iteration)하는 곱 암호로 달성된다.

곱 암호의 두 종류

현대 블록 암호는 모두 곱 암호이지만, 두 가지로 분류된다:

Feistel 암호
Non-Feistel 암호

Feistel 암호

Feistel이 설계한 암호로, 수십 년간 사용되어 왔다.

Feistel 암호의 구성요소:

자기 역원(Self-invertible): XOR
역연산 가능(Invertible)
역연산 불가능(Non-invertible)

Feistel 암호는 모든 역연산 불가능 요소를 하나의 유닛에 모아 암호화와 복호화 알고리즘에서 동일하게 사용한다.

핵심 질문: 역연산 불가능한 유닛이 있는데 어떻게 암호화와 복호화가 서로의 역이 될 수 있는가? Feistel은 이들이 상쇄될 수 있음을 보였다.

Feistel 암호 설계의 첫 번째 아이디어

개선된 Feistel 설계

2라운드 Feistel 암호의 최종 설계

Feistel 암호 구조

Horst Feistel이 고안했다.

입력 블록을 두 부분으로 분할
여러 라운드를 거침
각 절반에 다른 연산 적용
그 후 절반을 스왑하는 순열
Shannon의 S-P 네트워크 개념 구현

Feistel 암호 설계 요소

블록 크기: 클수록 보안 향상, 단 속도 저하
키 크기: 클수록 보안 향상, 전수 키 탐색이 어려워짐, 단 속도 저하 가능
라운드 수: 많을수록 보안 향상, 단 속도 저하
서브키 생성 알고리즘: 복잡할수록 분석이 어려움, 단 속도 저하
라운드 함수: 복잡할수록 분석이 어려움, 단 속도 저하
빠른 소프트웨어 암/복호화: 실용적 사용을 위한 최근의 관심사
분석 용이성: 강도 검증 및 테스트가 쉬움

Non-Feistel 암호

Non-Feistel 암호는 역연산 가능한 구성요소만 사용한다. 암호화 암호의 각 구성요소에 대응하는 구성요소가 복호화 암호에 존재한다.

DES (Data Encryption Standard)

세계에서 가장 널리 사용된 블록 암호이다.

1977년 NBS(현 NIST)에서 채택
FIPS PUB 46으로 발표
64비트 데이터를 56비트 키로 암호화
널리 사용되었으나 보안성에 대한 논란이 있었음

※ NIST: National Institute of Standards and Technology ※ FIPS: Federal Information Processing Standards Publication

DES의 역사

IBM이 Lucifer 암호 개발 (1960년대 후반, Horst Feistel 팀)
- 64비트 데이터 블록, 128비트 키 사용
NSA 등의 의견을 반영하여 상업용 암호로 재개발
1973년 NBS가 국가 암호 표준에 대한 제안 요청
IBM이 수정된 Lucifer를 제출, 이것이 DES로 채택

DES 개념도

DES는 블록 암호이다.

DES의 전체 단계

암호화 과정은 **2개의 순열(초기 순열, 최종 순열)**과 16개의 Feistel 라운드로 구성된다.

라운드

DES는 16라운드를 사용한다. 각 라운드는 Feistel 암호이다.

키 생성

라운드 키 생성기는 56비트 암호키로부터 16개의 48비트 키를 생성한다.

초기 64비트 키에서 56비트 키로 변환
8개의 패리티 비트(비트 8, 16, 24, ... 64)가 실제 생성 과정 전에 제거됨
56비트 키를 각 28비트의 두 부분으로 분할
이 부분들이 라운드에 따라 왼쪽으로 1 또는 2 위치 순환 시프트됨

DES 암호화와 복호화

DES의 약점

1. S-Box의 약점: 역으로 유추될 수 있는 취약점 존재

2. 키의 약점

DES의 가장 심각한 약점은 키 크기이다. 전수 공격(Brute-force attack)을 위해서는 2^56개의 키를 확인해야 한다. 56비트는 너무 작다.
1997년 연구팀이 3,500대의 컴퓨터로 RSA Lab의 도전을 120일 만에 해결
3,500대로 120일이면, 42,000명의 비밀 조직은 10일 만에 키를 찾을 수 있다.

3. 차분 및 선형 암호분석: 비선형 함수인 S-Box의 잘못된 설계로 인해 분석 가능

4. 타이밍 공격

다중 암호화와 DES

DES의 대체가 필요했다.

전수 키 탐색 공격이 입증됨
AES가 새로운 대안으로 등장
그 전에는 DES를 여러 번 사용하는 다중 암호화가 대안이었음
- Double DES: 두 개의 다른 키로 DES를 두 번 수행
- Triple DES with Three Different Keys
- Triple DES with Two Different Keys
Triple-DES가 선택된 형태

Double-DES

두 번의 DES 암호화 사용:

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

단일 단계로의 축소 문제가 있고, **중간자 공격(Meet-in-the-middle attack)**이 가능하다.

어떤 암호를 두 번 사용할 때마다 동작
$X = E_{K1}(P) = D_{K2}(C)$ 이므로
P를 모든 키로 암호화하여 저장
그 다음 C를 키들로 복호화하여 X 값 매칭
O(2 x 2^56) 단계 소요 (2^112이 아님)

Triple-DES with Two Keys

3번의 암호화가 필요하다. 3개의 다른 키가 필요할 것 같지만, 2개의 키로 E-D-E 순서를 사용할 수 있다:

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

K1 = K2이면 단일 DES와 호환 가능

ANSI X9.17 및 ISO8732에서 표준화되었다.

현재 알려진 실용적 공격 없음 (일부 비실용적 공격 제안이 향후 공격의 기반이 될 수 있음)

복잡도 문제가 있다.

Triple-DES with Three Keys

2키 Triple-DES에 대한 실용적 공격은 없지만 일부 지표가 있다. 이를 피하기 위해 3개의 키를 사용하는 Triple-DES를 사용할 수 있다:

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

일부 인터넷 애플리케이션(예: PGP, S/MIME)에서 채택되었다.

AES (Advanced Encryption Standard)

역사

DES의 대체가 필요했다.

Triple-DES 사용 가능하나 소프트웨어에서 느리고 블록이 작음

US NIST가 1997년 암호 공모:

NIST 정의 기준: 보안, 비용, 구현
1998년 6월 15개 후보 수락
1999년 8월 5개 최종 후보
2000년 10월 Rijndael이 AES로 선정
2001년 11월 FIPS PUB 197 표준으로 발행

Rijndael 암호

벨기에의 Rijmen-Daemen이 설계했다.

Non-Feistel 암호 (반복적 암호, Feistel이 아님)
블록 길이 128비트
10, 12, 14 라운드 사용
키 크기 128, 192, 256비트 (라운드 수에 따라 다름)

설계 목표:

알려진 공격에 대한 저항
다양한 CPU에서 빠른 속도와 코드 간결성
설계의 단순성

AES 전체 설계

AES 암호화 암호:

AES 데이터 단위

Byte: 8비트
Word: 32비트
Block: 128비트
State: 4x4 바이트

Block-to-state 및 state-to-block 변환:

평문을 state로 변환하는 예제:

각 라운드의 구조

보안을 위해 AES는 네 가지 유형의 변환을 사용한다:

Substitution (대체)
Permutation (순열)
Mixing (혼합)
Key-adding (키 추가)

변환: Substitution (역연산 가능)

SubBytes

바이트를 대체하기 위해 바이트를 두 개의 16진수 숫자로 해석한다. SubBytes 연산은 16개의 독립적인 바이트 간 변환을 수행한다.

InvSubBytes

SubBytes의 역연산이다.

예제:

두 바이트의 값이 같으면 변환 결과도 같다.

SubBytes 변환의 의사코드:

변환: Permutation

ShiftRows

암호화에서 ShiftRows 변환이라 한다.

InvShiftRows

복호화에서는 InvShiftRows라 하며 오른쪽으로 시프트한다.

ShiftRows 변환의 의사코드:

예제:

변환: Mixing

인접 바이트의 비트에 기반하여 바이트 내부의 비트를 변경하는 바이트 간 변환이 필요하다. 비트 수준에서 확산을 제공하기 위해 바이트를 혼합해야 한다.

MixColumns

MixColumns 변환은 열 수준에서 동작한다. state의 각 열을 새로운 열로 변환한다.

InvMixColumns

InvMixColumns 변환은 기본적으로 MixColumns 변환과 동일하다.

MixColumns 변환의 의사코드:

예제:

변환: Key Adding

AddRoundKey

AddRoundKey는 한 번에 한 열씩 처리한다. 각 state 열 행렬에 라운드 키 워드를 더한다. AddRoundKey의 연산은 행렬 덧셈이다.

AddRoundKey 변환은 자기 자신의 역연산이다.

변환 요약

키 확장 (Key Expansion)

각 라운드의 라운드 키를 생성하기 위해 AES는 키 확장 과정을 사용한다.

라운드 수가 N_r이면, 키 확장 루틴은 하나의 128비트 암호키로부터 N_r + 1개의 128비트 라운드 키를 생성한다.

각 라운드의 워드:

AES-128의 키 확장

RotWord: ShiftRows와 유사하지만 한 행에만 적용. 4바이트 배열의 워드를 받아 각 바이트를 래핑과 함께 왼쪽으로 시프트.

SubWord: SubBytes와 유사하지만 4바이트에만 적용. 워드의 각 바이트를 다른 바이트로 대체.

라운드 상수 (RCon)

각 라운드 상수 RCon은 오른쪽 세 바이트가 항상 0인 4바이트이다.

키 확장 루틴은 아래 테이블을 사용하거나 GF(2^8) 필드를 사용하여 가장 왼쪽 바이트를 동적으로 계산할 수 있다(prime은 기약 다항식):

AES-128 키 확장의 의사코드:

예제: Alice와 Bob이 합의한 128비트 암호키: (24 75 A2 B3 34 75 56 88 31 E2 12 00 13 AA 54 87)₁₆

한 비트만 다른 두 암호키로부터 두 세트의 라운드 키가 생성될 수 있다:

DES에서 논의한 약한 키(Weak keys) 개념은 AES에 적용되지 않는다. 암호키의 모든 비트가 0이라고 가정하면:

pre-round와 첫 번째 라운드의 워드는 모두 같다. 두 번째 라운드에서 첫 번째 워드는 세 번째와, 두 번째 워드는 네 번째와 일치한다. 그러나 두 번째 라운드 이후 패턴이 사라지고 모든 워드가 다르다.

AES-192와 AES-256의 키 확장

AES-192와 AES-256의 키 확장 알고리즘은 AES-128과 매우 유사하며, 다음과 같은 차이점이 있다:

AES-192: 워드가 4개가 아닌 6개 그룹으로 생성됨

암호키가 처음 6개 워드(w₀ ~ w₅) 생성
i mod 6 ≠ 0이면, wᵢ ← wᵢ₋₁ + wᵢ₋₆; 아니면, wᵢ ← t + wᵢ₋₆

AES-256: 워드가 4개가 아닌 8개 그룹으로 생성됨

암호키가 처음 8개 워드(w₀ ~ w₇) 생성
i mod 8 ≠ 0이면, wᵢ ← wᵢ₋₁ + wᵢ₋₈; 아니면, wᵢ ← t + wᵢ₋₈
i mod 4 = 0이지만 i mod 8 ≠ 0이면, wᵢ = SubWord(wᵢ₋₁) + wᵢ₋₈

암호: 원래 설계

표준에서 암호화 알고리즘은 cipher, 복호화 알고리즘은 inverse cipher라 한다.

AES-128 버전의 코드:

암호: 대안 설계

SubBytes와 ShiftRows 조합의 역연산 가능성:

MixColumns와 AddRoundKey 조합의 역연산 가능성:

복잡도가 감소한다.

KeyExpansion 알고리즘 변경: 역 암호에서 InvAddRoundKey 변환을 사용하는 대신, 키 확장 알고리즘을 변경하여 역 암호를 위한 다른 라운드 키 세트를 생성할 수 있다.

예제 (따라가 보기)

무작위로 선택한 암호키를 사용하여 평문 블록에서 생성된 암호문 블록:

7라운드의 State 엔트리:

평문이 모두 0일 때의 암호화 결과. 이전 예제의 암호키를 사용하면:

AES 분석

보안

AES는 DES 이후에 설계되었다. DES에 대해 알려진 대부분의 공격이 이미 AES에서 테스트되었다.

전수 공격(Brute-Force Attack): 더 큰 키 크기로 인해 AES가 DES보다 확실히 안전하다.
통계적 공격: 수많은 테스트에서 암호문의 통계 분석에 실패했다.
차분 및 선형 공격: 아직 AES에 대한 차분 및 선형 공격이 없다.

구현

AES는 소프트웨어, 하드웨어, 펌웨어로 구현할 수 있다. 구현은 테이블 조회 프로세스나 잘 정의된 대수 구조를 사용하는 루틴을 사용할 수 있다.

단순성과 비용

AES에 사용된 알고리즘은 매우 단순하여 저렴한 프로세서와 최소한의 메모리로 쉽게 구현할 수 있다.

암호화 모드

그림을 보고 각 모드를 구분할 수 있어야 한다.

블록 암호는 고정 크기 블록을 암호화한다.

DES: 64비트 블록
AES: 128비트 블록

임의의 양의 데이터(예: b비트 블록)를 암/복호화하는 방법이 필요하다.

NIST SP 800-38A는 5가지 모드를 정의한다. 다양한 응용을 커버하기 위한 것으로, Triple DES와 AES를 포함한 모든 블록 암호와 함께 사용할 수 있다.

ECB (Electronic Code Book)

메시지가 독립적인 블록으로 나뉘어 암호화된다. 각 블록은 코드북처럼 대체되는 값이다. 각 블록이 다른 블록과 독립적으로 인코딩된다.

$C_i = E_K(P_i)$

$P_i = D_K(C_i)$

용도: 단일 값의 안전한 전송

암호화:

동일한 키 사용, 마지막 블록은 패딩으로 채움

복호화:

ECB의 장점과 한계

메시지 반복이 암호문에 나타날 수 있음
- 특히 그래픽 같은 데이터나 거의 변하지 않는 메시지에서 메시지 블록과 정렬될 때, 코드북 분석 문제가 됨
약점은 암호화된 메시지 블록이 독립적이기 때문
- 암호문 블록 1, 3, 7이 같으면, 한 블록이 드러나면 나머지도 드러남
- Eve가 블록 8이 항상 특정 정보를 전달한다는 것을 알면, 이전에 가로챈 메시지의 해당 블록으로 교체할 수 있음
단일 블록의 오류가 다른 블록에 영향을 주지 않음
- 전송 중 단일 오류는 해당 블록에만 여러 오류를 생성할 수 있음
주요 용도: 소량의 데이터 블록 전송

CBC (Cipher Block Chaining)

메시지가 블록으로 나뉘고, 암호화 연산에서 연결된다. 이전 암호문 블록이 현재 평문 블록과 체인된다.

프로세스 시작을 위해 초기화 벡터(IV) 사용:

$C_0 = IV$

$C_i = E_K(P_i \oplus C_{i-1})$

$P_i = D_K(C_i) \oplus C_{i-1}$

용도: 대용량 데이터 암호화, 인증

병렬 처리 불가능

병렬 처리 가능

초기화 벡터 (IV)

무작위 값이며, 비밀일 필요는 없지만 송신자/수신자가 동일해야 한다.

IV 보호:

공격자가 IV의 비트를 예측 가능하게 변경하면, P1의 수신 값에서 해당 비트가 변경될 수 있다.

CBC의 장점과 한계

두 메시지가 같으면 동일한 IV에 대해 암호화가 같다.
- 일부는 타임스탬프를 IV로 사용할 것을 권장
Cⱼ의 단일 오류는 복호화 시 Pⱼ의 대부분 비트에 오류를 생성하고 Pⱼ₊₁의 한 비트만 토글(영향을 줌). Pⱼ₊₂부터 Pₙ은 영향권 밖