💻 computer science

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

This paper critically evaluates the security claims of the "Adams Bridge" PQC hardware accelerator by demonstrating that its partial masking and shuffling defenses are significantly weaker than asserted due to limited entropy and effective belief propagation attacks, while simultaneously proposing a strategic masking of three consecutive mid-layers as a robust countermeasure and establishing a reusable methodology for auditing partially masked NTT accelerators.

Original authors: Ray Iskander, Khaled Kirah

Published 2026-04-21

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ray Iskander, Khaled Kirah

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very valuable secret recipe (a cryptographic key) that you need to bake into a cake (a digital transaction) using a giant, complex machine (the hardware accelerator). To keep the recipe safe from spies, you put the most important ingredients in a locked, soundproof box (Boolean Masking). But because the machine is huge and expensive, you can't afford to lock every single ingredient. So, you decide to lock the first batch, and for the rest, you rely on a different trick: you tell the machine to mix the ingredients in a random order every time (Shuffling).

The designers of this machine, called Adams Bridge, claim that this mix of "one locked box + random mixing" makes it impossible for a spy to steal the recipe. They say, "Even if a spy watches the machine, the random mixing is so complex that it would take longer than the age of the universe to figure out the order."

This paper is a security audit that says: "Hold on. Let's check the math."

Here is the breakdown of what the paper found, using simple analogies:

1. The "Random Mixing" Trick Wasn't So Random

The designers claimed their mixing trick was like shuffling a deck of 64 cards into every possible order (which is trillions upon trillions of combinations). They thought this gave them a massive security wall.

The Reality: The paper looked at the machine's blueprints (the code) and found the mixing trick was much simpler. Instead of shuffling the whole deck randomly, the machine just picks a starting point and then mixes the cards in a circle from there.

The Analogy: Imagine a carousel with 64 horses. The designers thought the horses could be arranged in any order. But the machine only lets you pick which horse starts the ride. There are only 64 possible starting points, not trillions.
The Result: The "randomness" was actually very weak. It's like locking your front door but leaving the back window wide open, thinking the front door is enough.

2. The "Algebraic Shortcut"

The designers calculated the difficulty of stealing the recipe based on the idea that a spy has to guess every single ingredient one by one. They thought the math was too hard to crack.

The Reality: The paper found that the machine's math has a built-in "shortcut." Because of how the machine calculates (using something called a Gentleman-Sande butterfly), if you know the result of one step, you can mathematically figure out the other step without guessing.

The Analogy: Imagine a spy trying to guess a combination lock. The designers thought the spy had to try every number. But the paper found that the lock has a "master key" logic: if you know the first number, the second number is automatically determined by a simple rule. The spy doesn't need to guess; they just need to do a little math.

3. The "Super-Spy" Attack (Belief Propagation)

The designers assumed a spy would attack the machine piece by piece, like a detective checking one clue at a time.

The Reality: The paper used a "Super-Spy" technique called Belief Propagation. Instead of checking clues one by one, this technique looks at the entire machine at once, connecting all the dots simultaneously.

The Analogy: Imagine a detective trying to solve a crime. The designers thought the detective would interview one witness at a time. The paper showed that a "Super-Spy" can look at the whole crime scene, the weather, the timeline, and all the witnesses at once to instantly see the pattern.
The Result: When the paper ran this "Super-Spy" simulation on the machine's design, it found that the machine could be cracked much faster than the designers predicted. In fact, under certain conditions, the machine could be fully cracked with a relatively small amount of data.

4. The "Gap" in Security

The paper didn't just say "it's broken." It measured exactly how much weaker it is.

Designers' Claim: "It would take 2^132 tries to break this." (A number so big it's practically infinite).
Paper's Finding: "It might only take 2^63 tries." (Still a huge number, but trillions of times easier to break than claimed).
The Takeaway: The safety margin wasn't just a little smaller; it was a massive gap. It's like saying a fortress is impenetrable because the walls are 100 miles high, but the audit found a hidden tunnel that makes the walls only 10 miles high.

5. The Solution: "Strategic Gap Masking"

The paper doesn't just criticize; it offers a fix. It suggests that you don't need to lock every ingredient to be safe. You just need to lock the right ones.

