Differential Cryptanalysis of the Full 16-round DES

Differential Cryptanalysis of the Full 16-round DES(Eli Biham / Adi Shamir, 1993년) 

최초로 발표된 full round DES에 대한 합리적인 시간 복잡도($2^{37}$)의 공격입니다. DES는 1974년 IBM에서 발표한 lucifer라는 암호를 일부 수정해 만들어낸 암호로, 동시대에 제작된 다른 암호들이 1980년대 후반 Eli Biham, Adi Shamir(이 논문의 저자)가 고안한 Differential Cryptanalysis에 쉽게 깨졌던 반면 DES는 그렇지 않았습니다. 이후 IBM 측에서 DES를 만들 당시 이미 IBM에서는 Differential Cryptanalysis를 알고 있었고 DES를 만들 때 DC로부터 안전하게끔 만들었다고 밝혔습니다. 물론 현재는 DES의 키가 너무 짧아(56bit) brute force로도 쉽게 키를 알아낼 수 있기 때문에 AES로 넘어간 상태입니다.

기존의 DES에 대한 DC는 6/8 round에 대한 분석만 진행되었고 full round에서는 전수 조사보다 오히려 느렸습니다. 또한 확률이 높은 특정 경로를 택하게 되면 자연스럽게 키의 일부 bit만 찾아내기 때문에 right pair로 추정되는 pair로부터 키의 일부 bit를 복원해내더라도 이것이 맞다는 보장을 할 수가 없어서 내부적으로 counter를 두어서 키 후보의 등장 횟수를 확인해야하지만 이 논문의 공격에서는 complete 56-bit key를 알아내기 때문에 구한 키가 맞는지 아닌지 바로 확인해볼 수 있습니다.(CPA 환경이니까 임의의 평문에 대한 암호문을 알고, 내가 구한 키의 후보로 평문을 암호화했을 때 그 결과가 일치하는지 확인해보면 되니까요.) 비슷한 이유로 공간을 매우 적게 사용하게 됩니다.

이제 본격적으로 어떤 식으로 공격을 하는지 알아봅시다.

 

우선 DES에서 IP, FP는 보안의 관점에서 아무런 영향을 주지 않기 때문에 무시합니다.

평문 $P_1$, $P_2$의 차분이 19 60 00 00 00 00 00 00 일 때, 2라운드를 진행한 이후의 차분이 00 00 00 00 19 60 00 00 일 확률은 1/234입니다. (S1의 차분 : 000011, S2의 차분 : 110010, S3의 차분 : 101100, 나머지는 차분이 0. S1에서 000011 → 0000으로 가는 확률은 $14/64$, S2에서 110010 → 0000으로 가는 확률은 $8/64$, S3에서 101100 -> 0000으로 가는 확률은 $10/64$ 이니 $14/64 \times 8/64 \times 10/64 = 1/235$ 정도인데 실제로는 독립적이지 않으니 조금 확률이 다를 것임)

이런 식으로 13 round를 진행하면 평문 차분 19 60 00 00 00 00 00 00 으로부터  중간 값 차분이 19 60 00 00 00 00 00 00이 나올 확률이 $(1/234)^6 = 2^{-47.2}$가 됩니다.  이제 세 라운드를 추가하면 되는데, 또 다시 19 60 00 00 00 00 00 00 → 00 00 00 00 00 19 60 00 00 경로를 사용해버리면 확률이 $2^{-47.2} \times 1/234 = 2^{-55.1}$ 이 되어버려 전수조사와 다를바가 없어집니다. 대신 이 논문에서 제안한 방법은 확률을 더 나빠지지 않게 하면서 round를 추가하는 것입니다.

임의의 64-bit plaintext $P$를 정하고 $v_0, v_1, ... ,v_{4095}$를 P의 first round에서 S1, S2, S3의 output bit를 00 00 00부터 FF FF FF까지로 바꿔지게끔 하는 값이라고 해봅시다. 그러고나서 $P_i = P \oplus (v_i, 0)$으로, $Q_i = P_i \oplus (00 00 00 00 19 60 00 00)$ 으로 둔다면 $P_i$와 $Q_i$의 차분은 00 00 00 00 19 60 00 00 이 될 것입니다. 그리고 i, j = 0~4095에 대해 $2^{24}$개의 $P_i$, $Q_j$ pair를 생각해보면 이들의 차분은 ($v_k$, 19 60 00 00)이 되고 각 $v_k$는 정확히 $2^{12}$번씩 등장합니다.

