Post-Quantum Cryptography: CRYSTALS-Kyber and Dilithium

Current public-key cryptography — RSA, ECC, and Diffie-Hellman — relies on mathematical problems that are computationally infeasible for classical computers. RSA's security rests on the difficulty of factoring large integers; ECC's security rests on the elliptic curve discrete logarithm problem. A sufficiently powerful quantum computer running Shor's algorithm can solve both problems in polynomial time, effectively breaking all widely deployed public-key cryptography. While such a quantum computer does not exist today, the threat is taken seriously enough that NIST began standardizing quantum-resistant alternatives in 2016.

Nation-state adversaries may be collecting encrypted internet traffic today with the intention of decrypting it once quantum computers become available — a strategy called 'harvest now, decrypt later' or SNDL (Store Now, Decrypt Later). Data with long-term sensitivity (classified government secrets, financial records, medical data) is at particular risk because it may still be sensitive when quantum computers arrive. This is why organizations are urged to migrate to post-quantum cryptography (PQC) before quantum computers exist, not after, since the transition is complex and time-consuming.

It is important to distinguish the quantum threat to different algorithm classes. Shor's algorithm breaks RSA and ECC asymmetric cryptography. Grover's algorithm provides a quadratic speedup for searching, which halves the effective key length of symmetric ciphers and hash functions. This means AES-128 provides only 64-bit security against a quantum attacker — insufficient — while AES-256 maintains 128-bit post-quantum security, which is acceptable. SHA-256 similarly has its security halved but SHA-256 is still adequate; SHA-384 and SHA-512 are recommended for longer-term security.

In 2016, NIST launched a competition to select post-quantum cryptographic algorithms, receiving 82 submissions. After multiple evaluation rounds, NIST finalized its first set of PQC standards in 2024: FIPS 203 (ML-KEM, from CRYSTALS-Kyber) for key encapsulation, FIPS 204 (ML-DSA, from CRYSTALS-Dilithium) for digital signatures, and FIPS 205 (SLH-DSA, from SPHINCS+) as a hash-based signature alternative. These algorithms resist attacks from both classical and quantum computers and are intended to replace RSA and ECDSA in PKI systems.

Both CRYSTALS-Kyber and CRYSTALS-Dilithium are lattice-based cryptographic schemes. A lattice is a regular grid of points in high-dimensional space. The hard problem underlying both algorithms is the Learning With Errors (LWE) problem: given a set of linear equations with small random errors added, find the underlying secret. No known quantum algorithm solves LWE efficiently. The Module-LWE (MLWE) variant used in CRYSTALS provides a good balance between security level and key/ciphertext size.

CRYSTALS-Kyber (now ML-KEM) is a Key Encapsulation Mechanism (KEM) — it allows two parties to establish a shared secret over an insecure channel, replacing Diffie-Hellman and RSA key exchange. Kyber generates a public/private key pair; the sender encapsulates a random session key using the recipient's public key; the recipient decapsulates it using their private key. Kyber-768 (NIST security level 3, roughly equivalent to AES-192) has a public key of about 1,184 bytes and a ciphertext of about 1,088 bytes — much larger than a 256-byte RSA-2048 key.

CRYSTALS-Dilithium (now ML-DSA) is a digital signature algorithm that replaces ECDSA and RSA signatures. It produces signatures using lattice mathematics, and verification is efficient. Dilithium3 (security level 3) produces signatures of about 3,293 bytes — significantly larger than a 64-byte ECDSA signature. This size increase is the primary migration challenge for certificate-heavy PKI systems. Despite the size, Dilithium signs and verifies quickly on standard hardware and is resistant to all known quantum attacks.

SPHINCS+ (now SLH-DSA) is a stateless hash-based signature scheme selected by NIST as an alternative to Dilithium. Its security relies only on the security of its underlying hash function (SHA-256 or SHAKE), making it extremely conservative — if lattice mathematics is somehow broken, SPHINCS+ remains secure. The trade-off is signature size: SPHINCS+ signatures range from 8KB to 50KB depending on the parameter set, making it unsuitable for TLS certificates but excellent for code signing where signature size is less critical.

The recommended migration strategy is hybrid cryptography: combine a classical algorithm with a post-quantum algorithm, so the connection is secure as long as either algorithm remains unbroken. For example, X25519 + Kyber-768 for key exchange means an attacker would need to break both ECDH and Kyber to decrypt the traffic. This is already being deployed: Google's Chrome browser added support for X25519Kyber768 hybrid key exchange for TLS 1.3 in 2023, and Apple added it to iMessage. The hybrid approach allows a smooth transition without an abrupt flag-day cutover.

Migrating PKI to post-quantum algorithms involves enormous complexity: certificate sizes increase significantly, affecting TLS handshake sizes and performance; hardware security modules (HSMs) must be updated or replaced to support new algorithms; code signing infrastructure and certificate authorities need updates; and IoT devices with constrained memory may not support larger post-quantum keys. Organizations should begin cryptographic inventory — cataloguing all places where RSA and ECC are used — as the first step in their PQC migration plan.

Crypto agility refers to designing systems so that cryptographic algorithms can be swapped out without requiring a complete system redesign. Systems with crypto agility store algorithm identifiers alongside keys and ciphertexts, allowing future upgrades by changing a configuration parameter. TLS, SSH, and modern certificate standards already demonstrate crypto agility. Organizations should audit their custom protocols and applications for hardcoded algorithm choices — these are the systems that will be most expensive to migrate. Adopting a cryptographic library abstraction layer now makes PQC migration orders of magnitude easier.

Test your understanding of CompTIA Security+ (SY0-701) concepts from this lesson.

In this lesson you learned: Shor's algorithm threatens RSA and ECC while Grover's algorithm only halves symmetric key security, making AES-256 and SHA-384 still viable post-quantum, CRYSTALS-Kyber (ML-KEM) replaces key exchange and CRYSTALS-Dilithium (ML-DSA) replaces digital signatures as NIST's selected post-quantum standards, and hybrid cryptography combining classical and PQC algorithms is the recommended migration strategy while the transition unfolds. Next up we explore container security for cloud-native environments.