차분 공격 - 분석

1. 차분공격이란?

차분 공격이란 암호분석 방법의 한 종류이다. 차분이란 말은 말 그대로 차이, 즉 두 값 a, b 를 XOR 한 결과이다. 쉽게 생각해서 0 과 1 은 차이가 "존재"하기 때문에 XOR 한 결과가 1, 그리고 0과 0 혹은 1 과 1 의 차이는 "없음"이므로 XOR 결과가 0이다.

 

이러한 암호분석 방법의 존재 이유는 단 하나일 것이다. 전사공격보다 나은 방법. 즉 모든 값을 대입하여 원하는 결과를 얻는 무차별 대입 공격 (Brute Force Attack) 보다 더 빠르게, 효율적으로 공격을 수행하기 위해서 등장하였다. 

 

 

2. 차분분석

차분공격을 진행하기 위한 일련의 과정으로 DDT(Differential Distribution Table)을 작성하는 것, Propagation Ratio 구하기, 이를 바탕으로 차분 경로(Differential Trace)를 구성하는 것, 키복구 알고리즘을 작성하는 것이 있다. 먼저 DDT 부터 살펴보자.

 

 

2.1 DDT

DDT 란 차분분산표란 뜻으로, 고정된 값 x ⊕ x* = x' 를 만족하는 값들을 이용하여 특정 입력차분 값에 대하여 출력차분이 어떤 분포를 가지는지를 표로 나타낸 것이다. 아래 그림을 살펴보자.  

 

 

이것은 x ⊕ x* = 1011 으로 고정되어있으며 y = f(x), y* = f(x*), y ⊕ y* = y' 에 대하여 구성한 DDT 이다. 여기서 f(x) 는 S-Box 가 {1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16} 로 사용된 함수를 의미한다. 이 S-Box 는 흔히 암호 알고리즘에서 사용되는 방식중에서 [4-bit Input, 4-bit Output] 의 방식으로 사용한다. 

 

표를 해석해 보자. 먼저 예를 들어 a', 즉 입력차분이 A(1010)이 들어왔다고 하자. 그렇다면 출력차분이 될 수 있는 후보들은 1, 2, 8, B, E 가 있을 것이다. 하지만 균등하게 출력되지 않는다. 심지어는 출력값이 될 수 없는 값들도 있다. 바로 이 점을 차분공격에서 이용한다. 어느정도 수학적 확률을 가지고 "특정 입력차분에는 특정차분이 나올 확률이 높다!"라고 판단할 수 있다는 것이다. 또한 차분공격에서 가장 중요시하는 취약점이 있다. 바로 키와 XOR 된 후의 평문 (x ^ key) 와 (x* ^ key) 가 XOR 될 때 key 값은 무용지물이 되어버리는 상황이 발생한다.

 

 

바로 위와 같다. Key 에 대하여 입력차분과 출력차분이 일치해진다. 따라서 우리는 전 라운드의 출력차분은 현 라운드의 입력차분과 일치하며 Key 에 의존하지 않는다고 할 수 있다.

 

(참고 - DDT)

#include <stdio.h>

unsigned char sbox[16] = {1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16};
unsigned char ddt[16][16] = { 0, };

int main()
{
	for (int i = 0; i < 16; i++) {
		for(int j = 0; j < 16; j++) {
			ddt[i ^ j][sbox[i] ^ sbox[j]]++;  
		}	
	}

	for(int i = 0; i < 16; i++) {
		for(j = 0; j < 16; j++) {
			printf("%02d ", ddt);
		}
		printf("\n");
	}
}

 

 

2.2 Propagation Ratio

Propagation Ratio 란 말 그대로 전파비율, 즉 특정 입력차분에 대하여 특정 출력차분이 나올 확률을 의미한다. 그림을 보면서 이해해보자.

 

 

여기 하나의 암호 알고리즘이 있다. 제일 초기의 입력차분으로는 0x0B00 이 들어가게 된다. 화살표는 비트 0과 비트 1 중에서 1을 의미한다. 주의해서 봐야 할 것은 이 경로에는 모두 차분만이 존재한다. 파란색 글씨로 써진 것과 같이 차분이 입력으로 들어가는걸 보면 알 수 있다. 또한 앞서 이야기한 것처럼 key는 출력차분에 아무런 영향을 미치지 않는다. 

 

이 알고리즘에 대하여 Propagation Ratio 를 구해보자. Propagation Ratio 를 구하는 목적은 최적의 확률, 즉 제일 높은 확률을 선택해야 한다는 것이다. 우선 계산해보자. 위 그림에서는 이미 최적의 확률을 보여주고 있다. 또한 Propagation Ratio 는 다음과 같이 나타낸다.

 

 

쉽게 말해서 조건부 확률이다. (출력차분이 b' 일 확률 / 입력차분이 a' 일 확률) 이다. 위에서 구한 DDT 를 참고하여 구해보자.

 

 

위처럼 Propagation Ratio 가 27 / 1024 가 나온 것을 볼 수 있다. 이 27 / 1024 라는 확률이 가진 의미는 다음과 같다. 만약 차분이 [0000 1011 0000 0000] 인 평문 한 쌍을 입력값으로 넣는다면 출력차분이 [0000 0110 0000 0110] 이 될 확률이 27 / 1024 라는 것이다. 즉, 차분이 0x0b00 인 평문쌍 1024개를 준비한다면 그 중에서 27개가 출력차분이 0x0606 이 될 확률이라는 의미이다. 물론 준비하는 평문쌍이 "definetly random" 하다는 조건이 필요하지만 말이다. 어쨋든 적절한 1024개의 평문쌍을 준비한다면 수학적 확률에 의거하여 약 27개의 원하는 출력값을 얻을 수 있다.

 

3.  차분 경로 (Differential Trace)

이렇게 최적의 확률을 발견하여 Propagation Ratio 를 구하고 그에 따른 경로를 분석한 결과가 바로 차분 경로이다. 그냥 쉽게 생각해서 비트들이 암호 알고리즘이라는 미끄럼틀을 타고 내려온 그 흔적을 의미한다. 

 

 

4. 키복구 알고리즘

차분 경로까지 구성했다면 이제 이를 바탕으로 키를 복구하는 알고리즘을 짜야할 것이다. 기본적인 알고리즘에 대한 pseudo code 는 다음과 같다.

 

 

우리가 구할 수 있는 또는 알 수 있는 키는 8비트만큼이다. 따라서 첫번째 4비트를 L1, 다른 4비트를 L2 로 두고 그것이 마지막 출력값과 비교하여 특정값과 일치한다면 count 를 올려주는 식으로 진행한다. 여기서 포인트는 암호문으로부터 중간출력값을 비교하는 것이다. 암호문이 거꾸로 올라갈 때, 키와 XOR 되고, Permutation, S-Box 의 과정을 거친 출력값이 위에서 내려온 출력값과 일치하면 그 때 사용한 키의 count 를 올려주는 것이다. 더 쉽게 말하자면 암호 알고리즘을 하나의 긴 통로로 보았을 때, 중간에 특정 부분을 막고 양쪽 구멍에서 특정 값들을 넣어주어 그 막힌 부분에서 양쪽의 값이 어떻게 되는지를 비교하는 과정이라고 생각하면 된다.

 

후에 count 값들 중에서 가장 높은 count 값을 가진 candidate key(후보 키)가 right key 가 될 가능성이 수학적으로 가장 높다. 또한 이는 실제 right key 로 귀결된다.