Summary

Router Identities currently contain an ElGamal encryption key. This has been the standard since the beginnings of I2P. ElGamal is slow and needs to be replaced in all places it is used.

The proposals for LS2 [Prop123] and ECIES-X25519-AEAD-Ratchet [Prop144] (now specified in [ECIES]) defined the replacement of ElGamal with ECIES for Destinations.

This proposal defines the replacement of ElGamal with ECIES-X25519 for routers. This proposal provides an overview of the changes required. Most of the details are in other proposals and specifications. See the reference section for links.

Goals

See [Prop152] for additional goals.

• Replace ElGamal with ECIES-X25519 in Router Identities
• Reuse existing cryptographic primitives
• Improve tunnel build message security where possible while maintaining compatibility
• Support tunnels with mixed ElGamal/ECIES peers
• Maximize compatibility with current network
• Do not require "flag day" upgrade to entire network
• Gradual rollout to minimize risk
• New, smaller tunnel build message

Non-Goals

See [Prop152] for additional non-goals.

• No requirement for dual-key routers
• Layer encryption changes, for that see [Prop153]

Key Location and Crypto Type

For Destinations, the key is in the leaseset, not in the Destination, and we support multiple encryption types in the same leaseset.

None of that is required for routers. The router's encryption key is in its Router Identity. See the common structures spec [Common].

For routers, we will replace the 256 byte ElGamal key in the Router Identity with a 32 byte X25519 key and 224 bytes of padding. This will be indicated by the crypto type in the key certificate. The crypto type (same as used in the LS2) is 4. This indicates a little-endian 32-byte X25519 public key. This is the standard construction as defined in the common structures spec [Common].

This is identical to the method proposed for ECIES-P256 for crypto types 1-3 in proposal 145 [Prop145]. While this proposal was never adopted, the Java implementation developers prepared for crypto types in Router Identity key certificates by adding checks in several places in the code base. Most of this work was done in mid-2019.

Tunnel Build Message

Several changes to the tunnel creation specification [Tunnel-Creation] are required to use ECIES instead of ElGamal. In addition, we will make improvements to the tunnel build messages to increase security.

In phase 1, we will change the format and encryption of the Build Request Record and Build Response Record for ECIES hops. These changes will be compatible with existing ElGamal routers. These changes are defined in proposal 152 [Prop152].

In phase 2, we will add a new version of the Build Request Message, Build Reply Message, Build Request Record and Build Response Record. The size will be reduced for efficiency. These changes must be supported by all hops in a tunnel, and all hops must be ECIES. These changes are defined in proposal 157 [Prop157].

End-to-End Encryption

Request Encryption

The request encryption is the same as that specified in [Tunnel-Creation-ECIES] and [Prop152], using the Noise "N" pattern.

Replies to lookups will be encrypted with a ratchet tag if requested in the lookup. Database Lookup request messages contain the 32-byte reply key and 8-byte reply tag as specified in [I2NP] and [Prop154]. The key and tag are used to encrypt the reply.

Tag sets are not created. The zero static key scheme specified in ECIES-X25519-AEAD-Ratchet [Prop144] and [ECIES] will not be used. Ephemeral keys will not be Elligator2-encoded.

Generally, these will be New Session messages and will be sent with a zero static key (no binding or session), as the sender of the message is anonymous.

This is the "e" message pattern:

// Define protocol_name.
Set protocol_name = "Noise_N_25519_ChaChaPoly_SHA256"
(31 bytes, US-ASCII encoded, no NULL termination).

// Define Hash h = 32 bytes
// Pad to 32 bytes. Do NOT hash it, because it is not more than 32 bytes.
h = protocol_name || 0

Define ck = 32 byte chaining key. Copy the h data to ck.
Set chainKey = h

// MixHash(null prologue)
h = SHA256(h);

// up until here, can all be precalculated by all routers.

// Target router's X25519 static keypair (hesk, hepk) from the Router Identity
hesk = GENERATE_PRIVATE()
hepk = DERIVE_PUBLIC(hesk)

// MixHash(hepk)
// || below means append
h = SHA256(h || hepk);

// up until here, can all be precalculated by each router
// for all incoming messages

// Sender generates an X25519 ephemeral keypair
sesk = GENERATE_PRIVATE()
sepk = DERIVE_PUBLIC(sesk)

// MixHash(sepk)
h = SHA256(h || sepk);

End of "e" message pattern.

This is the "es" message pattern:

// Noise es
// Sender performs an X25519 DH with receiver's static public key.
// The target router
// extracts the sender's ephemeral key preceding the encrypted record.
sharedSecret = DH(sesk, hepk) = DH(hesk, sepk)

// MixKey(DH())
//[chainKey, k] = MixKey(sharedSecret)
// ChaChaPoly parameters to encrypt/decrypt
keydata = HKDF(chainKey, sharedSecret, "", 64)
// Chain key is not used
//chainKey = keydata[0:31]

