Side-Channel Attacks on Post-Quantum Implementations — Kyber Timing Leaks and Constant-Time Defences

PQ migration solves quantum-resistance and creates new side-channel exposure. The lattice-based algorithms (ML-KEM, ML-DSA) have many more arithmetic operations than RSA/ECDSA, more conditional branches, more polynomial-ring math — more opportunities for implementation flaws. Treat PQ libraries with the same suspicion you’d treat a new TLS implementation: ask for security audits, prefer reference implementations.

The side-channel attack landscape

Side-channel attacks recover secrets by measuring physical or computational artifacts of execution rather than breaking the algorithm directly. The classic categories:

• Timing — observe execution time of cryptographic operations to infer secret-dependent branches. The most prevalent class.
• Cache — measure CPU cache hits/misses to infer memory access patterns. Common in cloud / multi-tenant environments.
• Power analysis (DPA, SPA) — measure power consumption variations during cryptographic operation. Requires physical access to the device.
• Electromagnetic (EM) — capture EM emanations during operation. Similar to power analysis, less invasive.
• Fault injection — induce errors (clock glitching, voltage dips, laser pulses) to skip security checks.

For PQ algorithms, timing and cache attacks are the most relevant for software deployments. Power and EM matter for embedded / smart-card implementations.

Documented PQ side-channel attacks

Kyber timing leaks (2022-2024 papers):

• Reference implementation’s poly_compress function had data-dependent branching. Patched in 2023; libraries shipping pre-2023 reference may still be vulnerable.
• Several papers demonstrated key recovery from a few thousand decapsulation operations in network-adversary scenarios.
• NIST issued a “constant-time review required” advisory for production Kyber deployments.

Dilithium signing time leaks:

• Sign-and-rejection-sampling pattern (Fiat-Shamir-with-aborts) has a variable number of attempts per signature. Adversary can count attempts via timing → infer information about secret.
• Mitigation: pad each signing operation to constant time. Reference implementation does this; some early third-party libraries didn’t.

SLH-DSA chosen-message attacks:

• Timing-leak-based key recovery published 2023 against pre-FIPS-205 SPHINCS+ implementations on small embedded hardware. Updated reference closes the leak.

FALCON floating-point side-channel:

• FALCON (FN-DSA, NIST-pending) uses double-precision floating point in signing — non-constant-time on most CPUs. Mitigation requires custom integer-only implementation. This is one reason ML-DSA was preferred over FALCON for the standard.

How constant-time PQ implementations work

The principle: operation duration must be independent of secret values. Practically:

1. No branches on secret data. Replace if (secret_bit == 1) do_x; else do_y; with arithmetic that produces the same result without branching: result = secret_bit * x_term + (1-secret_bit) * y_term;
2. No memory accesses indexed by secret data. Cache-timing attacks measure these. Replace with constant-time table lookups.
3. Pad variable-time operations. If signing has rejection sampling (Dilithium), measure max time across many runs and sleep to that bound on each.
4. Use SIMD-vectorised arithmetic where possible — uniform execution across lanes.

Implementation library survey — what to use

Reference implementation (github.com/pq-crystals) — written in C, constant-time, audited multiple times. Use for compatibility / spec validation; not optimised for production throughput.

OpenSSL 3.5+ — uses optimised AVX2/AVX-512 implementations on Intel; constant-time across all algorithm variants. Default choice for Linux server deployments.

BoringSSL — Google’s TLS library used by Chrome. Constant-time PQ implementation; production-quality.

AWS-LC — Amazon’s TLS library. FIPS-validated, includes constant-time PQ. Used in AWS services.

liboqs (Open Quantum Safe) — research-grade implementations of many PQ candidates. Excellent for testing. Less hardened than the production libraries above.

BouncyCastle (Java) — has PQ support from version 1.78+. Reasonably reviewed; has had known issues that were patched. Use the latest version.

WolfSSL — embedded TLS library. PQ support 2024+. Reasonable for embedded; verify constant-time guarantees for your specific compile target.

Avoid: third-party “fast PQ” libraries from individual GitHub authors without published security review. Common pattern: optimised but non-constant-time, ships with side-channel exposure.

Verifying constant-time-ness in your environment

Tools:

• ctgrind — Valgrind extension that checks for non-constant-time operations. Compile with debug symbols; run cryptographic test vectors; ctgrind reports violations.
• dudect — empirical timing-leakage tool. Runs many decap/sign operations with random secrets, measures timing distribution. Statistical leakage detection.
• Vendor audit reports — for production libraries, request the third-party security audit reports (NCC Group, Trail of Bits typically). Read the cryptographic-implementation section.

Embedded / smart-card / HSM specifics

Constant-time on x86 server CPUs is achievable. Constant-time on small embedded MCUs (ARM Cortex-M, RISC-V) is harder — limited SIMD, constrained memory, divider instructions are variable-time on some chips.

For HSMs: vendor PQ implementations are vendor-attested. For high-assurance, request:

• FIPS 140-3 Level 3 or higher certification.
• Side-channel resistance attestation (CAVP, Common Criteria EAL4+).
• Open-source-able compliance reports if available.

FAQ

Should we prefer ChaCha20+Kyber over AES+Kyber for side-channel reasons?

ChaCha20 is more naturally constant-time on hardware without AES-NI. On modern x86 with AES-NI, AES-256 is constant-time and faster. Choose ChaCha20 for embedded / non-x86; AES-256 for server-side x86.

Are PQ algorithms more side-channel-prone than ECC?

Yes, in raw operations: more arithmetic, more conditional logic. In production: not meaningfully riskier when using mature libraries (OpenSSL 3.5, BoringSSL). The library quality dominates the algorithm choice for side-channel exposure.

Do we need to run side-channel testing on every release?

For production crypto code, yes — same hygiene as you’d apply to any cryptographic library. Most teams rely on the underlying library’s testing (OpenSSL has extensive constant-time testing); custom integrations need their own.

What about timing leaks in network protocols using PQ?

Protocol-level timing channels (TLS handshake completion time, JWT verification response time) can also leak. Defence: rate-limit API endpoints; use deliberate-delay middleware for security-sensitive verifications.

Are there papers on quantum-side-channel attacks?

“Quantum-side-channel” usually means using quantum sensors (atomic clocks, single-photon detectors) for side-channel measurement — research-stage, not production-relevant for typical enterprise threat models.

⚖️ Module 12 of 20. Advanced. Module 13 covers crypto-agility — engineering systems for algorithm replacement.