더블 DES(Double DES)는 암호화 과정에서 두 개의 DES 암호기를, 복호화 과정에서 두 개의 역방향 DES 암호기를 사용하는 방식입니다. 각 DES 암호기는 서로 다른 키를 요구하기 때문에 전체 키 길이가 112비트로 확장되어 단일 DES보다 훨씬 안전해 보입니다. 그러나 더블 DES는 중간자 공격(meet-in-the-middle attack)이라 불리는 기지 평문 공격(known-plaintext attack)으로 무력화될 수 있습니다.
더블 DES의 암호화·복호화 구조
평문 P와 두 개의 암호화 키 K1, K2가 주어졌을 때, 암호문 C는 다음과 같이 생성됩니다.
C = Ek2(Ek1(m))
반대로 복호화할 때는 키를 역순으로 적용해야 합니다.
P = Dk1(Dk2(C))
중간자 공격(Meet-in-the-Middle Attack)이란?
중간자 공격(MitM)은 공격자가 시간과 공간(메모리) 사이의 상충 관계(trade-off)를 활용하는 암호분석 공격 유형입니다. 이 공격을 통해 공격자는 원래 상태에서 공격을 수행하는 데 필요했던 난이도를 크게 낮출 수 있습니다.
'중간자 공격'이라는 용어는 머클(Merkle)과 헬먼(Hellman)이 처음 소개했습니다. 이름 그대로 한쪽 끝에서는 암호화를, 다른 쪽 끝에서는 복호화를 진행한 뒤 그 결과를 가운데에서 연결(matching)하는 방식입니다.
MitM 공격은 대상 연산을 둘로 나누어 각 부분을 독립적으로 처리할 수 있게 만듭니다. 즉, X만큼의 시간이 필요하던 공격을 Y만큼의 시간과 Z만큼의 저장 공간이 필요한 공격으로 변환하는 것입니다. 궁극적인 목표는 무차별 대입(brute-force) 공격에 드는 노력을 획기적으로 줄이는 데 있습니다.
중간자 공격의 공격자는 거대한 암호분석 공격에 내재된 어려움을 '가운데에서 만남'으로써, 분석해야 할 영역을 절반으로 줄여 자신들이 실행 가능한 수준으로 만들려 합니다.
공격의 목적과 주요 표적
공격의 목적은 로그인 자격 증명, 계좌 정보, 신용카드 번호 등 개인 정보를 탈취하는 것입니다. 주요 표적은 금융 애플리케이션 사용자, SaaS 기업, 전자상거래 사이트 등 로그인이 필요한 웹사이트들입니다.
공격으로 확보한 정보는 신원 도용, 승인되지 않은 자금 이체, 무단 비밀번호 변경 등 다양한 목적으로 악용될 수 있습니다.
중간자 공격의 작동 원리
두 개의 키 K1과 K2가 평문 P를 암호문 C로 암호화하는 데 사용되며, 복호화에도 동일한 K1, K2가 사용됩니다. 이때 첫 번째 암호화 단계와 첫 번째 복호화 단계에서 생성되는 중간값(intermediate value) M은 서로 같아야 하며, 다음 두 관계가 동시에 성립해야 합니다.
- Ek1(P) = M
- Dk2(C) = M
암호분석가가 평문 P와 암호문 C의 한 쌍을 미리 확보하고 있다면, K1의 가능한 모든 값(256개)을 대입하여 나오는 모든 M 값을 기록할 수 있습니다. 마찬가지로 K2의 모든 값에 대해 M을 구한 뒤, 양쪽의 M 값들을 서로 비교하여 일치하는 K1-K2 쌍을 찾아냅니다.
일치하는 쌍이 하나뿐이라면 그것이 바로 원하는 키입니다. 만약 후보 쌍이 여러 개 존재한다면, 가로챈 또 다른 평문/암호문 쌍을 추가로 이용하여 가능성을 좁혀 나갑니다.