Exploring Side-Channel Protections in Hardware Implementations of PQC ML-KEM Verification

기술 요약: PQC ML-KEM 검증의 하드웨어 구현에 있어서의 부채널 방어 기법 탐구

문제 정의
NIST에 의해 표준화되었으며 CRYSTALS-Kyber 알고리즘을 기반으로 하는 격자 기반 키 메커니즘(Module-Lattice-based Key-Encapsulation Mechanism, ML-KEM)이 채택됨에 따라, 물리적 부채널 공격(Side-Channel Attacks, SCA)에 대한 회복력 확보가 매우 중요해졌습니다. 기존 연구들은 소프트웨어 및 마이크로컨트롤러 구현, 특히 복호화 과정 중 Fujisaki-Okamoto(FO) 검증 단계에서의 취약점을 광범위하게 문서화해 왔으나, 하드웨어 가속 방식인 FPGA 기반 구현의 보안성은 여전히 미개척 영역으로 남아 있습니다.

FO 검증 단계는 로컬에서 재암호화된 암호문과 원래의 입력을 비교합니다. 만약 두 값이 일치하지 않으면, 알고리즘은 IND-CCA2 보안을 보장하기 위해 무작위 바이트를 출력합니다. 그러나 이 단계는 공격자가 약간 변형된 암호문을 생성하여 공격할 수 있는 부채널 분석에 취약합니다. 비교 과정 중 발생하는 전력 또는 전자기(EM) 방출을 분석함으로써, 공격자는 "복호화 성공"(차이가 최소임)과 "복호화 실패"(차이가 큼)를 구분할 수 있습니다. 이러한 분류를 통해 공격자는 벨리프 프로파게이션(Belief Propagation)을 통해 풀 수 있는 부등식 체계를 구축하여 장기 비밀키를 복구할 수 있습니다. 해시 기반 비교 및 고차 마스킹(Higher-order masking)과 같은 대응책이 직렬 플랫폼을 위해 제안되었지만, FPGA 아키텍처 특유의 높은 병렬성과 공간적 분포 환경에서 이들의 효용성은 알려진 바 없습니다.

방법론
저자들은 두 가지 하드웨어 플랫폼에서 세 가지 서로 다른 ML-KEM 검증 구현체를 체계적으로 평가했습니다.

1. 플랫폼: NIST 베이스라인을 나타내는 ARM Cortex-M4 마이크로컨트롤러(168 MHz)가 탑ium된 RISCURE Pinata 보드와 Xilinx Spartan-6 칩이 탑재된 SAKURA-G FPGA 보드를 사용했습니다. 전력 트레이스는 Teledyne LeCroy 오실로스코프를 사용하여 1 GS/s 속도로 캡처되었습니다.
2. 평가된 구현체:
   • 비보호(Unprotected): 직접적인 바이트 단위 XOR/AND 비교를 수행하는 베이스라인 구현입니다. FPGA에서는 병렬화의 영향을 연구하기 위해 가변적인 병렬성(32비트, 128비트, 512비트 폭)을 적용하여 구현되었습니다.
   • 해시 기반(1차 마스킹): 비교 전 암호문을 SHAKE-128(SHA-3)로 해싱하는 대응책입니다. FPGA 구현은 행 단위 병렬화를 활용하였으며, 시간적 엔트로피를 도입하기 위해 무작위 행 처리 순서를 실험했습니다.
   • 고차 마스킹(Higher-Order Masked): 데이터를 무작위 쉐어(Share)로 분할하도록 설계된 갈로아 필드(Galois Field, GF) 산술 기반의 마스킹 검증 알고리즘입니다(4-쉐어 및 6-쉐어 구성). FPGA 버전은 파이프라인 최적화를 거쳤으며, 구성 가능한 쉐어 수에 따라 병렬화되었습니다.
3. 분석: 저자들은 클락 드리프트(Clock drift)를 고려하여 정렬된 8,000개의 클래스당 트레이스를 전처리했습니다. 누설 지점을 식별하기 위해 T-테스트를 활용하였고, 신호 대 잡음비(SNR)를 계산했으며, 성공과 실패 케이스를 구별하는 정확도를 결정하기 위해 클러스터링 기반 머신러닝 분류기를 사용했습니다. 분류 정확도가 80% 미만인 경우 키 복구가 불가능한 것으로 간주했습니다.

주요 기여

