Post-Quantum Cryptography for Smart Cards

Post-Quantum Cryptography for Smart Cards

The NIST Post-Quantum Cryptography standardisation process (completed August 2024) published three algorithms: ML-KEM (CRYSTALS-Kyber), ML-DSA (CRYSTALS-Dilithium), and SLH-DSA (SPHINCS+). A fourth — FN-DSA (FALCON) — is expected in a follow-on standard. Deploying these algorithms on smart cards is technically challenging: public keys and signatures are orders of magnitude larger than their classical counterparts, and lattice operations require more RAM than typical ECC.

Classical vs. PQC Key Sizes

SLH-DSA has an extremely small public key but a 17 KB signature — impractical for APDU exchange without chaining. ML-DSA and FN-DSA are the realistic candidates for smart card digital signatures.

Memory Constraints on Smart Cards

A typical smart card has: - RAM: 4–8 KB (stack + working buffers) — some high-end cards up to 32 KB - ROM/Flash: 256 KB–1 MB (OS + applets) - EEPROM: 64–256 KB (personalisation data, keys, certs)

ML-KEM-768 key generation requires ~23 KB of RAM in a naive implementation. Optimised implementations (NTT-in-place, stack-only polynomial arithmetic) can reduce this to ~6–8 KB — within reach of high-end smart cards.

APDU Chaining for Large Objects

Standard T=1 APDU data length is limited to 255 bytes (short form) or 65,535 bytes (extended length). ML-DSA-65 signatures at 3,293 bytes require either:

• Extended length APDUs (ISO 7816-4 §12.1): Le/Lc encoded as 3 bytes Command: CLA INS P1 P2 00 [Lc_high] [Lc_low] [data...] 00 [Le_high] [Le_low]
• Command chaining (CLA bit 4 = 1): split large data across multiple APDUs; last command has bit 4 = 0

Not all terminals support extended length APDUs — compatibility testing against payment terminal firmware versions is mandatory.

Hybrid Schemes

The NIST and BSI both recommend transitioning via hybrid key exchange — combining a classical algorithm with a PQC algorithm so that the scheme is secure if either remains unbroken:

Hybrid TLS 1.3 Key Exchange:
  key_material = HKDF(ECDH_shared_secret || ML-KEM_shared_secret)

For smart card PIV and CAC cards, the transition path is:

1. Phase 1 (now): Dual-certificate slots — classical P-256 + ML-DSA-65 certs
2. Phase 2 (2026–2028): ML-DSA-65 as primary, P-256 as legacy fallback
3. Phase 3 (2030+): Classical algorithms deprecated

NIST SP 800-208 governs hash-based signature schemes (LMS/HSS, XMSS) for firmware signing — also relevant for smart card OS update authentication.

Implementation Status

Security Considerations

• Side-channel leakage on NTT: Number Theoretic Transform in ML-KEM/DSA is vulnerable to timing attacks on constrained hardware — constant-time NTT is mandatory
• Fault injection on decapsulation: ML-KEM decapsulation performs a re-encryption check; a fault skipping this check can leak the decapsulation key
• Random number quality: ML-DSA requires 32 bytes of fresh randomness per signature — critical for smart card RNG quality (NIST SP 800-90A CTR_DRBG mandatory)

For the underlying hardware security model, see TEE vs Secure Element. For the certification framework around Common Criteria and Protection Profiles as they evolve for PQC, see EAL Comparator.