하이브리드 ML-KEM은 CPU보다 전송량을 늘린다

이 프로젝트는 X25519, ML-KEM, 두 방식을 결합한 하이브리드 키 교환과 ML-DSA 서명을 더한 방식의 핸드셰이크 비용을 비교한다. 로컬호스트에서 지연 시간을 인위적으로 추가한 실험에서는 하이브리드 방식의 계산 시간은 1밀리초 미만이었지만, ML-DSA 서명 방식은 전송 바이트가 늘고 네트워크 왕복도 한 번 더 필요한 것으로 나타났다.

무엇을 측정했나

프로젝트 저장소는 고전 타원곡선 디피-헬만(ECDH) 방식인 X25519, 양자내성 암호(PQC) 표준 ML-KEM(FIPS 203 / Kyber), X25519와 ML-KEM을 결합한 하이브리드 방식, ML-DSA 서명을 붙인 ML-KEM 키 교환을 비교한다. 각 방식은 liboqs와 Python의 cryptography 라이브러리를 이용해 TCP 소켓으로 실제 핸드셰이크를 수행한다.

NIST가 최근 첫 양자내성 암호 표준(FIPS 203/204/205)을 확정했다. 프로젝트는 양자 컴퓨터가 현재 존재하는지보다 ‘지금 수집해 나중에 복호화하는’ 위협에 주목한다. 공격자가 암호화된 통신을 지금 기록해 두었다가 암호학적으로 유의미한 양자 컴퓨터가 등장하면 나중에 복호화할 수 있다는 것이다. 의료 기록, 인프라 자격 증명, 국가 기밀처럼 장기간 기밀을 유지해야 하는 데이터는 양자 컴퓨터의 등장 시점과 관계없이 이 위협에 노출될 수 있다고 설명한다.

프로젝트는 이런 이유로 많은 조직이 순수 PQC로 바로 전환하기보다 고전 암호와 PQC를 결합한 하이브리드 키 교환을 택한다고 설명한다. 기밀성을 깨려면 두 암호 방식이 모두 뚫려야 하기 때문이다. Chrome/BoringSSL과 OpenSSH는 하이브리드 X25519+ML-KEM을 기본 제공한다고 프로젝트는 덧붙였다.

측정 목표는 전환에 따른 핸드셰이크 지연 시간과 네트워크 전송량이다. 키 교환뿐 아니라 실제 핸드셰이크에서 상대 서버가 맞는지 인증하는 비용도 살펴본다. 이 프로젝트는 리오스 외 연구진의 「Toward the Quantum-Safe Web: Benchmarking Post-Quantum TLS」(IEEE Network, 2025)를 읽은 뒤 시작됐다. 해당 연구는 Docker에서 OpenSSL/liboqs/oqs-provider를 사용해 NIST PQC 표준을 적용한 전체 TLS 1.3 핸드셰이크를 벤치마크했다. 프로젝트 제작자는 Wells Fargo 사이버보안팀에서 인턴으로 일하며 대형 금융기관의 양자내성 암호 전환 접근 방식을 가까이서 본 경험도 언급한다.

이 실험은 전체 TLS 1.3 구현이 아니라 oqs의 ML-KEM·ML-DSA와 cryptography의 X25519를 사용한 최소 핸드셰이크 프로토콜이다. 전체 TLS 스택 안에 암호 연산을 묻어 두지 않고 기본 구성 요소를 비교하기 위한 설계다.

앞의 세 방식은 기밀성만 제공한다. TLS 인증서가 없을 때와 마찬가지로 중간자 공격자가 전송 중 키 자료를 바꿔치기하는 것을 막지 못한다. 서명 방식은 서버가 ML-DSA-65로 임시 ML-KEM 공개키에 서명하고, 클라이언트가 그 서명을 확인한 뒤 키를 신뢰하도록 해 이 문제를 보완한다. 프로젝트는 KEM만 다루는 PQC 벤치마크에서 이 단계가 빠지는 경우가 많으며, 측정 결과 이 단계의 비용이 상당했다고 설명한다.

