Trojan-Resilient NTT: Protecting Against Control Flow and Timing Faults on Reconfigurable Platforms

"트로이안-회복력 있는 NTT: 재구성 가능 플랫폼에서의 제어 흐름 및 타이밍 결함으로부터의 보호"에 대한 상세 기술 요약입니다.

1. 문제 제기

수론적 변환 (NTT) 은 격자 기반의 양자 내성 암호 (PQC) 알고리즘 (예: Kyber, Dilithium, NTRU) 의 핵심 구성 요소로, 다항식 곱셈의 복잡도를 $O(n^2)$에서 $O(n \log n)$으로 줄입니다. 그러나 FPGA 와 같은 재구성 가능 플랫폼에서의 NTT 구현은 다음과 같은 취약점에 노출되어 있습니다:

• 하드웨어 트로이안: 공급망 (RTL, 합성, 파운드리 또는 비트스트림 단계) 동안 삽입된 악성 수정으로, 데이터가 아닌 제어 신호를 표적으로 합니다. 단일 손상된 제어 신호는 전체 제어 흐름을 방해하거나 비정상적인 지연을 유발하여 치명적인 고장이나 정보 유출을 초래할 수 있습니다.
• 사이드 채널 공격 (SCA): 특히, 공격자가 전력 또는 타이밍 누출을 악용하여 비밀 공유를 복원하는 소프트 분석적 사이드 채널 공격 (SASCA) 이 있습니다.
• 기존 솔루션의 한계: 이전 연구들은 주로 데이터 신호의 결함 감지에 집중하거나 (무거운 재계산 필요) 주 설계와 긴밀하게 결합된 제어 흐름을 위한 중복 논리를 사용하여 동일한 트로이안에 취약합니다. 제어 흐름 중단, 타이밍 이상, SASCA 를 동시에 감지하면서도 상당한 성능 오버헤드 없이 적응형 수정을 제공하는 솔루션은 부재합니다.

2. 방법론

저자들은 세 가지 주요 감지 메커니즘과 적응형 결함 수정 시스템을 통합한 보안 NTT 아키텍처를 제안합니다.

A. 결함 감지 메커니즘

1. 독립 백업 CSR 을 통한 제어 흐름 무결성 (CFI):

   • 트로이안에 손상될 수 있는 주 논리 내부의 주 제어 상태 레지스터 (CSR) 를 중복하는 대신, 저자들은 주 NTT 논리와 완전히 독립적인 **경량 우측 시프트 레지스터 (RSR)**를 도입합니다.
   • 주 CSR 은 제어 신호 (예: rd_en, wr_en, barrett_strt) 를 생성합니다. RSR 은 이러한 신호를 모니터링합니다.
   • 논리: RSR 은 주 CSR 과 동기화되어 비트를 시프트합니다. 주 논리가 변조된 경우 (예: 트로이안이 클록을 게이트하거나 리셋을 반전), RSR 의 예상 상태는 실제 제어 신호와 달라져 cfi_fault 를 트리거합니다.
   • 이는 poly_mem, Barrett Reduction, uv_add/sub와 같은 특정 블록의 무결성을 검증합니다.

2. 클록 사이클 카운터 (CCC) 를 통한 타이밍 무결성:

   • CCC 는 주요 모듈의 활성 지속 시간을 모니터링합니다.
   • 차수가 $n-1$인 다항식의 경우, NTT 는 고정된 수의 사이클이 필요합니다: $(\log n \times n/2) + (p-1)$ (여기서 $p$는 파이프라인 깊이입니다).
   • 트로이안이 지연을 유발 (파이프라인 정지) 하거나 연산을 가속화하면, CCC 는 예상 사이클 수에서의 편차를 감지하여 ccc_fault 를 트리거합니다.

3. 로컬 마스킹 (LM) 을 통한 SASCA 완화:

   • SASCA 를 방지하기 위해, 아키텍처는 다항식 메모리 (poly_mem) 에 쓰기 작업 중 **회전 인자 ($\omega$)**를 무작위화합니다.
   • $(U+V)$와 $(U-V)$를 직접 쓰는 대신, 시스템은 $(U+V)\omega_r$과 $(U-V)\omega_r$을 씁니다. 여기서 $\omega_r$은 무작위 인자입니다.
   • 이는 실제 데이터와 관련된 전력 소비 프로파일을 마스킹하여 누출을 방지합니다. 역 NTT 에서 인자들은 원래 계수를 복원하기 위해 $\omega_r^{-1}$과 곱해집니다.

B. 적응형 결함 수정

결함 (cfi_fault 또는 ccc_fault) 을 감지하면, 시스템은 영구적으로 시스템을 중단하지 않고 오류를 수정하기 위해 **비트 패처 (호스트 측 소프트웨어)**와 **부분 재구성 (PR)**을 사용합니다. 수정 전략은 **위험 인자 ($R_i$)**에 따라 적응적입니다:

