💻 computer science

Partial Number Theoretic Transform Masking in Post-Quantum Cryptography (PQC) Hardware: A Security Margin Analysis

본 논문은 Caliptra 루트 오브 트러스트용 ML-DSA 및 ML-KEM 하드웨어 가속기 'Adams Bridge'의 부분적 INTT 마스킹 설계가 기존 주장보다 낮은 보안 마진을 가지며, BP(신호 전파) 수렴 조건과 레이어 선택 전략을 규명하여 부분 마스킹 아키텍처의 취약점을 분석하고 개선 방안을 제시합니다.

원저자: Ray Iskander, Khaled Kirah

게시일 2026-04-21

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Ray Iskander, Khaled Kirah

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

1. 배경: 새로운 금고와 '반쪽짜리' 잠금장치

미래의 암호 기술 (양자 컴퓨터에 대비한 PQC) 을 위해 설계된 **'Adams Bridge'**라는 칩이 있습니다. 이 칩은 은행의 금고처럼 중요한 데이터를 보호하는 역할을 합니다.

설계자의 주장: "우리는 금고의 문 (데이터 처리의 첫 단계) 에는 **강력한 자물쇠 (마스크링)**를 걸었습니다. 나머지 내부 통로들은 자물쇠 대신 **사람들이 무작위로 뛰어다니는 미로 (셔플링)**로 만들었습니다. 도둑이 미로에서 길을 잃고 헤매는 데 걸리는 시간은 우주의 나이보다 길기 때문에, 도둑은 절대 금고를 뚫을 수 없습니다!"
논문의 질문: "그게 정말 사실일까요? 아니면 설계자가 미로의 복잡함을 과장해서 계산한 걸까요?"

저희 연구팀은 이 주장이 진짜인지, 수학적으로나 컴퓨터 시뮬레이션으로 검증해 보았습니다.

2. 핵심 발견 1: 미로의 함정 (셔플링의 진실)

설계자는 "우리는 64 개의 통로가 있는 미로를 만들었고, 도둑이 들어갈 수 있는 길은 **64 개가 아니라 64! (64 의 팩토리얼, 약 10^89 개)**이나 된다"고 주장했습니다. 이는 마치 64 개의 문이 모두 서로 다른 순서로 배열되어 있어, 도둑이 모든 경우의 수를 다 시도하려면 우주가 끝날 때까지 걸린다는 뜻입니다.

하지만 우리가 칩의 설계도 (RTL 코드) 를 자세히 보니, 사실은 그렇지 않았습니다.

실제 상황: 도둑이 들어갈 수 있는 길은 64 개뿐이었습니다.
비유: 설계자는 "이 미로는 64 개의 문이 모두 서로 다른 순서로 섞여 있어, 64! 가지의 길이 있다"고 했지만, 실제로는 **"문 64 개가 있는 복도를 시작점만 바꿔서 64 번만 돌아다닐 수 있는 구조"**였습니다.
결과: 도둑이 헤매야 하는 시간은 설계자가 생각한 것보다 수조 배나 짧아졌습니다. 마치 거대한 미로인 줄 알았는데, 사실은 64 칸짜리 작은 방을 64 번만 돌면 되는 것이었습니다.

3. 핵심 발견 2: 수학적 속임수 (알고리즘의 약점)

도둑이 미로를 통과하는 동안, 금고 안의 데이터 (계산 과정) 는 서로 연결되어 있습니다.

설계자의 생각: "각 단계마다 23 비트 (또는 12 비트) 의 비밀 숫자가 숨어있으니, 도둑이 하나하나 추측하려면 엄청난 시간이 걸릴 거야 (2^46 또는 2^96 배)."
연구팀의 발견: "아닙니다. 이 암호 시스템의 수학적 구조 (Gentleman-Sande 버터플라이) 를 보면, 한 숫자를 알면 나머지 숫자는 자동으로 결정됩니다."
비유: 금고의 열쇠 구멍이 10 개 있는데, 1 개만 열면 나머지 9 개는 자동으로 열리는 구조였습니다. 도둑은 10 개를 다 열려고 노력할 필요 없이, 하나만 맞추면 전체가 풀리는 것입니다.

