MAC (Message Authentication Code) 도입

디지털 서명이 '비대칭키(공개키)'를 이용해 무거운 연산을 한다면, MAC은 '대칭키'를 이용해 아주 가볍고 빠르게 메시지를 인증하는 기술입니다.

동작 원리:

1. Alice와 Bob은 사전에 비밀 대칭키 $K$를 안전하게 공유하고 있습니다 (Secure CH).
2. Bob은 메시지 $x$와 비밀키 $K$를 이용해 짧은 MAC 값 $m$을 계산합니다. ($m = MAC_K(x)$)
3. Bob은 원본 $x$와 MAC $m$을 같이 보냅니다.
4. Alice는 받은 $x$와 자신이 가진 비밀키 $K$로 $m'$을 직접 계산해 보고, 받은 $m$과 비교합니다.

보안 특성 (Properties of MACs) ★기말고사 출제 포인트★:

1. Message Authentication (메시지 인증): $m$을 만들 수 있는 사람은 키 $K$를 아는 Bob밖에 없으므로, Alice는 "이 메시지는 무조건 Bob이 보낸 거구나"라고 확신할 수 있습니다.

2. Integrity (무결성): 해커가 중간에 $x$를 $\tilde{x}$로 변조하면, Alice가 계산한 $m'$이 받은 $m$과 달라지므로 변조 사실을 바로 알아챕니다.

3. Non-repudiation (부인 방지): NO!이것이 가장 치명적인 단점입니다. Alice도 키 $K$를 알고 있기 때문에, Alice 스스로 Bob인 척 메시지 $x$와 MAC $m$을 조작해 낼 수 있습니다. 따라서 법정에서 "이건 무조건 Bob이 보낸 거다"라고 증명할 수 없습니다. (내부자 공격 방어 불가)

HMAC (Hash-based MAC)

MAC을 구현하는 방법 중 하나로, 방금 전까지 뼈빠지게 배운 해시 함수를 재활용하여 MAC을 만드는 방식입니다.

• 요구 조건: 해시 함수처럼 입력 길이는 자유롭고(Arbitrary), 출력 길이는 고정(Fixed)되어야 합니다.
• HMAC의 기본 아이디어:새로운 암호 알고리즘을 짤 필요 없이, 기존에 잘 만들어둔 해시 함수 h에 원본 메시지 x와 비밀 대칭키 K를 같이 섞어서 넣어버리면 됩니다.
  $m = MAC_K(x) = h(x, K)$

키(K)와 메시지(X)의 결합 방식

MAC을 생성할 때 비밀키 $K$와 메시지 $X$를 해시 함수에 넣기 위해 섞는 방법으로 두 가지를 제시하고 있습니다.

• Secret Prefix (비밀 접두사): $m = h(K || X)$ (비밀키를 앞에 배치)
• Secret Suffix (비밀 접미사): $m = h(X || K)$ (비밀키를 뒤에 배치)

노트는 이 중 Secret Prefix MAC의 문제점에 집중합니다.
해시 함수는 한 번에 처리할 수 있는 데이터의 크기(예: 512 bits)가 정해져 있으므로, 긴 메시지 $X$는 여러 개의 블록 $X = (x_1 || x_2 || \dots || x_n)$으로 나뉘어 입력됩니다.

따라서 생성되는 MAC 값 $m$은 다음과 같습니다.
$m = h(K || x_1 || x_2 || \dots || x_n)$

이러한 블록 단위의 순차적 처리는 대부분의 해시 함수(MD5, SHA-1, SHA-2 등)가 Merkle-Damgård (머클-담고르) 구조를 사용하기 때문입니다.

머클-담고르 구조의 취약점

두 번째 이미지 상단의 다이어그램은 머클-담고르 구조의 연쇄적인 작동 방식을 보여줍니다.
이 구조에서는 이전 블록을 해싱한 결과값이 다음 블록을 해싱할 때의 초기화 벡터(IV, Initialization Vector) 또는 내부 상태값으로 사용됩니다.

여기서 길이 연장 공격의 핵심 원리가 발생합니다.
$K || X$에 대한 최종 해시 결과값인 $m$은 해시 함수의 마지막 내부 상태값과 같습니다. 따라서 공격자가 비밀키 $K$를 모르더라도, 이 $m$ 값을 새로운 IV로 삼아서 자신이 원하는 임의의 추가 블록 $x_{n+1}$을 해시 함수에 계속 밀어 넣을 수 있습니다.

수식으로 표현하면 다음과 같습니다.
$h(K || X || x_{n+1}) = h_{IV=m}(x_{n+1})$

길이 연장 공격(Length Extension Attack) 시나리오

