The Rejection Sampling Trap: Neutralizing Microarchitectural Timing Leaks in Post-Quantum HSM Co-Processors

Enterprise security teams accelerating their migration to post-quantum cryptography (PQC) have hit an unexpected hardware impasse. While the mathematical foundations of lattice-based schemes like ML-DSA (Module-Lattice-Based Digital Signature Algorithm, formerly Dilithium) are mathematically resilient against quantum Shor's and Grover's algorithms, their physical execution within modern enterprise Hardware Security Modules (HSMs) is falling prey to classical microarchitectural exploitation.

The culprit is not the Number Theoretic Transform (NTT) or key storage density, but the nondeterministic nature of rejection sampling. During post-quantum signature generation, candidate polynomial coefficients are iteratively sampled and discarded if they fail strict infinity-norm bounding conditions. In bare-metal silicon and firmware co-processors, this loop introduces variable-cycle execution timing. A remote attacker with high-resolution telemetry or co-located PCIe access can measure these sub-microsecond timing variances across millions of signing requests to reconstruct the private signing key bit by bit.

⚡ Executive Briefing & Core Takeaways - The Non-Deterministic Loop: ML-DSA signature routines require rejection sampling loops to prevent private key leakage via signature distribution shape; however, variable loop iterations create exploitable microarchitectural timing signatures. - Microarchitectural Contention: In multi-tenant cloud HSMs, shared arithmetic logic units (ALUs) and cache-line evictions during rejection cycles allow cross-VM attackers to infer coefficient boundaries. - Hardware-Enforced Constant-Time Pipelines: Eliminating this vector demands deterministic dummy-round insertion, blinded polynomial accumulation, and dedicated constant-cycle coprocessor microcode.

The Mechanics of the Rejection Sampling Vector

To prevent signature output from revealing information about the secret vector $s$, ML-DSA relies on Fiat-Shamir with Aborts. When signing a message hash, the HSM computes a candidate polynomial $z = y + c \cdot s$, where $y$ is a randomly sampled masking polynomial and $c$ is a challenge hash.

The algorithm checks whether any coefficient of $z$ exceeds the predetermined bound $\beta = \gamma_1 - \beta$. If a coefficient overflows this boundary, the candidate is discarded, and the entire sampling loop restarts with a fresh entropy seed.

flowchart TD
    A["Compute Masking Vector y"] --> B["Compute Challenge c = H(M, w1)"]
    B --> C["Generate Candidate z = y + c*s"]
    C --> D{"Rejection Check:<br/>||z||_∞ >= γ1 - β ?"}
    D -- "Yes (Reject)" --> E["Rejection Branch:<br/>Restart Sampling Loop"]
    E --> A
    D -- "No (Accept)" --> F["Output Valid PQC Signature"]

In software running on general-purpose CPUs, developers can attempt to mitigate timing differences using software-level branchless masking. However, within specialized cryptographic hardware - where high-throughput FPGA and ASIC accelerators parallelize NTT multiplication - rejection handling creates tangible physical deltas:

1. Cycle-Count Jitter: Signatures that pass on the first attempt execute in approximately 120,000 to 180,000 clock cycles, while multi-rejection signatures stretch beyond 450,000 cycles.
2. Power Trace Correlation: The memory bus activity triggered by fetching fresh entropy from the True Random Number Generator (TRNG) during a restart creates distinct electromagnetic and differential power analysis (DPA) signatures.
3. Multi-Tenant PCIe Cache Leaks: In virtualized Cloud HSM partitions, cache-line fills and DMA bus latency during rejection cycles can be profiled by adjacent tenant workloads.

Benchmarking Hardware Mitigations in Enterprise HSM Fleets

Securing lattice signature pipelines against rejection timing leaks requires balancing execution latency with deterministic silicon guarantees. Cryptographic engineers generally deploy three defensive postures across enterprise hardware fleets:

Table 1: Performance trade-offs across enterprise HSM microcode architectures executing ML-DSA-65 (NIST Level 3).

Structural Hardening: Building Constant-Time Lattice Co-Processors

To neutralize rejection sampling vulnerabilities without gutting cryptographic throughput, enterprise infrastructure must enforce three structural controls across the cryptographic hardware abstraction layer:

1. Deterministic Loop Padding and Blinded Accumulation

Instead of immediately aborting upon an out-of-bounds coefficient, the co-processor must execute a fixed maximum number of sampling iterations ($k_{\max}$) for every transaction. If a valid signature is generated in iteration 1, subsequent iterations run on dummy registers using pre-allocated pseudo-random data, ensuring every API invocation returns within an identical cycle window.

// Pseudocode for constant-time rejection loop handling in HSM microcode
void secure_ml_dsa_sample_pipeline(poly_vector *z, const poly_vector *s, const challenge_t *c) {
    uint32_t valid_found = 0;
    poly_vector candidate_z, final_z;
    
    for (size_t iteration = 0; iteration < MAX_DETERMINISTIC_ROUNDS; iteration++) {
        poly_vector y = sample_mask_polynomial();
        poly_matrix_ntt_mul(&candidate_z, c, s);
        poly_vector_add(&candidate_z, &y, &candidate_z);
        
        // Branchless constant-time norm verification
        uint32_t is_rejected = constant_time_check_norm(&candidate_z, GAMMA1_MINUS_BETA);
        
        // Conditional copy without branching
        constant_time_conditional_copy(&final_z, &candidate_z, valid_found == 0 && is_rejected == 0);
        valid_found |= (1 - is_rejected);
    }
    
    // Copy output buffer regardless of when validation succeeded
    memory_secure_copy(z, &final_z, sizeof(poly_vector));
}

2. Side-Channel-Resistant TRNG Prefetch Buffering

Rejection cycles deplete entropy reserves instantaneously. If the TRNG cannot feed the lattice engine fast enough, the processor stalls, producing an unmistakable latency signature. Enterprise HSMs must decouple entropy generation from mathematical execution by maintaining a memory-safe, hardware-isolated ring buffer that guarantees constant-rate entropy access regardless of rejection rates.

3. Dedicated PCIe Isolation and Virtual Function Pinning

In multi-tenant Cloud HSM environments (such as PCIe SRIOV virtualized accelerators), host-side drivers must pin each tenant’s cryptographic execution to isolated memory channels. This prevents neighboring virtual machines from deducing rejection frequency via memory controller latency or shared cache contention.

Strategic Implementation Roadmap

timeline
    title Enterprise PQC HSM Hardening Roadmap
    Phase 1 : Microcode & Firmware Audit : Profile Rejection Sampling Timing Jitter : Identify Shared ALU Bottlenecks
    Phase 2 : Hardware-Level Constant-Time Patching : Implement Deterministic Round Padding : Deploy TRNG Prefetch Ring Buffers
    Phase 3 : Multi-Tenant Cloud HSM Isolation : Pin PCIe Virtual Functions : Verify Zero-Jitter Signature Telemetry

Transitioning enterprise infrastructure to post-quantum standards involves more than swapping out RSA-4096 key pairs for ML-KEM or ML-DSA public keys. The shift to lattice-based mathematics radically alters how microarchitectural components - from register files to ALU pipelines - interact under load.

Security architects and infrastructure leaders must audit not just the algorithmic compliance of their cryptographic vendors, but the physical, constant-time guarantees of their underlying HSM co-processors. Without rigorous hardware-level mitigation against rejection sampling timing leaks, the post-quantum shield risks being shattered by classical microarchitectural side-channels.