DES, 기술 발전에 비해 짧은 길이로 보안 취약점 드러나 AES가 이어받아
역사 뒤안길로 사라졌지만, 암호 기술 발전에 지대한 영향 미쳐

[보안뉴스 김영명 기자] 데이터 암호 표준(Data Encryption Standard, 이하 ‘DES’)이란 ‘개인키(대칭키) 암호화 알고리즘’으로, 송신자와 수신자가 같은 키(key)로 데이터를 암호화·복호화하는 것을 말한다. 전 세계 컴퓨터 시장을 선도했던 IBM이 개발한 알고리즘을 바탕으로 DES를 발표했으며, 정부는 이를 공식 국가표준으로 채택, 30여년간 암호기술의 표준으로 자리매김했다. 하지만 DES는 차등 암호분석에는 강하지만, 56비트로 길이가 짧아 무차별 대입 공격에는 취약하다는 약점이 있다.


[이미지=utoimage]

DES, 정부 인증 ‘국가암호’였지만 AES에 자리 내줘
DES는 56비트의 키가 16라운드의 작업을 통해 만들어진 64비트 블록 암호문이다. 미국 국립표준기술연구소(NIST)의 전신인 NBS(National Bureau of Standards)는 암호기술의 필요성을 절감하고, 정부 주도로 표준 암호 알고리즘을 개발하기로 했다. 위키백과에 따르면, IBM은 1974년 ‘루시퍼 암호 알고리즘’을 제안, 이를 수정해 1975년에 DES를 발표했다. DES는 이후 NIST의 ‘국가표준(Federal Information Processing Standards, FIPS) 46’으로 등록돼 정부와 공공기관에서 사용하게 됐다.

하지만, DES는 56비트 키 길이로 현재 컴퓨터 환경에 비해 너무 짧아 보안에 취약하다. 특히, DES는 백도어가 포함돼 특수한 방법을 사용하면 정부기관에서 쉽게 해독할 수 있을 것이라는 주장도 제기되며, 국가표준으로 채택되기 전부터 키 크기의 적정성에 의문이 제기됐다. 하지만, DES는 초창기부터 NSA와 외부 컨설턴트가 논의한 끝에 단일 칩에 맞춰 적용이 가능하도록 키 크기를 128비트에서 56비트로 줄였다. 그 결과, 1999년 국제 비영리 단체인 전자 프론티어 재단(Electronic Frontier Foundation, EFF)과 디스트리뷰트닷넷은 공동으로 22시간 15분 만에 이를 해독했다.

이에 다급해진 NIST는 2001년 새로운 암호기술 표준을 정하기로 하고 공모전을 진행했다. 이때 벨기에에서 개발된 대칭키 암호 알고리즘인 ‘레인달(Rijndael)’이 새로운 암호기술 표준인 AES(Advanced Encryption Standard, 고급 암호화 표준)로 최종 선택됐다. 현재는 기존의 암호화된 문서를 복호화하는 용도로만 사용하는 데 그치고 있지만, DES 알고리즘 구조는 현대의 암호 기술 발전에 적지 않은 영향을 미쳤다고 평가되고 있다.

DES를 활용한 일반 텍스트의 암호화 알고리즘은 하나의 블록(64비트 평문)이 64비트 치환 입력을 얻기 위해 비트를 재정렬하는 초기순열(Initial Permutation, IP)을 거친다. 64비트 치환 입력은 32비트 왼쪽 블록과 32비트 오른쪽 블록으로 나뉘며 각각 라운드(round)로 불리는 16개의 동일한 기능을 반복한다.

앞서 말했듯이 DES는 기술의 발전으로 현재는 보안에 취약하지만, 16라운드로 이뤄지는 DES를 세 번 반복해서 사용하는 트리플(Triple) DES는 DES에 비해 안전한 것으로 알려졌다. 16라운드가 완료되면 최종순열(Final Permutation, FP)이 수행되고, 64비트 암호문을 얻게 된다. 이렇게 두 개의 32비트로 분할돼 번갈아 처리되는 과정을 ‘페이스텔 함수(Feistel scheme)’라고 부른다. 페이스텔(Feistel) 구조는 복호화와 암호화가 매우 유사한 프로세스이지만, 복호화 때는 서브키가 역순으로 적용된다.

