포스트 양자 암호: CRYSTALS-Kyber 및 Dilithium

현재의 공개 키 암호화인 RSA, ECC, Diffie-Hellman은 기존 컴퓨터로는 계산적으로 해결하기 어려운 수학적 문제에 의존합니다. RSA의 보안은 큰 정수를 소인수분해하기 어렵다는 점에 기반하며, ECC의 보안은 타원 곡선 이산 로그 문제를 풀기 어렵다는 점에 기반합니다. 충분히 강력한 양자 컴퓨터에서 Shor 알고리즘을 실행하면 두 문제를 다항 시간에 해결할 수 있어, 널리 사용되는 모든 공개 키 암호화를 사실상 깨뜨릴 수 있습니다. 오늘날에는 이러한 양자 컴퓨터가 존재하지 않지만, NIST는 이 위협을 심각하게 받아들여 2016년부터 양자 내성 대체 기술의 표준화를 시작했습니다.

국가 수준의 공격자는 양자 컴퓨터를 사용할 수 있게 된 후 복호화할 목적으로 오늘날 암호화된 인터넷 트래픽을 수집할 수 있습니다. 이를 '지금 수집하고 나중에 복호화하기' 또는 SNDL (Store Now, Decrypt Later) 전략이라고 합니다. 장기적으로 민감한 데이터(기밀 정부 문서, 금융 기록, 의료 데이터)는 양자 컴퓨터가 등장할 때에도 민감한 상태로 남아 있을 수 있으므로 특히 위험합니다. 따라서 조직은 양자 컴퓨터가 등장한 후가 아니라 등장하기 전에 양자 내성 암호(PQC)로 이전해야 합니다. 이 전환은 복잡하고 많은 시간이 걸리기 때문입니다.

서로 다른 알고리즘 종류에 대한 양자 위협을 구분하는 것이 중요합니다. Shor 알고리즘은 RSA와 ECC 비대칭 암호화를 깨뜨립니다. Grover 알고리즘은 검색 속도를 제곱 수준으로 향상하므로 대칭 암호와 해시 함수의 유효 키 길이를 절반으로 줄입니다. 따라서 AES-128은 양자 공격자에 대해 64비트 보안만 제공하여 충분하지 않지만, AES-256은 128비트의 양자 내성 보안을 유지하므로 허용할 수 있는 수준입니다. SHA-256 역시 보안 수준이 절반으로 줄어들지만 여전히 충분하며, 더 장기적인 보안을 위해서는 SHA-384와 SHA-512가 권장됩니다.

2016년 NIST는 양자 내성 암호 알고리즘을 선정하기 위한 공모를 시작했고 82개의 제안을 접수했습니다. 여러 차례의 평가를 거친 후 NIST는 2024년에 최초의 PQC 표준 세트를 확정했습니다. 키 캡슐화를 위한 FIPS 203 (ML-KEM, CRYSTALS-Kyber 기반), 디지털 서명을 위한 FIPS 204 (ML-DSA, CRYSTALS-Dilithium 기반), 해시 기반 서명 대안인 FIPS 205 (SLH-DSA, SPHINCS+ 기반)이 이에 해당합니다. 이 알고리즘들은 기존 컴퓨터와 양자 컴퓨터의 공격을 모두 견디며, PKI 시스템에서 RSA와 ECDSA를 대체하도록 설계되었습니다.

CRYSTALS-Kyber와 CRYSTALS-Dilithium은 모두 격자 기반 암호 체계입니다. 격자는 고차원 공간에 있는 점들의 규칙적인 격자 구조입니다. 두 알고리즘의 기반이 되는 어려운 문제는 오류가 있는 학습(LWE) 문제입니다. 작은 무작위 오류가 추가된 선형 방정식 집합이 주어졌을 때, 그 안에 숨은 비밀을 찾아야 합니다. 현재 LWE를 효율적으로 해결하는 양자 알고리즘은 알려져 있지 않습니다. CRYSTALS에서 사용하는 모듈러 LWE(MLWE) 변형은 보안 수준과 키 및 암호문 크기 사이에서 균형을 잘 이룹니다.

CRYSTALS-Kyber(현재 ML-KEM)는 키 캡슐화 메커니즘(KEM)으로, 안전하지 않은 채널을 통해 두 당사자가 공유 비밀을 설정할 수 있게 하며 Diffie-Hellman과 RSA 키 교환을 대체합니다. Kyber는 공개 키와 개인 키 쌍을 생성합니다. 송신자는 수신자의 공개 키를 사용해 무작위 세션 키를 캡슐화하고, 수신자는 자신의 개인 키를 사용해 이를 역캡슐화합니다. Kyber-768(NIST 보안 수준 3, 대략 AES-192에 해당)의 공개 키는 약 1,184바이트이고 암호문은 약 1,088바이트로, 256바이트인 RSA-2048 키보다 훨씬 큽니다.

