ISMS-P 인증심사원 - 해쉬함수

넓개 본다면 해쉬함수도 암호기술에 포함된다고 불 수 있으나 복호화가 되지 않는다는 점에서 차이가 있다.

그래서 해쉬함수를 일방향 암호화라고도 한다. 주로 무결성과 인증에 사용된다.

 

1.해시함수의 개요 및 요구사항

 

o 해시 알고리즘(H 혹은 Hash로 표기)은 임의의 길이의 입력 메시지를 고정된 길이의 출력값으로 압축시켜 주는 함수로, 데이터의 무결성 검증과 메시지 인증에 사용된다.

 

(1) 해시함수의 성질 - 해시함수 h가 가져야 할 기본 성질들로는 다음과 같은 것들이 있다.

구분	설명
일방향성	주어진 해시값 h에 대해서 ‘H(x) = h’를 만족하는 값을 찾는 것이 계산적으로 불가 능하다.
강한 충돌 회피성	주어진 x에 대해 'H(x)=H(y)'를 만족하는 임의의 입력 메시지 y (x와 같지 않은 값) 를 찾는 것이 계산적으로 불가능하다.

 

(가) 역상 저항성 - 주어진 임의의 출력값 y에 대해, y=h(x)를 만족하는 입력값 x를 찾는 것이 계산적으로 불가능하다.

(나) 두 번째 역상 저항성 - 주어진 입력값 x에 대해 h(x)=h(x'), x≠x'을 만족하는 다른 입력값 x'을 찾는 것이 계산적으로 불가능하다.

(다) 충돌 저항성 - h(x)=h(x')을 만족하는 임의의 두 입력값 x, x'을 찾는 것이 계산적으로 불가능하다.

 

(2) 전자서명에 이용되는 해시 함수의 특성

 

(가) 해시함수의 계산 효율이 양호해야 한다.

(나) 약 일방향성 (Weak onewayness) - 해시값 H로부터 h(M) = H되는 서명문 M을 찾는 것은 계산상 불가능해야 한다.

(다) 강 일방향성 (Strong onewayness) - 어떤 서명문 M과 그의 해시값 H=h(M)가 주어졌을 때 h(M')=H되는 서명문 M‘≠M을 찾는 것이 계산상 불가능해야 한다.

(라) 충돌 회피성(collision freeness) - h(M)=h(M')되는 서명문 쌍(M, M') (M≠M')을 찾는 것이 계산상 불가능해야 한다.

o 여기서 첫 번째 특성은 해시함수의 성능조건이고 두 번째, 세 번째, 네 번째 특성은 해시함수의 안전성에 관한 제약이다.

o 두 번째, 세 번째 특성은 해시함수의 역함수를 계산하는 것을 방지하는 기능을 말하며 네 번째 특성은 서명자가 서명문 M을 서명하여 전송하고 나중에 M'를 서명하여 전송하였다고 주장하는 이른바 내부 부정을 방지하기 위한 기능이다.

 

(3) 생일역설과 해시함수의 안전성 개념

 

o 해시함수의 특성 중 충돌 회피성은 서로 다른 서명문 M, M'의 해시값 H가 동일한 값을 갖지 않는다는 조건이나 실제의 경우 서명문 M의 길이가 해시값 H보다 훨씬 길기 때문에 충돌은 반드시 발생하기 마련이다.

o 이러한 충돌 회피성조건을 만족하기 위해서는 동일한 해시값 H를 갖는 서로 다른 서명문 M과 M'를 찾는 것이 어려워야 된다.

o 동일한 해시값 H를 갖는 서명문 M과 M'를 구하는 문제는 흔히 생일 공격으로 설명된다. 생일

이 같은 날일 확률이 1/2이려면 몇 명의 사람이 있어야 하나 그 결과는 23명이다.

o 일반적으로 해시값 H가 같아질 확률이 1/2이 되려면 서명문 M의 수가 몇 개나 있어야 하는 문제는 K = 1.17 M이다. 따라서 생일 공격을 차단하기 위해서는 적어도 128비트, 즉 264비트 서명문을 비교해야 하는 경우 이상이어야 한다. 예로 DSS에서는 160비트로 제한하고 있다.

 

(4) 해시 알고리즘 종류

- 일반적으로 쓰이는 해시 함수로는 MD5, SHA1, RIPEMD160, TIGER 등

구분	설명
MD5	널리 사용된 해시 알고리즘이지만, 충돌 회피성에서 문제점이 있다는 분석이 있으므로 기존의 응용과의 호환으로만 사용하고 더 이상 사용하지 않도록 하고 있다.
SHA1	DSA에서 사용하도록 되어 있으며 많은 인터넷 응용에서 기본 해시 알고리즘으로 사용된다.
SHA256, SHA384, SHA512	AES의 키 길이인 128, 192, 256 비트에 대응하도록 출력 길이를 확장한 해시 알고리즘이다.
RIPEMD128, RIPEMD160	RIPE 프로젝트의 RIPEMD나 MD4, MD5를 대신하기 위하여 디자인된 해시 알고리즘이다. 128 비트의 출력을 내는 RIPEMD128은 충돌 회피성에서 문제점이 있으며, RIPEMD160은 효율성은 떨어지지만 안전성을 높인 것으로 많은 인터넷 표준들에서 널리 채택되고 있다.
RIPEMD256과 RIPEMD320	각각 RIPEMD128과 RIPEMD160을 확장한 것이다.
HAS160	국내 표준 서명 알고리즘 KCDSA를 위하여 개발된 해시 알고리즘으로 MD5와 SHA1의 장점을 취하여 만들어진 것으로 현재 TTA 표준으로 제정 중에 있다.
TIGER	64 비트 프로세서에 최적화되어 있어 64 비트 프로세서에서는 매우 빠르다.

 

해시 알고리즘 소개

알고리즘	출력 길이	블록 크기	라운드 수	Endianness
MD5	128	512	64	Little
SHA1	160	512	80	Big
SHA256	256	512	64	Big
SHA384	384	1024	80	Big
SHA512	512	1024	80	Big
RIPEMD128	128	512	128	Little
RIPEMD160	160	512	160	Little
RIPEMD256	256	512	128	Little
RIPEMD320	320	512	160	Little
HAS160	160	512	80	Little
TIGER	192	512	56	Little

 

2.해시함수별 특징 및 구조

o n비트의 블록 암호를 이용하여 만들어진 해시함수들은 (n비트)단일 길이의 해시 값을 생성하는 것과 (2n비트) 이중 길이의 해시값을 생성하는 해시함수로 나누어 진다.

 

[표] n비트 블록 암호에 기초한 해시함수의 요약

해시함수	(n, k, m)	해시 비율
Matyas-Meyer-Oseas	(n, k, m)	1
Davies-Meyer	(n, k, m)	k/n
MDC-2(DES)	(64, 56, 128)	1/2
MDC-4(DES)	(64, 56, 128)	1/4

 

o 전용 해시함수란 블록 암호 혹은 모듈 연산과 같은 기존의 시스템 성분들을 다시 이용하지 않고 해시만을 목적으로 최적화된 수행을 하도록 디자인된 해시함수이다.

 

(1) MD4

 

o MD5의 초기 버전으로서, 입력 데이터(길이에 상관없는 하나의 메시지)로부터 128 비트 메시지 축약을 만듦으로써 데이터 무결성을 검증하는데 사용되는 알고리즘이다.

 

(가) MD4의 설계 원칙

 

1) 수학적인 가정 없이 안전한 해시함수를 설계한다.

2) 해시함수의 수행속도는 가능한 한 빨라야 한다. 특히, 소프트웨어로 구현했을 때의 속도를 고려한다.

3) 알고리즘은 단순하며 구현이 용이해야 한다.

4) little-endian 구조(word의 최하위 바이트가 low-address 바이트 위치에 있는 구조)를 고려한 알고리즘을 설계한다.

 

