본문으로 건너뛰기

12장. 메시지 인증 코드 (MAC)

학습 목표

  • 메시지 인증과 관련된 공격 유형을 나열·설명한다.
  • 메시지 인증 코드(MAC)를 정의한다.
  • MAC의 요구사항을 나열·설명한다.
  • HMAC의 개요를 제시한다.
  • CMAC의 개요를 제시한다.
  • 인증 암호화(authenticated encryption)의 개념을 설명한다.
  • CCM과 GCM의 개요를 제시한다.
  • 키 래핑(key wrapping)의 개념과 용도를 설명한다.
  • 해시 함수/MAC 기반 의사난수 생성을 이해한다.

12.1 메시지 인증 요구사항​

네트워크 통신에서 식별할 수 있는 8가지 공격:

#공격설명대응 범주
1Disclosure비인가자에게 메시지 내용 노출기밀성
2Traffic Analysis통신 패턴(빈도·기간·길이) 분석기밀성
3Masquerade위조된 출처로 메시지 삽입메시지 인증
4Content Modification삽입·삭제·전치·수정메시지 인증
5Sequence Modification메시지 순서 변조(삽입·삭제·재정렬)메시지 인증
6Timing Modification메시지 지연 또는 재전송메시지 인증
7Source Repudiation송신자의 송신 부인전자서명
8Destination Repudiation수신자의 수신 부인전자서명 + 프로토콜
요약

메시지 인증은 수신된 메시지가 주장된 출처에서 왔으며 변조되지 않았음을 검증하는 절차이다. 순서와 적시성도 검증할 수 있다. 전자서명은 인증에 더해 송신자의 부인 방지를 포함한다.

12.2 메시지 인증 함수​

인증 메커니즘은 두 수준의 기능을 가진다: (1) **인증자(authenticator)**를 생성하는 하위 함수, (2) 인증자를 사용하여 메시지를 검증하는 상위 프로토콜. 인증자를 생성하는 함수는 세 가지로 분류된다.

메시지 암호화​

대칭 암호화 — 공유 비밀키 KK로 E(K,M)E(K, M) 전송: 기밀성 + 인증을 제공한다. 단, 수신자가 복호화 결과가 유효한 평문인지 판별할 수 있어야 한다. 평문이 임의 비트 패턴이면 인증이 불가능하므로, 내부 오류 제어(FCS를 먼저 붙인 뒤 암호화)로 구조를 부여해야 한다.

내부 vs 외부 오류 제어

E(K,[M∥F(M)])E(K, [M \| F(M)])처럼 FCS를 먼저 계산하고 전체를 암호화(내부 오류 제어)해야 인증이 된다. F(E(K,M))F(E(K, M))처럼 암호문에 FCS를 추가하면(외부), 공격자가 유효한 FCS를 가진 위조 메시지를 생성할 수 있다.

공개키 암호화 — E(PUb,M)E(PU_b, M): 기밀성만 제공 (인증 없음). E(PRa,M)E(PR_a, M): 인증 + 서명 (기밀성 없음). E(PUb,E(PRa,M))E(PU_b, E(PR_a, M)): 기밀성 + 인증 + 서명 (공개키 연산 4회).

메시지 인증 코드 (MAC)​

비밀키 KK와 메시지 MM의 함수로 고정 길이 인증자(태그)를 생성한다:

MAC=C(K,M)\text{MAC} = C(K, M)

송신자가 M∥MACM \| \text{MAC}을 전송하면, 수신자가 동일한 KK로 MAC을 재계산하여 비교한다.

MAC이 일치하면 보장되는 것:

  1. 메시지가 변조되지 않았음 (공격자가 KK 없이 유효한 MAC 생성 불가)
  2. 메시지가 주장된 송신자로부터 온 것 (다른 누구도 KK를 모름)
  3. 시퀀스 번호가 포함되면 적절한 순서가 보장됨

MAC 함수는 비가역적(reversible할 필요 없음)인 다대일 함수이다. nn비트 MAC, NN개 가능한 메시지(N≫2nN \gg 2^n)이면, 각 MAC 값은 평균 N/2nN / 2^n개의 메시지에 대응한다.