DES, 쏟아지는 암호 해석기술은 이론뿐...우리나라도 독자 암호 선보여
DES는 다른 어떤 블록 암호보다 더 많은 해석 정보가 공개됐지만, 가장 실용적인 암호 분석 방식은 모든 암호를 대상으로 가능한 모든 키를 차례로 대입해보는 무차별 대입 방식이다. 이때는 키의 길이에 따라 가능한 키의 수와 함께 실현 가능성도 결정된다.

EFF의 25만 달러 DES 크래커(파괴하는 기계)에는 1,856개의 맞춤형 칩이 포함돼 며칠 만에 DES 키를 무차별 대입할 수 있다. 1977년 디피와 헬만은 약 2,000만 달러에 만들 수 있는 하루 만에 DES 키를 찾을 수 있는 기계를, Wiener는 7시간 이내에 키를 찾을 수 있는 100만 달러짜리 키 검색기를 제안했지만, 실제 구현하지는 못했다.

DES의 취약성은 1997년 RSA Security가 개최한 콘테스트에서 DESCHALL 프로젝트팀(Rocke Verser, Matt Curtin, Justin Dolske)이 DES로 암호화된 메시지를 해독해 1만 달러의 상금을 탔다. 또한, 1998년 EFF에서 25만 달러의 비용으로 맞춤형 DES 크래커를 구축했을 때 DES를 빠르게 크래킹할 수 있다는 것이 입증되기도 했다.

2012년에 데이비드 헐튼(David Hulton)과 목시 말린스파이크(Moxie Marlinspike)는 48개의 Xilinx Virtex-6 LX240T FPGA 시스템을 발표했다. 각 FPGA에는 400MHz에서 실행되는 40개의 파이프라인된 DES 코어가 포함됐으며, 초당 768기가키의 속도를 보였다. 이 시스템은 약 26시간 내에 전체 56비트 DES 키를 해석할 수 있다.

또한, 무차별 공격보다 덜 복잡하지만, DES의 16라운드를 깨뜨릴 수 있는 △차분 암호 분석(differential cryptanalysis, DC) △선형 암호 분석(linear cryptanalysis, LC) △데이비스 공격(Davies′ attack) 등 세 가지 공격이 알려졌다. 하지만 이 공격은 이론에 그치고 있다.

‘차분 암호 분석’은 1980년대 후반 이스라엘 과학자인 일라이 바이햄(Eli Biham)과 아디 샤미르(Adi Shamir)가 재발견했으며, IBM과 NSA도 이를 알고 있었지만 비밀에 부쳤다. 16라운드를 모두 해제하려면 차분 암호해석을 위해 2개의 평문을 선택해야 한다. DES는 차분 암호 분석에 내성을 갖도록 설계돼 있다.

‘선형 암호 분석’에 따르면 공격의 데이터 요건을 최소 4배를 줄이기 위해 복수의 선형 근사치를 사용할 수 있다. 선형 암호 분석의 선택된 평문 변형에서도 DES 데이터 복잡도와 비슷한 감소치를 얻을 수 있다.

‘개량된 데이비스의 공격’은 DES에 특화된 기술로 1980년대에 도널드 데이비스가 처음 제안했으며, 이후 일부 개선됐다. 가장 강력한 형태의 공격에는 알려진 2개의 평문이 필요하며, 계산 복잡도는 250, 계산 성공률은 51%이다.

한편, 현재도 은행 등 전 세계 일부 기관에서 트리플 DES를 사용하고 있는 것으로 알려졌다. 우리나라의 경우는 한국인터넷진흥원에서 1999년 순수 우리기술로 개발한 대칭키 암호화 알고리즘인 SEED(블록 크기 128비트)와 ARIA(블록 크기 128비트, 키 크기 128·192·256비트)를 일부 활용하고 있다.
[김영명 기자(boan@boannews.com)]

<저작권자: 보안뉴스(www.boannews.com) 무단전재-재배포금지>