# RFC-0013 — Post-Quantum Cryptography (Hybrid Classical+PQC)

- **Status:** **Ratified v1.0 — 2026-05-03.**
- **Date:** 2026-05-03
- **Ratified-By:** CTO via `tracking/sprint-3-extended-v2-plan.md` §8 (G-V2-A through G-V2-G).
- **Author:** 🧠 Agentic Architect.
- **Sprint:** Sprint 3 Extended — v2 protocol reset bundle (RFC-0012/0013/0014).
- **Audience:** Cloud Agents (LLMs); 🛡️ devex-protocol-sec; 🦀 edge-kubelet-engineer; ☁️ cloudflare-native-edge; CTO chair.
- **Depends on:** nothing new (foundational).
- **Will require v3.0 amendments to:** RFC-0003 (JWS alg identifier), RFC-0007 (enroll pubkey blob format/size). v3.0 amendment window: end-of-sprint-3-extended (2026-05-30).
- **Out of scope:** TLS-layer PQC (Cloudflare handles at their edge; we do not control the TLS handshake). PQC for client-side browsers (homepage uses CF-issued TLS only).

---

## Change Log

- **v1.0 (2026-05-03):** Ratified. Folded G-V2-A..G G-V2-G per Sprint-3-Extended plan §8. Drop+recreate D1 migration. UUIDv5 tenant_id (ns=`56bdc01c-052e-5f60-abfb-7fa367b284e3`). Pure-TS PQC on Worker (`@noble/post-quantum`), WASM swap deferred to S4. 6MB edge binary cap (single binary, PQC default-on, no feature flag). Self-sovereign tenant bootstrap (managed-tenant deferred to v3.0). Locked alg=`Ed25519+ML-DSA-65` with internal `alg_id` enum hedge.
- **v0.1 DRAFT (2026-04-29):** Initial draft.

---

## §1. Abstract

This RFC adopts **hybrid classical + post-quantum** cryptography for every new signature, KEM, and release-signing operation under our control. NIST-finalized algorithms only (FIPS 203 / 204 / 205). Hybrid mode means **two algorithms are run in parallel and BOTH must verify**; either failure is a hard reject. This bounds risk in two directions: a future quantum break of the classical primitive does not break us, and an as-yet-undiscovered weakness in the PQC primitive does not break us either. Sizes grow ~10–100×; we accept the cost as a one-time protocol-reset budget item.

## §2. Motivation — Threat Model

The store-now-decrypt-later (SNDL) threat is real: a passive adversary recording today's traffic can decrypt it once a cryptographically-relevant quantum computer (CRQC) exists. For long-lived material — device identity keys (years), release-signing keys (years), audit-log integrity (years) — pure classical cryptography is no longer prudent. NIST has finalized ML-KEM (FIPS 203), ML-DSA (FIPS 204), and SLH-DSA (FIPS 205) as the standard post-quantum primitives. Hybrid (classical + PQC) is the broadly-recommended transition mode (see [NIST IR 8547] draft, [BSI PQC migration guidance], [IETF hybrid PQC drafts]).

We adopt now, before we have customer keys to migrate later.

---

## §3. Algorithm Matrix (NORMATIVE, locked)

| Use                              | Classical | Post-Quantum    | Mode          | Spec                |
|----------------------------------|-----------|------------------|---------------|---------------------|
| Device leaf identity (enroll)    | Ed25519   | ML-DSA-65        | Hybrid sig    | FIPS 204            |
| Gateway-issued runtime tokens (JWS) | Ed25519 | ML-DSA-65       | Hybrid sig    | FIPS 204            |
| KEM (future encrypted channels)  | X25519    | ML-KEM-768       | Hybrid KEM    | FIPS 203            |
| Release artifact signing         | —         | SLH-DSA-128s     | PQC-only      | FIPS 205            |
| Hash (audit, compat)             | SHA-256   | —                | —             | FIPS 180-4          |
| Hash (high-throughput, e.g., manifest digest) | BLAKE3 | — | — | BLAKE3 spec        |

Notes:
- KEM is **specified now, not implemented this sprint.** WSS already runs over CF TLS; an explicit KEM is for future application-layer encryption (e.g., end-to-end tenant-keyed payloads). Listing it here locks the algorithm choice so the implementation surface doesn't drift later.
- Release signing transitions from minisign (Ed25519-only) to SLH-DSA-128s. **Coexistence during transition** (both signatures attached to the same artifact) is RECOMMENDED for at least one sprint to give installers time to upgrade their verifier; final removal of minisign is gated by §9 Q3.

---

## §4. Hybrid Mode — Rationale & Construction (NORMATIVE — v1.0)

