[보안] 해쉬 함수와 메시지 인증

1     해쉬 함수와 메시지 인증

1.1     해쉬 함수

-      임의의 길이를 갖는 메시지를 입력받아 고정된 길이의 해쉬 값을 출력하는 함수이다.

-      암호 알고리즘에는 키가 사용되지만, 해쉬 함수는 키를 사용하지 않으므로 같은 입력에 대해서 항상 같은 출력이 나온다.

-      입력 메시지에 대한 변경할 수 없는 증거 값을 뽑아냄으로써 메시지의 오류나 변조를 탐지할 수 있는 무결성을 제공하는 목적으로 주로 사용된다.

-      메시지를 일정 길이의 블록으로 분할 후 해쉬 함수에 입력하여 짧고 일정한 길이의 메시지 다이제스트를 생성한다.

-      메시지 다이제스트는 인증 알고리즘과 결합되어 디지털 서명 등에 사용되는 메시지 인증 코드를 생성한다.

해쉬 함수

1.1.1     해쉬 함수의 요구사항

-      메시지 다이제스트의 계산 효율이 좋아야 하며 구현의 실현성이 있어야 한다.

-      어떤 크기의 데이터 블록이든지 적용이 가능해야 한다

-      일방향성

s   메시지 다이제스트로부터 원래 메시지에 대한 계산이 불가능해야 한다.

-      강한 충돌 회피성 (Strongly collision-free)

s   다른 두 개의 메시지에 대하여 해쉬 함수를 적용한 결과, 항상 서로 다른 메시지 다이제스트를 출력해야 한다.

s   메시지 M과 해쉬 값 h(M)가 주어졌을 때, h(M)=h(M’)를 만족하는 다른 메시지 M’ (M≠M’) 를 만드는 것이 불가능하거나 적어도 무척 어려워야 한다.

 

1.2     안전 해쉬 알고리즘 (SHA: Secure Hash Algorithm)

-      디지털 서명을 위해서 미국에서 개발된 해쉬 함수로써 80단게의 논리 및 압축 함수를 수행한다.

-      160비트의 벡터와 512비트 블록을 입력 받아 160비트 메시지 다이제스트를 생성한다.

SHA

 

1.2.1     SHA 개정판

알고리즘	블록 길이 (비트)	메시지 다이제스트 길이 (비트)
SHA-1	512	160
SHA-256	512	256
SHA-384	1024	3844
SHA-512	1024	512

-      SHA-512는 메시지 다이제스트의 길이가 512비트인 SHA의 한 버전을 말하며, 다른 알고리즘보다 복잡하며 메시지 다이제스트의 길이가 가장 길다.

1.3     해쉬 함수 비교

-      MD5: 1992년 MIT에서 개발하였다.

s   단계의 수가 가장 짧아 빠르지만, 다이제스트 길이가 가장 짧기 때문에 취약하다.

-      SHA-1: 1995년 미국의 디지털 서명을 위해서 개발하였다.

-      RIPEMD-160: 1996년 유럽연합 프로젝트에서 개발하였다

-      HAS-160: 1998년 한국형 디지털 서명을 위해서 개발하였다.

	MD5	SHA-1	RIPEMD-160	HAS-160
다이제스트 길이	128비트	160비트	160비트	160비트
블록 길이	512비트	512비트	512비트	512비트
단계 수	64단계	80단계	160단계	80단계

1.4     메시지 인증 방법

1.4.1     관용 암호를 이용한 인증

-      인증은 관용 암호를 이용해서 간단하게 수행할 수 있다.

-      송신자와 수신자가 동일한 키를 가지고 있다고 가정하면 진짜 송신자만이 수신자에게 보내는 메시지를 성공적으로 암호화할 수 있다.

-      메시지가 오류 감지 코드와 순서 번호를 포함하고 있다면, 수신자는 메시지가 변경되지 않았고 순서도 틀리지 않았음을 확신할 수 있다.

-      메시지가 타임스탬프를 포함하고 있다면, 수신자는 메시지가 네트워크를 지나는 동안 소요되는 시간 지연 이외에는 고의적으로 지연되지 않았음을 확인할 수 있다.

1.4.2     메시지 인증 코드 (MAC: Message Authentication code)

-      메시지에 붙여지는 작은 데이터 블록을 생성하기 위해 비밀키를 이용하는 방법이다.

-      전송되는 메시지의 무결성을 확인하여 메시지에 대한 인증을 할 수 있다.

-      메시지의 인증에 쓰이는 작은 크기의 정보이다.

-      MAC 알고리즘은 비밀 키를 입력 받고, 임의 길이의 메시지를 인증한다.

-      출력으로써 MAC을 출력한다.

-      MAC 값 비밀키를 소유한 검증자의 허가에 의해 메시지의 데이터 인증과 더불어 무결성을 보호한다

-      메시지 인증코드의 응용

s   전자 문서의 전자서명에 적용함으로써 송신자의 신원을 확인할 수 있다.

s   전자 문서의 변조나 위조를 방지하는 무결성 서비스를 한다.