4. 핵심 발견 3: AI 도둑의 등장 (신뢰 전파 공격)

과거의 도둑들은 하나하나 열쇠를 시도했습니다 (CPA 공격). 하지만 최근의 도둑들은 **AI(신뢰 전파, Belief Propagation)**를 사용합니다.

AI 도둑의 능력: AI 는 미로의 전체 지도를 한눈에 보고, "여기서 이 길은 막혔으니 저쪽으로 가자"라고 연결된 정보들을 동시에 분석합니다.
실험 결과: 우리는 이 AI 도둑을 시뮬레이션으로 훈련시켰습니다.
- 결과: AI 는 설계자가 주장한 "수조 년 걸리는 시간" 대신, 수십 분에서 몇 시간 안에 금고의 열쇠를 찾아냈습니다.
- 특이점: 만약 금고의 **첫 번째 문 (입구)**만 제대로 잠가져 있다면, AI 도둑은 아무리 많은 정보를 모아도 금고 안으로 들어갈 수 없습니다. 하지만 입구가 잠겨있지 않거나, 중간에 빈틈이 있으면 AI 는 금방 뚫어버립니다.

5. 결론: 안전성은 '반쪽'입니다

이 논문의 결론은 다음과 같습니다.

주장보다 약하다: 설계자가 주장한 "완벽한 안전성"은 과장되었습니다. 실제로는 그보다 훨씬 쉽게 뚫릴 수 있는 여지가 있습니다.
미로 (셔플링) 는 부족합니다: 단순히 길을 섞는 것만으로는 양자 컴퓨터 시대의 강력한 도둑 (AI 공격) 을 막을 수 없습니다.
해결책 제안:
- 가장 중요한 것은 입구: 금고의 **첫 번째 문 (입구)**을 가장 튼튼하게 잠가야 합니다. 입구가 잠겨 있으면 AI 도둑도 아예 들어올 수 없습니다.
- 중간에도 잠금장치를: 전체를 다 잠그는 것은 비용이 많이 들지만, 중간 3 개의 통로만이라도 잠그면 도둑이 미로를 헤매는 시간을 충분히 늘려서 안전할 수 있습니다.

요약

이 논문은 **"새로운 금고가 정말 안전한가?"**를 검증한 보고서입니다.
설계자는 "미로가 너무 복잡해서 도둑은 절대 못 들어온다"고 했지만, 연구팀은 **"그 미로는 생각보다 단순하고, 도둑은 AI 를 써서 금방 길을 찾아낸다"**고 경고했습니다.

**"안전하려면 미로 (셔플링) 만 믿지 말고, 가장 중요한 문 (마스크링) 을 확실히 잠가야 한다"**는 것이 이 논문의 핵심 메시지입니다.

이 논문은 양자내성암호 (PQC) 하드웨어, 특히 Adams Bridge 가속기의 부분적 Number Theoretic Transform (NTT) 마스킹 전략에 대한 보안 마진 (Security Margin) 분석을 수행한 연구입니다. Adams Bridge 는 Caliptra 루트 오브 트러스트 (Root of Trust) 를 위해 설계된 하드웨어로, ML-DSA 와 ML-KEM 표준을 지원하며, 일부 NTT 계층에는 부울 마스킹을 적용하고 나머지는 셔플링 (Shuffling) 에 의존하는 방식을 채택했습니다.

저자들은 설계자가 주장하는 보안 수준이 실제 사이드 채널 공격 (Side-Channel Attack) 문헌과 실험적 분석에 비추어 과장되었음을 입증했습니다. 주요 내용은 다음과 같습니다.

1. 문제 제기 (Problem)