세 가지 사용 형태:

형태전송 내용제공 서비스
(a) 인증만M∥C(K1,M)M \| C(K_1, M)인증
(b) 평문 기반 인증 + 기밀성E(K2,[M∥C(K1,M)])E(K_2, [M \| C(K_1, M)])인증 + 기밀성
(c) 암호문 기반 인증 + 기밀성E(K2,M)∥C(K1,E(K2,M))E(K_2, M) \| C(K_1, E(K_2, M))인증 + 기밀성

일반적으로 인증을 평문에 직접 연결하는 (b) 방식이 선호된다.

별도 MAC이 필요한 6가지 이유:

  1. 브로드캐스트 환경에서 하나의 수신자만 인증 담당
  2. 부하가 큰 시스템에서 선택적 인증 검사
  3. 평문 프로그램의 무결성 검증 (매번 복호화 없이)
  4. SNMPv3처럼 기밀성 없이 인증만 필요한 경우
  5. 인증과 기밀성의 아키텍처적 분리 (다른 계층에서 수행)
  6. 수신 후에도 장기적 보호 유지
MAC ≠ 전자서명

MAC은 송·수신자가 동일한 키를 공유하므로, 제3자에 대한 증명(부인 방지)을 제공하지 못한다.

12.3 MAC의 요구사항​

T=MAC(K,M)T = \text{MAC}(K, M)에 대해, 공격자가 MAC 함수를 알지만 KK를 모를 때:

  1. MM과 MAC(K,M)\text{MAC}(K, M)을 관찰해도 MAC(K,M′)=MAC(K,M)\text{MAC}(K, M') = \text{MAC}(K, M)인 M′M'을 구성하기 불가능
  2. MAC(K,M)\text{MAC}(K, M)이 균등 분포: 랜덤 MM, M′M'에 대해 Pr⁡[MAC(K,M)=MAC(K,M′)]=2−n\Pr[\text{MAC}(K, M) = \text{MAC}(K, M')] = 2^{-n}
  3. 알려진 변환 M′=f(M)M' = f(M)에 대해서도 Pr⁡[MAC(K,M)=MAC(K,M′)]=2−n\Pr[\text{MAC}(K, M) = \text{MAC}(K, M')] = 2^{-n}

무차별 키 탐색 비용 분석​

k>nk > n (키 크기 > 태그 크기)일 때, 알려진 (M1,T1)(M_1, T_1)에 대해 모든 2k2^k 키를 시도하면 약 2k−n2^{k-n}개의 후보키가 남는다. 추가 쌍으로 반복하면 ⌈k/n⌉\lceil k/n \rceil 라운드 후 유일한 키를 찾을 수 있다.

예: 80비트 키, 32비트 태그 → 1라운드에서 2482^{48}개 후보 → 2라운드에서 2162^{16}개 → 3라운드에서 1개.

12.4 MAC의 보안​

무차별 대입 공격​

MAC의 보안 속성은 **계산 저항(computation resistance)**이다: 알려진 텍스트-MAC 쌍 [xi,MAC(K,xi)][x_i, \text{MAC}(K, x_i)]로부터 새로운 유효한 쌍 [x,MAC(K,x)][x, \text{MAC}(K, x)]을 계산하기 불가능.

두 가지 공격 경로:

공격 대상비용설명
키 공간∼2k\sim 2^k모든 가능한 키를 시도
태그 값∼2n\sim 2^n주어진 메시지에 유효한 태그를 찾기 (오프라인 공격 제한)

따라서 무차별 대입 비용은 min⁡(2k,2n)\min(2^k, 2^n)이며, min⁡(k,n)≥N\min(k, n) \ge N (예: N=128N = 128)을 권장한다.

암호분석​

이상적인 MAC 알고리즘은 무차별 대입 이상의 암호분석 노력을 요구해야 한다.

12.5 해시 기반 MAC: HMAC​

