Contents
- 차등 암호분석 개요
- TDES의 Sbox 차이 분석
- 입출력값의 차이를 선택하는 방법
- TDES의 차등 암호분석
- 보조키 비트 복구 알고리즘
- 키 비트를 모두 복구하는 방법
- 블록암호 설계원칙
- References
차등 암호분석 개요
차등 암호분석(Differential Cryptanalysis)은 DES를 분석하기 위해 개발되었으므로, DES 범주 내에서 검토해보자. Sbox를 제외한 DES의 다른 모든 요소는 선형이라는 것에 주목하자. 물론, Biham과 Shamir가 차등 암호분석을 여러 버전의 DES에 적용시켰을 때 원래 버전을 제외하고는 모두 보안성이 약화되었다는 것을 확인하였다는 점에서 선형 부분이 보안성에 기여하는 부분이 없다고 할 수 없다. 그러나, 선형 부분은 상대적으로 쉬운 부분에 속하기 때문에 단 하나 뿐인 비선형 요소에 집중하는 것이다.
여기서는 DES가 아닌 [1]에 제시된 TDES에 차등 암호분석을 적용할 것이지만 기본적인 동작 원리는 같다. 즉, 단일 Sbox에 대한 공격을 여러 Sbox에 대한 공격으로 확장시키고, 이를 다시 여러 회전에 대한 공격으로 확장시키는 것이다. 이는 어려운 문제로 보이지만 입력과 출력의 차이에 초점을 맞춘다면, 일부 Sbox를 “활성화”시키고 다른 것은 “비활성화”시킬 수 있다. 따라서 그 공격을 단일 회전에 대한 공격으로 확장할 수 있다. 그리고 이를 다시 다수의 회전에 대한 공격으로 확장하기 위해 현재 회전의 출력 차이가 다음 회전에 유용한 형식이 되도록 현재 회전의 입력 차이를 선택해야할 것이다. 이는 간단한 문제는 아니며 각 회전에서 일어나는 선형 혼합뿐 아니라 Sbox 고유 특성에도 의존한다. 이러한 차등 암호분석의 결과가 꼭 100%의 확률로 확정적일 필요는 없다. 즉, 어떤 결과가 만들어질 확률이 의미 있는 크기라면, 키를 성공적으로 찾아내는 데 있어 효과적으로 활용될 수 있는 확률적인 공격기법을 개발할 수 있다.
TDES의 Sbox 차이 분석
그럼 TDES의 유일한 비선형 요소인 Sbox의 입출력 차이를 살펴보자. Sbox를 다음과 같이 분석하면 유용한 입력 차이를 얻을 수 있다. 각각의 가능한 입력 X에 대해 X = X1 ⊕ X2 (단, ⊕는 XOR 연산) 를 만족하는 모든 쌍 (X1, X2)를 찾고 해당하는 출력 차이 Y = Y1 ⊕ Y2를 계산한다. 여기서 Y1 = Sbox(X1), Y2 = Sbox(X2)이다. 이 결과를 표로 정리하면 가장 편향된 출력 차이를 만들어내는 입력 값을 찾을 수 있다. 다음 표는 TDES의 Sbox 차이를 분석한 결과이다.
64 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 06 02 02 02 00 04 06 02 06 08 08 02 08 06 00
00 02 00 02 00 00 00 04 06 08 02 16 12 00 00 04
04 04 06 08 02 04 04 04 08 10 00 00 00 02 04 04
04 02 04 08 00 06 00 02 02 00 06 04 08 04 02 02
02 12 08 02 06 04 14 00 02 00 06 12 02 02 04 02
02 00 10 00 06 00 00 04 00 02 04 08 06 04 04 06
06 08 00 04 02 06 06 04 02 00 04 02 00 06 06 06
06 06 02 08 12 00 04 02 00 00 48 00 04 00 00 00
00 04 00 00 04 04 00 00 00 02 02 06 02 06 02 00
00 04 08 02 06 08 00 02 08 06 00 00 08 02 06 08
08 00 04 08 00 02 12 04 06 00 04 04 04 08 02 10
10 00 04 08 02 04 00 00 04 08 04 02 00 02 00 06
06 06 04 02 00 02 02 08 04 02 06 12 08 00 02 08
08 14 10 02 02 06 00 00 02 02 04 02 10 00 00 02
02 00 04 06 04 04 08 08 00 04 06 06 06 04 02 00
00 04 00 02 08 06 00 00 04 08 06 08 06 00 12 00
00 00 04 00 12 04 02 02 04 06 04 04 02 04 08 08
08 00 04 06 04 04 02 02 04 02 02 02 08 02 04 10
10 00 08 00 04 04 10 00 04 00 02 08 14 00 04 04
04 02 04 04 04 04 00 08 04 12 02 02 10 04 04 02
02 02 04 02 00 00 06 00 02 04 04 10 02 02 04 06
06 04 06 02 04 08 08 04 14 02 02 04 00 02 02 04
04 02 04 04 04 04 04 00 06 00 04 10 10 06 08 02
02 04 00 00 02 02 04 06 02 02 00 02 10 08 00 04
04 08 12 00 02 00 06 00 08 00 12 00 04 02 04 04
04 02 04 02 06 04 08 00 04 08 04 04 04 06 04 02
02 02 02 08 02 02 02 00 08 04 10 00 10 04 04 00
00 02 04 04 00 04 08 14 00 04 04 02 00 08 04 04
04 02 02 04 12 04 02 10 04 02 00 02 04 00 02 00
00 06 10 02 04 04 06 04 02 04 04 08 06 02 12 02
02 10 04 00 02 06 04 00 06 02 04 02 04 04 02 00
00 04 00 06 06 08 10 10 00 00 02 04 04 06 02 02
02 02 02 00 02 00 04 06 08 02 00 08 12 02 08 00
00 08 02 02 00 10 00 02 06 02 00 02 12 04 10 02
02 02 08 02 00 00 06 02 04 12 02 00 02 02 04 06
06 04 08 10 04 06 02 06 04 08 10 00 04 00 12 02
02 04 02 00 00 02 00 00 06 04 06 06 00 06 08 02
02 04 12 02 00 06 14 00 14 08 04 00 00 00 00 02
02 00 02 04 04 08 04 04 02 08 02 00 02 10 00 02
02 04 14 04 02 00 04 06 00 00 00 04 06 08 02 04
04 04 06 12 02 04 08 00 04 12 06 06 06 08 02 04
04 04 00 02 04 04 02 00 00 04 00 10 02 02 06 02
02 00 02 12 04 00 02 02 08 10 02 00 06 02 00 12
12 02 02 04 02 04 00 02 08 10 06 04 02 06 04 06
06 10 00 04 08 12 02 04 00 00 00 04 02 02 06 00
00 00 08 00 02 06 04 04 04 08 02 06 10 02 14 06
06 12 00 02 00 02 00 04 02 00 02 08 04 02 06 08
08 02 04 02 10 00 00 02 14 04 02 04 04 06 02 00
00 00 06 02 00 00 04 08 08 08 02 04 06 00 04 06
06 06 06 06 12 06 04 04 08 02 04 04 00 02 00 04
04 02 00 02 02 08 02 02 02 06 04 06 08 02 06 00
00 06 02 06 16 00 10 04 00 08 02 00 00 00 02 04
04 04 04 06 04 02 00 04 04 04 10 08 04 04 04 00
00 06 00 00 06 08 00 00 02 00 06 10 08 10 00 04
04 04 06 04 04 00 06 04 06 02 06 08 08 00 02 02
02 00 04 04 08 04 04 02 00 06 02 12 00 00 00 04
04 10 08 00 02 02 06 06 06 00 00 06 08 00 02 04
04 08 00 06 02 10 06 02 06 04 00 06 00 08 00 04
04 02 08 06 08 12 00 00 00 08 02 08 02 02 02 06
06 04 02 02 02 06 06 08 02 06 00 06 08 04 18 00
00 00 04 06 08 00 04 02 00 00 04 06 00 04 04 02
02 00 08 04 04 10 00 06 04 04 06 08 00 00 02 00
00 00 00 08 06 02 10 04 06 00 04 04 06 04 08 04
입출력값의 차이를 선택하는 방법
앞서 얻은 Sbox 분석 결과는 각각의 입력 차이에 대한 출력 차이가 편향된 정도의 분포를 나타낸다. 이 숫자가 클수록 편향의 정도가 큰 것이고, 분석을 위해서는 클수록 좋다. 다시 분석 결과를 살펴보면 편향의 정도가 가장 큰 경우가 64이고, 그 다음으로 큰 경우가 48임을 알 수 있다. 그리고 세 번째로 큰 값은 16으로 앞의 두 값에 비해 상당히 작다. 그럼 64, 48을 가지는 입출력 차이를 살펴보자.
64(probability 1): X1 ⊕ X2 = 000000 ⇒ SR(X1) ⊕ SR(X2) = 0000 --- (1)
48(probability 0.75): X1 ⊕ X2 = 001000 ⇒ SR(X1) ⊕ SR(X2) = 0010 --- (2)
단, SR()은 오른쪽 Sbox 연산
위 결과는 (1)이 항상 성립하고, (2)는 75% 확률로 성립한다는 것을 의미한다. (1)이 꼭 오른쪽 Sbox에서만 성립하는 것은 아니며, 그렇기 때문에 왼쪽 Sbox에도 적용시킬 수 있다. 이러한 (1)과 (2)는 각각 Sbox의 “비활성화”와 “활성화”된 Sbox에서 상당한 확률로 성립하는 입출력 차이라는 점에서 중요하다.
TDES의 차등 암호분석
차등 암호분석은 선택된 평문 공격이다. 어떤 평문을 선택해야 하는지는 (2)를 통해 알 수 있다. (2)에서 X1, X2는 각각 입력 I1, I2에 대해 E(I1), E(I2) (단, E()는 TDES 확장 연산을 수행하는 함수) 의 오른쪽 절반 비트들이다. 이때 X1 ⊕ X2 = 001000 이므로 확장의 정의로부터 I1 ⊕ I2 = 0010 이다. 그러므로 XOR 연산의 결과값이 0x0002인 평문 쌍을 선택해야 한다. 이러한 평문 쌍을 P, P_ 라고 하고, 각각의 왼쪽 절반 비트 집합을 L, L_, 오른쪽 절반 비트 집합을 R, R_이라고 하자. 그럼 다음 식이 성립한다.
P ⊕ P_ = (L, R) ⊕ (L_, R_) = 0x0002 --- (3)
그리고 TDES의 라운드 함수를 F()라고 하고, Sbox 연산을 수행하는 함수를 S(), 확장 연산을 수행하는 함수를 E()라고 하면 다음 식이 성립한다.
F(R, K) ⊕ F(R_, K) = S(E(R) ⊕ K) ⊕ S(E(R_) ⊕ K) --- (4)
단, K는 TDES 키
여기서 확장 연산은 선형 연산이므로 X1 ⊕ X2 = 0x02인 입력 X1, X2에 대해 다음이 성립한다.
(E(X1) ⊕ K) ⊕ (E(X2) ⊕ K) = E(X1) ⊕ E(X2)
= E(X1 ⊕ X2)
= 000000 000010 --- (5)
위 식에서 Z1 = E(X1) ⊕ K, Z2 = E(X2) ⊕ K 라고 하면 Z1 ⊕ Z2 = 000000 000010 이고, 오른쪽 절반 비트의 차이는 000010이다. Z1과 Z2의 왼쪽 절반, 오른쪽 절반 비트를 각각 ZL1과 ZL2, ZR1과 ZR2라고 하면 다음이 성립한다.
ZL1 ⊕ ZL2 = 000000 --- (6)
ZR1 ⊕ ZR2 = 000010 --- (7)
위 식에서 ZL1, ZL2는 왼쪽 Sbox, ZR1, ZR2는 오른쪽 Sbox에 대한 입력이 된다. 그리고 (1)에 의해
SL(ZL1) ⊕ SL(ZL2) = 0000 --- (8)
가 항상 성립한다고 말할 수 있고, (2)에 의해
SR(ZR1) ⊕ SR(ZR2) = 0010 --- (9)
가 성립할 확률이 0.75라고 말할 수 있다. 따라서 위 결과와 (4)에 의해
F(R, K) ⊕ F(R_, K) = 0000 0010 --- (10)
가 성립할 확률은 0.75이 된다. 정리하면 다음과 같다.
R ⊕ R_ = 0x02 ⇒ F(R, K) ⊕ F(R_, K) = 0x02 (Prob 0.75)
이로써 한 회전에 대한 식을 얻었다. 이제 이를 여러 회전에 연결시켜야 한다. P ⊕ P_ = 0x0002 인 평문 P, P_에 대해 위 식을 여러 회전에 적용시키면 다음을 얻는다.
P ⊕ P_ = 0x0002 ⇒ (L0 ⊕ F(R0, K1)) ⊕ (L_0 ⊕ F(R_0, K1)) = 0x02 = R1 ⊕ R_1
L1 = R0, L_1 = R_0
∴ (L1, R1) ⊕ (L_1, R_1) = 0x0202 (Prob 0.75)
P1 ⊕ P_1 = 0x0202 ⇒ (L1 ⊕ F(R1, K2)) ⊕ (L_1 ⊕ F(R_1, K2)) = 0x00 = R2 ⊕ R_2
L2 = R1, L_2 = R_1
∴ (L2, R2) ⊕ (L_2, R_2) = 0x0200 (Prob (0.75)^2)
P2 ⊕ P_2 = 0x0200 ⇒ (L2 ⊕ F(R2, K3)) ⊕ (L_2 ⊕ F(R_2, K3)) = 0x02 = R3 ⊕ R_3
L3 = R2, L_3 = R_2
∴ (L3, R3) ⊕ (L_3, R_3) = 0x0002 (Prob (0.75)^2)
P3 ⊕ P_3 = 0x0002 ⇒ (L3 ⊕ F(R3, K4)) ⊕ (L_3 ⊕ F(R_3, K4)) = 0x02 = R4 ⊕ R_4
L4 = R3, L_4 = R_3
∴ (L4, R4) ⊕ (L_4, R_4) = 0x0202 (Prob (0.75)^3)
∴ P4 ⊕ P_4 = C ⊕ C_ = 0x0202
보조키 비트 복구 알고리즘
앞에서 차등 암호분석을 여러 회전에 적용시켰다. 이제 이로부터 키 비트를 복구하는 알고리즘을 유도해야 한다. 공격자의 관점에서 “볼 수 있는” 비트는 P4, P_4 뿐이라는 것을 기억하자. 복구 알고리즘을 작성하기 위한 첫 번째는 암호문 비트만으로 구성된 식을 유도하는 것이다. 먼저 다음 두 식을 보도록 하자.
R4 = L3 ⊕ F(R3, K4) --- (11)
R_4 = L_3 ⊕ F(R_3, K4) --- (12)
여기서 L4 = R3, L_4 = R_3이므로
R4 = L3 ⊕ F(L4, K4) --- (13)
R_4 = L_3 ⊕ F(L_4, K4) --- (14)
이 성립한다. 그리고 앞의 적용결과에서 L3 ⊕ L_3 = 0x00 이었으므로 L3 = L_3 이다. 따라서 다음이 성립한다.
R4 ⊕ F(L4, K4) = R_4 ⊕ F(L_4, K4) --- (15)
위 식에서 알려지지 않은 것은 K4 뿐이며, 이에 앞의 여러 회전에 적용한 결과를 대입해보면
R_4 ⊕ R_4 = F(L4, K4) ⊕ F(L_4, K4) = 0000 0010 Prob .75 (∵ L4 ⊕ L_4 = 0x02) --- (16)
임을 알 수 있다. 이때 왼쪽 Sbox는 (1)을 따르고 오른쪽 Sbox는 (2)를 따른다. 그러므로 위 식은 L4 ⊕ L_4 = 0x02 를 만족하는 L4, L_4 쌍이 주어지고, 올바른 K4가 주어진다면, 상대적으로 가장 높은 확률로 성립할 것이다. 이를 구체적으로 살펴보자.
L4, L_4를 각각 L4[0,1,2,3,4,5,6,7], L_4[0,1,2,3,4,5,6,7]이라고 정의하자. 여기서 L4[0]은 L4의 가장 왼쪽에 위치한 비트를 의미하고, 그 다음 비트가 L4[1]이 된다. 그리고 L4[2,3,5,7]은 L4의 왼쪽에서 2, 3, 5, 7번째 비트를 이어붙인 것이다. 이를 바탕으로 (16)를 다시 쓰면 다음과 같다.
(SL(L4[4,7,2,1,5,7] ⊕ K[0,2,3,4,5,7]),
SR(L4[0,2,6,5,0,3] ⊕ K[13,14,15,9,10,11])) ⊕
(SL(L_4[4,7,2,1,5,7] ⊕ K[0,2,3,4,5,7]),
SR(L_4[0,2,6,5,0,3] ⊕ K[13,14,15,9,10,11])) = 0000 0010 --- (17)
단, L4[6] != L_4[6]
(17)에서 왼쪽 Sbox는 다음과 같이 정리된다.
(SL(L4[4,7,2,1,5,7] ⊕ K[0,2,3,4,5,7])) ⊕
(SL(L_4[4,7,2,1,5,7] ⊕ K[0,2,3,4,5,7])) = 0000 --- (18)
단, L4[6] != L_4[6]
위 식에서 L4[i] = L_4[i] (단, i != 6) 이므로 (1)에 의해 항상 성립한다. 따라서 (18)에서는 K4에 대한 어떤 정보도 얻을 수 없다. 이는 왼쪽 Sbox가 차이라는 관점에서 비활성화되었음을 보인다. 한편, 오른쪽 Sbox는 다음과 같이 정리된다.
SR(L4[0,2,6,5,0,3] ⊕ K[13,14,15,9,10,11])) ⊕
SR(L_4[0,2,6,5,0,3] ⊕ K[13,14,15,9,10,11])) = 0010 --- (19)
P ⊕ P_ = 0x0002, C ⊕ C_ = 0x0202 를 만족시키는 평문, 암호문 쌍에 대해 (19)는 적절한 K[13,14,15,9,10,11]이 주어진다면 항상 성립하겠지만, 그렇지 않은 경우에는 단지 어느 정도 확률을 가지고 성립될 것이다. 이로부터, 앞서 언급한 조건을 만족하는 평문, 암호문 쌍에 대해 식 (19)를 최대의 경우의 수로 성립시키는 키를 추출하는 보조키 비트 복구 알고리즘을 작성할 수 있다. 여기서는 이 알고리즘의 동작을 확인하기 위해 “http://www.hanb.co.kr/exam/1427” 에서 제공하는 평문, 암호문 쌍을 사용하였다. 그 결과로 다음 네 개의 키가 최대의 경우의 수를 가졌다.
K[13,14,15,9,10,11] = 0x13 = 010011 --- (20)
K[13,14,15,9,10,11] = 0x1b = 011011 --- (21)
K[13,14,15,9,10,11] = 0x22 = 100010 --- (22)
K[13,14,15,9,10,11] = 0x2a = 101010 --- (23)
식 (20), (21), (22), (23)은 다음과 같이 쓸 수 있다.
K[13,14,9,10,11] = 01011 --- (24)
K[13,14,9,10,11] = 10010 --- (25)
키 비트를 모두 복구하는 방법
앞에서 보조키 비트 일부를 얻어내었지만, 키를 완전히 복구하기 위해서는 나머지 2^11의 알려지지 않은 비트에 대해 전수 조사를 하고, (24), (25)를 각각 조사해야만 한다. 이러한 방식으로 추정되는 모든 2^12개의 키 K 각각에 대해 암호문 복호화를 시도해 정확한 키를 찾았을 때 비로소 평문을 복구할 수 있을 것이다. 정확한 키를 찾을 때까지 시도해야하는 조사 횟수의 기대값은 2^12의 절반인 2^11이라고 할 수 있다. 그러므로 전체 작업량의 기대값은 2^11에 해당하는 암호분석 작업량과 상대적으로 비중이 크지 않지만 차등 공격을 위해 요구되는 작업량을 더한 것이 된다. 결론적으로, 2^11개의 분석 작업량으로 16비트의 키를 복구할 수 있다. 이는 전수키 조사를 단축시키는 지름길이 있음을 의미하므로, TDES는 안전하지 않음이 증명된다.
블록암호의 설계원칙
TDES에 대한 차등 암호분석은 Sbox가 입출력 차이에 대한 편향이 있음을 확인하여 시작되었다. 해당 편향을 발생시키는 입력 차이를 확장 연산에 역으로 적용시켜 TDES에 적용되는 입력 차이를 구성하였다. 이와 함께 선형적인 확장 연산, XOR 연산의 특성을 이용하여 한 회전에 대한 암호분석을 완성하였다. 그리고 이를 연결하여 4개의 회전에 대한 분석을 얻었다. 이로부터 보조키 비트 복구 알고리즘을 구성하였고 이를 검증하기 위한 평문, 암호문 쌍을 통해 최종적으로 두 개의 후보를 추렸다. 마지막으로 발견되지 않은 나머지 비트에 대한 전수키 조사를 통해 완전한 키를 추출하였다.
이러한 과정을 통해 블록암호의 설계원칙을 엿볼 수 있다. 먼저 Sbox는 입출력 차이에 편향을 가능한 가지지 않도록 설계되어야 할 것이다. 그리고 TDES와 같이 한 회전에서 수행하는 연산이 복잡하지 않은 경우에는 회전의 수를 늘려 연결된 암호분석이 가지는 확률을 낮추어야 할 것이다. 끝으로 여기서 완전한 키를 손쉽게 얻을 수 있었던 것은 애초에 키 공간이 크지 않았기 때문이다. 크지 않은 키 공간이 차등 암호분석을 통해 더욱 작아졌고 이에 전수키 조사가 가능했던 것이다. 따라서 블록암호가 요구하는 키 공간은 충분히 커야 할 것이다.
References
[1] Mark Stamp, “Information Security: Principles and Practice”, Wiley-Interscience, Inc.
[2] Susan Landau, “Standing the Test of Time: The Data Encryption Standard”, NOTICES OF THE AMS