Comparative Performance Analysis of NIST PQC Standards: From STM32 Software Limitations to FPGA-SoC Acceleration

이 논문은 SPHINCS+ 및 Dilithium과 같은 NIST 표준 양자 내성 서명 방식이 심각한 성능 및 메모리 제한으로 인해 자원이 제한된 ARM Cortex-M4 마이크로컨트롤러에는 부적합하다는 것을 입증하는 한편, Zynq-7000 SoC 상에서 FPGA 가속 NTT 코어를 활용하는 하드웨어-소프트웨어 코디자인 접근 방식이 양자 내성 임베디드 시스템에 적합한 밀리초 단위의 효율적인 실행을 가능하게 함을 보여준다.

핵심

디지털 보안의 세계를 거대한 금고라고 상상해 보십시오. 수십 년 동안 이 금고의 자물쇠(RSA나 ECC 같은 것들)는 매우 강력했습니다. 하지만 새로운 종류의 도둑이 나타나고 있습니다. 바로 **양자 컴퓨터(Quantum Computer)**입니다. 이 도둑은 기존의 자물쇠들을 단 몇 초 만에 따버릴 수 있는 마스터 키를 가지고 있습니다. 이들을 막기 위해, NIST(미국 표준 기구)의 과학자들은 **양자 내성 암호(Post-Quantum Cryptography, PQC)**라고 불리는 새롭고 매우 복잡한 자물쇠를 설계했습니다.

이 논문은 이 새롭고 튼튼한 자물쇠를 두 가지 매우 다른 종류의 "문틀"에 설치하려는 시도에 대한 성적표입니다. 하나는 아주 작고 저렴한 마이크로컨트롤러(스마트 온도 조절기 내부의 두뇌와 같은 것)이고, 다른 하나는 강력하고 첨단 기술이 집약된 컴퓨터 칩(현대적인 서버나 고급 드론의 두뇌와 같은 것)입니다.

다음은 단순한 비유를 사용한 실험의 요약입니다.

1. 두 가지 새로운 자물쇠

연구진은 두 가지 특정 유형의 새로운 자물쇠를 테스트했습니다.

• 딜리튬(Dilithium, 수학 퍼즐): 이 자물쇠는 복잡한 격자(lattice) 수학을 기반으로 합니다. 이것은 마치 거대한 다항식 조각들로 이루어진 거대하고 다차원적인 직소 퍼즐을 푸는 것과 같습니다. 퍼즐 조각들을 풀면서 보관하기 위해 엄청난 작업 공간(메모리)이 필요합니다.
• SPHINCS+(해시 트리): 이 자물쇠는 해싱(데이터를 뒤섞는 것)을 기반으로 합니다. 이것은 마치 모든 가지가 작은 서명인 거대한 나무를 만드는 것과 같습니다. 메시지에 서명하려면 이 나무를 타고 위아래로 수천 번 오르내리며, 매 단계마다 많은 양의 무거운 작업(해싱)을 수행해야 합니다.

2. 첫 번째 시도: "작은 작업실" (STM32 마이크로컨트롤러)

연구진은 먼저 STM32라고 불리는 표준적이고 저렴한 칩에 이 자물쇠들을 설치하려고 시었습니다. 이 칩을 아주 작은 작업대(192 KB의 메모리)와 단 한 명의 느린 일꾼이 있는 작은 1인용 작업실이라고 생각해 보십시오.

• 딜리튬의 실패: 이 "수학 퍼즐"을 이 작은 작업실으로 가져오려 했을 때, 퍼즐 조각들이 너무 컸습니다. 일꾼이 작업대 위에 조각들을 펼쳐 놓으려 했지만, 작업대가 너무 작았습니다. 일꾼의 머리가 천장에 부딪혔고, 시스템 전체가 충돌했습니다. 기술적으로 말하면, 칩의 메모리가 즉시 고갈되었습니다(스택 오버플로).
• SPHINCS+의 실패: "해시 트리"는 작업실을 무너뜨리지는 않았지만, 진행 속도가 너무나 고통스러울 정도로 느렸습니다. 일꾼이 아무런 도움 없이 나무를 수천 번 오르내려야 했기 때문에, 메시지 하나에 서명하는 데만 약 10분이 걸렸습니다. 서명을 검증하려고 했을 때는 시스템이 아예 포기해 버렸습니다. 실생활에서 쓰기에는 너무 느렸습니다.

교훈: 표준적인 작은 마이크로컨트롤러에서 이러한 새로운 양자 내성 자물쇠를 실행하려는 것은, 마치 정원에 있는 창고 안에서 초고층 빌딩을 지으려는 것과 같습니다. 공간도, 속도도 부족합니다.