HMAC 설계 목표​

  1. 기존 해시 함수를 수정 없이 블랙박스로 사용
  2. 내장 해시 함수의 쉬운 교체 (예: SHA-2 → SHA-3)
  3. 원래 해시 함수의 성능 유지
  4. 키 처리를 단순하게 유지
  5. 내장 해시 함수의 강도에 기반한 증명 가능한 보안

HMAC 알고리즘​

HMAC(K,M)=H[(K+⊕opad)  ∥  H[(K+⊕ipad)  ∥  M]]\text{HMAC}(K, M) = H\bigl[(K^+ \oplus \text{opad}) \;\|\; H[(K^+ \oplus \text{ipad}) \;\|\; M]\bigr]

  • HH: 내장 해시 함수 (예: SHA-256)
  • K+K^+: KK에 0을 패딩하여 블록 길이 bb비트에 맞춤
  • ipad\text{ipad}: 0x36을 b/8b/8회 반복
  • opad\text{opad}: 0x5C를 b/8b/8회 반복

처리 과정:

  1. K+⊕ipadK^+ \oplus \text{ipad}를 MM에 선행 결합 → 내부 해시 H[(K+⊕ipad)∥M]H[(K^+ \oplus \text{ipad}) \| M] 계산
  2. K+⊕opadK^+ \oplus \text{opad}를 내부 해시 결과에 선행 결합 → 외부 해시 계산
효율적 구현

f(IV,K+⊕ipad)f(IV, K^+ \oplus \text{ipad})와 f(IV,K+⊕opad)f(IV, K^+ \oplus \text{opad})를 사전 계산하면, 키가 바뀔 때만 재계산하면 되므로 메시지당 추가 비용은 압축 함수 1회에 불과하다.

HMAC의 보안​

HMAC의 보안은 내장 해시 함수의 강도에 증명 가능하게 의존한다. 공격자가 HMAC을 깨려면:

  1. 랜덤·비밀 IV로 압축 함수의 출력을 계산하거나
  2. 랜덤·비밀 IV로 해시 함수의 충돌을 찾아야 한다

MD5의 충돌 저항은 2642^{64}이지만, HMAC에서는 공격자가 오프라인으로 메시지/코드 쌍을 생성할 수 없으므로, 1Gbps 링크에서 키 변경 없이 15만 년 이상 관측해야 공격 가능하다. 따라서 HMAC에서는 MD5도 여전히 수용 가능하다.

12.6 블록 암호 기반 MAC: DAA와 CMAC​

DAA (Data Authentication Algorithm)​

DES의 CBC 모드를 IV = 0으로 사용:

O1=E(K,D1),Oi=E(K,Di⊕Oi−1),DAC=MSBM(ON)O_1 = E(K, D_1), \quad O_i = E(K, D_i \oplus O_{i-1}), \quad \text{DAC} = \text{MSB}_M(O_N)

FIPS PUB 113, ANSI X9.17으로 표준화되었으나, 고정 길이 메시지에만 안전하다는 약점이 발견되어 현재는 CMAC으로 대체되었다.

DAA의 약점

1블록 메시지 XX의 CBC MAC이 TT이면, 2블록 메시지 X∥(X⊕T)X \| (X \oplus T)의 MAC도 TT이다. 이를 통해 메시지 길이가 고정되지 않으면 위조가 가능하다.

CMAC (Cipher-Based MAC)​

DAA의 취약점을 해결. AES 또는 3DES를 사용하며, NIST SP 800-38B에 표준화되었다.

핵심: 암호화 키 KK 외에 두 개의 bb비트 보조 키 K1K_1, K2K_2를 사용. 마지막 블록이 완전한 블록이면 K1K_1을, 불완전하면 (패딩 후) K2K_2를 XOR한다.

Cn=E(K,[Mn⊕Cn−1⊕K1]),T=MSBTlen(Cn)C_n = E(K, [M_n \oplus C_{n-1} \oplus K_1]), \quad T = \text{MSB}_{T_{len}}(C_n)

보조 키 도출:

L=E(K,0b),K1=L⋅x,K2=L⋅x2L = E(K, 0^b), \quad K_1 = L \cdot x, \quad K_2 = L \cdot x^2

