[컴퓨터보안] MAC_Hash

메시지 인증은 메시지에 대한 무결성과 누가 메시지를 보냈는지에 대한 인증을 하기 위해서 사용된다.(발신자 신원 확인 + 부인방지)

보안요구사항을 고려하여 세 가지 방식이 있다.

1. 메시지 암호화

2. MAC(메시지 인증 코드)

3. hash function

메시지 암호화

 메시지 암호화 자체만으로 인증 수단이 된다.

 대칭키 암호를 사용할 경우 기밀성이 보장된다.

 공개키 암호를 기밀성을 보장할 수 없다. (누구나 공개키를 알기 때문에) 

 더군다나 공개키 암호는 속도도 느려서 주로 대칭키 암호를 많이 사용한다고 한다.

MAC (메시지 인증 코드, Message Authentication Code) 

MAC 특징 

MAC 은 암호학적 checksum 이라고도 불린다. 

가변길이 메시지 M 을 비밀 키 K 를 통해 압축하여 고정된 길이 로 만든다.

메시지에 추가되어서 서명 역할을 한다. 이를 통해 수신자는 메시지가 발신자로부터 왔다는 확신을 얻을 수 있다.

메시지에 대한 무결성과 인증 기능을 한다.

송수신자는 비밀키 K를 알고 있는 상태이다.

MAC 은 many-to-one function 이다.

서로 다른 메시지들이 같은 MAC 값을 가지는 경우도 생길 수 있지만 그 메시지들이 어떤 것인지 알아내는 것은 어렵다.

*MAC 은 디지털 서명이 아니다.

MAC 요구사항

1. 어떤 메시지와 해당 MAC 을 알고 있다해도 동일한 MAC 을 가지는 다른 메시지를 찾는 것이 어려워야한다.

2. MAC 은 균일하게 분포되어야 한다.

3. 메시지 중 한 bit 라도 변경되면 MAC은 전체적으로 다 바뀌어야한다.

Hash Function

임의의 메시지를 고정된 길이로 압축시키는 것이다. 

일반적으로 hash function 은 공개되어있고 키가 없다고 가정한다.

메시지 변경을 감지하는데 사용된다.(메시지에 대한 무결성 체크), 인증은 못함

디지털 서명을 생성할 때 자주 쓰인다.

아래의 그림은 디지털 서명에서 hash 가 사용되는 모습을 보여준 것이다.

Hash 요구사항

1. 메시지 M 의 길이에 상관없이 다 적용되어야한다.

2. 고정된 길이의 output 인 h 가 생성되어야한다.

3. 메시지 M 에 대해서 hash 계산이 빨리 되어야한다.

4. h=H(x)  x 가 주어졌을 때 hash 를 통해 h 를 구하는 것은 쉽지만 h 를 통해 x를 구하는 것은 어려워야한다.

5. 메시지 x 가 주어졌을 때 x와  동일한 hash 값을 가지는 y 라는 메시지를 찾는 것이 어려워야한다.

6. hash 값이 같은 두 메시지 x,y 를 찾는 것이 어려워야한다.

기본적인 hash function 은 XOR 연산을 통해 만드는 것인데 메시지 조작의 위험성이 있기 때문에 안정성이 낮다.

Birthday paradox(=Birthday problem) 

임의의 사람들이 모였을 때 같은 생일을 가진 두 명이 존재할 확률을 구하는 것이다.

직관적인 생각의 경우 1년이 365일 이기 때문에 365명 정도가 모여야 같은 생일을 가진 사람이 존재한다 생각할 수 있지만

실제로는 23명 정도만 있으면 임의의 두 사람이 같은 생일일 확률이 50% 가 넘게 된다.

예를 들어 두 학생의 생일이 서로 다를 확률은

1 - 생일이 같을 확률 = 1- 1/365 가 된다.

n명의 생일이 모두 다를 확률은 아래와 같이 계산된다.

생일이 같은 사람이 존재할 확률은 

 으로 구할 수 있다.

Birthday Attack(생일 공격)

hash 함수에서의 충돌(collision) 을 찾을 때 쓰는 공격 방법 중 하나이다.

Birthday paradox 에 근거하여 hash function 을 공격하는 방식이다.

같은 hash 값을 가지는 두 input x_1,x_2 를 찾아내는 것이 목표이다.

hash 가 m 비트로 구성되어 있으면  일반적으로 2^m 개수 만큼을 다 조사해야된다고 생각할 수 있지만

Birthday paradox 의 확률에 기반하면 실제로는 2^(m/2) 개 만큼만 조사해보면 해시 충돌을 발견할 수 있다는 것이다.

결과적으로 Birthday Attack 과 같은 공격들이 있기 때문에 더 큰 MAC 이나 Hash 가 필요하다는 것을 알 수 있다.