• 최초의 체계적 FPGA 분석: 본 연구는 FPGA 가속 환경 내에서의 FO 검증 단계의 부채널 보안을 마이크로컨트롤러 베이스라인과 대조하여 체계적으로 조사한 최초의 연구 중 하나입니다.
• 병렬성과 누설의 상관관계: 본 연구는 FPGA가 상당한 처리량 향상을 제공하지만, 이를 달성하기 위한 병렬화 전략이 오히려 부채널 누설을 악화시킨다는 점을 입증합니다.
• 하드웨어에 대한 대응책 평가: 해싱 및 마스킹과 같은 표준 소프트웨어 대응책이 하드웨어로 효과적으로 전이되는지를 엄격히 테스트하여, 병렬화된 아키텍처에서 발생하는 특정 실패 모드를 밝혀냈습니다.

실험 결과

• 비보호 구현체:
  • 마이크로컨트롤러는 94.8%의 분류 정확도(SNR 2.40)를 달로했습니다.
  • FPGA의 32비트 병렬 구현은 더 낮은 정확도(62.9%, SNR 0.95)를 기록하여 키 복구에 불충분했습니다.
  • 그러나 FPGA 병렬성을 128비트 및 512비트로 높이자 누설이 급격히 증가하여, 각각 99.1%와 100.0%의 분류 정확도(SNR 3.83 및 8.33)를 달성했습니다. 더 넓은 조합 논리(Combinational logic)는 더 명확하고 구별 가능한 신호를 생성했으며, 512비트 FPGA는 마이크로컨트롤러 대비 약 530배의 처리량 향상을 보이면서도 훨씬 높은 취약성을 드러냈습니다.
• 해시 기반 구현체:
  • SHAKE-128을 사용했음에도 불구하고 FPGA 구현은 여전히 취약했습니다. T-테스트 결과, Keccak 치환의 초기 라운드에 있는 Rho/Pi 서브함수가 입력 데이터에 대한 구조적 의존성을 유지하고 있음이 밝혀졌습니다.
  • 분류 정확도는 94.7%에 도달했습니다.
  • 무작위 행 스케줄링은 누설을 은폐하는 데 실패했습니다. 다섯 개의 치환 세그먼트가 가진 뚜렷한 전력 시그니처 덕분에 공격자는 실행 순서를 99.9%의 정확도로 핑거프린팅할 수 있었으며, 이는 무작위화를 사실상 무력화했습니다.
• 고차 마스킹 구현체:
  • 마이크로컨트롤러 구현은 t-probing에 대해 안전했으나, FPGA 구현은 하드웨어 수준의 효과로 인해 정보를 누설했습니다.
  • 마스킹된 쉐어들의 병렬 처리는 유효 마스킹 차수를 감소시켰습니다. 4-쉐어 및 6-쉐어 FPGA 구현은 각각 97.9%와 98.5%의 분류 정확도를 달성했는데, 이는 마이크로컨트롤러에서 보고된 유사한 공격의 정확도인 95.0%보다 높았습니다.
  • 증가된 병렬성은 순간적인 활동(Instantaneous activity)이 기저의 비트 차이와 더 강력하게 상관되도록 만들어, 마스킹 기법의 이론적 보안을 저해했습니다.

의의 및 주장
본 논문은 직렬(마이크로컨트롤러)에서 병렬(FPGA) 실행으로의 전환이 ML-KEM의 부채널 위협 지형을 근본적으로 변화시킨다고 결론짓습니다. 저자들은 다음과 같이 주장합니다:

1. 성능-보안 트레이드오프: FPGA 환경에서 병렬성을 통한 성능 추구는 부채널 누설의 강화와 직접적으로 상관관계가 있으며, 이는 고처리량 구성이 직렬 구성보다 더 취약하게 만듭니다.
2. 이식된 대응책의 불충분함: 해시 기반 비교 및 고차 마스킹과 같이 직렬 실행을 위해 설계된 대응책은 FPGA에서 단순히 병렬화될 경우 불충분합니다. 하드웨어 수준의 효과(예: 논리의 공간적 분포, 동시 스위칭)가 기존의 보호 기능을 우회하는 새로운 누설 메커니즘을 생성합니다.
3. 맞춤형 하드웨어 솔루션의 필요성: 성능 제약이 있고 병렬화된 하드웨어에서 PQC 알고리즘을 보안화하려면, 소프트웨어 중심의 보안 전략을 단순히 적응시키는 것이 아니라 병렬 실행에 특화된 누설 모델을 명시적으로 고려하는 "맞춤형 솔루션(Bespoke solutions)"이 필요합니다.

저자들은 본 연구가 Spartan-6 FPGA를 기반으로 하고 있지만, 그 원리가 더 높은 병렬성을 제공하여 잠재적으로 더 큰 누설을 일으킬 수 있는 최신 소형 공정 노드의 FPGA에도 적용될 것이라고 강조합니다. 이들은 이론적 보안과 실제 하드웨어 배포 사이의 간극을 메우기 위해 PQC 알고리즘의 "설계 단계부터의 보안(Secure-by-design)" 구현에 대한 재평가를 촉구합니다.