The Fix: The paper found that if you lock the first layer of ingredients (which acts as a structural barrier) and then lock three layers in the middle, you create a "gap" that the Super-Spy cannot cross.
The Analogy: Instead of locking every single room in a mansion, you lock the front door and three rooms in the hallway. This creates a "dead zone" where the spy gets stuck. This is much cheaper than locking the whole house but provides strong protection.

Summary

This paper is a reality check for the world of Post-Quantum Cryptography.

The Problem: A popular hardware design (Adams Bridge) claimed to be super-secure by using a mix of locking and random mixing.
The Discovery: The "random mixing" wasn't random enough, and the math had hidden shortcuts that made it easier to crack than thought.
The Verdict: The security claims were too optimistic. The machine is likely weaker than the designers said.
The Advice: Don't rely on "random mixing" alone. If you must save money on security, lock the specific layers that matter most (the first and middle layers) to create an unbreakable gap, rather than trying to lock everything or nothing.

In short: The designers built a fortress with a moat they thought was 100 miles wide. The auditors measured it and found it was only 10 miles wide, with a bridge they missed. The paper tells them how to fix the bridge and make the moat deep enough again, without spending a fortune.

1. Problem Statement

The paper addresses the security risks associated with partial masking strategies in hardware accelerators for Post-Quantum Cryptography (PQC), specifically focusing on the Adams Bridge accelerator designed for the Caliptra root of trust.

The Trade-off: Fully masking the Number Theoretic Transform (NTT) operations (critical for ML-KEM and ML-DSA) incurs significant silicon area overhead. Designers often opt for partial masking (protecting only the first layer) and rely on shuffling and search space arguments to protect the remaining unmasked layers.
The Claim: The designers of Adams Bridge claim that the combination of first-layer masking and Random Start Index (RSI) shuffling renders side-channel attacks "entirely impractical," citing per-butterfly Correlation Power Analysis (CPA) complexities of $2^{46}$ (ML-DSA) and $2^{96}$ (ML-KEM), compounded multiplicatively by shuffling.
The Concern: The authors question whether these claimed security margins are accurate or if they rely on optimistic assumptions that fail under advanced algebraic side-channel attacks (SASCA) and belief propagation (BP).

2. Methodology

The authors employ a multi-faceted approach combining literature review, formal verification, and empirical simulation:

Evidence-Rated Literature Synthesis: They compile over 30 published papers, tagging every claim with an epistemic confidence level (Proven, Literature-Supported, Extrapolation, Speculative) and provenance (Software vs. Hardware).
RTL Analysis & Verification: They analyzed the publicly available Register-Transfer Level (RTL) source code of Adams Bridge to verify the actual implementation of shuffling mechanisms against the designers' claims.
Machine-Verified Algebraic Foundations: Using SMT solvers (Z3 and CVC5), they formally verified structural claims regarding the Gentleman-Sande (GS) butterfly constraints and the degrees of freedom (DOF) in the NTT factor graph.
SASCA Attack Pipeline: They developed a custom attack pipeline grounded in RTL-simulated leakage (Verilator). This pipeline includes:
- Factor graph construction.
- Template attack bridging (converting SNR to Mutual Information).
- Layer-by-layer RSI enumeration.
- Full-scale Belief Propagation (BP) on the complete ML-KEM INTT factor graph.
Layer-Ablation Studies: They systematically tested different observation topologies (which layers are observed) to determine the necessary conditions for BP convergence.

3. Key Contributions

Security Margin Audit Methodology: A reusable framework for evaluating partial-countermeasure designs that combines RTL verification, SW/HW provenance tagging, and sensitivity-scenario analysis.
RSI Shuffling Characterization: Discovery that Adams Bridge uses a Random Start Index (RSI) scheme with only 6 bits of entropy per layer (64 orderings), rather than the full random permutation ( $\approx 2^{296}$ orderings) assumed in the designers' security scaling argument.
Algebraic Search Space Reduction: Demonstration that the GS butterfly structure algebraically constrains outputs, reducing the independent unknowns per butterfly pair (e.g., from $2^{46}$ to $2^{23}$ for ML-DSA in ideal models).
Empirical Validation of BP: The first full-scale validation of Belief Propagation on a production PQC accelerator's factor graph (896 factors, 2,048 variables) using RTL-derived Signal-to-Noise Ratios (SNR).
Strategic Countermeasure Hierarchy: Identification of specific masking strategies (e.g., masking the input layer and creating "strategic gaps") that provide structural security barriers.