3. 두 번째 시도: "슈퍼 팩토리" (FPGA-SoC)

작은 작업실이 이 일을 감당할 수 없다는 것을 깨달은 연구진은 Zynq-7000 SoC로 옮겨갔습니다. 이것을 두 개의 서로 다른 부분이 함께 작동하는 거대하고 첨단 기술이 집약된 공장이라고 생각해 보십시오.

• 관리자 (프로세서 시스템): 서류 작업을 처리하고, 메시지를 정리하며, 일꾼들에게 무엇을 할지 지시하는 표준적인 컴퓨터 두뇌입니다.
• 특수 로봇 (FPGA 패브릭): 특정 작업을 위해 전용 기계를 직접 만들 수 있는 맞춤형 구역입니다.

해결책: 하드웨어-소프트웨어 공동 설계(Hardware-Software Co-Design)
연구진은 관리자에게 힘든 일을 시키는 대신, 어려운 수학 계산을 수행할 수 있도록 공장 안에 맞춤형 로봇(가속기)을 만들었습니다.

• 그들은 "수학 퍼즐"(NTT)을 순식간에 회전시킬 수 있는 전용 로봇을 만들었습니다.
• 또한 데이터를 빛의 속도로 뒤섞을 수 있는 "해시 트리"(Keccak) 전용 로봇을 만들었습니다.

결과:

• 관리자는 단순히 데이터를 로봇에게 전달했습니다.
• 로봇들은 병렬로(동시에) 무거운 작업을 수행했습니다.
• 결과는 밀리초(ms) 단위로 돌아왔습니다.
  • 키 생성(Key Generation): 약 1 밀리초.
  • 서명(Signing): 약 6 밀리초.

결론

이 논문은 "작은 작업실"(표준 마이크로컨트롤러)이 간단한 작업에는 훌륭하지만, 미래의 양자 내성 보안에 필요한 무거운 수학 계산을 수행하기에는 완전히 준비가 되어 있지 않다고 결론짓습니다.

이 새로운 자물쇠들을 현실 세계에서 작동하게 하려면, 단순히 소프트웨어에만 의존해서는 안 됩니다. 하드웨어-소프트웨어 공동 설계가 필요합니다. 즉, 표준적인 컴퓨터 두뇌가 과정을 관리하되, 특수 하드웨어 로봇(FPGA)이 무거운 짐을 대신 들어주는 시스템이 필요합니다. 이러한 특수 로봇이 없다면, 새로운 자물쇠들은 일상적인 기기에서 사용하기에 너무 느리거나 너무 큽니다.

기술 요약

기술 요약: 임베디드 하드웨어에서의 NIST PQC 표준에 대한 비교 성능 분석

