차등 암호 분석의 개념
차등 암호 분석(Differential Cryptanalysis)은 주로 블록 암호에 적용되는 대표적인 암호 해독(cryptanalysis) 모델입니다. 블록 암호뿐만 아니라 스트림 암호나 암호화 해시 함수에도 확장하여 적용할 수 있습니다. 가장 넓은 의미에서 차등 암호 분석은 입력 데이터의 차이가 출력 결과의 차이에 어떤 영향을 미치는지를 연구하는 학문이라고 할 수 있습니다.
차등 암호 분석의 핵심 목표는 암호문(ciphertext) 속에서 통계적 분포와 패턴을 찾아내고, 이를 통해 해당 암호에 사용된 키에 대한 정보를 추론해내는 것입니다.
왜 차등 암호 분석이 중요한가
차등 암호 분석은 입력값의 차이와 그에 대응하는 암호화 출력값의 차이를 비교·분석하는 암호학의 한 분야입니다. 특히 블록 암호 연구에서 평문(plaintext)의 변화가 암호문에 비무작위(non-random)한 결과를 만드는지 확인하는 데 주로 사용됩니다.
이 과정이 중요한 이유는, 암호문에 나타나는 비무작위적 변화는 곧 암호화 방식의 취약점을 시사하기 때문입니다. 허가받지 않은 제3자는 이러한 정보 변화를 관찰함으로써 무엇이 암호화되었는지, 또는 어떻게 암호화되었는지에 대한 단서를 얻을 수 있습니다.
블록 암호에서의 적용 원리
블록 암호에서 차등 분석은 변환 네트워크 전체를 통해 차이를 추적하고, 암호가 비무작위적 동작을 보이는 지점을 찾아내어 이를 이용해 비밀키(암호화 키)를 복원하는 일련의 기법으로 정의할 수 있습니다.
특정 암호에 대한 공격이 성공하려면 입력 차이를 신중하게 선택해야 합니다. 이를 위해 알고리즘 내부 구조를 분석하며, 표준적인 접근 방식은 높은 확률로 발생 가능한 차이의 경로를 여러 암호화 과정을 거치며 추적하는 것입니다. 이렇게 추적된 경로를 '차등 특성(differential characteristic)'이라고 부릅니다.
이 절차에서 선택된 두 개의 평문 입력 사이에서 의도한 출력 차이가 관찰되면, 그 결과로부터 가능성 있는 키 값을 도출해낼 수 있습니다.
역사와 공격 방법의 구조
차등 암호 분석은 1990년 엘리 바이함(Eli Biham)과 아디 샤미르(Adi Shamir)가 DES 블록 암호를 분석하기 위해 처음 소개했습니다. 현재까지도 차등 분석은 블록 암호에 대한 가장 효율적인 공격 방법 중 하나로 꼽힙니다.
차등 분석은 선택 평문 공격(chosen-plaintext attack)에 해당하며, 기본 개념은 암호화 과정에서 특정 평문 차이 값의 차이 전파(differential propagation) 확률을 연구하는 것입니다.
이 방법으로 블록 암호를 치환(permutation) 영역과 분리한 뒤, 그 기반 위에서 키 복원 공격을 수행할 수 있습니다. 다른 말로 표현하면, 높은 확률의 차등 경로(differential trail)를 찾아내는 것입니다.
마지막 단계에서는 차등 특성의 앞뒤에 여러 라운드를 추가하고, 해당 라운드에서 사용된 라운드 키(round-key)를 추측하며, 평문을 암호화하고 암호문을 복호화하는 과정을 반복함으로써 블록 암호의 올바른 키를 판별하게 됩니다.
MILP와의 연계
혼합 정수 선형 계획법(MILP, Mixed-Integer Linear Programming)은 일부 또는 모든 변수가 정수로 정의되는 과학적 최적화 혹은 실현 가능성 설계 기법입니다. 경우에 따라 정수 제약 조건을 제외하면 목적 함수와 제약 조건이 모두 선형인 정수 선형 계획(ILP, Integer Linear Program)으로 정의될 수 있습니다. MILP는 일반적으로 비즈니스와 금융 분야에서 최적화 문제를 해결하는 데 널리 사용되며, 암호 분석 분야에서도 차등 경로 탐색 등에 활용되고 있습니다.