170328 해쉬함수

1. 해시함수(hash function)

사람이 자신을 증명할 때 지문을 사용하는 것 처럼 전자서명등과 함께 이용하여 인증에 효율적으로 활용하기 위해 사용한다.

<수학적 조건>

적은 비용: 어떤 입력 x 에 대해 hash(x)를 계산하기 쉬워야 함.

일방향(단방향)성: hash(x)=y 에서 x 값을 찾기 어려워야 한다.

약한 충돌 방지: hash(a)=hash(b) 이면서 a 와 다른 b 를 찾기 어려워야 한다.

강한 충돌 방지: hash(a)=hash(b) 이면서 a!=b 인 a 와 b 를 찾기 어려워야 한다.

해시함수는 압축을 한다는 특징을 가지고 있다. 어떤 한 내용(긴 문장)에 대해 해시함수를 사용하면 압축이된 길이가 고정된 결과물(Digest)이 나오게 되는데 결과물을 보고 압축되기 이전에 내용을 알 수 없어야 한다. 또한 서로 다른 내용으로 압축한 결과물은 서로 달라야 한다.

하지만, 압축할때 충돌이라는 현상이 발생한다. 충돌은 무엇일까?

* 충돌

 : 입력되는 긴 문장은 압축되어 나오는 결과문장보다 공간이 크게 되는데 , 이때 출력된 결과가 같을 경우 충돌이라한다.

이러한 경우 서로 다른 데이터가 동일한 해시값에 매핑되기 때문에 문제가 발생한다. 이때 해시값으로 서로다른 데이터를 판단하기 힘들다. 동일한 데이터로 인식 하거나 오류가 날 것 이기 때문이다. 또한 충돌을 이용한 충돌공격에 대한 위험성도 있다.

충돌공격에 대한 안전성은 해시함수를 거꾸로 거슬로올라가 원래 내용에 대한 확인이 어려울 경우 어느정도 안전하다고 판단한다.

http://www.slavasoft.com/hashcalc/에서는 파일에 대한 해시값을 알아 볼수 있도록 툴을 제공한다.

해시에 대한 이해로 아무 txt 파일을 만들고 툴에서 사용해보면 해당 해시값이 산출된다. 이때 파일에 대한 제목을 바꿔도 내용이 그대로라면 해시값은 그대로이다. 반대로 파일의 이름이 달라도 제목이 같다면 파일의 해시값은 같다는걸 확인 할 수 있다.

이는 운영체제서 사람에 눈에 보이는 파일과 하드디스크에 적재되있는 파일의 이름이 직접적으로 연결이 되있는 것이 아니고 탐색기등을 통해 연결시켜 주는것이기 때문이라 한다. 내용은 당연히 하드디스크에 그대로 저장되기 떄문에 내용이 바뀌면 해시값에 영향을 준다.

[해시함수의 구조]

해시함수는 MAC에서 올바른 사용자에게 송신된 것인지 메세지를 인증하는 부분과 MDC 부분으로 메세지에 대한 무결성을 보장한다 .

- MDC (Modification Detection Code) : 메세지에 내용에 대한 변경을 감지한다.

수신한 메세지의 MDC를 계산하고 송신측의 MDC와 비교하여 무결성을 검사한다.

수신한 메세지를 암호학적인 해시함수로 계산하여 메세지 다이제스트 값을 산출(이것이 보통 MDC값이다)하고 송신자와 비교

MDC의 성질

1. Preimage resistance(One Way Hash Function ) : 주어진 원문을 해시값으로 바꾸었을때 해시값을 보고 원문을 찾기 힘들어야 한다.

( y(주어진 원문),  h(x)=y 일때 x를 알기 힘들어야 함.)

2. 2nd preimage resistance (weak collision resistance) : 서로 다른 문서에대해 동일한 해쉬값으로 인한 충돌 방지. x에 한정된 상황

( x(주어진 원문), h(x)=h(x')일 때, 'x!=x 를 찾기 어려움)

3. Collision resistance (strong collision resistance) : 동일한 해쉬값을 갖는 서로 다른 파일을 찾기 어려움 (충돌방지)

( h(x)=h(x') 일때 , x!=x' 를 찾기 어려움)

* MDC 는 무결성에 대한 인증은 가능하지만 누가 어떻게 보냈는지에 대한 출원인증은 안됨 → MAC로 해결

- MAC (Message Authentication Code) : 수신자가 받은 메세지가 송신자가 보낸 메세지와 

동일한지 확인하게 해줌.

MAC의 성질 

computation resistance(계산성 저항성) : x!=x' 일때 키값을 찾기 어렵다.

MAC 이용하기 mdc와는 다르게 키값으로 메세지인증을 한다.

MDC함수 기본 구성

메세지가 사전처리되어서 압축함수로 반복되어 내용이 고정된길이로 압축되어 출력된다.

- 사전처리

: 메세지를 고정된 길이 n 으로 분할, 패딩넣기

- 반복처리

: 압축함수를 이용하여 반복처리

- 사후처리

 : H(m) = g(hi) 선택적 적용

MDC 이용 하기 1. 무결성 2. 기밀성 + 무결성 3. 암호화를 통한 무결성 인증

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

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

meet in the middle attack 의 문제 발생

 : 암호화와 복호화를 반복하면서 가정한 해쉬값을 찾아낼 수 있기 때문에

- Davies-Mejer Hash Function : rabin을 개선 xor 사용

2. MD5 : 임의의 메세지를 입력받아 128비트의 고정길이 출력값을 낸다.

http://blog.doortts.com/65 md5의 한계

입력된 메세지를 패딩하여 512비트 단위로 나누어 떨어지게 만든다.

패딩부분은 메세지 다음에 1을 붙이고 512의 배수의 길이보다 64 비트가 적은 곳까지 0으로 채운다(b mod 64)

나머지 64 비트는 최초의(오리지널) 메시지의 길이를 나타내는 64 비트 정수

[ 메세지 + 패딩(512n -64bit) + 메세지의 길이(64bit) ] ← 512bit 단위

압축함수 : 하나의 메세지 블록을 4단계 라운드로 나누어 처리한다 

512비트 단위로 만든 블록을 라운드에서 연산

라운드 내부에서 연산되는 작업은 위와 같다.

3. SHA(Secure Hash Algorithm)

md5를 변형한 것 

패딩은 512비트 단위로 한다.

512개의 비트를 80개의 32비트 블록으로 확장

초기치 160비트를 메세지를 이용하여 반환

4. 해시함수에 대한 공격.

가정 1. 

m 은 서명자가 받아들일 수 있는 내용

m' 은 불법적인 이득을 취할 수 있는 내용

h(m)=h(m') 이 성립하게 되면 서명자는 m 에 서명했지만 m'에도 서명한게 되어버린다.

가정 2.

Birthday Paradox:어느 집단에서 생일이 같은 한쌍이 나올 확률은 개체수가 많을 수록 확률이 높다.

이는 인원이 조금만 늘어나도 복잡성이 기하급수적으로 증가하는 것을 알 수 있다.

이는 무결성을 해치는 요소이며 보안에서 무결성을 공격하는 방법으로 사용한다. MD5 의 한계가 바로 이 생일역설에 있는데

전세계가 네트워크로 묶이고 객체수가많아지면서 그 충돌 확률이 기하급수적으로 늘어나 몇초 단위로 충돌이 발생해 버린듯 하다. 생일역설은 해쉬함수 알고리즘에 대한 충돌에 대해 충분히 발생 할 확률이 많으며 공격당할 여지가 있다는걸 말해준다.