🔐 [클래식] Differential Cryptanalysis of DES-like Cryptosystems — DES를 무너뜨린 차분 분석의 탄생 (1990)

논문 정보

연구 배경 — "비밀의 블랙박스", DES

DES(Data Encryption Standard)는 1977년 미국 표준으로 채택된 세계 최초의 공개 블록 암호다. 56비트 키로 16라운드 Feistel 구조를 쓰는 DES는 1990년대 초까지 가장 널리 쓰였지만, 두 가지 그림자가 드리워져 있었다. 첫째, 핵심 부품인 S-box(치환 테이블)의 설계 기준이 비공개였다. 둘째, IBM이 설계 과정에서 NSA(미 국가안보국)의 개입을 받았다는 사실은 알려져 있었으나 그 의도는 수수께끼였다. Biham과 Shamir는 바로 이 S-box를 통계적으로 파고들어, "선택 평문만으로 DES를 전수조사보다 빠르게 깰 수 있다"는 놀라운 결과를 CRYPTO '90에서 발표했다. 이후 이 방법은 차분 분석(Differential Cryptanalysis)이라는 이름으로 현대 블록 암호 분석의 가장 기본적인 도구가 된다.

핵심 내용 — "차분(difference)"을 따라가는 통계적 공격

• 차분 특성(Differential Characteristic): 두 평문의 XOR 차분이 라운드를 거치며 어떻게 전파되는지를 확률적으로 추적한다. S-box는 입력 차분에 따라 특정 출력 차분이 다른 것보다 압도적으로 자주 나타나는데, 이 비균등한 확률 분포가 공격의 원료다.
• 선택 평문 공격: 공격자는 고정된 차분을 가진 평문 쌍을 대량으로 암호화해 그 결과를 비교한다. 특정 차분이 높은 확률로 살아남는 경로(라운드 축소판)를 찾아내면, 마지막 라운드의 후보 키를 통계적으로 추려낼 수 있다 — 틀린 키는 무작위 분포를 만들고, 맞는 키만 편향된 분포를 만들기 때문이다.
• 결정적 결과: 16라운드 전체 DES를 선택 평문 약 2^47개로 공격 — 전수조사(평균 2^55)보다 훨씬 빠르다. 축소 라운드 DES(8라운드)는 고작 2^14개의 선택 평문으로 무너뜨렸고, 이를 실험으로 직접 검증해 보였다.
• 일반화된 프레임워크: DES에만 국한되지 않고 Feistel 구조의 "DES 유사(DES-like)" 암호 전반을 분석하는 체계적 방법론을 제시 — 라운드 수·S-box 설계에 따른 안전성 한계를 이론적으로 도출했다.
• 역사적 반전 — NSA의 '선견지명': 분석 결과 DES의 S-box는 차분 분석에 이미 저항하도록 정교하게 설계되어 있었다. 이는 IBM/NSA가 1970년대 중반, 공개 학계보다 약 15년 먼저 차분 분석을 알고 있었음을 강력히 시사한다. (IBM의 Don Coppersmith가 1994년 이를 공식 확인)

"We have developed a new method for cryptanalysis of DES-like cryptosystems... capable of breaking the full 16-round DES in 2^47 chosen plaintexts." — Biham & Shamir, Journal of Cryptology (1991)

영향과 의의

• 암호 설계의 새로운 표준: 차분 분석 이후, 새 블록 암호는 "차분 공격에 대한 안전성 수치"를 설계 단계에서 제시해야 했다. AES로 선정된 Rijndael의 wide-trail 설계, 그리고 거의 모든 현대 암호의 S-box/라운드 설계가 이 논문의 직접적 후예다.
• 차분 분석 계열 전체의 시발점: truncated differential, 불능 차분 공격(impossible differential), 부메랑 공격(boomerang), 관련 키 공격 등 후속 연구 전부가 이 논문의 개념을 확장한 것이다. Matsui의 선형 공격(1993, DES를 2^43 기지 평문으로 파훼)과 함께 '현대 대칭 암호 분석의 양대 축'을 이룬다.
• 해시 함수 분석에도 적용: 차분 기법은 MD5·SHA-1 충돌 공격 등 해시 함수 암호해독의 핵심 도구로도 이어진다 — 암호학 전 분야를 관통하는 방법론이 되었다.
• 투명성 논쟁에 종지부: 비밀 설계 기준(S-box)이 "우연한 견고함"이 아니라 NSA의 사전 지식 때문이었음을 드러내며, 암호는 반드시 공개 검증을 거쳐야 한다는 현대 암호학의 원칙(Kerckhoffs의 원리)을 역사적으로 입증한 사례로 남았다.
• 오늘날의 의미: DES 자체는 1998년 전수조사 하드웨어(Deep Crack)로도 무너졌지만, 차분 분석이라는 '생각의 도구'는 AES, 경량 암호, 포스트퀀텀 후보 분석에 이르기까지 30년 넘게 살아 있는 현역 방법론이다.

출처

• Journal of Cryptology 원문 (Springer, DOI 10.1007/BF00630563): link.springer.com/article/10.1007/BF00630563
• 위키백과 (Differential cryptanalysis): en.wikipedia.org/wiki/Differential_cryptanalysis
• 위키백과 (Data Encryption Standard): en.wikipedia.org/wiki/Data_Encryption_Standard