노트 하단의 'Attack' 부분은 이 취약점을 이용해 공격자(Trudy)가 어떻게 검증자(Bob)를 속이는지 보여줍니다.

1. 가로채기: Alice가 Bob에게 금액 정보가 담긴 메시지 $X$ (예: 마지막 블록 $x_n = \$1$)와 MAC 값 $m$을 전송할 때, Trudy가 이를 중간에서 가로챕니다.
2. 메시지 변조: Trudy는 기존 메시지 $X$ 뒤에 새로운 내용 $x_{n+1}$ (예: $000,000$을 덧붙여 $\$1,000,000$으로 조작)을 추가하여 조작된 메시지 $X_\sigma$를 만듭니다.
3. MAC 위조: Trudy는 비밀키 $K$를 알지 못하지만, 가로챈 기존 MAC 값 $m$을 내부 상태값(IV)으로 설정한 뒤, 자신이 추가한 $x_{n+1}$ 블록만 한 번 더 해싱하여 새로운 해시값 $m_\sigma$를 만들어냅니다.
4. 검증 통과: Trudy가 조작된 $(X_\sigma, m_\sigma)$ 쌍을 Bob에게 보냅니다. Bob은 자신이 아는 비밀키 $K$를 이용해 $m' = h(K || X_\sigma)$를 직접 계산합니다. 머클-담고르 구조의 특성 때문에 Bob이 정상적으로 계산한 $m'$과 Trudy가 이어붙이기로 위조한 $m_\sigma$의 값이 완벽하게 일치($m' = m_\sigma$)하게 되며, 결국 Bob은 조작된 메시지를 신뢰하게 됩니다.

비밀 접미사 MAC (Secret Suffix MACs)

이 방식은 앞서 본 Prefix 방식과 반대로, 메시지 $X$를 먼저 넣고 비밀키 $K$를 맨 마지막(접미사)에 덧붙여 해시값을 만듭니다
공식: $m = h(X || K)$

길이 연장 공격(Length Extension Attack) 방어 성공:
노트의 다이어그램과 하단 수식은 이전 Prefix 방식의 치명적 약점이었던 '길이 연장 공격'이 여기서는 통하지 않음을 증명합니다.

• 공격자(Trudy)의 시도: 메시지 뒤에 임의의 블록 $X_{n+1}$을 붙여 조작된 메시지 $X_\sigma = (X || X_{n+1})$를 만듭니다. 그리고 기존 MAC 값 $m$을 이용해 조작된 MAC 값 $m_\sigma = h(X || K || X_{n+1})$를 만들어냅니다.

• 수신자(Alice)의 검증: Alice는 조작된 메시지 $X_\sigma$를 받고, 규칙대로 맨 끝에 비밀키 $K$를 붙여서 검증용 MAC $m'$을 계산합니다. 즉, $m' = h(X || X_{n+1} || K)$가 됩니다.

• 결과: 공격자가 만든 $m_\sigma$는 키 $K$ 뒤에 $X_{n+1}$이 오지만, 수신자가 계산한 $m'$은 $X_{n+1}$ 뒤에 키 $K$가 옵니다. 순서가 다르기 때문에 $m' \neq m_\sigma$가 되어, 수신자는 메시지가 조작되었음을 즉시 알아채고 공격을 차단할 수 있습니다.

비밀 접미사의 약점(해시 충돌)과 HMAC의 등장

길이 연장 공격은 막았지만, Secret Suffix 방식에는 해시 충돌(Collision)이라는 또 다른 치명적인 약점이 존재합니다.

해시 충돌 공격 (Collision Attack):

• 만약 공격자(Trudy)가 해시값이 완전히 똑같이 나오는 두 개의 다른 메시지 $X$와 $X_\sigma$를 찾아낸다면 어떨까요? 즉, $h(X) = h(X_\sigma)$인 상황입니다.
• 이 경우, 머클-담고르 구조의 특성상 그 뒤에 똑같은 키 $K$를 이어 붙여도 결과가 같습니다.$h(X || K) = h(X_\sigma || K) = m$
• 예시: 원래 메시지 $X$가 "1달러"이고, 조작된 메시지 $X_\sigma$가 "$1,000,000달러"인데 두 메시지의 해시값이 우연히 같다면, MAC 값도 완전히 같아져서 서명이 위조됩니다.

충돌을 찾는 난이도 (생일 역설, Birthday Paradox):

• 해시 함수 SHA-1(출력 160비트)을 예로 듭니다.
• 비밀키의 길이가 128비트($2^{128}$)로 아주 길더라도, 해시 함수의 충돌을 찾는 것은 출력값 길이의 절반에 해당하는 난이도를 가집니다.
• 생일 역설 원리에 의해 $\sqrt{2^{160}} = 2^{80}$ 번의 시도만으로 충돌하는 두 메시지를 찾아낼 수 있습니다. 이는 현대 컴퓨팅 성능으로는 충분히 뚫릴 수 있는 수준이므로 취약합니다.

1.3 HMAC 구조 (SSL/TLS 표준)

Prefix의 약점(길이 연장 공격)과 Suffix의 약점(해시 충돌 공격)을 모두 해결하기 위해 등장한 것이 바로 HMAC입니다.

핵심 아이디어: 두 번의 해싱을 중첩해서(Nested) 사용합니다.

• 공식: $h[K || h(K || X)]$
  • 먼저 안쪽 해시(inner hash)에서 $K$와 $X$를 섞어 해싱합니다.
  • 그 결과값에 다시 바깥쪽 해시(outer hash)에서 $K$를 붙여 한 번 더 해싱합니다.
• 이렇게 두 번 감싸는 방식을 통해 길이 연장 공격과 충돌 공격을 모두 안전하게 방어할 수 있으며, 오늘날 우리가 인터넷을 안전하게 사용하는 기술(HTTPS, SSL/TLS)의 핵심 요소로 사용되고 있습니다.

$\text{HMAC}_K(X) = h((K^+ \oplus \text{opad}) \parallel h((K^+ \oplus \text{ipad}) \parallel X))$

키 확장 및 패딩 (Key & Pads)

하나의 비밀키 $K$를 이용해 서로 다른 두 개의 키(내부용, 외부용)를 만들어내는 과정입니다.

• $K^+$ (Key Padding): 해시 함수의 입력 블록 크기(일반적으로 512 bits)에 맞추기 위해, 원래의 비밀키 $K$(예: 128 bits)의 앞부분을 모두 0으로 채웁니다.

• $\text{ipad}$ (Inner Pad): 해시 블록 크기와 동일한 길이의 고정된 비트 패턴입니다. 바이트 단위로 0x36 (0011 0110)이 반복됩니다.

• $\text{opad}$ (Outer Pad): 마찬가지로 고정된 비트 패턴이며, 바이트 단위로 0x5c (0101 1100)가 반복됩니다.

HMAC 연산 과정 (다이어그램 분석)

노트의 블록 다이어그램은 연산의 파이프라인을 보여줍니다.

Step 1: 내부 키($S_i$) 생성 및 내부 해시 (Inner Hash)

• 확장된 키 $K^+$와 $\text{ipad}$를 XOR($\oplus$) 연산하여 내부용 키 상태값인 $S_i$를 만듭니다.
• 이 $S_i$ 바로 뒤에 실제 검증할 메시지 $X = (x_1, x_2, \dots, x_n)$를 이어 붙입니다($\parallel$).
• 이를 해시 함수 $h$에 넣어 내부 해시 결과값 $h(S_i \parallel X)$를 도출합니다.
• 노트 우측 파란 글씨: "Message is only processed in the inner hash!" (메시지는 내부 해시 연산에만 들어갑니다.)

Step 2: 외부 키($S_o$) 생성 및 외부 해시 (Outer Hash)

• 확장된 키 $K^+$와 $\text{opad}$를 XOR($\oplus$) 연산하여 외부용 키 상태값인 $S_o$를 만듭니다.
• $S_o$ 뒤에 방금 Step 1에서 구한 내부 해시 결과값을 이어 붙입니다.
• 이를 다시 해시 함수 $h$에 넣어 최종 HMAC 값을 산출합니다.

구조적 안전성 (왜 해킹을 막을 수 있는가?)

노트 우측 하단의 빨간 글씨 "Trudy does NOT know outer K"가 이 구조의 핵심 방어 논리입니다.앞서 Secret Prefix의 치명적 약점이었던 길이 연장 공격(Length Extension Attack)을 떠올려 보십시오.

만약 공격자 Trudy가 내부 해시의 결과값인 $h(S_i \parallel X)$를 가로채서 그 뒤에 임의의 블록 $x_{n+1}$을 이어 붙여 공격을 시도하려 해도 소용이 없습니다.

최종 MAC 값은 단순히 내부 해시값이 아니라, 그 값을 외부 키 상태값인 $S_o$와 다시 결합하여 바깥쪽 해시(Outer Hash)를 한 번 더 거쳐야만 완성되기 때문입니다.
Trudy는 비밀키 $K$를 모르므로 $S_o$ 값을 계산할 수 없고, 결국 바깥쪽 해시를 뚫고 유효한 위조 MAC을 만들어내는 것이 수학적으로 불가능해집니다.