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

1. Problem Statement

The Number Theoretic Transform (NTT) is a critical component in lattice-based Post-Quantum Cryptography (PQC) algorithms (e.g., Kyber, Dilithium, NTRU), reducing polynomial multiplication complexity from $O(n^2)$ to $O(n \log n)$. However, NTT implementations on reconfigurable platforms like FPGAs are vulnerable to:

• Hardware Trojans: Malicious modifications inserted during the supply chain (RTL, synthesis, foundry, or bitstream stages) that target control signals rather than data. A single corrupted control signal can disrupt the entire control flow or introduce unconventional delays, causing catastrophic failure or information leakage.
• Side-Channel Attacks (SCA): Specifically, Soft Analytical Side-Channel Attacks (SASCA), where adversaries exploit power or timing leakages to recover secret shares.
• Limitations of Existing Solutions: Prior works focus primarily on detecting faults in data signals (requiring heavy re-computation) or use duplicate logic for control flow that is tightly coupled with the main design, making it susceptible to the same Trojans. There is a lack of solutions that simultaneously detect control-flow disruptions, timing anomalies, and SASCA while offering adaptive correction without significant performance overhead.

2. Methodology

The authors propose a Secure NTT Architecture that integrates three primary detection mechanisms and an adaptive fault-correction system.

A. Fault Detection Mechanisms

1. Control Flow Integrity (CFI) via Independent Backup CSR:

   • Instead of duplicating the main Control Status Register (CSR) within the logic (which a Trojan could corrupt), the authors introduce a lightweight Right Shift Register (RSR) that is fully independent of the main NTT logic.
   • The main CSR generates control signals (e.g., rd_en, wr_en, barrett_strt). The RSR monitors these signals.
   • Logic: The RSR shifts bits in sync with the main CSR. If the main logic is tampered with (e.g., a Trojan gates a clock or flips a reset), the RSR's expected state will diverge from the actual control signals, triggering a cfi_fault.
   • This verifies the integrity of specific blocks: poly_mem, Barrett Reduction, and uv_add/sub.

2. Timing Integrity via Clock Cycle Counter (CCC):

   • A CCC monitors the active duration of critical modules.
   • For a polynomial of degree $n-1$, the NTT requires a fixed number of cycles: $(\log n \times n/2) + (p-1)$, where $p$ is the pipeline depth.
   • If a Trojan introduces delays (stalling the pipeline) or accelerates operations, the CCC detects the deviation from the expected cycle count, triggering a ccc_fault.

3. SASCA Mitigation via Local Masking (LM):

   • To prevent SASCA, the architecture randomizes the twiddle factors ($\omega$) during write operations to the polynomial memory (poly_mem).
   • Instead of writing $(U+V)$ and $(U-V)$ directly, the system writes $(U+V)\omega_r$ and $(U-V)\omega_r$, where $\omega_r$ is a random factor.
   • This masks the power consumption profile associated with the actual data, preventing leakage. In the Inverse NTT, the factors are multiplied by $\omega_r^{-1}$ to recover the original coefficients.

B. Adaptive Fault Correction

Upon detecting a fault (cfi_fault or ccc_fault), the system employs a Bit Patcher (host-side software) and Partial Reconfiguration (PR) to correct the error without halting the system permanently. The correction strategy is adaptive based on a Risk Factor ($R_i$):

• Risk Factor ($R_i$) Calculation: The system calculates a risk score for each available PR bitstream location based on the frequency of detected faults normalized by the number of runs. This prevents bias toward frequently used cores.
• Three Correction Measures:
  1. Repeat Previous Loop (Low Risk): If the fault count is low, the system discards the current iteration's result and re-executes the loop using the same bitstream.
  2. Reload PR Bit (Medium Risk): If the fault count exceeds a lower threshold, the system reloads the same PR bitstream to the same FPGA location (resetting potential transient states).
  3. Relocate PR Bit (High Risk): If the fault count exceeds a higher threshold, the system selects a PR bitstream with the lowest $R_i$ (lowest risk) and reconfigures the NTT to a different physical location on the FPGA floor.
• Dynamic Interconnects: Bus interconnects dynamically route control signals and memory interfaces to the currently active NTT instance, allowing seamless switching between PR locations.

3. Key Contributions

• First Control-Flow Focused Defense: Unlike prior works focusing on data signals, this is the first design to specifically target control-signal Trojans using an independent, lightweight backup register (RSR) to ensure Control Flow Integrity (CFI).
• Adaptive Correction Strategy: Introduces a novel fault-correction algorithm that dynamically chooses between re-execution, reloading, or relocating based on a calculated risk factor ($R_i$), rather than a static "always relocate" approach.
• Comprehensive Protection: Simultaneously addresses Control Flow Integrity, Timing Faults (via CCC), and SASCA (via Local Masking) in a single architecture.
• Minimal Overhead: The solution is designed for high efficiency, avoiding the heavy resource costs of full re-computation or massive duplication.

4. Results and Evaluation

The system was implemented on an Artix-7 FPGA using the Kyber PQC algorithm (variants 512, 768, and 1024).

• Fault Detection & Correction Efficiency:
  • 100% Detection Rate: All emulated "Stuck-at-0" and "Stuck-at-1" faults on control signals were detected by the CFI and CCC modules.
  • 100% Correction Rate: All detected faults were successfully corrected using the adaptive module, ensuring correct cryptographic output.
• Overhead Analysis:
  • Area: The fault detection and correction modules incur a 19.7% slice overhead compared to a baseline NTT. The detection-only module adds only 8.7%.
  • Energy: Total energy overhead is 3%.
  • Timing:
    • Detection adds zero timing overhead.
    • Correction overhead depends on the measure:
      • Repeat Loop: ~10 ns (1 clock cycle).
      • Reload PR: ~150 µs (ICAP transfer time).
      • Relocate PR: ~256 µs (includes searching for the best bitstream).
• Trojan Scenarios: The system effectively mitigates Trojans located in the upstream/downstream data paths, inside the NTT core, and even inside the monitoring logic (though the latter is noted as a critical failure point if the monitor itself is compromised).

5. Significance

This paper presents a significant advancement in hardware security for Post-Quantum Cryptography. By shifting the focus from data integrity to control flow integrity, it addresses a high-impact, low-cost attack vector often ignored by traditional fault detection. The adaptive correction mechanism offers a practical balance between security and performance, allowing systems to recover from sophisticated hardware Trojans with minimal latency and resource penalty. This work paves the way for deploying resilient PQC accelerators in critical infrastructure (defense, aerospace, telecommunications) where supply chain security cannot be fully guaranteed.