배경: FIPS 203 (ML-KEM) 과 FIPS 204 (ML-DSA) 표준의 하드웨어 구현에서 NTT 연산은 성능의 핵심이지만, 사이드 채널 공격에 취약합니다. 완전한 마스킹은 실리콘 면적 (Area) 오버헤드가 커서 부분적 마스킹 (Partial Masking) 이 대안으로 제시되었습니다.
Adams Bridge 의 주장: 설계자는 첫 번째 INTT 계층만 마스킹하고 나머지는 랜덤 시작 인덱스 (RSI, Random Start Index) 셔플링과 검색 공간 (Search Space) 논리를 통해 보호한다고 주장했습니다.
- 주장된 보안 마진: ML-DSA 는 $2^{46}$ , ML-KEM 은 $2^{96}$ 의 CPA (Correlation Power Analysis) 복잡도이며, 셔플링이 계층 간에 곱셈적으로 작용하여 ( $S^L$ ) 전체 보안 마진이 ML-DSA 는 약 $2^{88}$ , ML-KEM 은 약 $2^{132}$ 에 달한다고 주장했습니다.
핵심 의문: 부분적 마스킹과 RSI 셔플링이 실제로 설계자가 주장하는 수준의 보안을 제공하는지, 그리고 기존 문헌과 새로운 공격 모델 (SASCA) 하에서 이 주장이 타당한지 검증이 필요했습니다.

2. 방법론 (Methodology)

저자는 7 가지 분석 트랙을 통해 설계자의 주장을 평가하고, RTL 시뮬레이션 기반의 실험적 검증 파이프라인을 구축했습니다.

증거 기반 평가 (Evidence-Rated Evaluation): 30 여 편의 기존 문헌을 분석하여 각 주장에 대해 '검증됨 (Proven)', '문헌 지원 (Literature-Supported)', '외삽 (Extrapolation)', '추측 (Speculative)' 등의 신뢰도 등급을 부여했습니다.
RTL 분석 및 TVLA: 공개된 RTL 소스 코드를 분석하여 RSI 셔플링의 실제 엔트로피를 확인하고, Register-Transfer Level 시뮬레이션을 통해 누출 (Leakage) 과 신호대잡음비 (SNR) 를 추출했습니다.
SASCA (Soft Analytical Side-Channel Attack) 파이프라인:
- 신호 처리: RTL 시뮬레이션에서 추출한 누출 데이터를 기반으로 템플릿 공격 (Template Attack) 과 상호 정보량 (Mutual Information, MI) 분석을 수행했습니다.
- 신뢰 전파 (Belief Propagation, BP): NTT 계산을 팩터 그래프 (Factor Graph) 로 모델링하고, BP 알고리즘을 적용하여 셔플링과 마스킹이 제거된 계층에서의 키 복구 가능성을 실험했습니다.
- 레이어 절단 분석 (Layer-Ablation Analysis): 어떤 계층을 관측해야 BP 가 수렴하는지, 그리고 어떤 구조적 조건이 필요한지 500 회 이상의 실험을 통해 규명했습니다.
수학적 검증: SMT 솔버 (Z3, CVC5) 를 사용하여 버터플라이 구조의 대수적 제약 조건과 보안 마진 계산의 정확성을 기계적으로 검증했습니다.

3. 주요 기여 (Key Contributions)

RSI 셔플링의 엔트로피 재평가: 설계자가 주장한 완전한 무작위 순열 ( $64! \approx 2^{296}$ ) 이 아닌, RSI 방식은 64 개의 순열만 생성하여 6 비트의 엔트로피만 제공함을 RTL 분석을 통해 확인했습니다. 이는 설계자의 $S^L$ 곱셈적 보안 증폭 가정을 무효화합니다.
보안 마진 재계산: 문헌 기반 시나리오 분석을 통해 설계자가 주장한 보안 마진 ( $2^{88}$ $2^{88}$ , $2^{132}$ $2^{132}$ ) 이 과대평가되었음을 보였습니다.
- ML-DSA: $2^{59} \sim 2^{63}$ 수준 (약 $2^{25} \sim 2^{29}$ 감소).
- ML-KEM: $2^{61} \sim 2^{65}$ 수준 (약 $2^{67} \sim 2^{71}$ 감소).
37 비트 공격 모델 간극 (Attack-Model Gap) 발견: 설계자의 CPA 기반 모델 ( $2^{46}$ ) 과 SASCA 기반 분석 ( $2^{9}$ , 즉 512 번의 RSI 시도) 사이의 37 비트 차이를 정량화했습니다. 이는 BP 가 아닌 MI 축적과 RSI 열거만으로도 공격 복잡도가 급격히 낮아짐을 의미합니다.
전체 규모 BP 검증 (Full-Scale BP Validation): ML-KEM 의 전체 7 계층 INTT 팩터 그래프 (896 개 버터플라이, 2,048 변수) 에 대한 BP 실험을 수행하여, SNR×N = 3,000 에서 100% 계수 복구를 달성했습니다. 이는 이전의 소프트웨어 기반 또는 부분 그래프 분석을 넘어선 결과입니다.
구조적 장벽 및 방어 계층화: BP 수렴을 위한 4 가지 조건 (NC1~NC4) 을 규명했습니다. 특히 입력 계층 (L1) 마스킹이 구조적 정보 장벽 (Structural Information Barrier) 을 형성하여 관측이 없으면 MI 가 0 이 됨을 증명했습니다.

