11. Message Authentication

Message Authentication

메시지 인증의 목적

- 메시지의 무결성 보호

- 발신자의 신원 확인

- 출처 부인 방지 (발신자가 메시지를 보낸 것에 대해 부인 X)

 

메시지 인증에 사용되는 3가지 대안적 함수

- 해시함수: 메시지의 내용을 바탕으로 고정된 길이의 해시 값 생성해서 무결성 확인

- 메시지 암호화: 개인키/공개키 암호화 사용해서 메시지의 기밀성과 발신자의 신원 모두 보장

- 메시지 인증 코드(MAC): 메시지와 비밀키 결합해서 생성되는 짧은 문자열, 메시지의 무결성과 발신자의 신원 확인

 

메시지 보안 요구 사항

공개 (Disclosure)	민감한 정보가 무단으로 공개되는 것을 방지
트래픽 분석 (Traffic Analysis)	메시지 흐름을 분석하여 중요한 정보를 추출하는 것을 방지
가장 (Masquerade)	다른 사용자나 장치로 가장하여 접근하거나 정보를 전송하는 행위를 방지
내용 변경 (Content Modification)	전송중인 메시지의 내용이 변경되지 않도록
순서 변경 (Sequence Modification)	메시지가 전송되는 순서가 변경되지 않도록
타이밍 변경 (Timing Modification)	메시지의 지연이나 재전송을 통해 발생할 수 있는 보안 문제를 방지
출처 부인 (Source Repudiation)	메시지 발신자가 메시지 전송을 부인하는 것을 방지
목적지 부인 (Destination Repudiation)	메시지 수신자가 메시지 수신을 부인하는 것을 방지

 

 

대칭키 암호화를 통해 인증도 제공할 수 있다. 비밀키로 암복호화 하기 때문이다.

메시지에 적절한 구조적 중복성, 여분성, 또는 체크섬이 있다면 내용이 변경될 수 없다. 이는 메시지의 무결성을 보장하는데 도움을 준다.

 

 

공개키 메시지 암호화만으로는 발신자에 대한 확신을 제공하지 않는다.

그러나, 발신자가 자신의 개인키로 메시지에 서명한 후에 수신자의 공개키로 메시지를 암호화하면 기밀성(secrecy)과 인증을 모두 확보할 수 있다.

 

 

MAC를 사용해서도 메시지 인증을 할 수 있다.

MAC란 메시지와 비밀 키를 결합하여 생성된 작은 고정 크기의 데이터 블록을 의미한다.

MAC는 C(K,M)으로 표현되며, 이는 비밀 키 K와 메시지 M을 암호화 알고리즘 C를 사용하여 변환한 결과이다.

아래 그림과 같이 키를 한 개 더 씀으로써 메시지의 기밀성을 챙겨 보안을 더 강화할 수 있다.

 

MAC를 사용하는 이유

오직 인증만 필요한 경우, 또는 메시지가 보관 목적으로 저장될 때 암호화된 메시지의 내용을 복호화하지 않고도 메시지가 변경되지 않았음을 확인할 수 있는 방법이 필요하다. **MAC는 전자서명을 제공하지 않는다**

 

MAC는 변수 길이를 가진 메시지 M을 비밀 키 K를 사용하여 고정된 크기의 인증자로 변환한다. 이 과정에서 메시지와 키가 입력으로 들어가고, MAC 알고리즘이 그 결과로 고정된 길이의 MAC를 출력한다.

다대일 함수이기 때문에, 이론상 여러 다른 메시지가 같은 MAC 값을 가질 수도 있지만, 이러한 경우는 매우 드물다.

 

 

MAC 요구사항

높은 난해성

- 메시지와 그에 해당하는 MAC를 알고 있어도 같은 MAC를 가지는 다른 메시지를 찾는 것이 불가능하거나 실질적으로 실행 불가능해야한다. 이것은 공격자가 유효한 MAC를 가진 위조 메시지를 생성하는 것을 방지한다.

 