각 핸드셰이크는 127.0.0.1에서 실제 TCP 서버 스레드를 실행하고, 클라이언트 소켓을 연결하는 방식으로 진행한다. 클라이언트가 첫 바이트를 보낸 시점부터 최종 키를 도출할 때까지의 실제 경과 시간을 잰다. 양쪽이 같은 세션 키를 도출했는지 확인하며, 값이 다르면 조용히 넘어가지 않고 오류를 낸다. 핸드셰이크 시간과 총 전송 바이트도 기록한다.

암호 연산 비용과 네트워크 비용을 나누어 보기 위해 각 소켓을 DelayedSocket으로 감싸고 단방향 지연 시간을 0·20·75밀리초로 설정한다. 이는 각각 로컬호스트, 같은 지역, 지역 간 통신에 가까운 조건을 나타낸다.

측정 결과

전체 실행은 방식 4개, ML-KEM 보안 수준 3개, 지연 시간 구간 3개를 조합해 설정별 60회씩 측정한다. 차트와 원시 데이터는 저장소의 results/에 있다.

지연 시간을 0밀리초로 설정했을 때 X25519의 평균 계산 시간은 약 0.29밀리초였다. ML-KEM 단독은 보안 수준에 따라 0.26~0.29밀리초로, X25519와 큰 차이가 없었다. 두 연산을 모두 수행하는 하이브리드는 0.51~0.59밀리초로 두 연산의 합에 가까웠다. ML-DSA 서명을 추가하면 0.71~0.77밀리초로 늘지만, 여전히 1밀리초 미만이다. 계산 시간만 보면 네 방식 가운데 서명 방식이 가장 오래 걸렸다.

전송량 차이는 더 컸다. X25519는 왕복 72바이트였고, ML-KEM-768 단독은 약 2,280바이트로 약 32배였다. 하이브리드 X25519+ML-KEM-768은 2,352바이트로 두 방식의 전송량을 더한 값에 가까웠다. ML-DSA-65 서명을 더하면 약 7,549바이트로 늘어 하이브리드보다 3배 이상, X25519보다 100배 넘게 많았다. 증가분 대부분은 ML-DSA 공개키와 서명에서 발생하며, NIST 보안 수준 3에서도 이 자료들은 각각 킬로바이트 단위라고 프로젝트는 설명한다.

서명 방식은 전송량뿐 아니라 네트워크 왕복도 한 번 더 필요한 것으로 나타났다. 고전 방식, PQC, 하이브리드 방식은 한 번 왕복하는 패턴에 따라 지연 시간과 함께 핸드셰이크 시간이 늘었다. 단방향 지연 시간이 20밀리초일 때 총 시간은 약 40.5밀리초, 75밀리초일 때 약 150.8밀리초였다. 같은 조건에서 서명 방식은 각각 약 81.3밀리초와 301.5밀리초로 거의 두 배였다.

프로젝트는 이 결과가 서명 방식에 두 번의 네트워크 왕복이 필요함을 시사한다고 본다. 서버가 ML-DSA 공개키를 별도 메시지로 먼저 보내고, 서명된 ML-KEM 키를 나중에 보내기 때문일 가능성이 있다. 두 자료를 한 번의 메시지 전송에 묶지 않았기 때문일 수 있다는 설명이다. 이 원인이 확정된 것은 아니다.

지연 시간이 없는 로컬 네트워크에서는 차이가 거의 드러나지 않는다. 반면 위성, 셀룰러 엣지, 지역 간 연결처럼 지연이 있는 링크에서는 인증 단계가 킬로바이트 단위의 데이터를 더하는 데 그치지 않고 핸드셰이크 전체의 네트워크 비용을 두 배로 만들 수 있다. 프로젝트는 실제 배포 계획에서 바이트 증가량보다 이 차이가 더 중요할 수 있다고 본다.

전환 계획에 주는 시사점

프로젝트는 일반적인 인터넷 서비스에서 하이브리드 PQC의 전송량 증가만으로 병목이 생길 가능성은 낮다고 본다. 네트워크 왕복 시간과 TLS 레코드 처리가 이를 웃돌 것이며, 이는 대규모 하이브리드 PQC를 실제 배포한 Cloudflare와 Google의 보고와도 맞는다고 설명한다.

키 교환에는 순수 PQC보다 하이브리드 방식이 기본 선택으로 적절하다는 것이 프로젝트의 판단이다. 순수 ML-KEM과 하이브리드 방식의 비용 차이는 큰 문제가 되지 않을 만큼 작다는 근거를 들었다.