**Algorithm identifier (BINDING, G-V2-E ratified):** the JWS / JWT `alg` value for the hybrid signature is the literal string `Ed25519+ML-DSA-65`. Implementations MUST use this exact string on the wire. Internally, both Worker (`src/auth/alg.ts::AlgId`) and edge (`crates/manifest::AlgId`) MUST expose a closed enum (`alg_id`) so that any future IETF rename (e.g. when draft-ietf-jose-pqc-hybrid finalizes) is a one-PR-per-side hedge rather than a call-site sweep. The wire string is binding for v2.0; the internal enum is normative.

**Edge-binary packaging (BINDING, G-V2-B ratified):** the edge `aiot-edge` binary ships PQC **default-on, single binary, no feature flag**. The static-musl release artifact size cap is **6.00 MB** (raised from 5.00 MB at G-V2-B ratification). 🦀 edge-kubelet-engineer's W1 PQC spike measured **3.62 MB** for the actual hybrid build — well under the 6 MB cap; G-V2-B headroom is healthy.

**Rationale.** Defense-in-depth across two independent cryptographic foundations:
- Classical (elliptic-curve Ed25519, X25519) — decades of cryptanalysis, broken by sufficiently-large CRQC.
- Post-quantum (ML-DSA, ML-KEM are lattice-based; SLH-DSA is hash-based) — recently standardized; future cryptanalysis may find weaknesses.

If either foundation breaks, the other still protects us. Both must pass for verification to succeed; this is a strict AND.

**Signature construction.** A hybrid signature is the concatenation:

```
hybrid_sig = ed25519_sig (64B) || mldsa65_sig (~3309B)
```

The verifier MUST split at the fixed Ed25519 boundary (64B), verify Ed25519 against the Ed25519 pubkey over the same message, verify ML-DSA-65 against the ML-DSA-65 pubkey over the same message, and reject if either verification fails. No early-exit on the first verifier failure (constant-time AND for side-channel hygiene).

**Hybrid public key blob.** Concatenated with explicit length tags (so component sizes can evolve):

```
hybrid_pubkey_v1 := 0x01            ; version
                 || u16_be(len_ed)  ; 32
                 || ed25519_pub
                 || u16_be(len_pq)  ; 1952 for ML-DSA-65
                 || mldsa65_pub
```

Stored PEM-encoded (`-----BEGIN AETHERMESH HYBRID PUBLIC KEY-----`) in D1 `enroll_pubkey_pem`; transmitted raw (with length prefixes per above) inside WSS auth frames.

**Domain separation.** Both signers sign the **identical canonical message bytes**; no per-algorithm prefix is used. Rationale: the algorithms are independent enough that combiner attacks on the message layer are not a known concern, and adding a prefix complicates cross-implementation interop.

**Verification pseudocode (NORMATIVE behaviour):**

```
fn verify_hybrid(msg, sig_blob, pubkey_blob) -> bool:
    (ed_pub, pq_pub)   = split_pubkey(pubkey_blob)        # length-tagged per §4
    (ed_sig, pq_sig)   = split_sig(sig_blob, ed_len=64)
    ok_ed = ed25519_verify(ed_pub, msg, ed_sig)           # do not short-circuit
    ok_pq = mldsa65_verify(pq_pub, msg, pq_sig)
    return ok_ed AND ok_pq                                # both required
```

The `AND` MUST evaluate both verifications regardless of the first result, to avoid timing oracles that distinguish "classical-failed" from "PQC-failed". Implementations SHOULD use a constant-time boolean AND.

---

## §4a. What This RFC Does NOT Adopt (out-of-scope, locked)

To bound implementation effort and keep ratification tractable, the following are explicitly out of scope and MUST NOT appear in the v2 implementation:

- **Falcon (FN-DSA / FIPS 206 draft):** smaller sigs than ML-DSA but floating-point hazards on embedded devices; defer until FIPS-206 finalizes and Rust-on-musl story matures.
- **Stateful hash-based sigs (XMSS, LMS):** state management on the signer is operationally hostile (lose-state = catastrophic key reuse); SLH-DSA chosen instead.
- **Composite-signature ASN.1 wrappers (draft-ietf-lamps-pq-composite-sigs):** richer X.509 integration but we don't speak X.509 internally.
- **TLS-layer PQC:** Cloudflare owns the TLS handshake at our edge; our concern starts above TLS.

---

## §5. Key & Signature Sizes — Cost Model

| Primitive          | Pub key   | Sig         | Notes                              |
|--------------------|-----------|-------------|------------------------------------|
| Ed25519            | 32 B      | 64 B        | baseline                           |
| ML-DSA-65          | 1 952 B   | 3 309 B     | NIST level 3                       |
| SLH-DSA-128s       | 32 B      | 7 856 B     | small key, large slow sig; conservative |
| X25519             | 32 B      | — (KEM)     | shared secret 32 B                 |
| ML-KEM-768         | 1 184 B   | — (KEM)     | ciphertext 1 088 B                 |
| **Hybrid pubkey blob** | **~2 KB** | **—**     | per-device, stored in D1           |
| **Hybrid signature**   | **—**     | **~3.4 KB** | per-frame on auth + per-token       |

