대칭키 암호를 이용한 해쉬함수에 대한 공격기법

대칭키 암호를 이용한 해쉬함수에 대한 공격기법

 

 

 

 

(1)   생일공격(Birthday Attack)

 

생일공격은 서명문의 길이가 해쉬값 보다 훨씬 길 경우에 충돌이 발생하게 되는 문제점에 이러한 해쉬 함수의 특징 중 충돌 회피성을 만족하기 위한 조건을 충족한다.

 

충돌회피성의 조건을 만족하기 위해서는 동일한 해쉬 값 H를 갖는 서명문 M과 M’을 찾는 것이 어려워야 하는데 생일공격은 이러한 M과 M’을 찾는 것을 구할 수 있게 한다.

 

생일공격은 생일모순에 근거하여 해쉬 함수를 공격하는 방법이다.

n명의 사람들 중,

동일한 생일을 가지는 2명이 존재할 확률을 P(n), 동일한 생일이 없는 경우를 Q(n)이라고 했을 때,                

                                                                                                                                      

 

의 연산을 반복적으로 수행하는 것을 의미한다. 여기에서 생일 모순은 임의로 모인 23명 중 생일이 같은 사람이 있을 확률이 50% 이상이 된다는 것을 의미한다.

 

 이러한 생일 공격을 막기 위해서는 해쉬 값의 길이를 늘이는 방법이 있다.

 

해쉬 값의 길이를 늘인다는 것은 메시지에 적용시킬 해쉬 함수를 바꾼다는 뜻이며, 해쉬함수는 임의의 길이의 메시지를 특정 길이의 해쉬 값으로 바꾸기 때문이다.

 

 

 

 

 

(2)   차분공격(Differential Attack)

 

차분공격은 입력과 출력 사이의 관계에 기반한 공격 방법이다. 차분공격은 특정 출력 차분을 유발하는 입력 차분을 탐색하는 통계적인 공격기법으로 블록암호와 해쉬함수 모두에 적용이 가능하다. 이 때 충돌을 발견하려면 출력차분이 0과 같아야 한다. 그러나 블록암호에 기반한 해쉬함수의 경우에는 추가적으로 출력차분이 입력 차분과 같은 것을 요구한다.

 

 

또한 차분공격은 마르코프 암호라고 불리는 특정 조건을 만족하는 반복적인 암호에만 적용이 가능한데, 현재 알려진 대부분의 반복적인 암호는 이 성질을 가지는 것으로 밝혀졌다. 그래서 잘 설계된 블록 암호에 대해 이 공격은 선택된 차분을 가진 많은 수의 평문이나 더 많은 기지평문에 기초하여 키를 발견한다.

 

 

다음은 차분암호 해독법(Differential Cryptanalysis)이다. 입력에 변화를 줘서 출력에 변화를 분석하는 방법인데, 두 개의 평문 블록들의 비트 차이에 대응하는 암호문 블록들의 비트 차이를 이용해서 사용된 키를 찾아내는 방법이다. 단순한 서명문과 암호만문으로는 불가능하며, 통계적 성질을 이용하는 데에 입력과 암호문의 차이를 쌍으로 비교를 하여 통계를 얻어낸다.

 

 

 

차분공격은 2개의 입력 I, I’에 같은 암호키 K를 이용하여 얻은 출력이 Q, Q’일 때

출력의 차이(differential) △Q = Q ⊕ Q’를 알고 있다.

 

 

이 때 입력의 차이 △I = I ⊕ I’는 K와 상관없는 값이다. 또한 △I에서 △Q 로 가는 가능한 입력쌍 I ⊕ K와 I’ ⊕ K를 미리 알고 있다.

 

 따라서 I ( I ⊕ K ) = ( I ⊕ I ) ⊕ K = K를 구할 수 있게 되는 구조를 갖는다.

 

이러한 사실은 특정 입출력 차이 패턴으로 입력의 특정 값에 발생한다는 사실에 기반을 두고 있다.

 

 

 

 

(3)   키 충돌 공격(Key Collision Attack)

 

 

키 충돌은 평문 P에 대해 E(K1,P) = E(K2,P) 가 되는 (K1,K2)쌍으로 보통 생일공격으로 찾을 수 있다. 또한 주어진 평문 P와 암호문 C에 대해 E(K2,E(K1,P))=C가 되는 하나의 키 충돌쌍을 만드는 것이 가능하다.  충돌 탐색은 키의 크기가 128비트보다 상당히 적다면 랜덤함수처럼 동작하는 어떤 블록함수에 대해서도 수행이 가능하다.

 

 

이러한 키 충돌 공격은 블록암호에 기반한 해쉬함수에만 적용이 가능하다. 만일 연쇄모드가 나쁘게 설계되었을 경우에는 키 충돌에 기반하여 공격이 가능하지만 해쉬함수가 좋게 설계되었다면 충돌을 쓸모없게 만들 수 있다.

 

하지만 이러한 것을 보장하기 위한 간단한 방법은 없기 때문에 모든 기법은 이 공격에 검증되어야 한다.

 

 

이외에도 여러가지의 공격 기법이 존재한다.