The Clock Is Ticking

Somewhere in a lab — or perhaps already in a classified facility — a quantum computer is inching toward the ability to break RSA-2048 in hours instead of billions of years. That day is called Q-Day, and the security community’s best estimate puts it between 2030 and 2040.

But here’s the uncomfortable truth: the threat is already active. Adversaries are executing “harvest now, decrypt later” (HNDL) attacks — collecting encrypted traffic today to decrypt when quantum computers mature. If your data needs to remain confidential for more than 5-10 years, the migration to post-quantum cryptography should have started yesterday.

What Quantum Computers Break

The Math Under Threat

Classical public-key cryptography relies on mathematical problems believed to be computationally intractable:

RSA: Factoring large integers
  n = p × q  (easy to multiply, hard to factor)
  Shor's algorithm: factors n in polynomial time on a quantum computer

ECDH/ECDSA: Elliptic Curve Discrete Logarithm Problem
  Q = k × G  (easy to compute, hard to reverse)
  Shor's algorithm: solves ECDLP in polynomial time

Diffie-Hellman: Discrete Logarithm Problem
  g^a mod p  (easy to compute, hard to reverse)
  Shor's algorithm: again, polynomial time

Shor’s algorithm makes all of these polynomial-time problems on a sufficiently powerful quantum computer. The key word is “sufficiently” — current quantum computers (1000-2000 noisy qubits) aren’t there yet. Breaking RSA-2048 likely requires ~4000 logical (error-corrected) qubits.

What’s NOT Broken

