DES 설계와 Lucifer 암호

1971년 IBM Research의 Horst Feistel은 Lloyd's of London을 위한 은행 보안 프로젝트의 일환으로 Lucifer라는 암호를 개발했습니다. Lucifer는 128비트 키와 128비트 블록을 사용하는 최초의 현대적 블록 암호 중 하나였습니다.

Lucifer는 블록의 절반에 치환과 순열을 번갈아 적용하는 Feistel 구조를 사용하면 강력한 블록 암호를 만들 수 있음을 보여 주었습니다. Lucifer는 DES의 직접적인 전신이었습니다.

DES는 64비트 블록에 Feistel 구조를 16라운드 적용합니다. 각 라운드에서 64비트 블록은 32비트 절반 두 개로 나뉩니다. 오른쪽 절반을 48비트로 확장하고, 48비트 하위 키와 배타적 논리합을 계산한 뒤, S-상자를 통과시키고 순열을 적용한 다음 왼쪽 절반과 배타적 논리합을 계산합니다.

그런 다음 두 절반을 서로 바꾸고 이 과정을 반복합니다. 16라운드가 끝나면 최종 순열을 적용하여 64비트 암호문을 만듭니다. 복호화는 하위 키를 역순으로 사용하여 동일한 구조로 실행됩니다.

DES는 64비트(8바이트) 블록 단위로 데이터를 암호화합니다. 이 고정 블록 크기는 1977년의 하드웨어에는 적합했지만 보안상의 약점이 되었습니다. 충분한 데이터가 있으면 생일 역설에 따른 충돌이 발생할 가능성이 커집니다.

64비트 블록에서는 같은 키로 암호화한 데이터가 약 2^32개 블록(약 32GB)에 이르면 통계적 패턴이 나타납니다. 이 Sweet32 공격으로 인해 HTTPS와 같은 대용량 트래픽에서 3DES를 안전하게 사용할 수 없게 되었습니다.

DES는 64비트 키를 사용하지만, 그중 8비트는 오류 감지에 사용하는 패리티 비트이며 암호화에는 사용되지 않습니다. 따라서 실질적인 키 길이는 56비트에 불과합니다.

이는 가능한 DES 키가 2^56개(약 7.2경 개)뿐이라는 뜻입니다. 1977년의 기준에서는 충분하다고 여겨졌지만, 1997년에는 결의가 있는 공격자가 실제로 해독할 수 있음이 입증되었습니다.

DES는 평문 블록의 64비트를 재배열하는 초기 순열(IP)로 시작하고, 정확히 그 역순인 최종 순열(IP^-1)로 끝납니다. 이러한 순열은 암호학적 강도를 높이지 않습니다.

이 순열은 특정 1970년대 칩 구조에서 하드웨어 효율을 높이고 레지스터에 비트를 더 빠르게 로드할 수 있도록 설계되었습니다. 현대의 분석 결과에 따르면 순열은 보안에 아무런 기여도 하지 않습니다.

8개의 S-상자(치환 상자)는 DES의 비선형성을 담당하는 핵심 요소입니다. 각 S-상자는 6비트 입력을 받아 고정된 조회표를 사용해 4비트 출력을 생성합니다. 바깥쪽 2비트가 행을 선택하고 안쪽 4비트가 열을 선택합니다.

S-상자가 제공하는 비선형성이 없다면 DES는 선형대수로 쉽게 해독할 수 있는 순수 선형 암호가 됩니다. DES의 S-상자는 차분 암호분석에 견디도록 구체적으로 설계되었습니다.

S-상자 다음에 DES는 S-상자에서 나온 32개 출력 비트를 재배열하는 P-상자 순열을 적용합니다. 이는 확산을 제공하여 각 S-상자의 출력이 다음 라운드에서 여러 S-상자에 영향을 주도록 합니다.

P-상자는 확산을 극대화하도록 신중하게 설계되었습니다. 한 S-상자의 각 출력 비트가 다음 라운드에서 서로 다른 두 개 이상의 S-상자에 영향을 주므로 빠른 눈사태 효과가 보장됩니다.

DES는 56비트 주 키에서 서로 다른 48비트 하위 키 16개를 생성하며, 각 라운드에 하나씩 사용합니다. 키 스케줄은 순열 선택(PC-1)을 적용하여 패리티 비트를 제거하고 키 비트의 순서를 재배열하는 것으로 시작합니다.

56비트는 28비트 절반 두 개로 나뉘며, 각 라운드마다 각각을 왼쪽으로 1칸 또는 2칸씩 회전합니다. 그런 다음 순열 선택(PC-2)이 56비트 중 48비트를 선택하여 각 라운드의 하위 키를 구성합니다.

NSA는 DES 개발 과정에서 IBM과 협력하여 키 길이를 Lucifer의 128비트에서 56비트로 줄이고 S-박스 설계를 변경했습니다. 이로 인해 백도어가 도입되었는지를 둘러싼 수십 년간의 논란이 일어났습니다.

1990년대에 NSA 관계자들은 IBM이 1974년에 발견한 차분 암호 분석이라는 기법에 대응하도록 S-박스를 강화했다고 확인했습니다. NSA는 학계보다 수년 앞서 차분 암호 분석을 알고 있었으므로, DES를 약화한 것이 아니라 더 강하게 만들었다는 해석이 제기되었습니다.

DES는 경쟁 평가 절차를 거쳐 1977년 1월 연방 정보 처리 표준 46으로 채택되었습니다. DES는 기밀로 분류되지 않은 정부 데이터의 표준 암호가 되었으며, 은행과 산업계에서도 널리 채택되었습니다.

DES의 표준화는 역사적으로 중요한 의미를 지닙니다. DES는 공개적으로 이용할 수 있으면서 정부가 승인한 최초의 암호 알고리즘이었습니다. 또한 하드웨어 구현의 발전을 촉진하고 이후 암호 표준화 절차의 본보기를 확립했습니다.

DES 자체는 한 번에 정확히 64비트를 암호화하는 블록 암호입니다. 실제 메시지는 더 길기 때문에 운용 모드는 암호를 여러 블록에 적용하는 방법을 정의합니다. 일반적인 모드로는 ECB(각 블록을 독립적으로 암호화), CBC(암호화하기 전에 각 블록을 이전 암호문과 XOR), CFB, OFB, CTR이 있습니다.

ECB는 가장 취약한 모드입니다. 동일한 평문 블록이 동일한 암호문 블록을 만들어 눈에 보이는 패턴이 나타나기 때문입니다. CBC와 CTR 모드는 이러한 취약점을 없애므로 실제 DES 및 3중 DES 사용에 선호됩니다.

DES는 IBM의 Lucifer 암호에서 발전하여 64비트 블록과 유효 키 길이 56비트를 사용하는 16라운드 페이스텔 암호가 되었습니다. DES의 보안성은 혼돈을 제공하는 비선형 S-박스 8개, 확산을 제공하는 P-박스, 그리고 눈사태 효과를 증폭하는 16개 라운드에서 비롯됩니다.

S-박스 설계에 NSA가 관여한 일은 논란이 되었지만, 결과적으로 차분 암호 분석에 대한 저항성을 높였습니다. 1977년 하드웨어를 기준으로 설계된 DES의 56비트 키는 1990년대 후반에 충분하지 않은 것으로 드러났습니다.