전환 비용은 인증 단계에서 더 크게 나타날 수 있다. ECDSA 또는 RSA 인증서를 ML-DSA로 바꾸는 일은 수 킬로바이트의 전송량만 더하는 것이 아니라, 이번 구현에서는 네트워크 왕복 한 번을 추가한다. 지연이 큰 연결에서는 원시 바이트 증가보다 왕복 시간이 더 중요할 수 있다. 프로젝트는 ML-DSA 공개키와 서명을 ML-KEM 키와 같은 메시지 전송에 묶을 수 있는지 살펴볼 필요가 있다고 제안한다. 추가 왕복은 구조적으로 꼭 필요한 것이 아닐 수도 있기 때문이다.

설치와 실행

주의할 점은 liboqs의 Python 바인딩인 oqs를 사용하려면 기반이 되는 C 라이브러리 liboqs를 시스템에 실제로 빌드해 사용할 수 있어야 한다는 것이다. Python 패키지만 설치하면 래퍼만 설치된다. 이 단계를 건너뛰면 oqs를 처음 가져올 때 RuntimeError: No oqs shared libraries found 오류가 발생한다.

저장소를 복제한다.

git clone https://github.com/RayDCodes/pqc-migration-bench.git
cd pqc-migration-bench

가상 환경을 만들고 활성화한 다음 의존성을 설치한다.

python3 -m venv venv
source venv/bin/activate # Windows: venv\Scripts\Activate.ps1
pip install -r requirements.txt

네이티브 라이브러리와 함께 liboqs Python 바인딩을 설치한다. WSL과 GitHub Codespaces를 포함한 Linux에서는 빌드 도구 모음이 설치돼 있으면 보통 다음 명령으로 설치할 수 있다.

sudo apt install build-essential cmake ninja-build -y
pip install git+https://github.com/open-quantum-safe/liboqs-python.git

네이티브 Windows에서는 기본적으로 C 빌드 도구 모음이 없어 같은 명령이 실패하는 경우가 많다. Visual Studio Build Tools와 CMake를 설치해도 빌드가 항상 깔끔하게 끝나는 것은 아니다. 문제가 생기면 Windows에서 직접 해결하기보다 WSL이나 GitHub Codespace에서 개발하는 편이 수월했다고 프로젝트 제작자는 설명한다.

설치가 제대로 됐는지 확인한다.

python -c "import oqs; print(oqs.get_enabled_sig_mechanisms())"

출력 목록에 ML-DSA-65가 있는지 확인한다.

빠른 스모크 테스트는 다음과 같이 실행한다.

cd src
python bench.py --quick --out ../results/smoke_test.csv

이 명령은 설정이 제대로 연결됐는지 확인하기 위한 작은 실행이다. 메커니즘 하나와 지연 시간 구간 2개에서 10회씩 측정한다.

전체 측정은 다음 명령으로 실행한다.

python bench.py --out ../results/handshake_results.csv

방식 4개, ML-KEM 보안 수준 3개, 지연 시간 구간 3개를 설정별 60회 측정하며, 완료까지 몇 분이 걸린다.

차트와 요약을 다시 생성하려면 다음 명령을 실행한다.

python analyze.py

한계와 다음 단계

이 프로젝트는 키 교환과 서명의 마이크로벤치마크이지 전체 TLS 1.3 구현은 아니다. 인증서, 레코드 계층, 암호 스위트 협상은 포함하지 않는다. 암호 구성 요소를 분리해 비교하려는 의도적인 설계지만, 이 수치를 PQC를 적용한 OpenSSL 또는 BoringSSL 스택의 실제 벤치마크를 대신하는 값으로 볼 수는 없다.

모든 실험은 로컬호스트에서 실행하고 sleep을 이용해 지연을 흉내 낸다. 패킷 손실이나 지터는 반영하지 않는다.

다음 단계로는 OpenSSL의 PQC provider를 사용한 실제 TLS 1.3 핸드셰이크를 구현해 최소 프로토콜과 비교하는 계획이 있다. 세션 재개처럼 연결을 반복하는 상황에서 서명 검증 비용도 별도로 측정할 예정이다. 이때 ML-DSA의 핸드셰이크당 비용이 가장 빠르게 누적될 수 있다고 프로젝트는 설명한다.