Hash Functions

@ Hash Function

@ Cryptographic Hash Functions

 - 암호학적으로 의미있는 해쉬함수가 되려면?

 - MDC (Modification Detection Code) : m || H(m) 

-  일단 여기선 키가 없고 에러가 있는지만 확인한다.

 - MAC (Message Authentication Code) : m || MACk(m)

- 여기서 k는 key를 의미한다.

- 키를 모르면 메시지 m에 대한 MAC값을 만들 수 없다. 알고 있을 때만 만들 수 있다.

- 메세지를 누가 보냈는지 알 수 있다.(인증)

@ MDC

 - 요구사항

1) Pre-image Resistance

2) Second Pre-image Resistance

3) Collision Resistance

 - MDC의 구조 및 설계

@ MAC (Message Authentication Code)

1. 개요

 - MAC는 데이터 암호화가 목적이 아니라 누가 보냈는지 인증을 하는 것이 목표이다.

 - 위 그림에 대한 시나리오는 다음과 같다.

1) A와 B가 메시지(m)을 암호화해서 보낸다.

2) 여기선 인증이 목표이므로 메시지(m)을 보낸다고 가정한다.

3) A가 B에게 m을 보낸다면 B는 누가 보냈는지 알 수 없다.

4) 따라서 메시지 인증을 위해 MAC을 사용한다.

5) MAC을 위해 대칭키를 공유한다.

6) 필요사항 : 메시지(m), MAC, 키(k)

7) B가 m을 받으면 MAC와 key로 A를 확인한다.

8) 맞으면 1을 틀리면 0을 출력한다.

- MAC을 정의하기 위해서는 3가지 알고리즘이 있다.

1) Key Gen 알고리즘 -> generate a security key

2) MAC 생성 알고리즘 -> make a MAC for a message with the secret key

3) MAC 유효 여부 확인 알고리즘 (verify) -> Output 1 if the MAC is valid

- 키를 가지고 있는 사람만이 MAC 값을 만들 수 있다.

- 위조가 힘듬 (strong unforgeability)

- 어떠한 공격자도 메시지와 MAC에 대한 유효햔 쌍을 만들 수 없다.

2. MAC이 안전한지 확인

- 키를 가지고 있는 사람만이 MAC 값을 만들 수 있다.

- 위조가 힘듦 (strong unforgeability)

- 어떠한 공격자도 메시지와 MAC에 대한 유효한 쌍을 만들 수 없다.

 - 공격자에겐 자유롭게 MAC 오라클을 사용하여 어떤 평문에 대한 MAC값을 얻어낼 수 있다.

 - 이때 이 공격자가 어떠한 메시지에 대해 MAC 값을 알아낼 수 있으면 공격자가 게임을 승리한다.

 - 단 MAC 오라클을 이용해 어떠한 메시지에 대한 MAC 값은 알아낼 수 없다.

 - 공격자는 키를 모른다고 가정한다.

3. 나쁜 MAC 구조

안전한 MAC 스킴을 만들기 위해 strong unforgeability을 증명하려면 이런 게임에서 높은 확률로 성공하는 어떠한 알고리즘도 존재하지 않음을 보여주면 된다. 반대로 말하면 어떤 애가 MAC 스킴을 만들었을 때 이러한 스킴이 안저하지 않음을 주장하려면 이 것이 뚫린다는 공격 알고리즘만 보여주면 된다. 그리고 지금부터 하나의 MAC 스킴을 보여주고 어떻게 깰 수 있는지 보여주겠다.

위와 같은 MAC 스킴을 작성하였다.

 - MAC은 고정된 길이 ( Constant size)

 - 기본 빌딩 블록으로 사용되는 m을 블록단위로 쪼갠다.

 - 그 메시지를 XOR 연산한 뒤 인크립션 한다.

 - 받은 사람은 똑같이 메시지를 XOR연산한 뒤 암호화하고 일치하는지 확인한다.

- 그리고 이것이 안전한 MAC을 보여주기 위해 strong unforgeability를 보여준다.

 - 공격자는 이것을 깨기 위해 m=m1이라는 것을 만든 뒤 MAC 값을 얻는다.

 - m1과 동일한 어떠한 값 m2를 2개 연속 뒤에 붙여서 m'를 만든다. 

 - m' = m1 || m2 || m2와 같이 만든다. (위의 오른쪽 식은 무시)

 - m2 xor m2 = 0

 - m1 xor 0 = m1

 - 따라서 Ek(m1) 의 값을 알 수 있게 된다.  이 값은 Ek(m)와 동일하다.

- 이런 식으로 어떠한 스킴을 주었을 때 MAC fair을 이용해 새로운 MAC을 만들 수 있는 것을 보여주면 깨는 것이 된다.

- 우선 메시지 블록의 순서를 바꾸어도 똑같은 결과가 나오면 안된다. 지금의 경우에는 이 점이 문제였다.

3. CBC-MAC

 

 - 순서가 바뀌면 암호문 또한 바뀌어야 한다. 그러기 위해선 CBC 모드를 이용해 MAC를 설계해야한다.

 - (m1, c1) -> (m1 || m2, c2) 를 유추하기 힘들다.

 - (m1 || m2 || m3, c3) -> (m1 || m2, c2) 또한 유추하기 힘들다.

4. HMAC

 - 이전에 배웠던 MDC를 가지고도 설계할 수 있다.

 - 우리가 m으로 프리 이미지 MDC(k,m) 해쉬값으로 키값을 알아내는 것은 매우 어렵다.

 - 여기서 출발한 것이 HMAC이다.

 - 기본적인 아이디어는 키와 메시지를 같이 해쉬 함수에 넣어 사용했다는 것이 기본적인 아이디어이다.