DES
1. 개요
'''D'''ata '''E'''ncryption '''S'''tandard
- 표준문서 : FIPS-46
2. 역사
갑자기 나온 알고리즘은 아니고 DES가 나오기 이전인 1971년에 IBM에서 '루시퍼'라는 암호 알고리즘을 개발했는데 이를 개량하여 NIST가 국가 표준으로 지정한 알고리즘이 바로 DES. 이름부터 'Data Encryption Standard'로 표준임을 어필하고 있다. 21세기에 와서는 이미 낡아도 한참 낡은 알고리즘이지만 70~80년대 당시에는 강력한 알고리즘이어서 워낙 오랫동안 표준으로 쓰여왔던 터라 오늘날에도 종종 이 기술의 흔적을 마주칠 수 있을 정도다.
블록 암호 기법을 사용하며 16단계의 파이스텔 네트워크(Feistel Network)를 거쳐 암호화를 수행한다. 블록의 단위는 64 비트로 평문을 64 비트 단위로 암호화를 수행하여 64 비트의 암호화 문서를 생성하며 키 길이는 64 비트지만 실제로는 패리티 비트가 8 비트 붙어있어서 실제 키 길이(=암호화 강도)는 56 비트이다. 이는 알고리즘 특성상 키 생성 단계에서 weak key가 존재하기 때문이다.
아직 기술적 근간인 파이스텔 네트워크(Feistel Network)상에서의 구조적인 취약점은 발견되지 않았으며[1] 알고리즘 자체는 여전히 견고한 편이지만, 문제는 56 비트 키가 오늘날 컴퓨팅 환경에서는 너무 짧다는 것이다. 이미 1998년에 미화 25만 불을 들여 만든 DES 공격 장치를 통해, 무차별 공격(Brutal Force Attack)방식으로 이틀 이내에 암호를 알 수 있었다. 그 이후로도 이러한 공격법은 계속되어서, 2006년엔 미화 1만 불만으로 COPACOBANA와 같은 더 강력한 장치가 개발되기도 했으며, 그보다 더 발전한 2015년을 기준으로 하면 '''암호화의 의미가 없다.''' 평범한 개인용 PC로도 최적화된 방법(SIMD, GPGPU 등등)을 사용하면 수 시간 만에 뚫을 수 있다. 따라서 현대에는 기존에 암호화된 문서를 복호화하는 용도로만 사용하고 신규 암호화 문서를 생성하는 데는 '''절대로''' 사용하지 말 것을 권장하는 암호화 알고리즘이다. 이 문제를 해결하기 위해 IBM이 임시로 만들어 제시한 것이 후술할 3-DES(Triple DES)이다.
이후 NIST에서 2001년 공모전을 통해 새로운 표준 암호 알고리즘을 정하기로 했고 5개의 최종 후보안 중에 선택된 것이 지금의 AES이다. 이쪽은 기본적으로 최소 128 비트, 최대 256 비트까지의 키를 사용할 수 있다. 공모전을 통해 알고리즘을 선정한다면 알고리즘이 공개되어버릴 것이고 그럼 무용지물이 아닌가 하겠지만 암호 알고리즘은 '''원래부터 공개하는 것이 원칙'''이다. 암호화의 견고함은 알고리즘의 비밀성이 아닌 '''키에 의존'''해야 하며[2] 알고리즘은 '''수학적으로 문제가 없는가를 검증'''받아야 하기 때문이다[3].
3. 취약점
- 선형 공격(Linear Cryptanalysis)
DES 알고리즘에 대한 공격으로 선형 공격이 가장 강력한 것으로 알려져있다. 이를 방지하기 위해 DES 직후에 개발된 알고리즘은 대부분 SPN(Substitution-Permutation-Network) 구조로 설계되었다.
- 차분 공격(Differential Cryptanalysis)
선형 공격에 안전하기 위해서는 차분 공격에 대한 안전성을 조금은 포기해야하는데, 이를 최소화하기 위한 방법으로 AES의 S-box가 설계되었다.
4. 응용
4.1. 3-DES(Triple-DES 또는 TDES)
이름 그대로 DES를 세 번 적용해서 키 길이를 세 배로 늘리는 기법이다. DES의 키 길이는 DES 개발 당시 충분히 안전한 길이었으나, 컴퓨터의 능력이 향상되면서 우려되는 수준까지 오게 되었다. 이에 NIST는 AES 알고리즘을 공모하면서 그 사이에 DES를 안전하게 사용하기 위한 방법을 고안하였는데, 이 중 하나가 3-DES이다.
$$E_{K_2}(D_{K_1}(E_{K_1}(x)))=E_{K_2}(x) $$
구체적으로는 DES 알고리즘을 이용하여 암호화→복호화→암호화를 거치는데, 키는 세 개를 전부 다른 것으로 쓸 수도 있고(168 비트[A]) 처음과 마지막 암호화는 같은 것을 쓰고 중간의 복호화만 다른 키를 써서 두 개만 쓸 수도 있다(112 비트[B]).[4] 이렇게 키를 112 비트[A]~168 비트[B]로 늘리는 효과를 얻어내는 것이다.[5] 게다가 이미 DES가 매우 널리 사용되고 있었기 때문에 비용적 측면에서도 굉장히 저렴한 해결책이었다. 다만 1 회의 암/복호화를 위해 걸리는 시간이 DES의 3 배가 되다보니 좀 느리다는 것이 결점이다. 컴퓨팅 환경이 좋아질수록 암호화에 사용하는 데이터(평문)의 크기 역시 증가하기 때문이다.
3-DES는 DES를 세번 돌리는 방법으로 EEE(Encryption-Encryption-Encryption), EDE(Encryption-Decryption-Encryption) 등 여러 방법이 있다. 이 중 EDE 방식이 가장 많이 쓰이는데, 이는 키를 어떻게 사용하느냐에 따라 기존에 사용중인 DES와 호환이 가능하다는 이유 때문이다.
하지만 시간이 지난 현재는 3-DES도 지원이 중단되었다. 키를 2개만 사용하는 방식은 2015년에, 키를 3개 사용하는 방식은 2018년에 지원이 중단되었으며, 2023년 이후에 사용이 금지된다. 이유는 Sweet32 공격이라는, 브루트 포스의 변종 알고리즘에 매우 취약하기 때문이다. 따라서 3-DES는 기존에 암호화된 문서를 해독하는 용도로만 사용하고, 새로 암호화하는 용도로 사용하지 않아야 한다.
5. 여담
앞에서도 이야기 했듯이 DES는 IBM에서 만든 원작(?)인 '루시퍼'(Lucifer)라는 암호 알고리즘에 기반하는 기술이다. 이 루시퍼를 NSA가 가져다가 S-Box[6]를 약간 고쳐서 만든게 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 비트가 이미 현저히 낮은 키 강도가 되어버린 관계로 별 의미가 없다.
[1] 실제로 다른 암호화 알고리즘에서도 여전히 사용하고 있으며 현행 AES는 파이스텔 네트워크 대신 SPN을 사용하지만 후보안 중에는 파이스텔 네트워크에 기반한 것이 많았다고 한다. 국산 암호 알고리즘인 SEED 알고리즘도 파이스텔 네트워크를 사용한다.[2] 이를 '커크호프의 원리'(Kerkhoff's principle)라고 한다. 원문은 "A cryptosystem should be secure even if everything about the system, except the key, is public knowledge."[3] 에릭 레이몬드(Eric Raymond)가 커크호프의 원리를 확장한 것으로 "상대방(암호 해독자)이 암호화 시스템의 소스 코드를 확보하지 못할 것이라고 가정하고 만든 시스템은 그 자체로 믿을 수 없다. 공개되지 않은 소스(closed source)는 절대로 신뢰하지 말라"고 했다.[A] A B 중간자 공격으로 인한 취약점 때문에 실질적으로는 112비트이다.[B] A B 중간자 공격으로 인한 취약점 때문에 실질적으로는 80비트이다.[4] 키를 한 개만 쓰면 멀쩡한 평문을 암호화-복호화-암호화를 거치는 것이 되어 '''그냥 DES 한 번만 적용한 것과 같은 결과가 나온다'''. 정확히는 1 단계와 2 단계의 키는 같은 것을 써서는 안 된다. 키 전수조사만 하면 복호화가 이루어지므로 56 비트의 키만을 추측하는 것과 동일한 안전성이기 때문이다.[5] 키 길이가 1 비트만 늘어나도 무차별 공격에 필요한 대입 횟수는 2 배로 늘어나기 때문에 키 길이를 늘리는 것은 일단 효과적인 방법이다.[6] 간단히 설명하자면 입력 데이터를 지정된 숫자로 바꿔서 암호를 어렵게 만드는 기법이다. AES는 이걸 창조롭게 재발명하여 암호화 속도를 높이고 싶으면 S-Box를 메모리에 박아놓고, 프로그램 메모리 양을 줄이려면 실행시 S-Box를 연산으로 구해내는 기법을 사용했다. 입맛에 따라 고를 수 있게 말이다.