차분 공격

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

차분 공격(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가 차분 공격에 강인하도록 설계되었다는 것을 발견하기도 했다.[1]

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

출처[편집]

  1. Eli Biham, 아디 샤미르 (1992년). Differential Cryptanalysis of the Data Encryption Standard - Advances in Cryptology.
  2. Don Coppersmith (1994년). The Data Encryption Standard (DES) and its strength against attacks.