균등한 분포

- 가능한 값들의 공간 내에서 균등하게 분포되어야 한다. 어떤 MAC값도 다른 값보다 더 자주 발생해선 안된다.

 

메시지의 모든 비트에 대한 의존성

- 메시지의 모든 비트에 동등하게 의존해야 한다.

 

 

HMAC

HMAC은 Hash-based Message Authentication Code이다.

K+는 키 확장으로, 키가 블록 크기보다 짧다면 키의 끝에 0을 추가하여 확장하고 같거나 길면 그대로 사용한다.

키에는 두 가지 상수 패딩이 적용된다. ipad는 내부 해시를 위한 패딩이고 opad는 외부 해시를 위한 패딩이다. 이들은 각각 키와 XOR 연산을 수행하여 두 개의 다른 블록을 생성한다.

내부 해시는, K+와 ipad의 XOR 결과에 메시지 M을 이어붙여서 하나의 긴 문자열을 생성한다. 이 문자열은 해시 함수를 통과하여 내부 해시 값을 생성한다.

외부 해시는, K+와 opad의 XOR 결과에 내부 해시 값을 이어붙여 또 다른 문자열을 생성한다. 이 문자열은 다시 해시 함수를 통과하여 최종 HMAC 값을 생성한다.

 

정리하자면, HMAC(K, M) = Hash[(K+ XOR opad) || Hash[(K+ XOR ipad) || M]] 이다.

 

HMAC의 보안성은 해시 알고리즘의 보안성과 연관되어있다. HMAC을 공격하는 것은 다음 두 가지 방법 중 하나를 통한다.

1. 키에 대한 브루트포스 공격 : 공격자가 사용된 키를 찾기 위해 가능한 모든 키 조합을 시도, 실질적 불가능

2. 생일 공격 : 해시 충돌을 찾기 위해 n비트의 해시 값이 있다면 2^(n/2)개의 시도가 필요하고, 여기에 키까지 사용되기에 실현 어려움

 

 

 

Data Authentication Algorithm

이 데이터 인증 알고리즘은 DES를 통해 MAC를 생성한다.

각 데이터 블록은 64bit의 크기를 가지고, 키는 56bit의 크기를 가진다.

각 데이터 블록에 대해 K로써 DES 암호화를 수행하고, 암호화 결과값은 다음 데이터블록과 XOR연산을 수행한다.

이렇게하여 마지막에 발생한 암호문이 DMAC가 된다.

 

 

CMAC - Cypher-based Message Authentication Code

블록 암호를 기반으로 한 메시지 인증 코드 생성 방법이다.

 

1. 먼저 메시지를 블록 크기에 맞춰 분할한다.

2. 각 블록 암호는 같은 키 K를 사용하여 암호화된다. 각 단게에서 이전 단계의 출력을 다음 단계의 입력과 XOR한다.

3-a. 메시지 길이가 블록 크기의 정수 배수일 경우, 마지막 블록 Mn은 특수한 키 K1과 XOR된 후 암호화된다.

3-b. 그렇지 않을 경우, 마지막 블록 Mn은 패딩이 추가된 후 다른 특수한 키 K2와 XOR된 후 암호화된다.

4. 마지막 블록의 암호화 결과로부터 가장 상위 비트(MSB)를 추출하여 태그 T를 생성한다. 이 태그가 MAC로 사용된다.

 

 

Authenticated Encryption (AE)

AE는 통신의 기밀성과 무결성을 동시에 보호하는 것을 목표로 한다.

Hash-then-encrypt	E(K,(M || H(M)))	MAC가 아니므로 해시 유출 가능성
MAC-then-encrypt	E(K2, (M || MAC(K1, M)))	일부 구현에서 선택 암호문 공격에 취약
Encrypt-then-MAC	(C=E(K2, M), T=MAC(K1, C))	안전함
Encrypt-and-MAC	(C=E(K2, M), T=MAC(K1, M))	MAC과 암호문 간 무결성 관계 명확X

 

 

CCM

Counter with Cipher Block Chaining-Message로, 무선 네트워크 통신의 보안을 위해 설계된 암호화 방식이다. 기밀성과 메시지 인증을 동시에 제공하는 방식이다.

CCM은 Encrypt-and-MAC 접근 방법의 변형으로 볼 수 있으며, 다음과 같은 알고리즘 구성 요소를 사용한다.

1. AES 암호화 알고리즘

2. CTR mode 운영

3. CMAC 인증 알고리즘

 

먼저 MAC 생성은, 랜덤값 Nonce와 메시지의 일부이지만 암호화되지 않고 인증만 되는 데이터 (예시 - 헤더 정보) Ass.Data, 그리고 메시지를 합친다.

합친 데이터를 블록 크기에 맞게 나눈 뒤, CMAC 알고리즘을 적용하여 Tag, MAC를 구한다.

 

암호화는 CTR 모드를 사용하여 암호화한다. 

먼저 CTR에 메시지를 넣는데, 카운터는 ctr1부터 사용한다. ctr0은 태그를 변형하기 위해 사용하는데, tag' = MSB(tLen, E(K, ctr0)) XOR tag를 수행한다.

 

 

GCM

GCM은 Galois Counter Mode로, 암호화와 인증을 동시에 제공하는 암호화 모드이다. 일반적으로 대칭키 암호화 시스템에서 사용되고, 특히 AES와 함께 사용된다.

GF(2^128)위의 갈루아 체에서 연산에 기반을 둔다. 

알고리즘 구성요소는 다음과 같다.

1. GMAC: MAC만을 제공하는 GCM의 변형

2. GHASH: 키가 적용된 해시 함수, 데이터의 무결성을 검증하는데 사용

3. GCTR: CTR의 변형으로 실제 데이터 암호화에 사용

 

같은 H 값이 사용된다면 병렬 처리가 가능하다.

 

위 그림은 GHASH의 작동 과정으로, H는 E(K, 0^128)으로 만들어진다. Yi = .H XOR Y1이다.

 

위 그림은 GCTR이 작동되는 과정이다. 

ICB는 초기 카운터 블록으로, 보통 nonce와 같은 유일한 값으로 설정된다.

CB는 각 블록 암호화마다 카운터 값이 1씩 증가한다. 이렇게 각 암호화 블록이 고유한 카운터 값을 가지게 된다.

E는 암호화 함수로, 주어진 K를 사용하여 카운터블록 CB를 암호화한다. 이때 사용되는 암호화 알고리즘은 AES와 같은 대칭키 블록 암호화 알고리즘이다.

E(K, CTR)과 평문 데이터 블록 Xi를 XOR연산하여 암호문 Y를 생성한다.

마지막 블록은 완전한 블록 크기를 채우지 않을 수 있다. 이 경우 MSB(Most Significant Bits, 최상위비트)를 선택해서 XOR 연산을 수행한다.

 

위 그림은 GCM에서 MAC 생성 과정을 도식화한 것이다.

IV를 인코딩하여 J0을 생성한다. 이는 첫 번째 카운터 블록이다.

평문에 대해 Ji와 K를 사용하여 암호문 C를 생성한다.

 

여기서 각종 정보를 합친 데이터 [ A=Ass.Data || 0^v || C || 0^u || [len(A)]64 || [len(C)]64 ] 를 만든다.

Ass.Data는 암호화되지 않고 인증에만 사용되는 데이터, 0^v와 0^u는 블록 사이즈에 맞추기 위한 패딩, len(A)_64와 len(C)_64는 A와 C의 길이를 64비트 공간에 나타낸 것이다.

 

이제 이를 GHASH에 적용시킨다. GHASH에서 사용하는 K는 0을 K로 암호화하여 만들어진다.

 

GHASH로 나온 결과값을 다시 GCTR 연산에 통과시키고 태그 길이에 알맞게끔 최상위비트로부터 잘라내 최종 태그를 생성한다.