Symmetric cryptography:
  AES-256 → reduced to AES-128 equivalent security (Grover's algorithm)
  Solution: Double key sizes. AES-256 remains secure.

Hash functions:
  SHA-256 → reduced to SHA-128 equivalent collision resistance
  Solution: Use SHA-384 or SHA-512 for post-quantum margins.

The threat is specifically to PUBLIC-KEY cryptography.

NIST Post-Quantum Standards

After an 8-year evaluation process, NIST finalized the first post-quantum cryptographic standards in 2024:

ML-KEM (FIPS 203) — Key Encapsulation

Formerly known as CRYSTALS-Kyber, ML-KEM is the primary standard for key exchange and encryption:

Based on: Module Learning With Errors (MLWE) lattice problem

Security levels:
  ML-KEM-512:  AES-128 equivalent
  ML-KEM-768:  AES-192 equivalent (recommended)
  ML-KEM-1024: AES-256 equivalent

Performance comparison with RSA-2048:
  Key generation:  ~0.03ms vs ~100ms (ML-KEM is faster)
  Encapsulation:   ~0.04ms vs ~0.05ms (comparable)
  Decapsulation:   ~0.03ms vs ~2ms (ML-KEM is faster)

  Public key size: 1184 bytes vs 256 bytes (ML-KEM is larger)
  Ciphertext size: 1088 bytes vs 256 bytes (ML-KEM is larger)

The trade-off is clear: post-quantum algorithms are computationally fast but produce larger keys and ciphertexts.

ML-DSA (FIPS 204) — Digital Signatures

Formerly CRYSTALS-Dilithium, ML-DSA is the primary standard for digital signatures:

Based on: Module Learning With Errors (MLWE) lattice problem

Security levels:
  ML-DSA-44: ~128-bit security
  ML-DSA-65: ~192-bit security (recommended)
  ML-DSA-87: ~256-bit security

Signature size comparison:
  ML-DSA-65: 3293 bytes
  Ed25519:   64 bytes
  RSA-2048:  256 bytes

  Key generation: ~0.1ms (comparable to classical)
  Sign:           ~0.3ms (comparable)
  Verify:         ~0.1ms (comparable)

SLH-DSA (FIPS 205) — Hash-Based Signatures

Formerly SPHINCS+, SLH-DSA provides a conservative fallback based purely on hash functions:

Based on: Hash function security (no lattice assumptions)

Advantage: Security relies only on hash function properties
           If lattices fall to a new attack, SLH-DSA survives

Disadvantage: Large signatures (7-50 KB depending on parameter set)
              Slower signing

Hybrid Cryptography: The Transition Strategy

Don’t rip out classical crypto overnight. The recommended approach is hybrid — combining classical and post-quantum algorithms:

Hybrid TLS handshake:
  Key exchange: X25519 + ML-KEM-768
  - If ML-KEM is broken (unlikely): X25519 still protects
  - If X25519 is broken (quantum): ML-KEM still protects
  - Both must be broken simultaneously for compromise

Authentication: Ed25519 + ML-DSA-65 (or RSA + ML-DSA)

Testing Hybrid TLS with OpenSSL

# OpenSSL 3.5+ includes post-quantum support via oqs-provider
# Install liboqs and oqs-provider

git clone https://github.com/open-quantum-safe/liboqs.git
cd liboqs && mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX=/usr/local ..
make -j$(nproc) && sudo make install

git clone https://github.com/open-quantum-safe/oqs-provider.git
cd oqs-provider && mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX=/usr/local ..
make -j$(nproc) && sudo make install

# Generate hybrid key and certificate
openssl req -x509 -new -newkey mlkem768 \
    -keyout pq-key.pem -out pq-cert.pem \
    -days 365 -nodes -subj "/CN=PQ Test"

# Start test server with hybrid key exchange
openssl s_server -cert pq-cert.pem -key pq-key.pem \
    -groups x25519_mlkem768 -port 4433

# Connect with hybrid client
openssl s_client -connect localhost:4433 \
    -groups x25519_mlkem768

Nginx Configuration

# Enable hybrid post-quantum key exchange in Nginx
ssl_ecdh_curve x25519_mlkem768:x25519:prime256v1;

# This requires Nginx compiled against OpenSSL 3.5+ with oqs-provider

Migration Roadmap

Phase 1: Inventory (Now)
  ├── Catalog all cryptographic usage
  │   ├── TLS certificates and key exchange
  │   ├── SSH keys
  │   ├── VPN tunnel encryption
  │   ├── Code signing certificates
  │   ├── Data at rest encryption
  │   └── API authentication tokens
  ├── Identify long-lived data (needs PQ protection NOW)
  └── Assess harvest-now-decrypt-later risk

Phase 2: Testing (2025-2026)
  ├── Deploy PQ algorithms in test environments
  ├── Benchmark performance impact
  ├── Test library compatibility
  └── Update cryptographic libraries

Phase 3: Hybrid Deployment (2026-2028)
  ├── Enable hybrid key exchange on all TLS endpoints
  ├── Deploy hybrid certificates where supported
  ├── Update SSH to PQ-safe algorithms
  └── Maintain classical fallback

Phase 4: Full PQ (2028-2030+)
  ├── Remove classical-only configurations
  ├── Mandate PQ-safe algorithms in policy
  └── Deprecate legacy systems

SSH Migration

# OpenSSH 9.0+ supports hybrid key exchange
# Check your version
ssh -V

# Generate a PQ-safe host key (when supported)
ssh-keygen -t ml-kem-768 -f /etc/ssh/ssh_host_mlkem_key

# sshd_config — prefer PQ key exchange
KexAlgorithms [email protected],curve25519-sha256

# sntrup761 is Streamlined NTRU Prime — a lattice-based KEM
# already available in OpenSSH since 9.0
# Combined with X25519 for hybrid security

# Verify PQ key exchange is active
ssh -vvv user@host 2>&1 | grep "kex:"
# Should show: [email protected]

Code-Level Integration

Python (Using liboqs-python)

import oqs

# Key Encapsulation
kem = oqs.KeyEncapsulation("ML-KEM-768")

# Key generation
public_key = kem.generate_keypair()

# Encapsulation (sender side)
ciphertext, shared_secret_sender = kem.encap_secret(public_key)

# Decapsulation (receiver side)
shared_secret_receiver = kem.decap_secret(ciphertext)

assert shared_secret_sender == shared_secret_receiver
print(f"Shared secret: {shared_secret_sender.hex()[:32]}...")
print(f"Public key size: {len(public_key)} bytes")
print(f"Ciphertext size: {len(ciphertext)} bytes")

# Digital Signature
sig = oqs.Signature("ML-DSA-65")
public_key = sig.generate_keypair()

message = b"Post-quantum signed message"
signature = sig.sign(message)

is_valid = sig.verify(message, signature, public_key)
print(f"Signature valid: {is_valid}")
print(f"Signature size: {len(signature)} bytes")

Go

package main

import (
    "fmt"
    "github.com/cloudflare/circl/kem/mlkem/mlkem768"
)

func main() {
    // Generate keypair
    publicKey, privateKey, _ := mlkem768.GenerateKeyPair(nil)

    // Encapsulate
    ciphertext, sharedSecretA, _ := mlkem768.Encapsulate(publicKey, nil)

    // Decapsulate
    sharedSecretB, _ := mlkem768.Decapsulate(privateKey, ciphertext)

    fmt.Printf("Shared secrets match: %v\n",
        string(sharedSecretA) == string(sharedSecretB))
    fmt.Printf("Public key: %d bytes\n", len(publicKey))
    fmt.Printf("Ciphertext: %d bytes\n", len(ciphertext))
}

Performance Considerations

Real-world TLS impact (ML-KEM-768 hybrid):

  Handshake latency:
    Classical (X25519):       ~1.2ms
    Hybrid (X25519+ML-KEM):   ~1.4ms (+17%)
    Acceptable for most applications.

  Bandwidth:
    Classical ClientHello:    ~300 bytes
    Hybrid ClientHello:       ~1500 bytes (+400%)
    Noticeable on constrained networks.

  CPU overhead:
    Negligible on modern hardware.
    Significant on IoT/embedded devices.

  Certificate chain:
    Classical (RSA): ~2 KB
    PQ (ML-DSA):     ~8 KB
    Impact: Larger initial handshake, especially on mobile.

What Could Go Wrong

Risks in the PQ transition:
  1. Lattice assumptions broken → ML-KEM and ML-DSA compromised
     Mitigation: SLH-DSA (hash-based) as fallback
  2. Implementation bugs in new libraries
     Mitigation: Use audited, NIST-validated implementations
  3. Performance regression breaks production
     Mitigation: Hybrid mode with classical fallback
  4. Premature deprecation of classical crypto
     Mitigation: Maintain hybrid through 2030+
  5. Standards change (unlikely post-FIPS but possible)
     Mitigation: Crypto-agility in your architecture

The quantum computer doesn’t care about your migration timeline. Start now, deploy hybrid, and build crypto-agility into everything you touch. The algorithms are ready. The question is whether you are.