Feistel 네트워크: 현대 암호의 구성 요소

1970년대 초 IBM 연구소의 호르스트 파이스텔은 루시퍼 암호를 연구하던 중 근본적인 통찰을 얻었습니다. 비가역적인 라운드 함수를 사용하면서도 가역적인 암호를 만들 수 있다는 것이었습니다.

이는 혁신적이었습니다. 안전하면서도 가역적인 함수를 설계하기는 어렵기 때문입니다. 파이스텔 구조는 이 요구 사항을 완전히 우회하여, 임의로 복잡한 일방향 라운드 함수를 사용할 수 있게 합니다.

파이스텔 암호에서는 입력 블록을 같은 크기의 두 절반, 즉 L(왼쪽)과 R(오른쪽)으로 나눕니다. 각 라운드에서는 라운드 함수 F를 R에 적용하고, 그 결과를 L과 XOR한 뒤 두 절반을 교환합니다.

n 라운드가 끝나면 두 절반을 다시 결합하여 암호문을 만듭니다. 교환 과정 덕분에 두 절반이 번갈아 가는 라운드에서 모두 처리되고, 서로 철저히 혼합됩니다.

파이스텔 네트워크의 라운드 함수 F는 오른쪽 절반과 라운드 하위 키를 입력으로 받아 왼쪽 절반과 XOR할 출력을 생성합니다. 중요한 점은 F가 가역적일 필요가 없다는 것입니다.

F는 치환, 순열, XOR 연산, 모듈러 산술을 임의로 조합하여 매우 복잡하게 만들 수 있습니다. F가 복잡하고 비선형적일수록 암호는 강력해집니다. 복호화에서 F를 역변환할 필요가 없기 때문입니다.

파이스텔 암호의 복호화는 암호화와 정확히 같은 구조를 사용하지만, 라운드 하위 키를 역순으로 적용합니다. 이는 XOR이 자기 자신의 역연산이기 때문에 가능합니다. A XOR B = C라면 C XOR B = A입니다.

복호화에서는 F^-1(F의 역함수)을 호출하지 않으므로, 암호의 가역성에 영향을 주지 않고 라운드 함수를 비가역 해시, 조회 표 또는 어떤 복잡한 연산으로도 만들 수 있습니다.

파이스텔 네트워크의 수학적 우아함은 F가 무엇을 하든 XOR 구조가 가역성을 보장한다는 데 있습니다. F가 SHA-256과 같은 일방향 함수여도 전체 파이스텔 암호는 가역적으로 유지됩니다.

따라서 파이스텔 암호는 매우 유연합니다. 암호학자는 가역성이 네트워크 구조 자체에서 처리된다는 사실을 알고 F를 최대한 혼란스럽고 확산적으로 만드는 데만 집중할 수 있습니다.

1977년에 발표된 데이터 암호화 표준(DES)은 64비트 블록과 56비트 키를 사용하는 16라운드 파이스텔 암호입니다. 각 라운드에서는 주 키에서 파생된 서로 다른 48비트 하위 키를 사용합니다.

DES의 라운드 함수에는 확장 순열, 하위 키와의 XOR, 비선형성을 제공하는 8개의 S-박스, 그리고 P-박스 순열이 포함됩니다. 이 조합은 섀넌의 암호 설계 원칙이 요구하는 혼돈과 확산을 모두 제공합니다.

브루스 슈나이어가 1993년에 설계한 Blowfish는 32~448비트의 가변 키 길이를 지원하는 16라운드 파이스텔 암호입니다. 키에 종속된 S-박스를 사용하므로 사전 계산 공격이 실용적이지 않습니다.

AES 대회의 최종 후보였던 Twofish는 128비트 블록과 16라운드를 사용하여 Blowfish의 개념을 확장했습니다. 두 암호 모두 아직 해독되지 않았으며, 수정된 Blowfish를 사용하는 bcrypt 비밀번호 해싱과 같은 응용 프로그램에 사용됩니다.

균형형 파이스텔 암호는 블록을 같은 크기의 두 절반으로 나눕니다. 불균형형 파이스텔은 3/4와 1/4로 나누는 것처럼 크기가 다른 절반을 사용합니다.

불균형형 파이스텔 네트워크는 특정 상황에서 보안상의 이점을 제공할 수 있으며, 일부 특수 목적 암호에 사용됩니다. CAST 암호군은 균형형 64비트 파이스텔 구조를 사용합니다.

1988년에 마이클 루비와 찰스 래코프는 의사난수 라운드 함수를 사용하는 3라운드 파이스텔 네트워크가 안전한 의사난수 순열(PRP)이고, 4라운드 버전은 강한 PRP라는 사실을 증명했습니다.

이 이론적 결과는 파이스텔 네트워크에 단순한 실험적 확신을 넘어 확실히 증명 가능한 보안 기반을 제공했습니다. 또한 파이스텔 구조 자체가 라운드 함수만으로 얻는 것 이상의 보안에 기여한다는 사실을 확인했습니다.

AES가 사용하는 치환-순열 네트워크(SPN)는 라운드마다 블록의 절반에 적용하는 대신 전체 블록에 치환과 순열을 동시에 적용합니다. 따라서 더 빠른 확산이 가능합니다.

AES는 단 4라운드 만에 완전한 확산을 달성하지만, DES의 파이스텔 구조는 비슷한 수준의 확산을 얻으려면 더 많은 라운드가 필요합니다. 또한 AES의 SPN은 SIMD 명령어를 사용하는 현대 프로세서 아키텍처에 더 잘 맞습니다.

루비-래코프 정리는 라운드 함수 F를 진정으로 무작위인 함수로 취급합니다. 그러나 실제로 F는 진정한 무작위 오라클이 아니라 의사난수 함수, 즉 키를 사용하는 암호나 해시입니다.

이론적 증명과 실제 구현 사이의 간극은 암호학에서 반복해서 나타나는 주제입니다. 증명은 확신을 제공하지만 이상화된 모델을 바탕으로 합니다. 실제 환경의 보안은 부채널 취약점이 없는 안전한 구현에도 달려 있습니다.

파이스텔 네트워크 설계를 이해했는지 확인해 보세요.

파이스텔 네트워크는 가역적일 필요가 없는 라운드 함수를 사용하는 블록 암호 구조입니다. 복호화는 하위 키를 역순으로 사용하여 동일한 구조를 반대로 실행하는 방식으로 이루어집니다.

DES, Blowfish, Twofish는 모두 파이스텔 암호입니다. 루비-래코프 정리는 이론적인 보안 보장을 제공합니다. 반면 AES는 SPN 구조를 사용하여 라운드당 더 나은 확산을 제공합니다.