// AEAD parameters
k = keydata[32:64]
n = 0
plaintext = 464 byte build request record
ad = h
ciphertext = ENCRYPT(k, n, plaintext, ad)

End of "es" message pattern.

// MixHash(ciphertext) is not required
//h = SHA256(h || ciphertext)

Reply Encryption

Replies to Database Lookup messages are Database Store or Database Search Reply messages. They are encrypted as Existing Session messages with the 32-byte reply key and 8-byte reply tag as specified in [I2NP] and [Prop154].

There are no explicit replies to Database Store messages. The sender may bundle its own reply as a Garlic Message to itself, containing a Delivery Status message.

Basic Point-to-Point

ECIES routers can connect to and receive connections from ElGamal routers. This should be possible now, as several checks were added to the Java code base by mid-2019 in reaction to unfinished proposal 145 [Prop145]. Ensure there's nothing in the code bases that prevents point-to-point connections to non-ElGamal routers.

Code correctness checks:

• Ensure that ElGamal routers do not request AEAD-encrypted replies to DatabaseLookup messages (when the reply comes back through an exploratory tunnel to the router)
• Ensure that ECIES routers do not request AES-encrypted replies to DatabaseLookup messages (when the reply comes back through an exploratory tunnel to the router)

Until later phases, when specifications and implementations are complete:

• Ensure that tunnel builds are not attempted by ElGamal routers through ECIES routers.
• Ensure that encrypted ElGamal messages are not sent by ElGamal routers to ECIES floodfill routers. (DatabaseLookups and DatabaseStores)
• Ensure that encrypted ECIES messages are not sent by ECIES routers to ElGamal floodfill routers. (DatabaseLookups and DatabaseStores)
• Ensure that ECIES routers do not automatically become floodfill.

No changes should be required. Target release, if changes required: 0.9.48

NetDB Compatibility

Ensure that ECIES router infos may be stored to and retrieved from ElGamal floodfills. This should be possible now, as several checks were added to the Java code base by mid-2019 in reaction to unfinished proposal 145 [Prop145]. Ensure there's nothing in the code bases that prevents storage of non-ElGamal RouterInfos in the network database.

No changes should be required. Target release, if changes required: 0.9.48

Tunnel Building

Implement tunnel building as defined in proposal 152 [Prop152]. Start with having an ECIES router build tunnels with all ElGamal hops; use its own build request record for an inbound tunnel to test and debug.

Then test and support ECIES routers building tunnels with a mix of ElGamal and ECIES hops.

Then enable tunnel building through ECIES routers. No minimum version check should be necessary unless incompatible changes to proposal 152 are made after a release.

Target release: 0.9.48, late 2020

Ratchet messages to ECIES floodfills

Implement and test reception of ECIES messages (with zero static key) by ECIES floodfills, as defined in proposal 144 [Prop144]. Implement ant test reception of AEAD replies to DatabaseLookup messages by ECIES routers.

Enable auto-floodfill by ECIES routers. Then enable sending ECIES messages to ECIES routers. No minimum version check should be necessary unless incompatible changes to proposal 152 are made after a release.

Target release: 0.9.49, early 2021. ECIES routers may automatically become floodfill.

Rekeying and New Installs

New installs will default to ECIES as of release 0.9.49.

Gradually rekey all routers to minimize risk and disruption to the network. Use existing code that did the rekeying for sig type migration years ago. This code gives each router a small random chance of rekeying at each restart. After several restarts, a router will probably have rekeyed to ECIES.

The criterion for starting rekeying is that a sufficient portion of the network, perhaps 50%, can build tunnels through ECIES routers (0.9.48 or higher).

Before aggressively rekeying the entire network, the vast majority (perhaps 90% or more) must be able to build tunnels through ECIES routers (0.9.48 or higher) AND send messages to ECIES floodfills (0.9.49 or higher). This target will probably be reached for the 0.9.52 release.

Rekeying will take several releases.

Target release: 0.9.49 for new routers to default to ECIES; 0.9.49 to slowly start rekeying; 0.9.50 - 0.9.52 to repeatedly increase the rekeying rate; late 2021 for the majority of the network to be rekeyed.

New Tunnel Build Message (Phase 2)

Implement and test the new Tunnel Build Message as defined in proposal 157 [Prop157]. Roll the support out in release 0.9.51. Do additional testing, then enable in release 0.9.52.

Testing will be difficult. Before this can be widely tested, a good subset of the network must support it. Before it is broadly useful, a majority of the network must support it. If specification or implementation changes are required after testing, that would delay the rollout for an additional release.

Target release: 0.9.52, late 2021.

Rekeying Complete

At this point, routers older than some version TBD will not be able to build tunnels through most peers.

Target release: 0.9.53, early 2022.