차분 공격

3. 공격 방법

차분 공격은 선택 평문 공격뿐만 아니라 기지 평문 공격, 암호문 단독 공격에도 적용될 수 있도록 확장할 수 있다. 공격의 기본적인 방법은 고정된 차이를 가지는 평문 쌍을 이용하는 것이다. 차이는 주로 배타적 논리합(XOR) 연산을 사용하며, 암호문의 차이 분포에서 통계적 패턴을 찾는다.

대부분의 암호에서 공격을 성공시키기 위해서는 입력 차분을 신중하게 선택해야 한다. 이를 위해 암호 알고리즘의 내부 구조를 분석하여 각 단계에서 높은 확률로 유지되는 차분 경로, 즉 '차분 특성'을 찾는다. 차분 특성은 암호화 과정의 각 단계를 거치면서 높은 확률로 유지되는 차이의 경로를 의미한다.^[5]

차분 공격은 주어진 입력/출력 차이 패턴이 특정 입력 값에 대해서만 발생한다는 사실에 의존한다. 비선형 구성 요소(주로 S-box)에서 원하는 출력 차이를 관찰하면 가능한 키 값을 추측할 수 있다.

예를 들어, 입력과 출력의 최하위 비트(LSB) 차이가 1로 같을 확률이 4/256인 경우 (이는 AES 암호의 비선형 함수에서 가능하다), 가능한 입력 값은 4개(2쌍)뿐이다. 만약 키가 XOR 연산 전에 비선형 함수를 통과하고, 차분을 허용하는 값이 {2, 3}, {4, 5}라고 가정하면, 공격자가 {6, 7}을 입력하고 올바른 출력 차이를 얻었을 때, 키 K는 2 또는 4가 된다.

암호를 차분 공격으로부터 보호하려면 n비트 비선형 함수에서 '차분 균일성'을 2^{−(n − 1)}에 가깝게 만들어야 한다. 이렇게 하면 차분 공격은 무차별 대입 공격과 동일한 수준의 복잡도를 가지게 된다.^[7]

3. 1. 기본 원리

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

3. 2. 공격 절차

3. 3. 차분 특성

4. 세부 유형

차분 공격에는 다음과 같은 다양한 유형이 있다.

• 고차 미분 공격: 일반적인 차분 공격보다 더 높은 차수의 차분을 사용한다.
• 절단 미분 공격: 전체 비트가 아닌 일부 비트에 대한 차분만을 고려한다.
• 불가능 차분 공격: 특정 차분이 발생할 확률이 0인 경우를 이용하며, 고차 미분 공격, 절단 미분 공격과 함께 사용되기도 한다.
• 부메랑 공격: 두 개의 짧은 차분 특성을 연결하여 전체 암호에 대한 공격을 구성한다.

4. 1. 고차 차분 공격 (Higher-Order Differential Attack)

4. 2. 절단 차분 공격 (Truncated Differential Attack)

4. 3. 불능 차분 공격 (Impossible Differential Attack)

4. 4. 부메랑 공격 (Boomerang Attack)

5. 현대 암호에의 적용 및 대응

현대 암호 설계에서는 차분 공격이 공개된 이후, 이 공격에 대한 저항성을 갖추는 것이 중요한 고려 사항이 되었다. 고급 암호화 표준(AES)을 포함한 많은 암호 알고리즘이 차분 공격에 대해 안전하다고 증명되었다.^[6]

이상적인 n비트 비선형 함수는 차분 공격에 대한 최적의 저항성을 제공하기 위해 2^{−(''n'' − 1)}에 가까운 차분 균일성을 가져야 한다.^[7]

5. 1. 현대 암호의 안전성

5. 2. AES의 예시

6. 한국의 관점 및 대응

한국은 암호 해독 기술에 대한 연구와 함께, 암호 알고리즘의 안전성을 확보하기 위한 정책적 노력을 기울이고 있다. 특히, 국가보안기술연구소를 중심으로 암호 알고리즘의 안전성 평가 및 새로운 암호 개발 연구가 이루어지고 있다.

6. 1. 연구 동향

참조

_[1] 서적 Differential cryptanalysis of the data encryption standard Springer Verlag 1993
_[2] 간행물 The Data Encryption Standard (DES) and its strength against attacks http://simson.net/re[...] 1994-05
_[3] 서적 Crypto: How the Code Rebels Beat the Government — Saving Privacy in the Digital Age Penguin Books
_[4] 웹사이트 Re: Reverse engineering and the Clipper chip https://groups.googl[...] 1996-08-15
_[5] 웹사이트 Differential Cryptanalysis - an overview {{!}} ScienceDirect Topics https://www.scienced[...] 2023-04-13
_[6] 간행물 Report on the Development of the Advanced Encryption Standard (AES) 2001-05
_[7] 서적 Fast Software Encryption Springer 2009
_[8] 간행물 The Data Encryption Standard (DES) and its strength against attacks http://www.research.[...] 1994-05
_[9] 서적 "Crypto: How the Code Rebels Beat the Government — Saving Privacy in the Digital Age Penguin Books 2001
_[10] 뉴스 Re: Reverse engineering and the Clipper chip" https://groups.googl[...] sci.crypt 1996-08-15
_[11] 저널 Differential Cryptanalysis of the Data Encryption Standard - Advances in Cryptology 1992
_[12] 저널 The Data Encryption Standard (DES) and its strength against attacks 1994