(2) MD5

 

o 128비트 출력

o 512비트 블록단위로 처리

o 4라운드 64단계로 구성

(가) MD4와 MD5의 차이

 

1) MD4는 16단계의 3라운드를 사용하나 MD5는 16단계의 4라운드를 사용한다.

2) MD4는 각 라운드에서 한번씩 3개의 기약함수를 사용한다. 그러나 MD5는 각 라운드에서 한번씩 4개의 기약 논리 함수를 사용한다.

3) MD4는 마지막 단계의 부가를 포함하지 않지만, MD5 각 단계는 이전 단계의 결과에 부가된다.

 

(3) SHA-1

 

o 160비트 출력

o 512비트 블록단위로 처리

o 4라운드 80단계로 구성

 

(4) RIPEMD-160

 

o 21워드 입력값을 5개의 워드 출력값으로 변환시킨다. 각 입력 블록은 동시에 각기 다른 압축 함수에 의해 실행된다.

o 임의의 길이의 메시지를 512비트-블록 단위 처리

o 160비트 출력

 

MD5, SHA-1, RIPEMD-160 비교

	MD5	SHA-1	RIPEMD-160
다이제스트 길이	128비트	160비트	160비트
처리의 기본단위	512비트	512비트	512비트
단계 수	64(16번의 4라운드)	80(20번의 4라운드)	160(16번의 5병행 라운드)
최대 메시지 크기	Unlimited	264 - 1 비트	264 - 1 비트
기약 논리 함수	4	4	5
덧셈 상수	64	4	9
Endianness	Little-endian	Big-endian	Little-endian

(5) 해시함수 공격의 종류 및 그 특성

