구 암호표준 DES(Data Encryption Standard) 란? [이해편]

"We sent the S-boxes off to Washington. They came back and were all different."

"우리는 S-Box 들을 워싱턴으로 보냈다. 모든 것이 달라져서 돌아왔다."

 

 

- Alan Konheim(DES 설계자)

 

 

DES 개발에 참여한 몇몇 설계자는 미 국가안보국인 NSA가 DES를 좀 더 취약하도록 수정하지

않았다고 얘기한다.

 

DES는 Data Encryption Standard 의 줄임말이다.

DES는 IBM사의 암호 설계 연구원이었던 Horst Feistel의 루시퍼(Lucifer) 암호에 기반하고 있다.

또한 DES는 비밀키(Secret Key) 방식의 암호화 알고리즘이다.

암호화를 할 때 입력한 키 값을 모르면 복호화가 안된다는 의미다.

1972년에 NBS 미 국가표준국에서는 암호체계 제안요구서를 발표하여 유일하게 이 요구서의 요구를

충족하는 IBM의 루시퍼 암호를 당시 암호 분야에 전문가가 없었던 NBS는 NSA로 이관했다.

 

 

[NSA 로고]

 

이 때, 미 국가안보국 NSA는 초 극비기관이었고, 미군과 미 정부에 사용되는 암호체계를 설계하고

구현하는 업무를 맡은 중요한 정보기관이었다.

DES의 유력한 후보였던 IBM사의 루시퍼 암호를 NSA 입장에서는 극비리에 검토하게 된다.

뒤늦게 NSA가 DES를 검토했다는 사실이 일반에 알려지게 되면서, NSA가 DES에 몰래

해독가능한 뒷 경로(Backdoor)를 숨겨놨을 것이라고 사람들은 의심하게 되었다.

 

 

[NSA 본부 전경]

 

 

어찌되었건, 이러한 의심은 오랜 기간 동안 DES가 시장에서 사용되어 오면서 백도어가 없는 것처럼

여겨진다. 많은 사람들의 의심은 단지 의심으로 끝났다.

이런 의심 때문에 DES는 표준암호로써 별로 좋은 인상을 남겨주지는 못했다.

 

초창기 IBM사에서 만든 루시퍼 암호는 128bit 키(Key) 값을 가지도록 설계되었다.

하지만, NSA가 검토할 당시 이 키 값을 64bit로 변경하였고, 내부적으로 56bit만을 사용하게 된다.

또, S-Box 부분도 변경되었는데, 이 S-Box의 독특한 부분은 DES가 안전할 수 있는 중요한 부분이다.

따라서 사람들의 의심이 끊이지 않았던 것이기도 하다.

 

[DES의 근간이 되는 페이스텔 암호체계의 원리]

 

DES는 페이스텔이란 사람이 설계한 암호체계인 페이스텔 암호체계를 기반으로 하고 있다.

이 암호체계는 입력 값 P를 두 개로 나눠서 연산하는데, L과 R로 각각 나누게 된다.

DES는 64bit 블록 암호이기 때문에 입력 값 64bit 마다 연산이 진행되고, L과 R이 각각 32bit다.

 

DES는 많은 부분이 선형식으로 구성되어 있다.

선형식은 말 그대로 수학 식으로 풀 수 있는 형태다.

암호학에서는 선형식을 비 선형식으로 바꾸는데 주안점을 둔다.

선형식은 수학자들이 풀기 쉽지만, 비 선형식은 특정한 규칙이 없는 것처럼 보이기 때문에

식을 도출하기가 매우 난해하다.

 

DES는 실제 56bit의 키 길이를 가지고 있기 때문에 전수 키 조사(Exhaustive Key Search)를

진행할 때의 걸리는 작업량이 2^55(2에 55승) 가 된다.

이는 현재의 컴퓨터 연산처리 속도에 비하면 매우 적은 것으로 취약하다고 할 수 있다.

 

암호학에서 생일문제(Birthday Problem)는 이러한 전수 키 조사의 작업량을 확률적으로 1/2 가량

줄어들 수 있다.

생일문제란, 한 방에 얼마 만큼의 사람이 있어야 생일이 같은 두 사람을 찾을 수 있느냐는 문제인데,

확률적으로 생일이 같은 사람이 있을 확률은 약 23명만 있어도 찾을 수 있다는 것이다.

사람들의 생일은 무작위기 때문에 최악의 경우는 365명이 있어도 서로 같지 않을 수도 있지만,

평균적인 경우나 최상의 경우도 생각을 해볼 수 있기 때문에 확률적으로 역설적이지만

많은 수의 사람이 필요하지는 않다는 것을 알 수 있게 된다.

아래 생일문제 계산기를 이용하면 그래프로 좀 더 쉽게 확인할 수 있다.

Enter number of Birthdays to calculate: 에 15라고 입력된 값은 한 방에 15명이 있다는 의미다.

이 값은 변경할 수 있으니 직접 테스트 해보기 바란다. 우측의 Calculate 단추를 누르면 시작한다.

 

 

 

[생일문제 계산기]

 

 

생일문제 계산기의 좌측은 무작위로 생성된 생일들이고, 이 생일들 중에서 서로 동일한 생일이 있으면

우측의 그래프에 어느 정도 확률인지 출력된다.

한 방에 있을 수 있는 사람의 수의 최대 값은 60이다.

 

전수 키 조사에서 또한 마찬가지로 모든 수를 조사하기 전에 절반 쯤 조사를 하다보면 발견하게 될

가능성이 높다는 의미다.

DES의 이론적인 공격 방법은 다양하지만, 하드웨어의 급속한 발전 탓에 전수 키 조사에서 조차

취약성을 나타내고 있어 급기야 이 문제의 대안으로 삼중(Triple) DES를 고안하기에 이른다.

 

삼중 DES가 나오기 전에 두번 DES를 연산하려는 시도도 있었으나, 공격 방법이 발견되면서

삼중 DES로 대체되었다.

이중 또는 삼중 DES의 핵심은 키 길이를 늘리는데 있다.

키 길이가 늘어나면 전수 키 조사의 작업량이 늘어나기 때문에 새로 나올 암호 표준이 준비되는 동안

어느 정도 시간을 벌 수 있었다.

 

삼중 DES는 다행히 공격 방법의 비실용적인 측면 때문에 이중 DES 보다는 안전하다고 할 수 있었다.

삼중 DES의 암호화 방법은 약간 독특한데 암호화-복호화-암호화의 형태가 주로 사용되었다.

이런 형태는 기존 DES와의 하위 호환성을 위해 사용되었으며, 키 길이는 112bit였다.

 

현재에는 AES(Advanced Encryption Standard) 가 블록암호의 표준이자 보편화가 되어 있다.

AES는 좀 더 다른 형태의 연산과 강화된 키 길이 등으로 기존의 구 암호표준인 DES와 Triple-DES를

대체한다.

 

 

 

 

 

출처 : http://blog.naver.com/tpinlab/10121774937