4. 주요 결과 (Key Results)

셔플링의 한계: RSI 방식은 완전한 무작위 셔플링보다 훨씬 취약하며, BP 공격은 셔플링 순서를 동시에 해결할 수 있어 설계자의 보호 가정이 무너집니다.
대수적 제약: Gentleman-Sande 버터플라이의 대수적 구조로 인해 독립적인 미지수 개수가 줄어들어 ( $2^{46} \to 2^{23}$ 등), 공격 공간이 축소됩니다.
관측 토폴로지의 중요성: BP 성공 여부는 관측된 계층의 '개수'가 아니라 '분포'에 달려 있습니다.
- 고르게 분산된 4 개 계층 (L1, L3, L5, L7) 은 100% 복구를 달성하지만, 연속된 4 개 계층 (L1-L4) 은 0% 성공률을 보입니다.
전략적 마스킹 제안: 모든 계층을 마스킹하는 대신, 3 개의 연속된 중간 계층 (예: L3-L5) 을 마스킹하면 공격자가 관측할 수 있는 계층 간의 간격 (Gap) 이 3 이상이 되어 BP 수렴을 실패하게 만듭니다. 이는 전체 마스킹 오버헤드의 약 43% 만으로 상당한 보안을 제공합니다.

5. 의의 및 결론 (Significance)

보안 마진 감사 방법론 제시: RTL 검증, 신뢰도 등급 부여, 민감도 시나리오 분석, 실험적 검증을 결합한 재사용 가능한 보안 마진 감사 방법론을 제시했습니다.
PQC 하드웨어 설계에 대한 경고: 부분적 마스킹이 실리콘 면적 절감의 합리적인 타협일 수는 있으나, 설계자가 주장하는 보안 수준은 SASCA 및 BP 공격 모델 하에서 과장되었음을 경고합니다. 특히 RSI 셔플링만으로는 충분하지 않습니다.
실용적 방어 전략:
1. L1 (입력 버터플라이) 마스킹 필수: 구조적 장벽을 형성하는 가장 효과적인 투자입니다.
2. 전략적 간격 마스킹: 3 개의 연속된 중간 계층을 마스킹하여 BP 수렴을 방해하는 비용 효율적인 대안을 제시했습니다.
한계와 향후 과제: 현재 결과는 RTL 시뮬레이션 기반이며, 실제 실리콘 (SoC) 환경에서의 노이즈와 전력 공급 네트워크 필터링 효과를 반영하지는 못했습니다. 또한, ML-KEM 에서 검증된 BP 결과가 더 큰 모듈러스를 가진 ML-DSA 로 확장 가능한지는 추가 검증이 필요합니다.

결론적으로, 이 논문은 Adams Bridge 와 같은 부분적 마스킹 PQC 하드웨어의 보안 주장이 현재까지의 사이드 채널 공격 문맥에서 충분히 방어적이지 않을 수 있음을 체계적으로 증명하고, 더 견고한 하드웨어 설계를 위한 구체적인 가이드라인을 제시했습니다.