Chapter 03. 공개키 암호와 메시지 인증 - 3.2 안전 해시함수(1)

하루에 1개의 소단원씩 끝내는건 도저히 못하겠다. 

뒤로 갈수록 점점 더 어렵다. ㅠㅠ

정보보호에서 암호학이 가장 자신있는 분야라고 생각했는데, 암호 챕터가 끝나면 좀 쉬워지지 않을까 하는 기대를 하고 있다. ㅠㅠ 

안전 해시함수에 대한 원리를 이해하기 위해서 며칠동안 붙잡고 있었다. 

그래서 100%이해한 것 같지는 않지만 어느정도 이해한 내용을 적기로 했다. 

그래서 안전해시함수 소단원을 끝내지 못했지만 1/2 포스팅 하겠다. 

 

---

Chapter 03. 공개키 암호와 메시지 인증 - 3.2 안전 해시함수(1)

 

□ 안전 해시함수(Secure Hash Function)

 ㅇ 메시지 인증, 디지털 서명 등에 활용된다. 

 ㅇ 해시함수의 목적은 파일, 메시지, 데이터블록에 대한 지문(Finger Print)을 생성하는 것이다. 

 

□ 해시함수 H의 요건 

1. H는 어떠한 크기의 데이터블록에도 적용될 수 있어야 한다. 
2. H는 일정한 길이의 출력을 생성해야 한다. 
3. H(x)는 어떤 x에 대해서도 개산이 쉬워야 하며 소프트웨어나 하드웨어에서 실제로 구현할 수 있어야 한다. 
4. 어떤 주어진 값 h에 대해서 H(x)=h가 성립되는 x를 찾는 것이 계산적으로 불가능해야 한다.(일방향 성질)
5. 주어진 블록 x에 대하여 H(x) = H(y)를 만족하는 y(≠x)를 찾는 것이 계산적으로 불가능해야 한다. (충돌 저항성)
6. H(x) = H(y)를 만족하는 (x,y)쌍을 찾는 것이 계산적으로 불가능해야 한다.(강한 충돌 저항성)

ㅇ 1~5호 조건을 만족하는 해시함수를 약한 해시함수라고 하며, 1~6호 조건을 모두 만족하는 해시함수를 강한 해시함수라고 한다. 6호 성질은 생일공격(birthday attack)을 막아준다. 

 

□ 해시함수 보안

ㅇ 현재 128 비트 코드는 안전성이 보장되지 않는다. 

ㅇ 160 비트는 계산적으로 충돌을 찾아내기 위해서 4000년 이상이 걸리지만, 급속히 발전하는 컴퓨팅 기술로 인하여 160비트도 더이상 안전하다고 할 수 없다. 

 

□ 단순 해시함수

 

ㅇ 단순 해시함수의 형태는 다음 그림과 같다.

단순 해시함수 구조

C_i : 해시코드의 i번째 비트, 1≦i≦n

m : 입력의 n비트 블록의 수

b_ij = j번째 블록의 i번째 비트

 

ㅇ 이 단순 해시 함수는 데이터 무결성에 주로 사용되는데, 각 n-비트 해시값이 나타날 가능성은 동일하므로, 한 데이터 오류가 해시값에 변화를 초래하지 않을 확률은 2^(-n) 이다. 

ㅇ 대부분의 텍스트 파일은 각 바이트의 첫번째 비트가 항상 0이므로, 128 비트 해시값이 사용될 경우 해시함수의 효과는 2^(-128)이 아니라 2^(-112)로 안전성이 현저히 떨어진다. 

ㅇ 안전성 저하의 문제를 개선하기 위하여 다음과 같은 절차를 추가하였다. 

1. n-비트 해시값을 0으로 초기화한다. 
2. 뒤에 이어지는 n-비트 데이터 블록에서 현재 해시값을 왼쪽으로 한 비트 회전한다. 
3. 블록을 해시값에 XOR한다. 

  -> 이 과정은 데이터 무결성을 검증하기에 좋은 방법이지만, 아래 그림과 같이 관용암호 사용하는 MAC 메시지 인증 방식에는 적절하지 못하다. 공격자가 메시지를 탈취하여 수정한 후, 자신이 수정한 메시지에 해시코드를 덧붙여서 보낸다면, 인증할 방법이 없기 때문이다.  

 

ㅇ미국 표준국(National Bureau of Standard)에서 64비트 메시지를 단순 해시함수와 암호블록체인모드(CBC)를 결합한 암호 방식을 제안하였다. 

 

메시지 X1|X2|X3|...|Xn 의 마지막에 해시코드 C를 덧붙인다.  

C = Xn+1 = X1 ⊕ X2 ⊕ X3 ⊕... ⊕Xn

 

다음으로 암호화된 메시지 Y1|Y2|....|Yn 을 생성하기 위해 전체 메시지와 해시코드를 암호화한다. 

 

Y1 = E(K, X1⊕IV)

Y2 = E(K, X2⊕Y1)

Y3 = E(K, X3⊕Y2)

....

Yn+1 = E(K, Xn⊕Yn)

 

따라서 다음이 성립된다. 

 

X1 = IV⊕D(K,Y1)

X2 = Y1⊕D(K,Y2)

....

Xn+1 = Yn⊕D(K,Yn+1)

 

그런데 Xn+1은 해시코드이므로

 

Xn+1 = X1 ⊕ X2 ⊕ X3 ⊕... ⊕Xn

        = IV⊕D(K,Y1)⊕Y1⊕D(K,Y2)⊕......⊕Yn⊕D(K,Yn+1)

이 성립된다. 

 

 

XOR 연산자는 순서를 변경해서 계산해도 같은 값이 나오기 때문에 암호분 블록이 치환되어도 해시코드 값은 변하지 않는다.