여기서 곱셈은 GF(2b)GF(2^b)에서 수행된다. 기약 다항식: x128+x7+x2+x+1x^{128} + x^7 + x^2 + x + 1 (AES), x64+x4+x3+x+1x^{64} + x^4 + x^3 + x + 1 (3DES).

12.7 인증 암호화: CCM과 GCM​

**인증 암호화 (Authenticated Encryption, AE)**는 기밀성과 인증을 동시에 제공하는 단일 알고리즘이다.

네 가지 일반적 접근법​

접근법순서사용 프로토콜
H→EH \to E해시 → 암호화WEP (취약)
A→EA \to EMAC → 암호화SSL/TLS
E→AE \to A암호화 → MACIPsec
E+AE + A독립적 암호화·MACSSH

CCM (Counter with CBC-MAC)​

IEEE 802.11 Wi-Fi용으로 표준화 (NIST SP 800-38C). **단일 키 KK**로 AES CTR 암호화 + CMAC 인증을 수행.

입력 3요소:

  • PP: 인증 + 암호화 대상 (평문)
  • AA: 인증만 대상 (관련 데이터, 예: 프로토콜 헤더)
  • NN: 논스 (재전송 방지)

동작:

  1. 인증: NN, AA, PP를 블록 B0,B1,…,BrB_0, B_1, \dots, B_r로 포맷 → CMAC 적용 → 태그 TT 생성
  2. 암호화: 카운터 Ctr0\text{Ctr}_0으로 태그를 암호화, Ctr1,Ctr2,…\text{Ctr}_1, \text{Ctr}_2, \dots로 평문을 CTR 모드 암호화
  3. 출력: 암호문 ∥ 암호화된 태그
CCM의 특성

평문을 2회 완전 통과 (MAC용 1회 + 암호화용 1회). 논스 길이와 태그 길이 간에 트레이드오프가 있다는 제약이 있으나, 높은 보안 수준으로 평가된다.

GCM (Galois/Counter Mode)​

NIST SP 800-38D. 병렬 처리가 가능하도록 설계되어 고속·저비용·저지연을 달성한다.

두 핵심 함수:

GHASH — 키 기반 해시 함수. 해시키 H=E(K,0128)H = E(K, 0^{128})을 사용:

GHASHH(X)=(X1⋅Hm)⊕(X2⋅Hm−1)⊕⋯⊕(Xm⋅H)\text{GHASH}_H(X) = (X_1 \cdot H^m) \oplus (X_2 \cdot H^{m-1}) \oplus \cdots \oplus (X_m \cdot H)

여기서 ⋅\cdot는 GF(2128)GF(2^{128})에서의 곱셈. 동일 해시키로 여러 메시지를 인증하면 H2,H3,…H^2, H^3, \dots를 사전 계산하여 각 블록을 병렬 처리 가능.

GCTR — CTR 모드 변형. 카운터를 단순 1씩 증가시키며 AES 암호화:

Yi=Xi⊕E(K,CBi),CBi=inc32(CBi−1)Y_i = X_i \oplus E(K, CB_i), \quad CB_i = \text{inc}_{32}(CB_{i-1})

전체 GCM 절차:

  1. H=E(K,0128)H = E(K, 0^{128})
  2. IV로부터 프리카운터 블록 J0J_0 생성
  3. C=GCTRK(inc32(J0),P)C = \text{GCTR}_K(\text{inc}_{32}(J_0), P) — 평문 암호화
  4. S=GHASHH(A∥0v∥C∥0u∥[len(A)]64∥[len(C)]64)S = \text{GHASH}_H(A \| 0^v \| C \| 0^u \| [\text{len}(A)]_{64} \| [\text{len}(C)]_{64})
  5. T=MSBt(GCTRK(J0,S))T = \text{MSB}_t(\text{GCTR}_K(J_0, S)) — 태그 생성
  6. 출력: (C,T)(C, T)
GCM의 장점

CTR 기반이므로 암호화와 인증 모두 병렬화 가능. 갈로아 필드 곱셈은 하드웨어에서 효율적으로 구현되어 높은 처리량과 보안을 동시에 달성한다.

12.8 키 래핑 (Key Wrapping)​