• 위험 인자 ($R_i$) 계산: 시스템은 실행 횟수로 정규화된 감지된 결함 빈도에 기반하여 각 사용 가능한 PR 비트스트림 위치에 대한 위험 점수를 계산합니다. 이는 자주 사용되는 코어에 편향이 생기지 않도록 방지합니다.
• 세 가지 수정 조치:
  1. 이전 루프 반복 (낮은 위험): 결함 수가 적으면, 시스템은 현재 반복의 결과를 폐기하고 동일한 비트스트림을 사용하여 루프를 다시 실행합니다.
  2. PR 비트 다시 로드 (중간 위험): 결함 수가 하위 임계값을 초과하면, 시스템은 동일한 FPGA 위치에 동일한 PR 비트스트림을 다시 로드합니다 (잠재적 일시적 상태를 재설정).
  3. PR 비트 재배치 (높은 위험): 결함 수가 상위 임계값을 초과하면, 시스템은 **가장 낮은 $R_i$(가장 낮은 위험)**를 가진 PR 비트스트림을 선택하고 FPGA 바닥면의 다른 물리적 위치로 NTT 를 재구성합니다.
• 동적 인터커넥트: 버스 인터커넥트는 제어 신호와 메모리 인터페이스를 현재 활성화된 NTT 인스턴스로 동적으로 라우팅하여 PR 위치 간 원활한 전환을 가능하게 합니다.

3. 주요 기여

• 최초의 제어 흐름 중심 방어: 데이터 신호에 초점을 맞춘 이전 작업들과 달리, 이는 제어 흐름 무결성 (CFI) 을 보장하기 위해 독립적이고 경량인 백업 레지스터 (RSR) 를 사용하여 제어 신호 트로이안을 구체적으로 표적으로 삼는 최초의 설계입니다.
• 적응형 수정 전략: 정적 "항상 재배치" 접근 방식 대신, 계산된 위험 인자 ($R_i$) 에 기반하여 재실행, 다시 로드, 또는 재배치 사이를 동적으로 선택하는 새로운 결함 수정 알고리즘을 도입했습니다.
• 종합적 보호: 단일 아키텍처에서 제어 흐름 무결성, 타이밍 결함 (CCC 를 통해), SASCA (로컬 마스킹을 통해) 를 동시에 해결합니다.
• 최소한의 오버헤드: 이 솔루션은 전체 재계산이나 대규모 중복의 무거운 리소스 비용을 피하도록 설계되어 높은 효율성을 제공합니다.

4. 결과 및 평가

시스템은 Kyber PQC 알고리즘 (512, 768, 1024 변형) 을 사용하여 Artix-7 FPGA에 구현되었습니다.

• 결함 감지 및 수정 효율성:
  • 100% 감지율: 제어 신호에 대한 모든 에뮬레이션된 "Stuck-at-0" 및 "Stuck-at-1" 결함이 CFI 및 CCC 모듈에 의해 감지되었습니다.
  • 100% 수정율: 모든 감지된 결함이 적응형 모듈을 사용하여 성공적으로 수정되어 올바른 암호학적 출력을 보장했습니다.
• 오버헤드 분석:
  • 면적: 결함 감지 및 수정 모듈은 기준 NTT 대비 19.7% 의 슬라이스 오버헤드를 발생시킵니다. 감지 전용 모듈은 8.7% 만 추가합니다.
  • 에너지: 총 에너지 오버헤드는 **3%**입니다.
  • 타이밍:
    • 감지는 0 의 타이밍 오버헤드를 추가합니다.
    • 수정 오버헤드는 조치에 따라 다릅니다:
      • 루프 반복: 약 10 ns (1 클록 사이클).
      • PR 다시 로드: 약 150 µs (ICAP 전송 시간).
      • PR 재배치: 약 256 µs (최적 비트스트림 검색 포함).
• 트로이안 시나리오: 시스템은 상류/하류 데이터 경로, NTT 코어 내부, 심지어 모니터링 로직 내부에 위치한 트로이안을 효과적으로 완화합니다 (후자의 경우 모니터링 자체가 손상되면 치명적인 고장 지점으로 간주됨).

5. 의의

이 논문은 양자 내성 암호를 위한 하드웨어 보안에서 중요한 발전을 제시합니다. 데이터 무결성에서 제어 흐름 무결성으로 초점을 이동시킴으로써, 전통적인 결함 감지에 의해 종종 간과되는 고영향 저비용 공격 벡터를 해결합니다. 적응형 수정 메커니즘은 보안과 성능 사이의 실용적인 균형을 제공하여, 시스템이 최소한의 지연 시간과 리소스 페널티로 정교한 하드웨어 트로이안으로부터 복구할 수 있게 합니다. 이 연구는 공급망 보안을 완전히 보장할 수 없는 국방, 항공우주, 통신과 같은 핵심 인프라에 회복력 있는 PQC 가속기를 배포하는 길을 마련합니다.