Key Exchange

We will support key exchange in the following protocols:

PQ KEM provides ephemeral keys only, and does not directly support static-key handshakes such as Noise XK and IK. While there is some recent research [PQ-WIREGUARD] on adapting Wireguard (IK) for pure PQ crypto, there are several open questions, and this approach is unproven.

Noise N does not use a two-way key exchange and so it is not suitable for hybrid encryption.

So we will support hybrid encryption only, for NTCP2, SSU2, and Ratchet. We will define the three ML-KEM variants as in [FIPS203], for 3 new encryption types total. Hybrid types will only be defined in combination with X25519.

Overhead will be substantial. Typical message 1 and 2 sizes (for XK and IK) are currently around 100 bytes (before any additional payload). This will increase by 8x to 15x depending on algorithm.

Signatures

We will support PQ and hybrid signatures in the following structures:

So we will support both PQ-only and hybrid signatures. We will define the three ML-DSA variants as in [FIPS204], for 6 new signature types total. Hybrid types will only be defined in combination with Ed25519. We will use the standard ML-DSA, NOT the pre-hash variants (HashML-DSA).

X.509 certificates and other DER encodings will use the composite structures and OIDs defined in [COMPOSITE-SIGS].

Overhead will be substantial. Typical Ed25519 destination and router identity sizes are 391 bytes. These will increase by 3.5x to 6.8x depending on algorithm. Ed25519 signatures are 64 bytes. These will increase by 38x to 76x depending on algorithm. Typical signed RouterInfo, LeaseSet, repliable datagrams, and signed streaming messages are about 1KB. These will increase by 3x to 8x depending on algorithm.

As the new destination and router identity types will not contain padding, they will not be compressible. Sizes of destinations and router identities that are gzipped in-transit will increase by 12x - 38x depending on algorithm.

TODO: Add RSA4096 hybrid types for su3?

New Crypto Required

• ML-KEM (formerly CRYSTALS-Kyber) [FIPS203]
• ML-DSA (formerly CRYSTALS-Dilithium) [FIPS204]
• SHA3-128 (formerly Keccak-256) [FIPS202]
• SHA3-256 (formerly Keccak-512) [FIPS202]
• SHAKE128 and SHAKE256 (XOF extensions to SHA3-128 and SHA3-256) [FIPS202]

Alternatives

We will not support [FIPS205] (Sphincs+), it is much much slower and bigger than ML-DSA. We will not support the upcoming FIPS206 (Falcon), it is not yet standardized.

Common Structures

Handshake Patterns

Handshakes use [Noise] handshake patterns.

The following letter mapping is used:

• e = one-time ephemeral key
• s = static key
• p = message payload
• e1 = one-time ephemeral PQ key, sent from Alice to Bob
• ekem1 = the KEM ciphertext, sent from Bob to Alice

The following modifications to XK and IK for hybrid forward secrecy (hfs) are:

XK:                       XKhfs:
<- s                      <- s
...                       ...
-> e, es, p               -> e, es, e1, p
<- e, ee, p               <- e, ee, ekem1, p
-> s, se                  -> s, se
<- p                      <- p
p ->                      p ->

e1 is encrypted together with the message 1 payload p
ekem1 is encrypted together with the message 2 payload p


IK:                       IKhfs:
<- s                      <- s
...                       ...
-> e, es, s, ss, p       -> e, es, e1, s, ss, p
<- tag, e, ee, se, p     <- tag, e, ee, ekem1, se, p
<- p                     <- p
p ->                     p ->

e1 is encrypted together with the message 1 alice static key s
ekem1 is encrypted with the message 2 ee DH result state FIXME

Noise Handshake KDF

The KEM 32-byte shared secret is combined or mixHash()ed or HKDF()ed into the final Noise shared secret, before split(), for a final 32-byte shared secret. Not concatenated with the DH shared secret for a 64-byte final shared secret, which is what TLS does [TLS-HYBRID].

Ratchet

Noise identifiers:

• "Noise_IKhfselg2_25519+MLKEM512_ChaChaPoly_SHA256"
• "Noise_IKhfselg2_25519+MLKEM768_ChaChaPoly_SHA256"
• "Noise_IKhfselg2_25519+MLKEM1024_ChaChaPoly_SHA256"

Details TODO

NTCP2

Noise identifiers:

• "Noise_XKhfsaesobfse+hs2+hs3_25519+MLKEM512_ChaChaPoly_SHA256"
• "Noise_XKhfsaesobfse+hs2+hs3_25519+MLKEM768_ChaChaPoly_SHA256"
• "Noise_XKhfsaesobfse+hs2+hs3_25519+MLKEM1024_ChaChaPoly_SHA256"

Details TODO

SSU2

Noise identifiers:

• "Noise_XKhfschaobfse+hs1+hs2+hs3_25519+MLKEM512_ChaChaPoly_SHA256"
• "Noise_XKhfschaobfse+hs1+hs2+hs3_25519+MLKEM768_ChaChaPoly_SHA256"
• "Noise_XKhfschaobfse+hs1+hs2+hs3_25519+MLKEM1024_ChaChaPoly_SHA256"

Details TODO

Issues:

For messages 1 and 2, MLKEM768 would increase packet sizes close to or beyond the 1280 minimum MTU. Probably would just not support it for that connection if the MTU was too low.

For messages 1 and 2, MLKEM1024 would increase packet sizes beyond 1500 maximum MTU. This would require fragmenting messages 1 and 2, and it would be a big complication. Probably won't do it.

Other Specs

The new maximum Destination size will be 2599 (3468 in base 64).

Update other documents that give guidance on Destination sizes, including:

• SAMv3
• Bittorrent
• Developer guidelines
• Naming / addressbook / jump servers
• Other docs

Key Exchange

Size increase (bytes):

Speed:

Speeds as reported by [CLOUDFLARE].

Signatures

Size:

Typical key, sig, RIdent, Dest sizes or size increases (Ed25519 included for reference) assuming X25519 encryption type for RIs. Added size for a Router Info, LeaseSet, repliable datagrams, and each of the two streaming (SYN and SYN ACK) packets listed. Current Destinations and Leasesets contain repeated padding and are compressible in-transit. New types do not contain padding and will not be compressible, resulting in a much higher size increase in-transit. See design section above.

Speed:

Speeds as reported by [CLOUDFLARE].

Handshakes

Probably need to prefer MLKEM768; MLKEM512 is not secure enough.

Signatures

MLDSA44 hybrid is preferable to MLDSA65 PQ-only. The keys and sig sizes for MLDSA65 and MLDSA87 are probably too big for us, at least at first.

Reliability

Size increase will result in much more tunnel fragmentation for NetDB stores, streaming handshakes, and other messages. Check for performance and reliability changes.

Structure Sizes

Find and check any code that limits the byte size of router infos and leasesets.

NetDB

Review and possibly reduce maximum LS/RI stored in RAM or on disk, to limit storage increase. Increase minimum bandwidth requirements for floodfills?

Ratchet

Auto-classify/detect on same tunnels? If not, destinations would be hybrid-only, no support for regular ratchet.

TODO

NTCP2

Need different transport address/port, would be hard to run both on the same port, we have no header or flags for message 1, it is fixed size (before padding). So probably a protocol name such as "PQTCP".

TODO

SSU2

MAY Need different transport address/port, but hopefully not, we have a header with flags for message 1. Maybe just v=2,3 in the address would be sufficient. But we need identifiers for all 3 new flavors: 3a, 3b, 3c?

Check and verify that SSU2 can handle the RI fragmented across multiple packets (6-8?)

TODO