차분 19 60 00 00이 F 함수를 통과할 때를 생각해보면 S1, S2, S3의 output으로는 알 수 없는 어떤 차분을 가지게 될 것이고 S4, S5, S6, S7, S8에서는 반드시 차분이 0입니다.(입력 차분이 0이기 때문에) 각 $P_i$에 대해 반드시 단 하나의 적절한 $Q_j$가 존재하므로 정확히 $2^{12}$개의 ($P_i$, $Q_j$) 쌍이 right pair입니다. 그러면 이제 전체 구조를 생각해봅시다. 첫 번째 라운드에서 $2^{12}$개의 right pair가 존재하고 각 right pair가 2~14번째 라운드에서 19 60 00 00 ... 이 경로를 잘 타고 내려올 확률은 $2^{-47.2}$ 이므로 전체 구조에서 임의의 $P$를 택할 때 마다 $2^{-35.2}$의 확률로 right pair를 찾아낼 수 있습니다.

그러면 이제 가능한 $2^{24}$개의 pair 중에서 $2^{12}$개의 pair를 어떻게 골라낼 것인가 하는 문제를 생각해보아야 하는데, right pair라면 반드시 암호문의 차분 상에서 S4, S5, S6, S7, S8로부터 도달한 비트는 0이 되어야합니다. 그러니 $P_i$에 대한 암호문, $Q_i$에 대한 암호문에서 이 20비트의 값을 가지고 sort를 합니다.(혹은 hash를 사용해도 됩니다.) 그리고 그 20bit가 일치하는 것을 찾으면 됩니다. 이렇게 하면 $2^{24}$개의 pair를 전수조사하는 대신에 hash를 쓰면 대략 $2^{12}$, sort를 쓰면 대략 $2^{16}$ 정도의 시간복잡도로 해결할 수가 있겠네요. 두 암호문에서 20 bit position이 일치할 확률은 $2^{-20}$이므로 확률적으로는 $2^{24}$개의 pair 중에서 16개의 pair만 살아남을 것입니다. 그리고 그 16개 pair 중에서도 1, 15, 16 round에서 S-box를 통과할 때 XOR distribution table 상으로 불가능한 값이 나오는 경우에는 버리게 됩니다. 이 과정에서 $14/16 \times 13/16 \times 15/16)^2 \times 0.8^8 = 0.0745$ 의 확률로 살아남기 때문에 최종적으로 임의의 P에서 1.19 pair만 살아남게 됩니다.

(DES distribution table: http://www.cs.technion.ac.il/~cs236506/ddt/DES.html) 

$14/16 \times 13/16 \times 15/16)^2 \times 0.8^8 = 0.0745$ 이라는 식의 의미는 S1에서 input 차분 000011에서 갈 수 있는 16개의 output 차분 중에서 1011, 1111에는 도달할 수가 없으므로 14/16, S2에서 input 차분 110010에서 갈 수 있는 16개의 output 차분 중에서 0011, 1011, 1111에는 도달할 수가 없으므로 13/16, S3에서 input 차분 101100에서 갈 수 있는 16개의 output 차분 중에서 1100에는 도달할 수가 없으므로 15/16이고 1R와 15R에서는 S1, S2, S3에 대해서만 확인하니 $14/16 \times 13/16 \times 15/16)^2$입니다. 그리고 16R에서는 8개의 S-box에 대해 Input 차분 / Output 차분이 중구난방일테니 rough하게 0.8로 잡아서 $0.8^8$이 붙게 됩니다.)

이후, 13R에서 위로 2라운드를 더 진행합니다. 이를 통해 S/N(Signal to Noise, 잘못된 키가 1번 나올 때 올바른 키가 몇번 나오는지를 의미)를 $2^{12}$ 배 높일 수 있습니다.

이제 마지막으로 키를 복원하는 부분입니다. left key register에서는 우선 16라운드의 S4에 쓰이는 key bit 6개(총 64가지)를 전수조사해서 올바른 출력을 내는 4가지 키 후보를 찾아냅니다. 그리고 16R의 S4에 쓰이는 key bit 6개 중에서 3개는 1R의 S3에도 쓰입니다. 그렇기 때문에 16R의 S4에 쓰이는 key bit가 고정될 경우, 1R의 S3에서 key bit를 확인하기 위해 단 3개의 bit에 대해서만 전수조사를 하면 됩니다. 비슷한 방식으로 16R S4 → 1R S3 → 16R S1 → 1R S2로 진행하면서 전수조사를 하면 13개의 bit만 전수조사해서 28bit의 left key register를 복원할 수 있습니다. 다만, wrong pair를 택했다면 이상한 key register를 택하게 될 것입니다.

right key register에서는 left key register를 이미 구한 상황이므로 15R에서 쓰이는 key bit중에 1~28 bit는 알고 있습니다. 그러면 15R의 S1, S2에서는 2비트를 알고 있고, S3에서는 3비트를 알고 있습니다. 이후에는 left key register와 비슷하게 15R/16R에서 S-box를 옮겨다니면서 key를 채워나가면 됩니다. 이를 통해 4-5 bit 정도를 줄일 수 있다고 합니다.

DES-12Round-Differential-Attack구현 링크