Hash Function

[Hash Function]

해시 함수는 임의의 문자열(메시지)을 고정된 짧은 길이 문자열(해시 값)로 출력하는 단방향 함수이다.

Cryptographic Hash function = Hash function + Cryptographic properties

단방향 함수는 한 방향에서 작동하는 것으로 주어진 메시지의 해시 값은 계산하기 쉽지만 해시 값은 계산하기가 쉽지 않다.

해시 함수의 용도: 빠른 데이터 검색

해시 함수의 특징: 같은 입력 값이라면 같은 출력값이 나타남(결정론적 알고리즘)

-> 두 해시 값이 다르면 원래의 데이터도 다르다.

<해시 함수의 안정성 목표>

- 역상 저항성(one-wayness): 임의의 z가 주어질 때, H(x) = z인 x값을 찾기 어려워야 함

è  해시 값(z)의 복호화가 어려워야 함

- 제 2역상 저항성(2^nd pre-image resistance): 임의의 x가 주어질 때, H(y) = H(x)인 y(!= x)를 찾기 어려워야 함

è  문자열(x)가 있을 때, x의 해시 값과 동일한 다른 문자열(y)를 찾기 어려워야 함

- 충돌 저항(collision resistance): H(x) = H(y)인 x, y(x != y)를 찾기 어려워야 함

è  해시 값이 같은 서로 다른 문자열을 찾기 어려워야 함

따라서, 제 2역상 저항성 및 충돌 저항은 약하고 강한 충돌 저항으로서 알려져 있으나 충돌 저항성이 역상 저항성을 함축하는 것은 아니다.

1. 충돌쌍 공격 - 생일 역설(Birthday paradox)

어떤 사람과 생일이 같을 확률은 1/365 이다.

해시함수의 경우, 출력의 크기를 원하는 안정성수준의 두 배 크기로 정하고 있다.

[표1 - 안정성의 목표치]

Brute force 공격(무차별 대입 공격)은 약 2ⁿ 해시 연산에서 n비트 해시를 사용하여 일반 해시 함수에 대한 역상 저항성 또는 제2 역상 저항성을 찾을 수 있다. 생일 역설 때문에 충돌을 생성하는 무차별 대입 방식은 약 2^{(n / 2)}의 해시 연산에서 성공한다. 무차별 공격보다 해시 연산이 덜 필요한 공격은 공식적으로 암호 해시 함수의 중단으로 간주한다.

2. MD(Merkle-Damgard)방식

자주 사용해왔던 해시 함수는 MD5와 SHA-1으로 둘 다 Merkle-Damgard 구조를 기반으로 하여 압축 함수를 사용하는 반복 해시 함수

고정된 입출력 크기를 갖는 함수(압축 함수)를 이용하여 임의의 길이의 입력 값을 다루는 해시 함수를 구성하는 방법이다.

[그림1 - Merkle-Damgard schema]

<MD방식의 주요 성질>

- 압축 함수가 충돌 저항성을 가지면, MD방식으로 구성된 해시 함수도 충돌 저항성을 가짐(단, 적절한 패딩을 사용해야 함)

- 압축 함수가 역상 저항성을 가지면, MD 방식으로 구성된 해시 함수도 역상 저항성을 가짐

- MD-strengthening(for SHA-1)

è  일반적으로 메시지 맨 끝에 (반드시) 1을 붙인 후, 0을 계속 연접하여, 전체 블록이 압축 함수의 메시지 블록 길이의 배수-64 가 되도록 함

è  64 비트는 메시지의 길이로 채움(따라서, SHA-1은 2⁶⁴-1 비트 메시지까지만 압축할 수 있음)

3. 압축 함수 설계 방식

압축 함수만 설계하면, MD 방식으로 해시 함수를 구성할 수 있음

- 원전에서부터 설계하는 방식과 기존의 블록암호를 사용하는 방식이 있음

- 전자의 경우도, 일정한 블록암호 논리를 사용하여 설계

블록암호 사용시 유리한 점

-  잘 알려진 블록암호에 기반하므로, 이에 맞먹는 안전성을 확보할 수 있음

-  압축함수 설계를 따로 할 필요가 없음

-  블록암호, 해시함수를 동시에 사용하는 환경에서, 블록암호만 구현하면 됨

-  단, 전용 해시함수에 비해 속도가 낮음

70년대말 ~ 90년대초 : DES 사용

DES : 블록 사이즈가 작고(64비트), 취약 키들이 발견되어 압축 함수 구성에 방해요소

현재 : AES 사용

AES : 128 비트 블록사이즈, 취약 키가 발견되지 않음

블록암호 출력 크기 n에 대해, 압축 함수(해시 함수)의 출력 크기

- n인 경우, SBL(single block length) – 압축 함수

- 2n인 경우, DBL(double block length) – 압축 함수

n비트의 충돌저항성이 요구될 때, 출력 사이즈는 2n 비트로 설계해야 한다.

- Birthday 공격 때문

- 대표적인 DBL 압축 함수

MDC-2, MDC-4(block cipher / w n-bit keys) /

Tandem-DM, Abreast-DM(block cipher / w 2n-bit keys)

4. 전용 해시 함수

Ÿ   MD4

- R.Rivest 설계(1992): 128비트 출력, MD5, SHA 해시 함수 등에 영향을 줌

- 효율적인 충돌쌍 공격이 발견됨: 더 이상 사용 불가

Ÿ   MD5

- R.Rivest 설계(1992): 128비트 출력, 실제 공격(인증서 위조)에 적용 가능한 충돌쌍 공격이 발견됨(Crypto '09)

5. Merkle-Damgard 이후

기존 해시 함수 설계는 전용 압축 함수, 또는 블록 암호 기반 압축 함수를 설계한 뒤, 이를 MD 모드에 적용하는 방식이었다.

이후 MD 설계 방식에 대한 구조적인 취약성이 드러났다.

<취약성 발견>

-    Joux's multicollision attack (Crypto 2004)

-    Long-message second preimage attack (Eurocrypt 2005)

-    Herding attack (Eurocrypt 2006)

취약성이 발견된 이후, 새로운 형태의 해시 운용모드가 다양하게 제안되고 있다.

ex) 블록암호의 키를 고정해서 쓰는 방식(random permutation model)

- 키스케줄링 비용을 절감, 블록암호의 연관키 공격에 대한 취약점 해소