CRYSTALS-Dilithium(현재 ML-DSA)은 ECDSA와 RSA 서명을 대체하는 디지털 서명 알고리즘입니다. 격자 수학을 사용해 서명을 생성하며 검증도 효율적입니다. Dilithium3(보안 수준 3)의 서명 크기는 약 3,293바이트로, 64바이트인 ECDSA 서명보다 훨씬 큽니다. 이 크기 증가는 인증서가 많은 PKI 시스템에서 이전을 어렵게 만드는 주요 요인입니다. 크기는 크지만 Dilithium은 일반 하드웨어에서 빠르게 서명하고 검증하며, 알려진 모든 양자 공격에 내성을 가집니다.

SPHINCS+(현재 SLH-DSA)는 NIST가 Dilithium의 대안으로 선정한 비상태형 해시 기반 서명 체계입니다. 보안이 기반 해시 함수(SHA-256 또는 SHAKE)의 보안에만 의존하므로 매우 보수적인 선택입니다. 격자 수학이 어떤 방식으로든 깨지더라도 SPHINCS+는 안전하게 유지됩니다. 그 대신 서명 크기가 커서, 매개변수 집합에 따라 SPHINCS+ 서명은 8KB에서 50KB에 이릅니다. 따라서 TLS 인증서에는 적합하지 않지만 서명 크기가 덜 중요한 코드 서명에는 매우 적합합니다.

권장되는 이전 전략은 하이브리드 암호입니다. 기존 알고리즘과 양자 내성 알고리즘을 결합하여 어느 한 알고리즘도 깨지지 않는 한 연결을 안전하게 유지하는 방식입니다. 예를 들어 키 교환에 X25519 + Kyber-768을 사용하면 공격자는 트래픽을 복호화하기 위해 ECDH와 Kyber를 모두 깨뜨려야 합니다. 이 방식은 이미 배포되고 있습니다. Google의 Chrome 브라우저는 2023년에 TLS 1.3용 X25519Kyber768 하이브리드 키 교환 지원을 추가했고, Apple도 이를 iMessage에 추가했습니다. 하이브리드 방식은 특정 날짜에 일괄 전환하지 않고도 원활하게 이전할 수 있게 합니다.

PKI를 양자 내성 알고리즘으로 이전하려면 매우 복잡한 작업이 필요합니다. 인증서 크기가 크게 증가하여 TLS 핸드셰이크 크기와 성능에 영향을 미치고, 하드웨어 보안 모듈(HSM)은 새 알고리즘을 지원하도록 업데이트하거나 교체해야 합니다. 코드 서명 기반 시설과 인증 기관도 업데이트해야 하며, 메모리가 제한된 IoT 장치는 더 큰 양자 내성 키를 지원하지 못할 수 있습니다. 조직은 PQC 이전 계획의 첫 단계로 암호 자산 목록화를 시작해야 합니다. 즉, RSA와 ECC가 사용되는 모든 위치를 목록으로 작성해야 합니다.

암호 민첩성은 시스템을 완전히 다시 설계하지 않고도 암호 알고리즘을 교체할 수 있도록 설계하는 것을 의미합니다. 암호 민첩성을 갖춘 시스템은 키와 암호문에 알고리즘 식별자를 함께 저장하므로 구성 매개변수를 변경해 향후 업그레이드를 수행할 수 있습니다. TLS, SSH 및 최신 인증서 표준은 이미 암호 민첩성을 보여 주는 사례입니다. 조직은 자체 프로토콜과 애플리케이션에서 알고리즘 선택을 코드에 하드코딩한 부분을 점검해야 합니다. 이러한 시스템은 이전 비용이 가장 많이 들기 때문입니다. 지금 암호화 라이브러리 추상화 계층을 도입하면 PQC 이전이 몇 자릿수나 더 쉬워집니다.

이 단원에서 배운 CompTIA Security+ (SY0-701) 개념을 이해했는지 확인해 보세요.

이 단원에서는 다음을 배웠습니다. Shor 알고리즘은 RSA와 ECC를 위협하지만 Grover 알고리즘은 대칭 키의 보안 수준을 절반으로 줄일 뿐이므로 AES-256과 SHA-384는 양자 환경에서도 여전히 사용할 수 있습니다. 또한 CRYSTALS-Kyber(ML-KEM)는 키 교환을 대체하고 CRYSTALS-Dilithium(ML-DSA)은 디지털 서명을 대체하는 NIST 선정 양자 내성 표준입니다. 그리고 전환이 진행되는 동안에는 기존 알고리즘과 PQC 알고리즘을 결합한 하이브리드 암호가 권장되는 이전 전략입니다. 다음에는 클라우드 네이티브 환경을 위한 컨테이너 보안을 살펴보겠습니다.