0004 Hybrid post-quantum cryptography in v1
Mandatory Noise_XXhfs_25519+MLKEM768_ChaChaPoly_SHA256 key exchange and hybrid Ed25519 + ML-DSA-65 signatures directly in pre-1.0 wire v1.
Context
ADR 0002 originally specified Noise_XX_25519_ChaChaPoly_SHA256 and pure Ed25519 signatures for Tendril wire v1 (0x01). Before 1.0 release compatibility freezes the wire format, harvest-now-decrypt-later quantum adversaries pose an asymmetric risk to long-lived device-to-device links, stored grants, and rotation histories: recorded Noise ciphertexts from classical X25519 handshakes become decryptable later, whereas migrating early while pre-1.0 avoids dual-stack protocol complexity and classical downgrade surfaces.
Six design questions required resolution:
- Mandatory profile vs. versioned negotiation: Whether to upgrade wire v1 (
0x01) directly before 1.0 release or support runtime suite negotiation (classicalvs.hybrid). - Algorithm selection: Which hybrid KEM and digital signature instantiations minimize total bandwidth while fitting comfortably within Tendril's
65,519-byte Noise frame budget and pure-Rust WASM target (wasm32-unknown-unknown). - Handshake transcript ownership: Replacing
snow(NoSnow) cleanly without reintroducing classical-only fallback code. - Keeping
tendril://pairQR codes compact: Carrying raw1984-byte hybrid public keys in QR URIs exceeds dense mobile QR usability budgets. - Relay control authentication boundary: Whether untrusted ciphertext relays need ML-DSA-65 verification on
register/accept. - Independent cross-implementation verification: Preventing single-implementation blind spots in
fips203/fips204.
Decision
1. Mandatory hybrid post-quantum suite directly in wire 0x01
Pre-1.0 Tendril v1 (WIRE_VERSION = 0x01) mandates one fixed hybrid cryptographic suite with zero classical downgrade path or algorithm negotiation:
- Key exchange and session encryption:
Noise_XXhfs_25519+MLKEM768_ChaChaPoly_SHA256, replacingsnowwith an in-tree pure-Rust Sans-I/O implementation incrates/tendril-core/src/noise.rscombiningx25519-dalekand NIST FIPS 203fips203(ml_kem_768):msg1 -> e, e1:1216bytes (32 BX25519 ephemeral +1184 BML-KEM-768 encapsulation key, empty payload).msg2 <- e, ee, ekem1, s, es:1200 + len(HostHello)bytes (32 Be+1104 Bencryptedekem1+48 Bencrypteds+HostHello+16 Btag), carrying the host's1984-byte hybridsigning_pub.msg3 -> s, se:64 + len(payload)bytes (48 Bencrypteds+ payload +16 Btag).- Both handshake and transport writers (
NoiseTransport::write_message_vec) enforceMAX_FRAME_LEN(65,519B) before encrypting or incrementing AEAD nonces.
- Hybrid identity signatures: Fixed concatenation
Ed25519 (32 B pub / 64 B sig) || ML-DSA-65 (1952 B pub / 3309 B sig)(1984-byte public keys,3373-byte signatures), with FIPS 204 context stringHYBRID_MLDSA_CTX = "tendril-hybrid-v1"viafips204, required across grants, delegated chains, CRLs,4031-byteRotationRecordtranscripts, and M2Menroll_proofclaims. Verification requires both Ed25519 strict verification and ML-DSA-65 verification to succeed.
2. Compact QR pinning via HostHello.signing_pub + sh= SHA-256 pins
To keep tendril://pair?v=1&... QR URIs scannable without weakening authentication:
- Pairing URIs replace
s=<32B>withsh=<b64url(SHA-256(host_signing_pub))>(32bytes), represented intendril-coreasSigningKeyPin::{Full(HybridSigningPublicKey), Hash([u8; 32])}. - Encrypted
msg2(HostHello) transmits the responder's full1984-bytesigning_pub, which the initiator validates against itsSigningKeyPin(and anyRotationRecordchain) before emittingmsg3, persisting the resolved full key once verified. - M2M
enroll_initiateaccepts either the full1984-bytesigning_pubor the32-bytesigning_pub_hashexposed in endpointinfo_json.
3. Relay control plane retains 32-byte Ed25519 prefix (relay_pub)
Stateless WebSocket relays (spec/relay-v1.md) remain untrusted ciphertext forwarders with zero visibility into plaintext, grants, or Noise session keys. Relay register and accept proofs continue using only the 32-byte Ed25519 prefix (relay_pub) and 64-byte Ed25519 challenge-response signatures, keeping control frames compact while end-to-end Noise_XXhfs and hybrid signing protect confidentiality and identity end-to-end.
4. Independent Go verification
spec/vectors/verify_go verifies every canonical test vector independently using Go standard library crypto/mlkem (crypto/mlkem/mlkemtest), github.com/cloudflare/circl/sign/mldsa/mldsa65, and an independent Go Noise_XXhfs implementation sharing zero code with Rust tendril-core.
Consequences and measured release overhead
All release sizes below were measured directly on Linux x86_64 (lto = "thin", codegen-units = 1, strip = true):
| Artifact | Configuration | Measured Size | Pre-PQ Baseline / Delta |
|---|---|---|---|
target/release/libtendril_ffi.so |
--no-default-features |
4,834,416 B (4.61 MiB) |
4,052,248 B (+763.8 KiB) |
target/release/libtendril_ffi.so |
Default (p2p-iroh) |
15,196,176 B (14.49 MiB) |
14,606,424 B (+575.9 KiB) |
target/release/tendril |
tendril-cli default (p2p-iroh) |
17,836,408 B (17.01 MiB) |
- |
bindings/web/pkg/tendril_wasm_bg.wasm |
Sans-I/O release (gzip -9) |
1,027,782 B raw / 363,833 B gzip (355.3 KiB) |
782,671 B raw / 292,452 B gzip (+69.7 KiB gzip) |
bindings/web/pkg-p2p/tendril_wasm_bg.wasm |
p2p-iroh release (gzip -9) |
4,279,199 B raw / 1,565,104 B gzip (1.49 MiB) |
4,116,121 B raw / 1,519,232 B gzip (+44.8 KiB gzip) |
- Zero classical downgrade surface: Pre-1.0 peers reject pre-PQ
HostHello(missingsigning_pub), classical Noise transcripts, and 32-byte/64-byte grants or rotation signatures immediately. - Handshake latency and bandwidth impact: Initial
Noise_XXhfshandshakes move roughly~6 KiBtotal acrossmsg1/msg2/msg3(well below65,519B), adding negligible latency relative to Argon2id (~106 msdesktop browser) and P2P ICE setup while preventing retrospective decryption of recorded sessions. - State persistence upgrade: Endpoints persist the
32-byte ML-DSA-65 seed (pq_signing_seed_b64in CLI/runtime state and sealed browser/FFI state stores) alongside the Ed25519 seed, zeroized in memory on drop.
Connections
Local graphLinked from
- Top of page“ADR 0004”
- 1. Tendril-native wire domain separators and handshake-bound salt“ADR 0004”