What Happened
A research team implemented Rijndael-256 (R256), the 256-bit block variant of the Rijndael family that underpins AES, across three hardware platforms: ARM Cortex-M4, ARMv8-A, and CUDA-enabled GPUs. Their goal was to optimize R256 for use in NIST post-quantum cryptography (PQC) reference implementations.
The core issue: R256's structure doesn't align with standard AES optimizations. AES uses a 4×4 state matrix, while R256 uses a 4×8 state. AES applies ShiftRows offsets of (0,1,2,3), but R256 uses (0,1,3,4). These differences mean AES-optimized code can't be directly applied to R256.
The team developed three platform-specific strategies. On Cortex-M4, they used classical bitslicing, achieving 4,962 cycles per block with secret-independent control flow and memory access patterns. On AArch64 (Apple M2), they created a pre-shuffle design using the AESE instruction with AddRoundKey folded in, reaching throughput up to 6,520 MB/s. On CUDA, they built a shared-memory T-table implementation that hit 81.16 GiB/s.
When integrated into four NIST PQC reference codebases, these optimized R256 cores delivered signing speedups between 1.18× and 114.3×, with verification speedups up to 155.6×.
Timeline
This research effort highlights a mismatch between cipher design and hardware optimization strategies:
- Design phase: NIST draft discussions identify R256 as relevant for post-quantum signature schemes.
- Implementation phase: The team encounters performance issues when applying AES optimizations to R256.
- Adaptation phase: They develop three platform-specific strategies to address the mismatches.
- Integration phase: Optimized R256 cores replace reference implementations in four NIST PQC codebases.
- Measurement phase: Performance gains are measured across signing and verification operations.
Which Controls Failed or Were Missing
This case reveals a gap in cryptographic implementation planning:
No performance baseline for non-AES ciphers. Organizations often benchmark cryptographic performance using AES. When shifting to a wider-block cipher like R256, those baselines can be misleading. Initial implementations may show unacceptable latency, potentially violating internal SLAs for transaction processing.
Hardware-cipher mismatch not documented. Modern processors have AES-specific instructions (AES-NI on x86, AESE on ARM). Deploying a cipher that doesn't map to these instructions means operating outside your hardware's designed performance envelope. If your documentation assumes AES-level performance for all symmetric ciphers, you're risking production surprises.
No constant-time implementation requirement. The Cortex-M4 implementation maintains secret-independent control flow and memory access patterns, defending against timing side-channels. Without a constant-time implementation mandate, you're vulnerable to timing attacks that leak key material through performance variations.
Integration testing limited to functional correctness. The team had to replace R256 cores in four different PQC codebases, requiring "minimal changes where needed". Original implementations weren't designed for drop-in cipher replacement. Your integration tests might verify signature validation but may not measure if a cipher swap degrades performance below transaction processing thresholds.
What the Relevant Standard Requires
FIPS 140-3 mandates security testing for cryptographic modules, including verification that implementations don't leak sensitive data through timing channels. The Cortex-M4 implementation's secret-independent behavior aligns with this requirement. If deploying post-quantum cryptography in a PCI DSS environment, your implementations must meet FIPS 140-3 validation.
PCI DSS Requirement 3.6.1 states: "Cryptographic keys are generated within secure cryptographic devices." When optimizing cipher implementations for specific hardware, verify that optimizations don't weaken the key generation or encryption process. The research team's approach of adapting optimizations rather than weakening the cipher is the correct model.
NIST SP 800-63B provides guidance on cryptographic algorithm selection for authentication. It requires using FIPS-approved algorithms. If NIST standardizes R256 for post-quantum applications, ensure your implementations meet both functional requirements and performance thresholds necessary for production use.
NIST Cybersecurity Framework calls for organizations to "develop and implement appropriate safeguards to ensure delivery of critical infrastructure services." Deploying cryptography that performs 100× slower than expected due to hardware mismatches creates an availability risk. Your safeguards must include performance testing under realistic load conditions.
Lessons and Action Items for Your Team
Benchmark non-AES ciphers independently. Don't assume post-quantum or wider-block ciphers will perform like AES. Measure their performance on your hardware under realistic load before committing to a cipher for production use. If evaluating NIST PQC candidates, test them on representative payment processing workloads.
Document hardware-cipher compatibility. Your architecture documentation should state which cryptographic instructions your processors support and which ciphers can use those instructions. When deploying a cipher that doesn't map to hardware acceleration, document the performance impact and verify it doesn't violate your SLAs.
Require constant-time implementations. Add a requirement to your cryptographic standards: all symmetric cipher implementations must maintain secret-independent control flow and memory access patterns. This defends against timing side-channels. Verify this during code review and include timing analysis in security testing.
Test cipher swaps under load. When NIST finalizes post-quantum standards, you'll need to replace existing ciphers in production systems. Build integration tests that measure performance degradation when swapping ciphers. If replacing a cipher slows transaction processing by more than 10%, consider hardware upgrades or better optimizations before deployment.
Plan for platform-specific optimizations. The research team developed different strategies for Cortex-M4, ARMv8-A, and CUDA due to each platform's constraints. Your cryptographic roadmap should account for this: you may need separate implementations for embedded payment terminals (ARM Cortex), server-side processing (x86 or ARM), and high-throughput batch operations (GPU). Budget for platform-specific engineering work.
Validate FIPS 140-3 compliance after optimization. Performance optimizations can introduce side-channels or weaken security properties. After optimizing a cipher implementation, revalidate it against FIPS 140-3 requirements. Don't assume faster code is still secure code.
