차분 공격

차분 공격(differential cryptanalysis)은 암호해독(cryptanalysis)의 한 방법으로, 입력값의 변화에 따른 출력값의 변화를 이용하는 방법이다.

공격 방법

차분 공격은 일반적으로 선택 평문 공격(chosen-plaintext attack)을 가정한다. 일반적인 차분 공격의 과정은 다음과 같다.

$n$비트 평문 $X$ 및 그 평문과 비슷한 다른 평문 $X'$을 준비하고, 이들의 XOR 차이를 $\Delta _{X}$라고 둔다. 그리고 $X,X'$를 각각 암호화한 결과를 $Y,Y'$라고 정의하며 이들의 XOR 차이를 $\Delta _{Y}$로 둔다.

이상적인 경우, 어떤 $\Delta _{X}$에 대해 특정 $\Delta _{Y}$가 나타날 확률은 $1/2^{n}$이다. 하지만 암호에 취약점이 존재하는 경우 이 확률은 더 크게 나타날 수 있다. 이때 $(\Delta _{X},\Delta _{Y})$를 차분(differential)이라고 부른다. 차분 공격은 이러한 차분 쌍을 찾아내는 것을 목표로 한다.

차분 쌍을 이용하여 블록 암호의 암호 키를 찾는 공격이 가능할 수도 있다. 가령 블록 암호가 대입-치환 네트워크(substitution-permutation network) 구조를 가질 때 마지막 라운드를 제외한 나머지 과정에서 차분 현상이 일어났다면, 마지막 라운드에 입력되는 값의 차이를 일정 확률로 알 수 있고, 출력값의 차이를 관측할 수 있으므로 마지막 라운드에 더해지는 키의 일부도 알 수 있기 때문이다.

역사

차분 공격은 Eli Biham과 아디 샤미르가 1980년대 후반에 발견하면서 처음 알려졌다. 이들은 여러 블록 암호와 암호학적 해시 함수의 취약성을 발표하였으며, DES의 취약성을 연구하면서 DES가 차분 공격에 강인하도록 설계되었다는 것을 발견하기도 했다.

이후 1994년 IBM의 DES 팀에 있었던 Don Coppersmith는 1974년에 IBM이 차분 공격을 발견하였으며, IBM 내부에서는 이를 "T-attack"으로 불렀다는 것과 DES의 설계 목적 중 하나가 이에 문제가 없도록 하는 것이었다고 밝혔다.