기사자격증(알기사, 해시함수의 응용1)

해시함수

1. 임의의 길이의 입력값을 고정된 해시값으로 출력

 

2. 다대일 대응 → 충돌이 일어날 수 밖에 없음 → 비둘기집 원리

비둘기집 원리 : n+1마리의 비둘기가 n개의 비둘기집에 들어갈 경우 적오도 한 비둘기집에는 두 마리의 비둘기가 들어가있다는 원리

 

3. 일방향성을 가짐 → 충돌 내성을 가질 필요가 있음

충돌 내성 : 충돌 발견이 어려운 성질

 

4. msg 값이 달라지면 해시 값도 달라짐

 

5. 해시함수의 보안 요구 사항

- 1. 프리이미지 저항성 2. 제 2 프리이지 저항성, 3. 충돌 저항성

- 프리이미지 저항성 : y값이 주어질 때 y = h(x)에 해당하는 x값을 찾기 어려워야한다.

- 제 2 프리이미지 저항성 : msg를 쉽게 위조할 수 없는 성질, 공격자가 x를 알고 있는 상태에서 h(x) = h'(x), x=x'일 때 x'를 찾기 어려워야 한다.

- 충돌 저항성 : 아무것도 주어지지 않을 때 h(x) = h'(x)일 때 (x,x')을 찾기 어려워야 한다.

 

6. 해시함수의 특성

1. 고속계산 - 성능의 조건

2. 약 일방향성 - y=h(x)에서 x를 찾는 것이 어려워야 한다.

3. 강 일방향성 - y= h(x) h(x')일 때 x !=x'를 찾는 것이 어려워야 한다.

4. 충돌 회피성 - y = h(x) = h(x')일 때 (x,x') 찾는 거이 어려워야 한다.

2,3,4는 안정성의 조건이고 2,3은 역함수 계산 방지를 위한 조건이고 4은 부인방지를 위한 조건이다.

 

7. 해시함수의 관계

- 충돌 저항성은 제 2프리이미지 저항성을 보장한다.

- 프리이미지 저항성과 제 2 프리이미지 저항성은 서로 보장하지 않는다.

- 충돌 저항성은 프리이미지 저항성을 보장하지 않는다.

 

 

8. 해시함수의 종류 - 키가 있는 해시함수, 키가 없는 해시함수

8-1. 키가 없는 해시함수 : 블록암호로 구성, 전용 해시함수, 모듈 연산기초 해시함수

8-1-1 전용해시함수 : SHA-1, HAVAL, RIPEMD 등

SHA-1, HAVAL-128,160, HAVAL = MD4를 기반으로 만들어졌다.

MD5 : 512비트의 입력값을 128비트의 값으로 출력

→ 충돌 내성을 갖기에는 길이가 짧고, 생일 공격에 취약

생일공격 :　강한충돌내성(순서쌍(x,x')을 찾는공격을 막는 것)을 깨려는 공격

8-1-1-1 SHA 함수 : DSS에서 사용하기 위해 NIST에서 개발

SHA 함수는 SHA-1, SHA-2, SHA-3가 있다.

SHA-2 함수에는 SHA-224, 256,384,512가 있다.

SHA-1 함수와 SHA-2 함수 비교

구분	SHA-1	SHA-224	SHA-256	SHA-384	SHA-512
MD 길이	160	224	256	384	512
최대msg길이	264-1	264-1	264-1	2128-1	2128-1
블록길이	512	512	512	1024	1024
워드길이	32	32	32	64	64
단계	80	64	64	80	80

 

8-1-1-2 기타함수

- Tiger :SHA-1, MD5보다 속도가 빠른 함수, 64비트 시스템에서 수행하기 위해 함수 개발

- HAVAL : 1024비트의 블록을 128,160,192,224,256비트의 MD로 출력

- HAS-160 : 한국에서 개발한 해시함수로써 512bit의 입력값으로 160 bit 출력

8-1-1-3 키가 없는 해시함수들의 비교

항목	MD5	SHA-1	RIPEMD-160
Digest 길이	128	160	160
처리단위	512	512	512
단계수	64(16*4)	80(20*4)	160(20*4*2)
최대 msg 길이	무한	264-1	264-1
앤디언	리틀 앤디언	빅 앤디언	리틀 앤디언

 

8-1-2 모듈연산 기반 해시함수

- H/W, S/W에서 사용가능

- 속도가 느리고 안정성을 보장 할 수 없음

 

8-2 키를 사용하는 해시함수

- 키를 사용하는 해시함수는 msg 인증 기능을 가진 함수

- 함수 자체의 안정성과 키의 비밀성에 안정성을 두고 있다.

- 블록암호에 기반을 둔 메시지 인증 알고리즘은 CBC모드를 이용한다.

 

9. 암호학적으로 해시함수의 응용

1. 무결성 점검

- 메시지 또는 문서의 무결성을 보장하기 위해 해시함수를 사용한다.

- 새로운 msg 다이제스트와 이전 msg 다이제스트를 비교 하였을 때 값이 일치하면 원래 msg가 변경되지 않았다는 것을 알 수 있다.

 

2. S/W 변경여부 확인

- 일방향 해시함수를 이용해 HASH 값을 비교해서 S/W 변경여부를 확인한다.

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

- 키가 있는 해시함수에서 주로 사용

- 송, 수신자간에 정보 인증, 비밀키를 공유하기 위해 사용

4. 전자서명

 

10. 랜덤 오라클 모델

- 임의의 길이를 갖는 메시지 + 오라클 = MD

- 이미 다이제스트가 존재하는 메시지가 주어지면, 저장되어 있던 다이제스트를 제공

- 새로운 msg에는 새로운 다이제스트가 생성 → 모든 다이제스트는 독립적이어야 함

→ 오라클이 다이제스트를 만들기 위해서는 공식이나 알고리즘을 이용하면 안된다.

- 랜덤 오라클의 공격난이도

1. 프리이미지, 제 2 프리이미지 공격 : 2n

2. 충돌 저항성 : 2n/2

 

11. 해시함수의 공격

- 무차별공격 : 약한 충돌을 깨기 위함으로써 모든 값을 다 대입해서 msg를 알아내기 위한 공격

- 일치블록 연쇄공격 : h(x)와 같은 해시값 x'를 대입해 사용

- 중간자 연쇄 공격 : 해시 중간값에 대한 충돌쌍을 찾는 공격(특정 포인트를 공격대상으로 한다.)

- 고정점 연쇄블럭 : 메시지 블로과 연쇄블럭 쌍을 얻게되면 연쇄변수가 발생하는 특정 지점에서 동등한 블록 xi를 메시지 중간에 삽입해도 전체 해시값이 변하지 않는 것을 이용한 공격

- 차분 연쇄공격

12. 일방향 해시함수로 해결할 수 없는 문제

- 일방향 해시함수로는 거짓행세를 검출하지 못한다. → MAC과 전자서명으로 인증을 해야 한다.