문제 정의
대규모 양자 컴퓨팅의 등장은 현재의 공개 키 암호 인프라, 특히 쇼어 알고리즘(Shor's algorithm)에 취약한 RSA 및 ECC를 위협하고 있습니다. 이는 NIST의 표준화 노력에 의해 주도되는 양자 내성 암호(Post-Quantum Cryptography, PQC)로의 전환을 필연적으로 요구합니다. 그러나 이러한 새로운 표준의 수학적 복잡성과 자원이 제한된 임베디드 시스템의 역량 사이에는 상당한 격차가 존재합니다. 본 논문은 두 가지 NIST 표준 서명 방식인 CRYSTALS-Dilithium(격자 기반)과 SPHINCS+(해시 기반)를 표준 마이크로컨트롤러에 구현하는 것의 타당성을 조사합니다. 연구 결과, Dilithium에 요구되는 고차 다항식 곱셈과 SPHINCS+의 하이퍼트리(hypertree) 구조는 ARM Cortex-M4와 같은 범용 마이크로컨트롤러의 한계를 초과하는 계산 및 메모리 병목 현상을 생성한다는 점을 밝혀냈습니다.

방법론
본 연구는 서로 다른 하드웨어 아키텍처 전반에 걸친 성능을 평가하기 위해 이단계 실험 접근 방식을 채택했습니다:

1. 소프트웨어 전용 베이스라인 (STM32F407G):

   • 플랫폼: 32비트 ARM Cortex-M4 코어(168 MHz), 192 KB SRAM, 1 MB Flash를 탑재한 STM32F407G-DISC1 보드.
   • 접근 방식: 하드웨어 특화 최적화나 알고리즘 단순화 없이 CRYSTALS-Dilithium 및 SPHINCS+의 참조 구현(reference implementation)을 베어메탈(bare-metal) 환경으로 포팅했습니다.
   • 목적: 표준을 준수하는 베이스라인을 구축하고, 일반적인 임베디드 환경에서의 구체적인 실패 지점(메모리 오버플로, 타이밍 제약)을 식별하는 것입니다.

2. 하드웨어-소프트웨어 공동 설계 (Xilinx Zynq-7000 SoC):

   • 플랫폼: 듀얼 코어 ARM Cortex-A9 프로세싱 시스템(PS)과 Artix-7 FPGA 프로그래머블 로직(PL) 패브릭을 갖춘 ZedBoard (XC7Z020).
   • 접근 방식: CityUHK-CALAS 아키텍처를 활용하여 계산 집약적인 프리미티브(primitives)를 FPGA로 오프로딩했습니다.
   • 구현 세부 사항:
     • 오프로딩: 수론적 변환(NTT), 역 NTT(INTT), 그리고 Keccak 기반 해싱(SHA-3)을 PL 내의 전용 하드웨어 가속기로 구현했습니다.
     • 제어: PS는 고수준 프로토콜 로직, 메시지 포매팅 및 상태 머신(state machines)을 관리했습니다.
     • 통신: 제어 신호에는 AXI4-Lite를 사용하였고, 벌크 데이터 전송(키, 메시지, 서명) 시 병목 현상을 방지하기 위해 DMA를 포함한 AXI4-Stream 인터페이스를 사용하여 데이터를 처리했습니다.

주요 기여

• 한계의 실증적 검증: 본 연구는 수정되지 않은 PQC 참조 구현이 심각한 메모리 및 타이밍 제약으로 인해 표준 32비트 마이크로컨트롤러에서 실제로 사용 불가능하다는 구체적인 증거를 제공합니다.
• 아키텍처 솔루션: 이기종 SoC 접근 방식을 사용하여 암호화 워크로드를 프로세서와 FPGA 패브릭 간에 분할함으로써 성공적인 마이그레이션 전략을 입증했습니다.
• 성능 벤치마킹: MCU 상의 순수 소프트웨어 구현과 SoC 상의 하드웨어 가속 구현 간의 실행 시간에 대한 직접적인 비교 분석을 제공합니다.

결과
실험 결과는 두 플랫폼 간의 극명한 성능 차이를 보여주었습니다:

• STM32F407G (소프트웨어 전용):

  • CRYSTALS-Dilithium: 실행에 완전히 실패했습니다. 다항식 계수를 위한 중간 버퍼가 192 KB SRAM 한계를 초과함에 따라 키 생성 및 서명 생성 중에 스택 오버플로(stack overflow)가 발생했습니다.
  • SPHINCS+: 실행은 되었으나 지나치게 높은 지연 시간이 발생했습니다. 키 생성 및 서명 생성에 각각 약 10분이 소요되었습니다. 수천 번의 해시 평가를 요구하는 검증 과정은 하드웨어 해싱 가속의 부재로 인해 시스템 붕괴를 야기했습니다.

• Zynq-7000 SoC (HW-SW 공동 설계):

  • NTT 및 Keccak 연산을 FPGA로 오프로딩함으로써, 시스템은 밀리초(ms) 단위의 성능으로 성공적인 실행을 달성했습니다.
  • 키 생성: ~1.109 ms
  • 서명 생성: ~5.94 ms
  • 검증: ~1.17 ms

의의 및 주장
본 논문은 실시간 임베디드 애플리케이션을 위해 하드웨어 가속이 단순한 최적화가 아니라 NIST PQC 표준 배포를 위한 기능적 필수 요소라고 결론짓습니다. 연구 결과는 다음을 시사합니다:

1. 표준 마이크로컨트롤러에서의 순수 소프트웨어 PQC 구현은 메모리 오버플로와 과도한 지연 시간 때문에 차세대 보안 요구 사항을 충족하기에 불충분합니다.
2. 수학적 프리미티브(NTT, Keccak)를 위한 FPGA 가속을 활용하는 하드웨어-소프트웨어 공동 설계 접근 방식은 이러한 병목 현상을 효과적으로 완화합니다.
3. 이기종 컴퓨팅 아키텍처는 임베디드 시스템에서 효율적이고 안전한 양자 내성 암호 알고리즘 배포를 위해 필수적입니다.

저자들은 PQC로의 전환이 매우 중요하지만, 근본적인 하드웨어 인프라는 이러한 복잡한 알고리즘을 지원하기 위해 범용 마이크로컨트롤러에서 특화된 가속 SoC 플랫폼으로 진화해야 함을 입증하며 본 연구의 위치를 정립하였습니다.