4. Key Results

A. Security Margin Gap

The analysis reveals a significant gap between the designers' claims and literature-supported bounds:

Designers' Claim: Implied margins of $\approx 2^{88}$ (ML-DSA) and $\approx 2^{132}$ (ML-KEM).
Literature-Supported Bounds (Scenario B): Effective margins fall to $2^{59}–2^{63}$ (ML-DSA) and $2^{61}–2^{65}$ (ML-KEM).
Pro-Attacker Bounds (Scenario A): Margins drop further to $2^{15}–2^{27}$ (ML-DSA) and $2^{16}–2^{30}$ (ML-KEM) when accounting for lattice reduction and KCA (Known-Ciphertext Attack) reductions.
Conclusion: The claimed margins are 25 to 71 bits lower than estimated, primarily due to the weakness of RSI shuffling and algebraic constraints.

B. The 37-Bit Attack-Model Gap

The authors demonstrate a 37-bit reduction in enumeration complexity independent of Belief Propagation gains:

The designers' model assumes $2^{46}$ hypotheses per butterfly.
The SASCA pipeline reduces this to $2^9$ (512 runs) by exploiting the enumerable nature of RSI shuffling and algebraic constraints.
This gap exists even without BP, simply by chaining Mutual Information (MI) accumulation and RSI enumeration.

C. Belief Propagation (BP) Findings

Full Recovery: On the complete ML-KEM INTT factor graph, BP achieves 100% coefficient recovery at an SNR $\times$ N of 3,000 (under a profiled, simulated model).
Topological Dependency: Recovery depends on observation topology, not just the number of traces.
- 4 evenly spread layers (e.g., L1, L3, L5, L7) achieve 100% recovery.
- 4 consecutive layers achieve 0% recovery, despite extracting significant Mutual Information.
Structural Barrier (NC1): If the first layer (L1) is not observed, the factor graph structurally disconnects the secret inputs, resulting in zero Mutual Information regardless of trace count. This is a hard structural barrier.

D. Countermeasure Recommendations

Based on the ablation studies, the authors propose a prioritized defense strategy:

Mask L1 (Input Layer): This creates a structural barrier (MI = 0) that cannot be overcome by increasing trace counts.
Strategic Gap Masking: Masking 3 consecutive mid-layers (e.g., L3–L5) creates a gap $\ge 3$ in the attacker's observation set. This defeats BP at moderate trace budgets (SNR $\times$ N $\le$ 5,000) with only 43% of the overhead of full masking.

5. Significance

Paradigm Shift: The paper challenges the industry assumption that shuffling can substitute for masking in unmasked NTT layers. It demonstrates that shuffling supplements masking but does not replace it.
Validation of SASCA: It bridges the gap between theoretical algebraic attacks and hardware implementation, showing that RTL-simulated leakage is sufficient to drive successful BP attacks on complex factor graphs.
Design Guidance: The identification of the "Structural Barrier" (L1 masking) and "Strategic Gap Masking" provides actionable, cost-effective guidelines for hardware designers to secure PQC accelerators without incurring the full cost of total masking.
Methodological Rigor: By introducing confidence-rated evidence and machine-verified algebraic proofs, the paper sets a new standard for evaluating side-channel security margins in PQC hardware.

Limitations: The study relies on RTL-simulated leakage rather than physical silicon measurements (though it uses the same abstraction level as the designers' TVLA). The full BP results are validated for ML-KEM ( $q=3,329$ ); transfer to ML-DSA ( $q=8,380,417$ ) requires approximate BP methods which are not yet fully validated for this specific hardware. No published attack has yet recovered keys from Adams Bridge hardware with countermeasures enabled, leaving a "potential vs. demonstrated" gap.