[Encryption] 해쉬 함수

1. 해쉬함수

임의의 길이 이진 수열을 입력 받아 고정된 길이의 이진 수열을 출력

압축( Compression ) -> h:D→R, |D|>|R|    many to one => Collision

계산 용이성 h(x)

해쉬함수의 분류

2. 해쉬 함수의 특성

* MDC( Modification Detection Code )의 성질

- Preimage resistance (one-way)

주어진 y에 대하여 h(x) = y가 되는 x를 찾는 것이 어렵다.

- 2nd preimage resistance (weak collision resistance)

주어진 x에 대하여 h(x) = h(x')가 되는 x'≠x 를 찾는 것이 어렵다.

- Collision resistance (strong collision resistance)

h(x) = h(x')이 되는 x≠x'의 쌍을 찾는 것이 어렵다.

OWHF : preimage resistance, 2nd preimage resistance

CRHF : 2nd preimage resistance, collision resistance

* MAC( Message Authentication Code )의 성질

- 계산 저항성 (computation resistance)

(xi, hk(xi)) 쌍이 주어지든, 주어지지 않았든 간에

∀x≠xi 에 대하여 MAC 값 hk(x)를 계산하기 어렵다.

3. MDC 해쉬 함수의 기본 구성법

* 사전 처리

- 메시지를 고정된 길이 n으로 분할 m = m1m2K mr

- padding : mr'=mr||0K 0|| |m| if |mr| ≠ n

   mr' = 100K 0|| |m| if |mr| = n

* 기초함수( 압축함수 )를 이용하여 반복 처리 hi = f(mi, hi-1)

* 사후처리 : H(m) = g(hr) 선택적으로 적용

4. 블록 암호를 기초로 한 해쉬 함수

* Rabin Hash Function

- 메시지를 블록 암호에 적용될 입력의 크기와 동일한 블록으로 나눈다.

- m = m1m2K mt

- IV : 초기 벡터

- Meet-in-the middle attack이 적용된다.

M||H(M)이 관찰되면 M'=m1'm2'을 선택

m1'으로 IV를 암호화하고, m2'으로 H(M)을 복호화하여 그 값이 일치하면 메시지 위조 가능

*Davies-Mejer Hash Function

- Rabin 방식을 개선하여, '중간충돌' 공격으로부터 안전한 해쉬 함수

5. 전용 해쉬 함수

- 소프트웨어로 고속 동작이 가능한 형태로 제안

- MD4 : Rivest가 제안(1990), 취약점이 발견되어 폐기

- MD5 : MD4를 보강(1992)

- SHA : 미국 표준 해쉬 알고리즘(1993, SHA1(1995))

- RIPEMD-128, RIPEMD-160 : 유럽에서 제안

- HAVAL : 호주에서 제안

- HAS : 한국 표준

< MD4를 기준으로 작성된 표 >

6. MD5

* 기본구조

- b 비트 메시지를 512비트 단위로 분할

- 최종적으로 남은 메시지에 1000...을 삽입하여 448비트가 되게 하고 b mod 2⁶⁴를 삽입하여 512비트 생성

* 압축함수

- 각 mi를 32비트씩 분할하여 16개의 소블록 X[j]를 생성하여 압축함수에 입력

- 4라운드로 구성

- 128 비트 A,B,C,D를 메시지 블록으로 변환하여 128비트 출력

* Round 함수

7. MDC 이용 방법

* 무결성 제공

* 메시지 기밀성과 동반한 무결성 제공

* MD 암호화를 통한 무결성 검증