구분	설명
일치블록 연쇄공격	새로운 메시지 M'를 사전에 다양하게 만들어 놓았다가 공격하고자 하는 메시지 M의 해시함수 값 h(M)과 같은 해시함수 값을 갖는 것을 골라 사용하는 공격
중간자 연쇄공격	전체 해시값이 아니라 해시 중간의 결과에 대한 충돌 쌍을 찾는다. 특정 포인트를 공격대상으로 한다.
고정점 연쇄공격	압축함수에서 고정점이란 f(H i - 1, x i) = H i - 1을 만족하는 쌍 (H i - 1, x i)를 말한다. 그러한 메시지 블록과 연쇄변수 쌍을 얻게 되면 연쇄변수가 발생하는 특정한 점에서 임의의 수의 동등한 블록들 x i를 메시지의 중간에 삽입해도 전체 해시값이 변하지 않는다.
차분 연쇄공격	1) 다중 라운드 블록 암호의 공격 - 다중 라운드 블록 암호를 사용하는 해시 함수에서, 입력값과 그에 대응하는 출력값의 차이의 통계적 특성을 조사하는 기법을 사용 2) 해시함수의 공격 - 압축함수의 입출력 차이를 조사하여, 0의 충돌 쌍을 주로 찾아내는 방법을 사용.

 

3.메시지 인증 코드(MAC)의 원리 및 구조

 

(1) 압축함수와 패딩기법

 

(가) 압축함수란

o 크기가 고정된 해시함수로 압축성, 계산의 용이성에 일방향 성질을 추가시킨 함수이다.

o 하지만 정의역이 제한되어 있어 고정된 크기의 입력값을 갖는다.

o 즉, m 비트 크기의 입력을 n비트 크기의 출력값으로 압축시킨다. ( m > n )

 

(나) 패딩기법

o 블록 단위로 해시하는 방법에서 일반적으로 블록 길이를 맞추기 위해 해시하기 전에 메시지에 대한 비트열이 패딩된다.

o 패딩 된 비트는 보내는 사람과 받는 사람이 동의한다면 전송 또는 저장될 필요가 없다.

구분	설명
패딩방법 1	o 입력: 비트길이가 n인 데이터 x. o 출력: 비트 길이가 n의 배수인 패딩된 데이터 x'. o 패딩: 비트 길이가 n의 배수가 되도록 필요한 만큼 x에 '0'비트들을 패딩한다.
패딩방법 2	o 입력: 비트 길이가 n인 데이터 x. o 출력: 비트 길이가 n의 배수인 패딩된 데이터 x'. o 패딩: x에 ‘1’비트를 패딩한다. 비트 길이가 n의 배수가 되도록 필요한 만큼 데이터 x에 ‘0’비트들을 패딩한다.

o 위의 패딩방법 1은 데이터의 뒤에 붙은 ‘0’비트가 패딩 ‘0’비트와 구별되지 않으므로 모호하다.

o 이런 방법은 다른 수단에 의해 수신자에게 데이터의 길이를 알려줄 수 있다면 좋은 방법이 될 수 있다.

o 패딩방법2는 패딩되지 않은 데이터 x와 패딩 된 데이터 x'사이에 일대일 관계가 있으므로 모호하지 않다.

 

(2) MD-method

 

(가) MDC 해시 함수의 안전성

o 안전하고 효율적인 MDC 해시함수 h( )는 다음 조건을 만족하는 함수이다.

 

1) 함수 h( )는 공개된 함수이고 어떠한 비밀키도 함수계산에 사용되지 않는다.

2) 변수 m의 길이에는 제한이 없고 h(m)의 길이는 l비트로 고정된다. ( l > 64 )

3) h( )와 m이 주어졌을 때 h(m)의 계산은 용이하여야 한다.

4) m가 h(m)이 주어졌을 때 h(m')=h(m)을 만족하는 m'( ≠m)을 찾는 것은 계산적으로 불가능해야 한다.

 

구분	입력	출력	해시율
MDC-2	n	2n	1/2
MDC-4	n	2n	1/4

 

(3) Universal One-Way Hash Function

 

o 일방향성 - 임의의 해시값 h(M)이 주어졌을 때 그것에 대해서 입력 메시지 M를 도출해 내는 것이 불가능한 조건

 

(4) 해시 함수를 이용하여 MAC을 설계하는 방법

 

(가) MAC의 안전성

o 안전하고 효율적인 MAC 해시함수 h( )는 다음 조건을 만족하는 함수이다.

1) 함수 h( )는 공개된 함수이고 비밀키 k가 함수 계산에 사용된다.

2) 변수 m의 길이에는 제한이 없고 h(k, m)의 길이는 l비트로 고정된다. (l ≥ 64)

3) h( ), m 그리고 k가 주어졌을 때 h(k, m)의 계산은 용이하여야 한다.

4) 여러 쌍의 {mi, h(k, mi)}가 관측되었다고 할지라도 이를 이용하여 비밀키 k를 도출한다거나 또는 임의의 m'( ≠mi)에 대해서 h(k, m')을 계산해 내는 것 역시 계산적으로 불가능해야 한다.

 

[표] 해시유형 표

해시 유형	설계 목적	이상적인 길이	공격자의 목적
OWHF	역상 저항; 두 번째 역상 저항	2n 2n	역상 생성; 같은 상을 갖는 다른 역상 생성
CRHF	충돌 저항	2n/2	충돌 생성
MAC	키 회복불능; 계산 저항	2t Pf=max(2-t, 2-n)	MAC키 찾기; 새로운(메시지, MAC) 생성

실제 심사에는 안전한 해쉬함수를 사용하고 있는지 확인하면 된다.

주로 정보보호시스템과 개인정보가 포함된 데이터베이스 등을 확인한다.