Implications:
- D1 `enroll_pubkey_pem` column grows from ~120 B (Ed25519 PEM) to **~3 KB** PEM (hybrid blob base64-armored). Well within SQLite TEXT limits.
- WSS auth frame grows from ~200 B to **~4 KB**. Worker `MAX_FRAME_BYTES` may need bumping if currently set below 16 KB; recommended setting is 16 KB to leave headroom.
- JWS runtime token (compact serialization) grows from ~400 B to **~5 KB**. Cookies/headers carrying these need to handle larger sizes; recommend never cookie-carrying these tokens (header-only).
- Per-device storage cost in production at 1 M devices: ~3 GB of pubkey material in D1. Acceptable.

---

## §6. Library Choices

### §6.1 Worker (TypeScript / V8 isolate) — BINDING (G-V2-A ratified)

**WebCrypto today does NOT support ML-DSA, ML-KEM, or SLH-DSA.** The W3C WebCrypto Level 2 draft has open issues for PQC algorithms but no shipping browser/runtime exposes them.

**Binding for v2.0 (G-V2-A):** the Worker uses **pure-TS [`@noble/post-quantum`](https://github.com/paulmillr/noble-post-quantum)** (audited; ML-DSA + ML-KEM + SLH-DSA). Bundle-size impact ~150 KB; verify ~10–15 ms. Zero build-system change; safe with `nodejs_compat` OFF.

**WASM swap deferred:** liboqs-wasm (or a Rust→WASM fragment) trades +500 KB – 1 MB bundle for ~2–4 ms verify and is a **Sprint 4 follow-up**, not a v2.0 binding. The decision is a deliberate cost-trade per G-V2-A: pure-TS saves 2 days of CI build-step work that would otherwise cascade into W2/W3 slippage on tenant lifecycle endpoints, and no currently-known v2.0 path blows the 50 ms CPU budget. Re-opening the WASM swap requires a new RFC at S4 KO.

Ed25519 stays on WebCrypto (`crypto.subtle`, native, fast).

### §6.2 Edge (Rust, aarch64-musl Pi) — BINDING (G-V2-B ratified)

Recommended: [`pqcrypto`](https://crates.io/crates/pqcrypto) family (`pqcrypto-mldsa`, `pqcrypto-mlkem`, `pqcrypto-sphincsplus`); upstream tracks NIST FIPS finalization. Backup: `liboqs-rust` (FFI to liboqs; larger binary but broader algorithm coverage and faster updates).

**Single binary, PQC default-on, no `--features pqc` flag.** Per G-V2-B ratification, the edge binary ships one SKU with PQC always compiled in. 🦀's W1 PQC spike measured the actual hybrid build at **3.62 MB** static-musl, well under the 6.00 MB cap (raised from 5.00 MB at ratification). Two-binary OSS-vs-cloud configurations are explicitly rejected.

Ed25519 stays on `ed25519-dalek` (already a dependency).

### §6.3 Release signing

[`liboqs`](https://github.com/open-quantum-safe/liboqs) provides an SLH-DSA-128s CLI via the `oqs` companion tools, or we can wrap a small Rust utility around `pqcrypto-sphincsplus`. Choice deferred to 🛡️ devex-protocol-sec at implementation time. The release artifact gains a `.slhdsa` sidecar alongside the existing `.minisig`; the v2 `install.sh` MUST verify the SLH-DSA signature and MAY additionally verify the minisign signature during the coexistence window.

---

## §7. Encoding

| Surface                 | Encoding                                                            |
|-------------------------|----------------------------------------------------------------------|
| D1 `enroll_pubkey_pem`  | PEM-armored hybrid pubkey blob (§4)                                  |
| WSS frames              | Raw bytes per §4 length-prefixed format                              |
| JWS header `alg`        | `"Ed25519+ML-DSA-65"` (custom; IANA-registration-pending)            |
| JWS-Compact signature   | base64url(`hybrid_sig` per §4)                                       |
| JWS-JSON serialization  | two `signatures` array entries: `{alg:"EdDSA", signature:…}` and `{alg:"ML-DSA-65", signature:…}` — verifier requires both present and valid |
| Release artifact sig    | `.slhdsa` sidecar file, raw SLH-DSA-128s signature bytes, base64-armored |

**Compact vs JSON serialization for JWS:** the gateway emits **JWS-Compact with the concatenated hybrid signature** for runtime tokens (smaller, simpler, single string). JWS-JSON with two signature entries is permitted for offline-signed payloads where multiple verifiers may want to selectively verify. The `alg` value `Ed25519+ML-DSA-65` is a stable string identifier for the hybrid; we will request IANA registration but do not block on it.

---

## §8. Backward Compatibility

- v1 Ed25519-only signatures: **deprecated**, removed at v2 cutover (2026-05-31). No coexistence at the WSS/JWS layer (cleaner code, smaller surface).
- v1 minisign release signatures: **coexist for at least one sprint** during release-tooling transition (§3 note).
- HS256 JWT signing: already cut over; not in scope here.

---

## §9. Performance Targets (NORMATIVE budgets)

| Operation                                      | Target          | Notes                                  |
|------------------------------------------------|-----------------|----------------------------------------|
| Device hybrid keygen on aarch64-musl Pi 4      | < 100 ms        | Ed25519 ~1 ms + ML-DSA-65 ~10–50 ms    |
| Token mint (Worker, hybrid sign)               | < 50 ms p95     | Ed25519 ~1 ms + ML-DSA-65 ~10–30 ms (WASM) |
| WSS auth-frame verify (gateway, hybrid verify) | < 100 ms p95    | both verifications, no early-exit       |
| Release sign (SLH-DSA-128s) on CI runner       | < 30 s          | one-shot per release, slow is OK        |
| Release verify (SLH-DSA-128s) on installer     | < 500 ms        | one-shot per install, must feel snappy  |

Implementation dispatch will publish actual measurements; numbers above are budgets, not facts.

---

## §10. Open Questions — Resolved at v1.0 Ratification

1. **Key custody for PQC larger keys:** RESOLVED — file-on-disk with OS-level protection (umask 0600, optionally `age`-encrypted at rest). HSM revisited at S4+ as vendors ship ML-DSA support.
2. **HSM roadmap:** RESOLVED — deferred. CF Secrets-bound material is the v2.0 stance; HSM commitment deferred until ecosystem matures.
3. **SLH-DSA vs continue-with-minisign for release signing:** RESOLVED — cut over to SLH-DSA-128s; minisign coexistence for one sprint per §3 note.
4. **`alg` identifier:** RESOLVED — lock `Ed25519+ML-DSA-65` for v2.0 (G-V2-E ratified) with internal `alg_id` enum hedge in both Worker and edge to make a future IETF rename a one-PR-per-side change rather than a call-site sweep.
5. **Worker PQC packaging:** RESOLVED — pure-TS `@noble/post-quantum` for v2.0 (G-V2-A ratified); WASM swap deferred to Sprint 4.
6. **Edge binary cap:** RESOLVED — 6.00 MB (G-V2-B ratified); single binary, PQC default-on, no feature flag. 🦀's W1 spike measured 3.62 MB — well under cap.

---

## §11. Dependency Graph

```
RFC-0013 (this)  ──foundational, depends on nothing new
RFC-0012         ──uses §3 algorithms for DID proof-of-control & JWT signing
RFC-0014         ──carries hybrid signatures over the wire (§7 encoding)
RFC-0003 v1.3    ──will need v3.0 amendment for `alg` identifier + pubkey blob format
RFC-0007 v1.1    ──will need v3.0 amendment for enroll pubkey blob (PEM hybrid format)
```

## §12. References

- NIST FIPS 203 — Module-Lattice-Based Key-Encapsulation Mechanism Standard (ML-KEM)
- NIST FIPS 204 — Module-Lattice-Based Digital Signature Standard (ML-DSA)
- NIST FIPS 205 — Stateless Hash-Based Digital Signature Standard (SLH-DSA)
- NIST IR 8547 (draft) — Transition to Post-Quantum Cryptographic Standards
- BSI TR-02102-1 — Cryptographic Mechanisms (PQC migration guidance)
- IETF draft-ietf-pquip-pqc-engineers, draft-ietf-jose-pqc-hybrid (work in progress; cited for direction, not normative)
- BLAKE3 specification — https://github.com/BLAKE3-team/BLAKE3-specs
- noble-post-quantum — https://github.com/paulmillr/noble-post-quantum
- liboqs — https://github.com/open-quantum-safe/liboqs
- pqcrypto (Rust) — https://crates.io/crates/pqcrypto
- `tracking/sprint-3-extended-v2-plan.md` §2 (G-V2-A..G), §8 (CTO sign-off) — ratification source of record.
- RFC-0012 v1.0 RATIFIED 2026-05-03 — tenant model (consumes §3 algorithms for DID proof-of-control).
- RFC-0014 v1.0 RATIFIED 2026-05-03 — v2 wire format (carries hybrid signatures over the wire).