← Week 1: The Quantum Threat

Day 2: Grover's Algorithm and Symmetric Crypto

Phase 3 · July 9, 2026

← Week 1: The Quantum Threat

Agenda (2–3 hours)

  • Read (45 min): NIST FIPS 203 §1 Introduction (pp. 1–6); NIST IR 8413 §2.B (symmetric crypto under quantum)
  • Study (45 min): Grover's speedup, why doubling key sizes is sufficient
  • Practice (30 min): Parameter comparison exercise
  • Challenge (30 min): Symmetric crypto recommendation memo
← Week 1: The Quantum Threat

Shor's is exponential speedup — it breaks public-key crypto.
Grover's is only quadratic speedup — it weakens symmetric crypto.

Classical brute-force AES-128: 2^128 operations
Quantum Grover on AES-128:     2^64 operations  (still enormous)

Classical brute-force AES-256: 2^256 operations
Quantum Grover on AES-256:     2^128 operations (acceptable security margin)

Practical implication: double your symmetric key sizes to maintain equivalent
post-quantum security. AES-128 → AES-256. SHA-256 → SHA-384 or SHA-512.

← Week 1: The Quantum Threat

TLS 1.3 Cipher Suites: Are We OK?

Cipher Suite Classical Security Quantum Security
TLS_AES_128_GCM_SHA256 128-bit ~64-bit (Grover)
TLS_AES_256_GCM_SHA384 256-bit ~128-bit ✓
TLS_CHACHA20_POLY1305_SHA256 256-bit ~128-bit ✓

Key exchange is the problem, not the cipher.
Even with AES-256 bulk encryption, the TLS session key is derived from ECDHE —
and ECDHE is broken by Shor's. The perfect-forward-secrecy property vanishes.

← Week 1: The Quantum Threat

Hash Functions Under Grover's

Hash Output size Classical collision Quantum collision
SHA-256 256-bit 2^128 2^85 (BHT algorithm)
SHA-384 384-bit 2^192 2^128 ✓
SHA-512 512-bit 2^256 2^170 ✓

For certificate signatures and TLS: SHA-384 provides 128-bit post-quantum security.
SHA-256 is borderline — not broken, but the margin is smaller.

ML-KEM and ML-DSA internally use SHA-3 (SHAKE) with sufficient output sizes.

← Week 1: The Quantum Threat

What Doesn't Need to Change

Symmetric primitives are quantum-safe with larger parameters:

  • ✓ AES-256-GCM — use instead of AES-128
  • ✓ ChaCha20-Poly1305 — 256-bit key, already safe
  • ✓ SHA-384 / SHA-512 — already used in TLS 1.3 AES-256 suites
  • ✓ HMAC-SHA384 — safe for MACs and PRFs

What must change:

  • ✗ All RSA operations (key exchange, signatures)
  • ✗ All ECDH/ECDSA operations (signatures, key exchange)
  • ✗ All DSA/DH operations
← Week 1: The Quantum Threat

Practice Exercise

For your current TLS stack (assume rustls with TLS 1.3 + aws-lc-rs):

List every cryptographic operation in a TLS 1.3 handshake and classify each as:

  • Safe: unaffected or safe with current parameters
  • Upgrade needed: safe with parameter change (e.g., AES-128 → AES-256)
  • Replace: fundamentally broken by Shor's, requires PQC replacement

Use the TLS 1.3 handshake diagram from Phase 1 as your reference.

← Week 1: The Quantum Threat

Challenge Assignment

Write a 1-page "Symmetric Crypto Recommendation" memo:

Context: your team is doing a pre-migration audit. You're asked to recommend
which symmetric algorithms and key sizes should be used in the service today
to be quantum-safe, without waiting for PQC migration.

Cover: cipher suites for TLS, HMAC for internal MACs, hash functions for cert
signing, and key sizes for any symmetric data-at-rest encryption (DynamoDB, S3).

This is a quick win your team can implement before the full PQC migration.

← Week 1: The Quantum Threat

Resources

  • NIST FIPS 203 §1: Introduction and security levels
  • NIST IR 8413 §2.B: symmetric and hash functions under quantum
  • NIST SP 800-131A Rev 2: algorithm transitions (current NIST guidance)