암호 설계상의 약점
DES(데이터 암호화 표준)는 오랫동안 널리 사용되어 왔지만, 암호 자체의 설계 구조에서 몇 가지 약점이 발견되었습니다.
S-박스(S-box)의 약점
S-박스에서는 다음 세 가지 약점이 확인되었습니다.
- 출력 비트 간 종속성: S-박스 4의 경우, 일부 입력 비트를 조합하면 마지막 3개의 출력 비트가 첫 번째 출력 비트와 동일한 방식으로 변경될 수 있습니다.
- 동일 출력 생성: 특수하게 선택된 서로 다른 두 개의 입력이 S-박스 배열에서 같은 출력을 만들어낼 수 있습니다.
- 제한된 비트 변환으로 동일한 결과: 인접한 3개의 S-박스에서만 비트를 변환해도 단일 라운드에서 동일한 출력을 얻을 수 있습니다.
D-박스(D-box)의 약점
D-박스 설계에서는 하나의 미스터리와 하나의 약점이 지적되었습니다.
- 목적 불명확: 초기 순열(IP)과 최종 순열(FP)이 왜 필요한지 그 목적이 명확하게 규명되지 않았습니다.
- 비트 중복: 함수 내부의 확장 순열에서 각 4비트 그룹의 첫 번째 비트와 네 번째 비트가 반복해서 사용됩니다.
암호 키의 약점
암호 키와 관련해서도 여러 약점이 발견되었으며, 그중 가장 대표적인 것이 키 크기와 약한 키 문제입니다.
키 크기(Key Size)
전문가들이 지적하는 DES의 가장 심각한 약점은 바로 56비트라는 짧은 키 길이입니다. 공격자가 특정 암호문 블록에 대해 무차별 대입 공격(brute-force attack)을 시도하려면 최대 256개의 키를 모두 시험해야 하지만, 현대 컴퓨팅 환경에서는 이마저도 현실적으로 가능한 범위에 들어섰습니다.
- 현재의 기술로는 초당 약 100만 개의 키를 검사할 수 있으며, 이 경우 프로세서 하나를 사용하는 컴퓨터로 전체 키 공간을 탐색하는 데 100년 이상이 걸립니다.
- 그러나 100만 개의 칩을 장착한 병렬 처리 컴퓨터를 구축하면 약 20시간 만에 전체 키 공간을 검사할 수 있습니다.
- DES가 처음 등장했을 때 이러한 컴퓨터의 가격은 수백만 달러에 달했지만, 이후 비용은 빠르게 하락했습니다. 실제로 1998년에 개발된 특수 목적 컴퓨터는 단 112시간 만에 DES 키를 찾아냈습니다.
- 컴퓨터 네트워크 역시 병렬 처리를 흉내 낼 수 있습니다. 1997년 한 연구 단체는 인터넷에 연결된 3,500대의 컴퓨터를 활용해 RSA 워크숍에서 제시한 키를 120일 만에 찾아냈습니다. 전체 키 공간을 참여 컴퓨터들에게 분배하고, 각 컴퓨터가 담당 구간을 검사하는 방식이었습니다.
- 3,500대의 컴퓨터로 120일 안에 키를 찾을 수 있다면, 회원 42,000명 규모의 비밀 조직이라면 불과 10일 만에 키를 찾아낼 수 있다는 계산도 가능합니다.
약한 키(Weak Keys)
256개의 가능한 키 중 4개는 '약한 키'로 알려져 있습니다. 약한 키란 패리티 드롭(parity drop) 연산을 거친 후 모든 비트가 0이거나, 모두 1이거나, 절반은 0이고 절반은 1인 키를 말합니다. 이러한 약한 키로부터 생성되는 라운드 키들은 서로 동일하며, 원래 암호 키와 같은 패턴을 보입니다.
예를 들어, 어떤 약한 키에서 생성된 16개의 라운드 키는 모두 0으로만 구성되고, 다른 키에서 생성된 라운드 키는 절반은 0, 절반은 1로 구성됩니다. 그 이유는 키 생성 알고리즘이 먼저 암호 키를 두 개의 절반으로 나누기 때문입니다. 블록이 모두 0이거나 모두 1로 이루어져 있으면, 시프트나 순열 연산을 적용해도 블록의 내용은 전혀 변하지 않습니다.
이러한 약점들 때문에 DES는 안전한 암호 표준으로 인정받기 어려웠고, 결국 더 긴 키 길이와 강력한 구조를 갖춘 AES(고급 암호화 표준)로 대체되었습니다.