169-pq-crypto.rst

Post-Quantum Crypto Protocols

Contents

• Overview
• Goals
• Non-Goals
• Threat Model
• Design
  • Key Exchange
  • Signatures
  • Legal Combinations
  • New Crypto Required
  • Alternatives
• Specification
  • Common Structures
    • PublicKey
    • PrivateKey
    • SigningPublicKey
    • SigningPrivateKey
    • Signature
    • Key Certificates
    • Destination sizes
    • RouterIdent sizes
  • Handshake Patterns
  • Noise Handshake KDF
    • Defined ML-KEM Operations
    • Alice KDF for Message 1
    • Bob KDF for Message 1
    • Bob KDF for Message 2
    • Alice KDF for Message 2
    • Alice/Bob KDF for split()
  • Ratchet
    • Noise identifiers
    • 1b) New session format (with binding)
    • 1g) New Session Reply format
  • NTCP2
    • Noise identifiers
    • 1) SessionRequest
    • 2) SessionCreated
    • 3) SessionConfirmed
    • Key Derivation Function (KDF) (for data phase)
  • SSU2
    • Noise identifiers
    • Long Header
    • Short Header
    • SessionRequest (Type 0)
    • SessionCreated (Type 1)
    • SessionConfirmed (Type 2)
    • KDF for data phase
    • Relay and Peer Test
    • Issues
  • Streaming
  • SU3 Files
  • Other Specs
• Overhead Analysis
  • Key Exchange
  • Signatures
• Security Analysis
  • Handshakes
  • Signatures
• Type Preferences
• Implementation Notes
  • Library Support
  • Reliability
  • Structure Sizes
  • NetDB
  • Ratchet
  • NTCP2
  • SSU2
• Router Compatibility
  • Transport Names
  • Router Enc. Types
    • Type 5/6/7 Routers
    • Type 4 Routers
    • NTCP2 Alternatives
    • SSU2 Alternatives
    • Recommendations
  • Router Sig. Types
  • LS Enc. Types
  • Dest. Sig. Types
• Priorities and Rollout
• Migration
• Issues
• References

Overview

While research and competition for suitable post-quantum (PQ) cryptography have been proceeding for a decade, the choices have not become clear until recently.

We started looking at the implications of PQ crypto in 2022 [FORUM].

TLS standards added hybrid encryption support in the last two years and it now is used for a significant portion of encrypted traffic on the internet due to support in Chrome and Firefox [CLOUDFLARE].

NIST recently finalized and published the recommended algorithms for post-quantum cryptography [NIST-PQ]. Several common cryptography libraries now support the NIST standards or will be releasing support in the near future.

Both [CLOUDFLARE] and [NIST-PQ] recommend that migration start immediately. See also the 2022 NSA PQ FAQ [NSA-PQ]. I2P should be a leader in security and cryptography. Now is the time to implement the recommended algorithms. Using our flexible crypto type and signature type system, we will add types for hybrid crypto, and for PQ and hybrid signatures.

Goals

• Select PQ-resistant algorithms
• Add PQ-only and hybrid algorithms to I2P protocols where appropriate
• Define multiple variants
• Select best variants after implementation, testing, analysis, and research
• Add support incrementally and with backward compatibility

Non-Goals

• Don't change one-way (Noise N) encryption protocols
• Don't move away from SHA256, not threatened near-term by PQ
• Don't select the final preferred variants at this time

Threat Model

• Routers at the OBEP or IBGW, possibly colluding, storing garlic messages for later decryption (forward secrecy)
• Network observers storing transport messages for later decryption (forward secrecy)
• Network participants forging signatures for RI, LS, streaming, datagrams, or other structures

Design

We will support the NIST FIPS 203 and 204 standards [FIPS203] [FIPS204] which are based on, but NOT compatible with, CRYSTALS-Kyber and CRYSTALS-Dilithium (versions 3.1, 3, and older).

Key Exchange

We will support key exchange in the following protocols:

Proto	Noise Type	Support PQ?	Support Hybrid?
NTCP2	XK	no	yes
SSU2	XK	no	yes
Ratchet	IK	no	yes
TBM	N	no	no
NetDB	N	no	no

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.

The new encryption types are:

Type	Code
MLKEM512_X25519	5
MLKEM768_X25519	6
MLKEM1024_X25519	7

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:

Type	Support PQ?	Support Hybrid?
RouterInfo	yes	yes
LeaseSet	yes	yes
Streaming SYN/SYNACK/Close	yes	yes
Repliable Datagrams	yes	yes
Datagram2 (prop. 163)	yes	yes
I2CP create session msg	yes	yes
SU3 files	yes	yes
X.509 certificates	yes	yes
Java keystores	yes	yes

So we will support both PQ-only and hybrid signatures. We will define the three ML-DSA variants as in [FIPS204], as well as three hybrid variants with Ed25519 prehash for SU3 files only, for 9 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).

The new signature types are:

Type	Code
MLDSA44_EdDSA_SHA512_Ed25519	12
MLDSA65_EdDSA_SHA512_Ed25519	13
MLDSA87_EdDSA_SHA512_Ed25519	14
MLDSA44	15
MLDSA65	16
MLDSA87	17
MLDSA44_Ed25519ph	18
MLDSA65_Ed25519ph	19
MLDSA87_Ed25519ph	20

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?

Legal Combinations

For Destinations, the new signature types are supported with all encryption types in the leaseset. Set the encryption type in the key certificate to NULL (255).

For RouterIdentities, ElGamal encryption type is deprecated. The new signature types are supported with X25519 (type 4) encryption only. The new encryption types will be indicated in the RouterAddresses. The encryption type in the key certificate will continue to be type 4.

New Crypto Required

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

Test vectors for SHA3-256, SHAKE128, and SHAKE256 are at [NIST-VECTORS].

Note that the Java bouncycastle library supports all the above. C++ library support will be in OpenSSL 3.5 [OPENSSL].

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. We will not support NTRU or other PQ candidates that were not standardized by NIST.

Specification

Common Structures

Update the sections and tables in the common structures document [COMMON] as follows:

PublicKey

The new Public Key types are:

Type	Public Key Length	Since	Usage
MLKEM512_X25519	32	0.9.xx	See proposal 169, for Leasesets only, not for RIs or Destinations
MLKEM768_X25519	32	0.9.xx	See proposal 169, for Leasesets only, not for RIs or Destinations
MLKEM1024_X25519	32	0.9.xx	See proposal 169, for Leasesets only, not for RIs or Destinations
MLKEM512	800	0.9.xx	See proposal 169, for handshakes only, not for Leasesets, RIs or Destinations
MLKEM768	1184	0.9.xx	See proposal 169, for handshakes only, not for Leasesets, RIs or Destinations
MLKEM1024	1568	0.9.xx	See proposal 169, for handshakes only, not for Leasesets, RIs or Destinations
MLKEM512_CT	768	0.9.xx	See proposal 169, for handshakes only, not for Leasesets, RIs or Destinations
MLKEM768_CT	1088	0.9.xx	See proposal 169, for handshakes only, not for Leasesets, RIs or Destinations
MLKEM1024_CT	1568	0.9.xx	See proposal 169, for handshakes only, not for Leasesets, RIs or Destinations
NULL	0	0.9.xx	See proposal 169, for destinations with PQ sig types only, not for RIs or Leasesets

Hybrid public keys are the X25519 key. KEM public keys are the ephemeral PQ key sent from Alice to Bob. Byte order defined in [FIPS203].

MLKEM*_CT keys are not really public keys, they are the "ciphertext" sent from Bob to Alice in the Noise handshake. They are listed here for completeness.

PrivateKey

The new Private Key types are:

Type	Private Key Length	Since	Usage
MLKEM512_X25519	32	0.9.xx	See proposal 169, for Leasesets only, not for RIs or Destinations
MLKEM768_X25519	32	0.9.xx	See proposal 169, for Leasesets only, not for RIs or Destinations
MLKEM1024_X25519	32	0.9.xx	See proposal 169, for Leasesets only, not for RIs or Destinations
MLKEM512	1632	0.9.xx	See proposal 169, for handshakes only, not for Leasesets, RIs or Destinations
MLKEM768	2400	0.9.xx	See proposal 169, for handshakes only, not for Leasesets, RIs or Destinations
MLKEM1024	3168	0.9.xx	See proposal 169, for handshakes only, not for Leasesets, RIs or Destinations

Hybrid private keys are the X25519 key followed by the PQ key. KEM private keys are the ciphertext sent from Bob to Alice. Byte order defined in [FIPS203].

SigningPublicKey

The new Signing Public Key types are:

Type	Length (bytes)	Since	Usage
MLDSA44_EdDSA_SHA512_Ed25519	1344	0.9.xx	See proposal 169
MLDSA65_EdDSA_SHA512_Ed25519	1984	0.9.xx	See proposal 169
MLDSA87_EdDSA_SHA512_Ed25519	2624	0.9.xx	See proposal 169
MLDSA44	1312	0.9.xx	See proposal 169
MLDSA65	1952	0.9.xx	See proposal 169
MLDSA87	2592	0.9.xx	See proposal 169
MLDSA44_Ed25519ph	1344	0.9.xx	Only for SU3 files, not for netdb structures
MLDSA65_Ed25519ph	1984	0.9.xx	Only for SU3 files, not for netdb structures
MLDSA87_Ed25519ph	2624	0.9.xx	Only for SU3 files, not for netdb structures

Hybrid signing public keys are the Ed25519 key followed by the PQ key. Byte order defined in [FIPS204].

SigningPrivateKey

The new Signing Private Key types are:

Type	Length (bytes)	Since	Usage
MLDSA44_EdDSA_SHA512_Ed25519	2592	0.9.xx	See proposal 169
MLDSA65_EdDSA_SHA512_Ed25519	4064	0.9.xx	See proposal 169
MLDSA87_EdDSA_SHA512_Ed25519	4928	0.9.xx	See proposal 169
MLDSA44	2560	0.9.xx	See proposal 169
MLDSA65	4032	0.9.xx	See proposal 169
MLDSA87	4896	0.9.xx	See proposal 169
MLDSA44_Ed25519ph	2592	0.9.xx	Only for SU3 files, not for netdb structuresSee proposal 169
MLDSA65_Ed25519ph	4064	0.9.xx	Only for SU3 files, not for netdb structuresSee proposal 169
MLDSA87_Ed25519ph	4928	0.9.xx	Only for SU3 files, not for netdb structuresSee proposal 169

Hybrid signing private keys are the Ed25519 key followed by the PQ key. Byte order defined in [FIPS204].

Signature

The new Signature types are:

Type	Length (bytes)	Since	Usage
MLDSA44_EdDSA_SHA512_Ed25519	2484	0.9.xx	See proposal 169
MLDSA65_EdDSA_SHA512_Ed25519	3373	0.9.xx	See proposal 169
MLDSA87_EdDSA_SHA512_Ed25519	4691	0.9.xx	See proposal 169
MLDSA44	2420	0.9.xx	See proposal 169
MLDSA65	3309	0.9.xx	See proposal 169
MLDSA87	4627	0.9.xx	See proposal 169
MLDSA44_Ed25519ph	2484	0.9.xx	Only for SU3 files, not for netdb structuresSee proposal 169
MLDSA65_Ed25519ph	3373	0.9.xx	Only for SU3 files, not for netdb structuresSee proposal 169
MLDSA87_Ed25519ph	4691	0.9.xx	Only for SU3 files, not for netdb structuresSee proposal 169

