[암호공학] 11장, Message Integrity and Message Authentication

핵심 Keyword : message integrity, message authentication, cryptographic hash function, MDC, MAC, MACs

 

1. Message Integrity

:지금까지 우리가 공부한 암호화 시스템은 기밀성은 제공하나 무결성은 제공하지 않았다. 그러나 가끔씩 기밀성보다 무결성이 더 중요할 때가 존재한다.

무결성을 보존하는 한가지 방법은 document에 fingerprint를 이용하는 것이다. 만약 Alice가 document의 내용이 바뀌기 않기를 원하면, Alice는 지문을 문서 맨 마지막에 찍을 수 있다.

 

문서와 지문 pair는 message와 digest pair로 비교된다.

(document / fingerprint)와 (message / message digest) 는 similar하나 몇몇 다른 점을 갖고 있다. document와 fingerprint는 물리적으로 연결되어 있다. 하지만 message와 message digest는 별도로 unlinked될 수 있다. 그리고 가장 중요하게, message digest는 be safe from change해야한다.

무결성을 체크하기 위해서는 우리는 cryptographic hash function에 메시지를 통과시켜서 previous message digest와 current digest를 비교한다. 만약 둘이 같다면 메시지가 변경되지 않음 확인할 수 있고, 그게 아니라면 discard된다.

 

이 cryptographic hash function은 항상 세가지 기준을 만족한다.

1) preimage resistance

2) second preimage resistance

3) collision resistance

1) Preimage resistance

: hash function h가 주어졌다. y = h(M)이라고 하자. Eve가 y = h(M`)을 만족하는 메시지 M`을 찾기는 매우 힘들다.

만약 hash function이 preimage resistance하지 않다면, Eve는 digest h(M)을 중간에 가로채서 메시지 M`을 생성할 수 있다. 그리고 Bob에게 M`을 보내면서 그것이 마치 M인것처럼 속일 수 있다.

 

2) Second Preimage Resistance

: 메시지가 쉽게 위조되지 못하도록 한다. 만약 Alice가 메시지를 만든 후 digest해서 메시지와 digest를 Bob에게 보낸다고 치자. 이 기준은 Eve가 완전 동일한 digest를 생성하는 메시지를 생성할 수 없도록 한다. 다른 말로, 같은 digest를 갖는 다른 message를 생성하는것을 불가능하게 만든다는 것이다. 

M과 h(M)이 주어졌을 때, M과 M`이 다르다면, h(M)과 h(M`)이 항상 다르다.

 

3) Collision Resistance

: 두 메시지가 같은 hash function을 지나서 동일한 digest가 될 수 없게 한다.  

 

3. Message Authentication

위에서 언급한 message digest는 메시지의 전송자를 authenticate하지 않는다. messaage authentication을 제공하기 위해서는, Alice는 Alice가 이 메시지를 보냈다는것에 대한 증명을 제공해야 한다. cryptographic hash function으로 생성된 digest는 일반적으로 modification detection code(MDC)라고 한다. 그리고 message authentication을 위해 필요한것은 message authentication code(MAC)이라 한다.

 

1) Modification Detection Code (MDC)

: MDC는 메시지의 무결성을 증명하는 message digest를 뜻한다.

Alice가 Bob에게 메시지를 전송하는데, message가 전송도중 변경되지 않았음을 확실히 한다. Alice는 message digest(여기서는 MDC)와 함께 message를 Bob에게 전송한다. Bob은 새로운 MDC를 메시지로부터 생성한 후 받은 MDC와 생성된 MDC값을 비교한다. 같다면 Accept되고, 다르다면 Reject된다. 

메시지는 insecure channel으로 전송할 수 있어서 Eve가 메시지를 read나 modify할 수 있다. 하지만 MDC는 safe channel을 통해 전송되어야 한다. 여기서 'safe'란 change에 immune하다는 뜻이다. 만약 메시지와 MDC 둘다 insecure channel으로 전송된다면 Eve가 message를 가로채서 바꾸고, new MDC를 만들어서 둘다 Bob에게 보낼 수 있기 때문에 Bob은 그 메시지가 Eve에게서 온지조차 알 수 없어서 문제가 생긴다.

 

2) Message Authentication Code (MAC)

: MAC의 security는 hash function의 hash algorithm에 dependent하다. 

Alice는 message를 보내는 originator이다. 우리는 MDC를 message authentication code(MAC)으로 바꿔야 할 필요가 있다. MDC와 MAC의 차이점은 MAC는 Alice와 Bob간의 비밀을 유지한다. 예를 들어, Eve가 possess할 수 없는 secret key를 갖는다. 

위 그림에서, Alice는 hash function으로, key와 message를 합쳐서(concatenation) MAC을 만든다. Alice가 insecure channel을 통해서 Bob에게 MAC을 전송하고 Bob은 MAC에서부터 message를 분리해낸다. 그리고 Bob이 새로운 MAC을 concatenation을 통해 만들고 들어온 MAC과 만들어진 MAC을 비교한다. 만약 같다면 accept, 다르다면 reject된다.

이 경우에는 MAC을 전송할 때 insecure channel으로 전송해도 된다. Eve가 메시지를 볼 수 있더라도 그것을 위조할 수는 없다. 왜냐하면 Eve는 Alice와 Bob만 알고 있는 secret key를 모르기 때문이다. 

우리가 지금까지 언급한 MAC은 prefix MAC이라 하는데, 왜냐하면 secret key가 message의 앞부분에 appended되었기 때문이다. 이와 반대로 secret key가 메시지의 뒷부분에 appended된 postfix MAC을 쓸수도 있다. 그렇다면 postfix와 prefix MAC을 합치면 어떻게 될까? 앞뒤가 같은 MAC인 것이다. 이 경우의 MAC은 insecure하다. 

 

** Nested MAC

MAC의 안전성을 높이기 위해서 Nested MAC이 고안되었다. hashing이 두 단계를 나눠서 수행된다.

첫번째 단계에서는 key가 메시지와 concatenated된다. 그리고 hash function을 거쳐 중간의 immediate digest를 생성하게 된다. 

두번째 단계에서, key는 중간의 intermediate digest와 concatenate되고 이는 final digest(MAC)이 된다.

 

**HMAC

 

HMAC은 hashed MAC으로, nested MAC보다 과정이 훨씬 복잡하다. padding이라는 feature이 추가되었다.

1. 메시지는 N개의 block으로 분할된다. 각각은 b bits이다.

2. Secret key는 b-bits 로 맞추기 위해 왼쪽에 '0'을 패딩하여 b-bits key를 생성한다. 이 때 secret key는 n bits보다는 긴 것을 권장하고 있대. 이 때의 n은 HMAC size를 뜻한다.

3. 2단계와 ipad(input pad)라 불리는 상수와 exclusive-or되어 b-bit block을 생성한다. ipad의 값은 b/8 repetition of the sequence 00110110(36 in hex)이다.

4. 그 결과로 나온 block은 N-block 메시지 앞에 달린다. 그러면 총 N+1개의 block이 된다.

5. 4번의 결과를 hash시켜서 n-bits digest를 생성한다. 이 digest를 intermediate HMAC이라고 한다.

6. 이 intermediate n-bit HMAC은 b-bit block으로 만들어주기 위해서 '0'을 왼쪽에 padding한다.

7. 2번과 3번 과정이 반복되는데 이 때는 ipad가 아니라 opad(output pad)를 쓴다. opad의 값은 b/8 repetition of the sequence 01011100(5C in hex)이다.

8. 7번의 결과를 블록 앞에 달아준다.

9. 8번이 위와 동일한 hash algorithm을 가진 hash function을 통과하면 final n-bit HMAC이 생성된다.

 

** CMAC

 

CMAC은 8장에서 소개된 cipher block chaining(CBC)방법과 유사하다. CMAC의 아이디어는 한 블럭의 MAC을 N block의 평문으로부터 대칭 키 암호화 방식을 N번 이용하여 생성하는 것이다. 

메시지는 N blocks로 분할되고, 각각의 블록은 m bits 길이이다. CMAC의 크기는 n bits이다. 마지막 블록이 m bits길이가 아니면, '1'으로 패딩해서 m-bit로 맞춰준다. 메시지의 첫번째 블록은 대칭키 방식으로 암호화되고 m-bit block의 암호화된 데이터가 된다. 이 암호화된 블럭이 다음 평문 블럭과 XOR되고 그 결과가 다시 암호화되는 식이다. 마지막 블록의 메시지가 암호화될때 까지 반복하며, 마지막 블럭의 n leftmost bit가 CMAC이다. CMAC은 대칭 키 K뿐만 아니라 다른 암호 k도 쓰는데, 마지막 단계에서만 이용된다.