s   전자상거래 사실을 부인하거나 번복하지 못하게 하는 부인 방지를 한다.

1.4.2.1      대칭키 암호 기반의 메시지 인증.

-      PC A의 경우

s   메시지를 작성한 후 해쉬 함수를 적용하여 메시지 다이제스트를 생성한다.

s   암호화 키로 메시지 다이제스트를 암호화하여 메시지 인증 코드를 생성한다.

s   메시지와 메시지 인증 코드를 B에게 동시에 전송한다.

-      PC B의 경우

s   수신된 메시지에 해쉬 함수를 적용하여 메시지 다이제스트를 생성한다.

s   수신한 메시지 인증 코드를 복호화하여 메시지 다이제스트를 유도한다.

s   두 메시지 다이제스트가 일치하면 A가 생성한 메시지임을 증명한다.

대칭키 암호 기반의 메시지 인증

1.4.2.2      해쉬 함수를 이용한 공개키 기반의 메시지 인증

-      사용자 A 의 경우

s   메시지를 작성한 후 해쉬 함수를 적용하여 메시지 다이제스트를 생성한다.

s   A의 개인키로 메시지 다이제스트를 암호화하여 메시지 인증 코드를 생성한다.

s   메시지와 메시지 인증 코드를 B에게 동시에 전송한다.

-      사용자 B의 경우

s   수신한 메시지에 해쉬 함수를 적용하여 메시지 다이제스트를 생성한다.

s   수신한 메시지 인증 코드를 A의 공개키로 복호화하여 메시지 다이제스트를 유도한다.

s   두 메시지 다이제스트가 일치하면 A가 생성한 메시지임을 인증한다.

-      특징

s   메시지 인증 코드의 추가 전송으로 전송량이 증가한다.

s   메시지 다이제스트에만 공개키 암호 알고리즘을 적용하므로 메시지 인증 코드의 생성 및 검증이 빠르다.

s   현재 많이 사용되는 추세이다.

해쉬 함수를 이용한 공개키 기반의 메시지 인증

 

1.4.2.3      해쉬 함수가 없는 공개키 기반의 메시지 인증

-      메시지를 작성한 후 송신자인 A의 개인키로 메시지 전체를 암호화한다.

-      B는 공개키 링에서 A의 공개키를 선택하여 수신한 암호문을 복호화한다.

-      해독할 수 있는 평문을 얻으면 A가 생성한 메시지임을 인증한다.

-      특징

s   메시지 전체에 대하여 메시지 인증 코드의 생성 및 검증을 수행하므로 시간이 많이 소요된다.

s   별도의 해쉬 함수가 필요 없다.

해쉬 함수가 없는 공개키 기반의 메시지 인증

 

1.4.2.4      공유 비밀키 기반의 메시지 인증

-      송신자와 수신자는 메시지 인증에 사용할 비밀키를 사전에 공유한다.

-      송신자는 비밀키를 메시지에 추가하여 해쉬 함수를 수행한다.

-      비밀키를 제외한 메시지와 생성된 메시지 다이제스트를 동시에 전송한다.

-      수신자는 수신된 메시지에 비밀키를 추가하여 해쉬 함수를 수행한다.

-      생성된 메시지 다이제스트와 수신한 메시지 다이제스트가 일치하면 검증된 송신자가 송신한 메시지임을 인증한다.

비밀키 기반의 메시지 인증

 

1.5     HMAC

1.5.1     HMAC이란?

-      공유 비밀키 기반의 메시지 인증 알고리즘이다.

-      MD5, SHA-1, RIPEMD-160 또는 임의의 다른 해쉬 함수와 조합될 수 있다.

-      HMAC-MD5와 HMAC-SHA-1은 IP 보안 프로토콜의 인증 기능에 사용되는 필수 알고리즘이다.

-      HMAC의 안전성: 사용되는 해쉬 함수가 강한 충돌 회피성[1]을 갖고 있는 경우를 의미한다.

-      HMAC도 안전성을 보장한다.

1.5.2     HMAC의 절차

1)     메시지를 해쉬 함수가 요구하는 블록의 배수가 되도록 비트를 추가한다.

2)     비밀키의 길이가 블록 길이와 같도록 뒤에 0을 추가하여 확장 키를 생성하고, 패드-1[2]과 XOR 한다.

3)     단계1과 단계 2의 바이트 스트링들을 서로 연결한다.

4)     단계3의 결과에 해쉬 함수를 적용하여 중간 메시지 다이제스트를 생성한다.

5)     확장 키와 패드-2[3]를 XOR 한다.

6)     단계5의 결과와 중간 메시지 다이제스트를 서로 연결한다.

7)     단계6의 결과에 해쉬 함수를 적용하여 송신할 최종 메시지 인증 코드를 생성한다.

HMAC  절차

---

[1] 강한 충돌 회피성: 다른 두 개의 메시지에 대하여 해쉬 함수를 적용한 결과는 서로 다른 메시지 다이제스트를 출력한다.

[2] 패드-1: 00110110이 블록 길이만큼 반복된다.

[3] 패드-2: 01011100이 블록 길이만큼 반복된다.