차분 암호 분석 (Differential Cryptanalysis, DC)

차분 암호 분석(differential cryptanalysis, DC)은 평문 쌍 사이의 고정된 차이(보통 비트 단위 XOR 차이)가 암호화를 거친 뒤 암호문 쌍 사이에서 키에 따라 예측 가능한 차이로 이어지는 경향을 이용하는 공격 방식입니다. 기본 아이디어는 평문을 암호화한 다음, 그 평문에 정해진 변경을 가해 다시 암호화하고, 두 암호문의 차이를 통계적으로 분석해 비밀 키에 대한 정보를 얻는 것입니다.

어떻게 작동합니까?

1. 평문 쌍 선택: 공격자는 초기 평문을 고르고, 여기에 정해진 차이를 적용한 두 번째 평문을 만듭니다.
2. 암호화: 두 평문을 같은 알고리즘과 같은 비밀 키로 암호화해 암호문 A와 B를 얻습니다.
3. 차이 분석: 암호문 A와 B를 비교해 평문 차이가 출력에 어떤 차이로 나타나는지 관찰합니다.
4. 키 추정: 이 과정을 많은 평문 쌍에 반복해, 예상한 차이가 나타나는 빈도가 가장 높은 키 후보(주로 마지막 라운드의 부분 키)를 고릅니다.

대부분의 경우 공격자가 원하는 평문을 골라 암호문을 얻을 수 있어야 하므로 선택 평문 공격에 속합니다.

핵심 개념

• 차분 특성: 입력 차이가 각 라운드를 지나며 어떤 차이로 바뀌는지를 이어 놓은 경로입니다. 이런 전파는 확정적이지 않고 확률적으로 일어납니다.
• S-box의 역할: XOR 차이는 키 덧셈에서 상쇄되고 선형 연산에서는 확정적으로(확률 1로) 전달되므로, 예측 가능성은 주로 S-box 같은 비선형 구성 요소에서 특정 입력 차이가 특정 출력 차이로 바뀔 확률에 좌우됩니다.
• 확률과 데이터 양: 차분 특성의 확률이 높을수록 공격에 필요한 평문 쌍이 줄어듭니다.

예시 시나리오

약간 다른 두 메시지(평문)가 있다고 상상해 보세요. 같은 키로 암호화하면 암호문의 특정 비트가 일정한 방식으로 바뀌는 경향이 보일 수 있습니다. 공격자는 이러한 변화를 체계적으로 연구해 암호의 내부 구조에 관한 패턴을 추론하고, 약점을 찾거나 비밀 키의 일부를 알아낼 수 있습니다.

역사와 최신 암호에 미치는 영향

• 공개 연구: 엘리 비햄(Eli Biham)과 아디 샤미르(Adi Shamir)가 1990년 무렵 공개적으로 발표했고, DES(Data Encryption Standard)를 비롯한 여러 블록 암호에 적용했습니다. 16라운드 전체 DES를 깨려면 약 2⁴⁷개의 선택 평문이 필요해 실제 위협이 되지는 않았습니다.
• 설계에 반영: DES를 설계한 IBM 팀은 이 기법을 이미 알고 S-box를 그에 맞서도록 설계했다고 이후 밝혀졌습니다.
• 현재의 표준: AES 같은 최신 암호는 차분 공격에 대한 저항성을 증명하거나 평가하도록 설계되며, 새로운 알고리즘은 차분 암호 분석에 대해 엄격하게 시험받습니다.

장점과 한계

• 효과적: 널리 쓰이던 여러 암호 알고리즘의 약점을 드러냈습니다.
• 범용성: 블록 암호뿐 아니라 해시 함수, 스트림 암호 분석에도 응용됩니다.
• 데이터 집약적: 효과를 내려면 많은 양의 평문-암호문 쌍이 필요합니다.
• 복잡함: 좋은 차분 특성을 찾고 공격을 구현하는 것이 어렵습니다.

사용 영역

1. 암호 연구: 기존 및 새로운 암호 알고리즘의 보안을 분석하고 개선합니다.
2. 보안 평가: 암호에 의존하는 시스템의 견고성을 평가합니다.

차분 암호 분석은 암호를 공격하는 방법이면서, 동시에 이런 공격에 견디는 알고리즘을 설계하기 위한 기본 점검 도구입니다.