DES는 어떻게 해독되었는가

DES에는 2^56개의 가능한 키가 있으며, 이는 약 7경 2천조(72,057,594,037,927,936)개의 키에 해당합니다. 엄청난 수처럼 보이지만 유한한 공간이므로 충분한 컴퓨팅 성능이 있으면 체계적으로 탐색할 수 있습니다.

키 공간 전수 탐색(무차별 대입)으로 올바른 키를 찾으려면 평균적으로 키 공간의 절반을 시험해야 합니다. DES의 경우 이는 약 2^55회의 시험 복호화에 해당하며, 현대 하드웨어에서는 각각 몇 번의 연산만 필요합니다.

1997년에 RSA Data Security는 DES로 암호화된 메시지를 해독하는 대가로 10,000달러의 상금을 내걸었습니다. 록 버서는 인터넷에 연결된 수만 대의 컴퓨터를 활용한 분산 컴퓨팅 활동을 조정했습니다.

96일간 탐색한 끝에 키가 발견되었습니다. 평문은 "강력한 암호 기술은 세상을 더 안전한 곳으로 만듭니다."였습니다. 이 활동은 DES를 해독할 수 있음을 보여 주었지만, 수개월의 시간과 막대한 규모의 조정이 필요했습니다.

Electronic Frontier Foundation은 1998년에 250,000달러를 들여 딥 크랙을 제작했습니다. 딥 크랙에는 주문형 집적 회로 1,856개가 들어 있었고, 각 회로는 초당 DES 키 250만 개를 시험할 수 있었습니다. 따라서 딥 크랙의 총 처리 속도는 초당 900억 개를 넘었습니다.

딥 크랙은 평균 약 9일 만에 전체 DES 키 공간을 전수 탐색할 수 있었습니다. 이는 250,000달러를 투자한 집요한 공격자가 2주 안에 DES를 해독할 수 있다는 증거였습니다.

DES Challenges II-1(1998년 2월)에서는 딥 크랙이 distributed.net 자원봉사 컴퓨팅 네트워크와 결합하여 단 39일 만에 DES를 해독했습니다. Challenges II-2(1998년 7월)는 56시간 만에 해독되었습니다.

단 1년 만에 96일에서 56시간으로 빨라진 것은 하드웨어의 발전과 더 나은 협력이 무차별 대입 공격을 얼마나 빠르게 가속할 수 있는지를 보여 주었습니다.

1999년 1월, EFF의 딥 크랙은 distributed.net과 협력하여 단 22시간 15분 만에 DES Challenge III를 해독하고 RSA Security가 수여한 10,000달러의 상금을 받았습니다.

DES를 24시간 안에 해독할 수 있다는 이 결정적인 시연으로 DES의 보안성을 옹호할 근거는 사실상 사라졌습니다. 얼마 지나지 않아 NIST는 DES를 대체할 암호를 선정하는 절차를 시작했고, 그 결과 고급 암호화 표준이 채택되었습니다.

Distributed.net은 일반 인터넷 사용자가 DES 챌린지에 자신의 CPU 연산 능력을 기부하는 자원봉사 컴퓨팅 활동을 조직했습니다. 가장 활발할 때는 수십만 대의 컴퓨터가 참여했습니다.

각 컴퓨터는 키 공간의 서로 다른 부분을 시험했고, 중앙 서버가 이를 조정했습니다. 이는 암호 분석을 위한 분산 컴퓨팅 모델의 선구적인 사례였으며, 오늘날에도 오래된 암호를 해독하는 것과 같은 도전에 사용됩니다.

키 공간 전수 탐색이 가능한 이유는 각 DES 복호화가 빠르고(하드웨어에서 마이크로초 단위) 서로 독립적이기 때문입니다. 키 N을 시험하는 것과 키 N+1을 시험하는 것 사이에는 의존성이 없으므로, 여러 컴퓨터에 탐색 작업을 완벽하게 병렬화할 수 있습니다.

이처럼 매우 쉽게 병렬화되는 특성 때문에 하드웨어를 두 배로 늘리면 시간이 정확히 절반으로 줄어듭니다. 컴퓨터를 더 추가하면 속도가 선형적으로 향상되므로 공격자에게 비용 면에서도 유리합니다.

Eli Biham과 Adi Shamir는 1990년에 차분 암호 분석을 발표했습니다. 이는 입력 쌍의 차이가 암호 라운드를 거치며 어떻게 전파되는지를 이용하는 기법입니다. DES에 적용하려면 이론적으로 2^47개의 선택 평문이 필요합니다.

DES의 S-박스는 나중에 차분 암호 분석에 대한 저항성을 염두에 두고 설계되었다는 사실이 밝혀졌으며, 이는 NSA가 1970년대에 이 기법을 알고 있었음을 시사합니다. 이 공격은 이론적으로 인상적이지만 실제로는 하드웨어 무차별 대입 공격에 비해 압도적으로 불리합니다.

Mitsuru Matsui는 1993년에 DES를 공격하려면 2^43개의 알려진 평문이 필요한 선형 암호 분석을 발표했습니다. 그는 이 공격을 구현하여 1994년에 실험적으로 DES를 해독했고, 이론적 분석을 확인했습니다.

선형 암호 분석은 S-박스 동작에 대한 선형 근사를 찾아 통계적 편향을 이용해 키 비트를 복구합니다. 이론적으로는 무차별 대입보다 훨씬 적은 데이터가 필요하지만, 하드웨어 공격이 등장하기 전에는 실용적이지 않았습니다.

차분 암호 분석은 1990년에 발표되었지만 선택 평문이 필요하므로 대부분의 실제 상황에서는 실용적이지 않습니다. 선형 암호 분석은 1993년에 발표되었고 알려진 평문으로 수행할 수 있지만, 그러한 평문이 2^43개 필요합니다.

하드웨어 무차별 대입 공격인 딥 크랙은 1999년에 22시간 만에 DES를 해독했습니다. 실제로는 이론적인 암호 분석 발전보다 하드웨어 공격이 훨씬 더 치명적이었습니다. 하드웨어 공격에는 특수한 평문-암호문 쌍이 전혀 필요하지 않았기 때문입니다.

공개적으로 문서화된 DES 해독은 정책에 즉각적인 영향을 미쳤습니다. NIST는 DES Challenge I이 성공한 해인 1997년에 고급 암호화 표준 경쟁 절차를 시작했습니다. 이 경쟁은 DES 표준화 절차의 약점을 피하도록 명시적으로 설계되었습니다.

은행과 정부 기관은 고급 암호화 표준이 개발되는 동안 임시 조치로 3중 DES로 전환하기 시작했습니다. DES 해독의 시간표는 고급 암호화 표준 도입 작업의 긴급성과 일정을 직접적으로 결정했습니다.

DES 해독 역사에 대한 이해를 확인해 보십시오.

DES는 점점 더 빠르게 해독되었습니다. 1997년에는 96일, 1998년에는 56시간, 1999년에는 22시간이 걸렸습니다. EFF의 250,000달러짜리 딥 크랙은 주문형 집적 회로를 사용해 초당 900억 개의 키를 시험했습니다.

차분 암호 분석(2^47개의 선택 평문)과 선형 암호 분석(2^43개의 알려진 평문)도 이론적으로 DES를 해독할 수 있지만, 실제로 결정타가 된 것은 하드웨어 무차별 대입 공격이었습니다. 22시간 만의 해독으로 DES는 실용적인 암호로서의 수명을 다했습니다.