ML-KEM (FIPS 203) 및 CRYSTALS-Kyber 표준

2024년 8월 FIPS 203으로 표준화된 ML-KEM(Module-Lattice-based Key Encapsulation Mechanism)은 Diffie-Hellman과 RSA 키 교환을 대체하는 양자 이후 방식입니다. 공개 키로 대칭 키를 캡슐화하여 양쪽 당사자가 대칭 암호화에 사용할 수 있는 공유 비밀을 생성합니다. ML-KEM은 더 명확한 명세를 위해 약간 수정된 CRYSTALS-Kyber에서 파생되었습니다.

ML-KEM은 세 가지 매개변수 집합을 정의합니다. ML-KEM-512는 약 128비트의 고전 보안과 100비트의 양자 이후 보안을 목표로 하며, 공개 키는 800바이트이고 암호문은 768바이트입니다. ML-KEM-768은 192비트의 고전 보안을 목표로 하며, 공개 키는 1184바이트이고 암호문은 1088바이트입니다. ML-KEM-1024는 256비트의 고전 보안을 목표로 하며, 공개 키와 암호문은 각각 1568바이트입니다. NIST는 대부분의 애플리케이션에 ML-KEM-768을 권장합니다.

ML-KEM의 키 생성은 다음과 같이 진행됩니다. SHAKE-128을 사용해 시드에서 무작위 행렬 A를 추출하고, 작은 비밀 벡터 s와 오차 벡터 e를 추출한 다음, t = As + e mod q를 계산합니다. 공개 키는 (seed, t)이고 개인 키는 공개 키 해시와 함께 저장되는 s입니다. A를 저장하는 대신 시드를 사용하면 메모리와 대역폭을 크게 절약할 수 있습니다.

캡슐화할 때 송신자는 무작위 메시지 m을 생성하고 SHA-3을 통해 대칭 키 K와 무작위성 r을 모두 도출합니다. 암호문은 두 부분으로 구성됩니다. u = Ar + e1 mod q 및 v = t^T r + e2 + encode(m) mod q입니다. 공유 비밀 K는 m의 해시에서 도출됩니다. 무작위성은 m에서 결정론적으로 도출되므로 암호문이 키에 결속됩니다.

디캡슐화에서는 v - s^T u를 계산하고 디코딩하여 m을 복원한 다음, m에서 K를 다시 도출합니다. Fujisaki-Okamoto 변환은 중요한 단계를 추가합니다. 복원한 m으로 다시 암호화하고 암호문이 일치하는지 확인하는 단계입니다. 일치하지 않으면 개인 키와 암호문의 해시에서 도출한 의사 난수 값을 반환합니다. 이를 통해 디캡슐화가 결정론적이고 검증 가능해져 선택 암호문 공격을 방지합니다.

ML-KEM은 양자 무작위 오라클 모델(QROM)에서 IND-CCA2 보안을 달성하며, 이는 Module-LWE 가정 아래에서 증명되었습니다. 양자 이후 공격자는 해시 함수를 중첩 상태로 질의할 수 있으므로 QROM이 중요합니다. Hofheinz, Hovelmanns, Kiltz가 제시한 보안 증명(HHK 프레임워크)은 QROM에서 Module-LWE를 ML-KEM 보안으로 연결하는 긴밀한 환원을 제공합니다.

동일한 보안 수준에서 ML-KEM은 키 교환에 RSA보다 훨씬 뛰어난 성능을 보입니다. 최신 CPU에서 ML-KEM-768의 키 생성에는 약 16마이크로초, 캡슐화에는 20마이크로초, 디캡슐화에는 18마이크로초가 걸립니다. RSA-2048의 키 생성에는 수 초가 걸립니다. ML-KEM의 공개 키(1184바이트)는 ECDH(32~64바이트)보다 크지만, RSA-2048보다 훨씬 작습니다. RSA-2048은 키 자체만 256바이트이고 실제로는 더 긴 경우가 많습니다.

전환 기간에는 하이브리드 키 교환을 사용해 ML-KEM을 고전 알고리즘(일반적으로 X25519 또는 P-256 ECDH)과 결합합니다. 공유 비밀은 두 KEM 출력의 해시입니다. K = Hash(K_classical || K_pqc). 따라서 보안 수준이 어느 한 구성 요소보다 낮아지지 않습니다. 하이브리드 TLS는 IETF 초안 draft-ietf-tls-hybrid-design에 명시되어 있으며 BoringSSL, OpenSSL 3.x, Rustls에서 지원됩니다.

IETF는 TLS 1.3의 하이브리드 키 공유 방식으로 X25519ML-KEM-768을 정의했습니다(draft-ietf-tls-hybrid-design). Chrome은 124 버전(2024년 4월)에서, Firefox는 132 버전(2024년)에서 지원을 추가했습니다. Cloudflare는 TLS 종료 인프라에 ML-KEM을 배포했습니다. 이러한 빠른 도입으로 이제 하루 수억 건의 TLS 연결에 양자 이후 키 교환이 포함됩니다.

LWE의 오차 항 때문에 공격자가 없어도 디캡슐화가 실패할 가능성이 매우 작게 존재합니다. ML-KEM-512의 실패 확률은 약 2^{-139}이고, ML-KEM-768에서는 2^{-164}입니다. 이 비율은 실제로 우려할 수준보다 훨씬 낮습니다. 하드웨어 오류가 훨씬 더 자주 발생한다는 점과 비교해 볼 수 있습니다. 보안에는 영향을 주지 않지만 명세에서는 반드시 고려해야 합니다.

ML-KEM은 수많은 공개 소스 라이브러리에 구현되어 있습니다. Kyber 팀의 참조 구현은 퍼블릭 도메인으로 공개되어 있습니다. PQClean은 정리된 이식 가능한 C 구현을 제공합니다. liboqs(Open Quantum Safe 프로젝트)는 라이브러리 래퍼에 ML-KEM을 통합합니다. AWS-LC(BoringSSL을 Amazon이 포크한 버전)에는 AWS TLS 엔드포인트를 위한 ML-KEM이 포함되어 있습니다. NIST FIPS 203 표준에는 모든 연산에 대한 상세한 의사 코드가 포함되어 있습니다.

NIST는 대부분의 애플리케이션에 어떤 ML-KEM 매개변수 집합을 권장합니까?

ML-KEM(FIPS 203)은 Module-LWE를 기반으로 NIST가 표준화한 양자 이후 KEM입니다. 세 가지 매개변수 집합(512/768/1024)은 128/192/256비트의 고전 보안을 제공합니다. 키 생성에서는 무작위 시드로부터 크기가 작은 공개 키를 만들고, 캡슐화에서는 공유 비밀을 도출하며, 디캡슐화에서는 CCA2 보안을 위해 FO 변환을 사용합니다. ML-KEM은 RSA보다 훨씬 빠르며 이미 Chrome, Firefox, Cloudflare의 TLS에 배포되어 있습니다.