Hybrid signatures are the Ed25519 signature followed by the PQ signature. Hybrid signatures are verified by verifying both signatures, and failing if either one fails. Byte order defined in [FIPS204].

Key Certificates

The new Signing Public Key types are:

Type	Type Code	Total Public Key Length	Since	Usage
MLDSA44_EdDSA_SHA512_Ed25519	12	1344	0.9.xx	See proposal 169
MLDSA65_EdDSA_SHA512_Ed25519	13	1984	0.9.xx	See proposal 169
MLDSA87_EdDSA_SHA512_Ed25519	14	2624	0.9.xx	See proposal 169
MLDSA44	15	1312	0.9.xx	See proposal 169
MLDSA65	16	1952	0.9.xx	See proposal 169
MLDSA87	17	2592	0.9.xx	See proposal 169
MLDSA44_Ed25519ph	18	n/a	0.9.xx	Only for SU3 files
MLDSA65_Ed25519ph	19	n/a	0.9.xx	Only for SU3 files
MLDSA87_Ed25519ph	20	n/a	0.9.xx	Only for SU3 files

The new Crypto Public Key types are:

Type	Type Code	Total Public Key Length	Since	Usage
MLKEM512_X25519	5	32	0.9.xx	See proposal 169, for Leasesets only, not for RIs or Destinations
MLKEM768_X25519	6	32	0.9.xx	See proposal 169, for Leasesets only, not for RIs or Destinations
MLKEM1024_X25519	7	32	0.9.xx	See proposal 169, for Leasesets only, not for RIs or Destinations
NULL	255	0	0.9.xx	See proposal 169

Hybrid key types are NEVER included in key certificates; only in leasesets.

For destinations with Hybrid or PQ signature types, use NULL (type 255) for the encryption type, but there is no crypto key, and the entire 384-byte main section is for the signing key.

Destination sizes

Here are lengths for the new Destination types. Enc type for all is NULL (type 255) and the encryption key length is treated as 0. The entire 384-byte section is used for the first part of the signing public key. NOTE: This is different than the spec for the ECDSA_SHA512_P521 and the RSA signature types, where we maintained the 256-byte ElGamal key in the destination even though it was unused.

No padding. Total length is 7 + total key length. Key certificate length is 4 + excess key length.

Example 1319-byte destination byte stream for MLDSA44:

skey[0:383] 5 (932 >> 8) (932 & 0xff) 00 12 00 255 skey[384:1311]

Type	Type Code	Total Public Key Length	Main	Excess	Total Dest Length
MLDSA44_EdDSA_SHA512_Ed25519	12	1344	384	960	1351
MLDSA65_EdDSA_SHA512_Ed25519	13	1984	384	1600	1991
MLDSA87_EdDSA_SHA512_Ed25519	14	2624	384	2240	2631
MLDSA44	15	1312	384	928	1319
MLDSA65	16	1952	384	1568	1959
MLDSA87	17	2592	384	2208	2599

RouterIdent sizes

Here are lengths for the new Destination types. Enc type for all is X25519 (type 4). The entire 352-byte section after the X28819 public key is used for the first part of the signing public key. No padding. Total length is 39 + total key length. Key certificate length is 4 + excess key length.

Example 1351-byte router identity byte stream for MLDSA44:

enckey[0:31] skey[0:351] 5 (960 >> 8) (960 & 0xff) 00 12 00 4 skey[352:1311]

Type	Type Code	Total Public Key Length	Main	Excess	Total RouterIdent Length
MLDSA44_EdDSA_SHA512_Ed25519	12	1344	352	992	1383
MLDSA65_EdDSA_SHA512_Ed25519	13	1984	352	1632	2023
MLDSA87_EdDSA_SHA512_Ed25519	14	2624	352	2272	2663
MLDSA44	15	1312	352	960	1351
MLDSA65	16	1952	352	1600	1991
MLDSA87	17	2592	352	2240	2631

Handshake Patterns

Handshakes use [Noise] handshake patterns.

The following letter mapping is used: