DES

Data Encryption Standard

표준문서 : FIPS-46

1 개요

1975년에 IBM에서 개발하고 1979년에 미국 NBS(National Bureau of Standards, 현 NIST)가 국가 표준 암호 알고리즘으로 지정한 대칭키 암호 알고리즘. 갑자기 나온 알고리즘은 아니고 DES가 나오기 이전인 1971년에 IBM에서 '루시퍼'라는 암호 알고리즘을 개발했는데 이를 개량하여 NIST가 국가 표준으로 지정한 알고리즘이 바로 DES. 이름부터가 'Data Encryption Standard'로 표준임을 어필하고 있다. 21세기에 와서는 이미 낡아도 한참 낡은 알고리즘이지만 70~80년대 당시에는 강력한 알고리즘이어서 워낙 오랫동안 표준으로 쓰여왔던 터라 오늘날에도 종종 이 기술의 흔적을 마주칠 수 있을 정도.

블록 암호 기법을 사용하며 16단계의 파이스텔 네트워크(Feistel Network)를 거쳐 암호화를 수행한다. 블록의 단위는 64비트로 평문을 64비트 단위로 암호화를 수행하여 64비트의 암호화 문서를 생성하며 키 길이는 64비트지만 실제로는 패리티 비트가 8비트 붙어있어서 실제 키 길이(=암호화 강도)는 56비트.[1] 아직 기술적 근간인 파이스텔 네트워크(Feistel Network)상에서의 구조적인 취약점은 발견되지 않았으나[2] 알고리즘 자체는 여전히 견고한 편이지만 문제는 56비트 키가 오늘날 컴퓨팅 환경에서는 너무 짧다는 것. 이미 1998년에 미화 25만불을 들여 만든 DES 공격장치를 통해, 무차별 공격(Brutal Force Attack)방식으로 2일 이내에 암호를 털어낼 수 있었다. 그 이후로도 이러한 공격 시도는 계속되어서, 2006년엔 미화 1만불만으로 COPACOBANA와 같은 더 강력한 장치가 개발되기도 했으며 그보다 컴퓨팅 환경이 훨씬 발전한 2015년 현재를 기준으로 하면 암호화의 의미가 없다. 평범한 개인용 PC로도 3,4일 안에 뚫을 수 있다. 따라서 현대에는 기존에 암호화된 문서를 복호화하는 용도로만 사용하고 신규 암호화 문서를 생성하는데는 절대로 사용하지 말 것을 권장하는 암호화 알고리즘이다.

이 문제를 해결하기 위해 IBM이 땜빵으로 만들어 제시한 것이 3-DES(Triple DES)다. 이름 그대로 3중으로 DES를 적용해서 키 길이를 3배로 늘리는 기법이다. 구체적으로는 DES 알고리즘을 이용하여 암호화→복호화→암호화를 거치는데, 키는 세개를 전부 다른 것으로 쓸 수도 있고 처음과 마지막 암호화는 같은 것을 쓰고 중간의 복호화만 다른 키를 써서 2개만 쓸 수도 있다. [3] 이렇게 키를 112비트~168비트로 늘리는 효과를 얻어내는 것. 이 방법은 꽤 효과가 있어서[4] 168비트의 경우 오늘날에도 쓸만한 수준의 안전성을 제공한다. 게다가 이미 DES가 매우 널리 사용되고 있었기 때문에 비용적 측면에서도 굉장히 저렴한 해결책이었다. 다만 1회의 암/복호화를 위해 걸리는 시간이 DES의 3배가 되다보니 좀 느리다는 것이 결점.[5] 아래 언급하는 AES가 나올 때까지는 널리 쓰였다.

결국 땜빵에 지친 NIST가 2001년 공모전을 통해 새로운 표준 암호 알고리즘을 정하기로 했고 5개의 최종 후보안 중에 선택된 것이 현행 AES. 이쪽은 기본적으로 최소 128비트, 최대 256비트까지의 키를 사용할 수 있다. 공모전을 통해 알고리즘을 선정한다면 알고리즘이 공개되어버릴 것이고 그럼 무용지물이 아닌가 하겠지만 암호 알고리즘은 원래부터 공개하는 것이 원칙이다. 암호화의 견고함은 알고리즘의 비밀성이 아닌 키에 의존[6] 해야하며 알고리즘은 수학적으로 문제가 없는가를 검증[7]받아야하기 때문.

앞에서도 이야기 했듯이 DES는 IBM에서 만든 원작(?)인 '루시퍼'(Lucifer)라는 암호 알고리즘에 기반하는 기술이다. 이 루시퍼를 NSA가 가져다가 S-Box[8]를 약간 고쳐서 만든게 DES. 그런데 이 S-Box에 들어간 숫자들 때문에 루머가 생기기도 했다. 보통 암호 디자인에 어떤 숫자가 필요하다면 'nothing up my sleeve number' 라고해서 파이라던가 황금비율라던가 아니면 12345678... (..) 에서 따온 숫자를 넣어 여기에 수작 안부렸음ㅇㅇ이라는 사실을 표명하는데, NSA는 DES의 S-Box에 어째 근본없는 이상한(...) 숫자를 집어넣었던 관계로 아무리 봐도 수상했던 것. 이때문에 DES가 현역이던 당대부터 "NSA가 혹시 일부러 마스터키나 백도어를 만든 것이 아니냐" 라는 의혹이 따라불었지만 학계에서 조사한 결과 그런 거 없었고 NSA가 S-Box를 변경한 이유는 Lucifer/DES가 만들어질 당시에는 민간 학계에 알려지지 않은 분차별 공격 방식 (differential cryptanalysis)에 루시퍼가 취약했기 때문에 NSA가 비밀 연구의 결과물을 추가하여 보완했던 것으로 판명났다.

하지만 NSA 구성원들이 수학계의 신이 아니라서(..) DES S-Box 일부에 분차별 공격 취약점이 남아있어서 보장된 56비트보다는 약간 낮은 보안 레벨로 판명났으나 이제와서는 어차피 56비트가 이미 현저히 낮은 키 강도가 되어버린 관계로 별 의미가 없다 (...)

2 기여

2.1 선형 공격(Linear Cryptanalysis)

DES는 선형 공격에 취약하다. DES 알고리즘에 대한 공격으로 선형 공격이 가장 강력하는 것으로 알려져있다.
이를 방지하기 위해 DES 직후에 개발된 알고리즘은 대부분 SPN(Substitution-Permutation-Network) 구조로 설계되었다.

2.2 차분 공격(Differential Cryptanalysis)

DES는 차분 공격에 취약하다.
선형 공격에 안전하기 위해서는 차분 공격에 대한 안전성을 조금은 포기해야하는데
이를 최소화하기 위한 방법으로 AES의 S-box가 설계되었다.

3 활용

3.1 3DES(Triple-DES 또는 TDES)

DES의 키 길이는 DES 개발 당시 충분히 안전한 길이었으나 컴퓨터의 능력이 향상되면서 우려되는 수준까지 오게 되었다.
이에 NIST는 AES 알고리즘을 공모하면서 그 사이에 DES를 안전하게 사용하기 위한 방법을 고안하였는데
이 중 하나가 3DES이다. 이 외로는 DES-X 등이 있다.
3DES는 DES를 세번 돌리는 방법으로 EEE(Encryption-Encryption-Encryption), EDE(Encryption-Decryption-Encryption) 등 여러 방법이 있다.
이 중 EDE 방식이 가장 많이 쓰이는데
이는 키를 어떻게 사용하느냐에 따라 기존에 사용중인 DES와 호환이 가능하다는 이유 때문.
[math]E_{K_2}(D_{K_1}(E_{K_1}(x)))=E_{K_2}(x) [/math]

3DES는 키를 세개를 사용할 수 있지만
키를 두개를 쓰는것과 세개를 쓰는 것과 키 강도가 동일하기 때문에
일반적으로 키를 두개 쓰는 방식을 사용한다.

자세한 것은 수식 잘 쓰는 사람이 남기길 바란다
  1. ↑ 알고리즘 특징상 키 생성단계에서 weak key가 존재한다
  2. ↑ 실제로 다른 암호화 알고리즘에서도 여전히 사용하고 있으며 현행 AES는 파이스텔 네트워크 대신 SPN을 사용하지만 후보안 중에는 파이스텔 네트워크에 기반한 것이 많았다고 한다. 국산 암호 알고리즘인 SEED 알고리즘도 파이스텔 네트워크를 사용한다.
  3. ↑ 여담으로 1개만 쓰면 어떻게 되느냐...면 멀쩡한 평문을 암호화-복호화-암호화를 거치는 것이 되어 그냥 DES 1번만 적용한 것과 같은 결과가 나온다(...). 정확히는 1단계와 2단계의 키는 같은 것을 써서는 안된다.키 전수조사만 하면 복호화가 이루어지므로 56비트의 키만을 추측하는것과 동일한 안전성이기 때문이다.
  4. ↑ 키 길이가 1비트만 늘어나도 무차별 공격에 필요한 대입횟수는 2배로 늘어나기 때문에 키 길이를 늘리는 것은 일단 효과적인 방법이다.
  5. ↑ 이 부분은 암호화 알고리즘에서 가장 중요한 이슈인데, 컴퓨팅 환경이 좋아질수록 암호화에 사용하는 데이터(평문)의 크기 역시 증가하기 때문이다.
  6. ↑ 이를 '커크호프의 원리'(Kerkhoff's principle)라고 한다. 원문은 "A cryptosystem should be secure even if everything about the system, except the key, is public knowledge."
  7. ↑ 에릭 레이몬드(Eric Raymond)가 커크호프의 원리를 확장한 것으로 "상대방(암호해독자)가 암호화 시스템의 소스코드를 확보하지 못할 것이라고 가정하고 만든 시스템은 그 자체로 믿을 수 없다. 공개되지 않은 소스(closed source)는 절대로 신뢰하지 말아라"라고 했다.
  8. ↑ 간단히 설명하자면 입력 데이터를 지정된 숫자로 바꿔서 암호를 어렵게 만드는 기법이다. 사족으로 AES는 이걸 창조롭게 재발명하여 암호화 속도를 높이고 싶으면 S-Box를 메모리에 박아놓고, 프로그램 메모리 양을 줄이려면 실행시 S-Box를 연산으로 구해내는 기법을 사용했다. 입맛에 따라 고를 수 있게. (..)