배경​

대칭키를 안전하게 교환하기 위해, 이미 공유된 **키 암호화 키(KEK)**로 새 키를 감싸는(wrap) 기법이다. NIST SP 800-38F (KW 모드). 키 데이터는 다른 데이터보다 가치가 높으므로 (한 키의 타협이 모든 암호문에 영향), 일반 모드보다 강건한 암호화가 필요하다.

핵심 특성​

일반 CBC/CTR 모드에서는 마지막 평문 블록이 마지막 암호문 블록에만 영향을 주지만, KW 모드에서는 모든 출력 비트가 모든 입력 비트의 함수이다. 대신 처리량이 낮으므로 키 관리 등 소량 데이터에만 사용한다.

래핑 알고리즘​

64비트 블록 단위로 동작. nn개의 평문 키 블록 P1,…,PnP_1, \dots, P_n과 KEK KK를 입력 받아, (n+1)(n+1)개의 암호문 블록 C0,C1,…,CnC_0, C_1, \dots, C_n을 출력.

s=6ns = 6n 단계(stage)를 수행하며, 각 단계에서:

W=E(K,[A(t−1)∥R(t−1,1)])W = E(K, [A^{(t-1)} \| R^{(t-1, 1)}])

A(t)=t⊕MSB64(W),R(t,n)=LSB64(W)A^{(t)} = t \oplus \text{MSB}_{64}(W), \quad R^{(t, n)} = \text{LSB}_{64}(W)

A(0)A^{(0)} = ICV (A6A6A6A6A6A6A6A6). RR 출력은 슬라이딩 버퍼를 통해 nn 단계 후에야 다시 입력으로 사용되어 눈사태 효과를 극대화한다.

언래핑 (Key Unwrapping)​

래핑의 역과정. 복호화 함수 DD를 사용하고, 복원된 ICV가 A6A6A6A6A6A6A6A6과 일치하면 키를 수락하고, 그렇지 않으면 무결성 오류로 거부한다. 따라서 키 래핑은 기밀성 + 데이터 무결성을 동시에 제공한다.

12.9 해시/MAC 기반 의사난수 생성​

해시 기반 PRNG (SP 800-90)​

시드 VV와 해시 함수 HH를 사용:

wi=H(data),data=(data+1) mod 2seedlenw_i = H(\text{data}), \quad \text{data} = (\text{data} + 1) \bmod 2^{\text{seedlen}}

출력 시퀀스: w1∥w2∥⋯∥wmw_1 \| w_2 \| \cdots \| w_m. 강력한 해시 알고리즘(예: SHA-2)에 대해 알려진 약점 없음.

MAC 기반 PRNG (SP 800-90 / HMAC)​

키 KK와 시드 VV를 사용. HMAC을 반복 적용:

wi=MAC(K,wi−1),w0=Vw_i = \text{MAC}(K, w_{i-1}), \quad w_0 = V

해시 기반보다 실행 시간이 2배 (HMAC = 해시 2회)이지만 보안 신뢰도가 더 높다.

프로토콜별 HMAC PRNG 비교​

방식데이터 입력특징
SP 800-90wi−1w_{i-1} (이전 출력)표준
IEEE 802.11iV∥iV \| i (시드 + 카운터)입출력 분리로 보안 강화
TLS/WTLSA(i)=MAC(K,A(i−1))A(i) = \text{MAC}(K, A(i-1)), wi=MAC(K,A(i)∥V)w_i = \text{MAC}(K, A(i) \| V)HMAC 2회/블록 (보안 과잉 가능)

주요 용어​

한글영문
인증자authenticator
블록 암호 기반 MACCipher-Based MAC (CMAC)
CBC-MAC 카운터 모드Counter with CBC-MAC (CCM)
암호학적 체크섬cryptographic checksum
데이터 인증 알고리즘Data Authentication Algorithm (DAA)
갈로아/카운터 모드Galois/Counter Mode (GCM)
해시 기반 MACHMAC
키 암호화 키key encryption key (KEK)
키 래핑key wrapping
메시지 인증message authentication
메시지 인증 코드message authentication code (MAC)