============================= ECIES-X25519 Tunnel Creation ============================= Category: Protocols Last updated: 2021-07 Accurate for: 0.9.51 Overview ======== This document specifies Tunnel Build message encryption using crypto primitives introduced by [ECIES-X25519]. It is a portion of the overall proposal [Prop156] for converting routers from ElGamal to ECIES-X25519 keys. There are two versions specified. The first uses the existing build messages and build record size, for compatibility with ElGamal routers. This specification is implemented as of release 0.9.48. The second uses two new build messages and a smaller build record size, and may only be used with ECIES routers. This specification is implemented as of release 0.9.51. For the purposes of transitioning the network from ElGamal + AES256 to ECIES + ChaCha20, tunnels with mixed ElGamal and ECIES routers are necessary. Specifications for handling mixed tunnel hops are provided. No changes will be made to the format, processing, or encryption of ElGamal hops. This format maintains the same size for tunnel build records, as required for compatibility. ElGamal tunnel creators will generate ephemeral X25519 keypairs per-hop, and follow this spec for creating tunnels containing ECIES hops. This document specifies ECIES-X25519 Tunnel Building. For an overview of all changes required for ECIES routers, see proposal 156 [Prop156]. For additional background on the development of the long record specification, see proposal 152 [Prop152]. For additional background on the development of the short record specification, see proposal 157 [Prop157]. Cryptographic Primitives ------------------------ The primitives required to implement this specification are: - AES-256-CBC as in [Cryptography] - STREAM ChaCha20 functions: ENCRYPT(k, iv, plaintext) and DECRYPT(k, iv, ciphertext) - as in [EncryptedLeaseSet] and [RFC-7539] - STREAM ChaCha20/Poly1305 functions: ENCRYPT(k, n, plaintext, ad) and DECRYPT(k, n, ciphertext, ad) - as in [NTCP2] [ECIES-X25519] and [RFC-7539] - X25519 DH functions - as in [NTCP2] and [ECIES-X25519] - HKDF(salt, ikm, info, n) - as in [NTCP2] and [ECIES-X25519] Other Noise functions defined elsewhere: - MixHash(d) - as in [NTCP2] and [ECIES-X25519] - MixKey(d) - as in [NTCP2] and [ECIES-X25519] Design ====== Noise Protocol Framework ------------------------ This specification provides the requirements based on the Noise Protocol Framework [NOISE] (Revision 34, 2018-07-11). In Noise parlance, Alice is the initiator, and Bob is the responder. It is based on the Noise protocol Noise_N_25519_ChaChaPoly_SHA256. This Noise protocol uses the following primitives: - One-Way Handshake Pattern: N Alice does not transmit her static key to Bob (N) - DH Function: X25519 X25519 DH with a key length of 32 bytes as specified in [RFC-7748]. - Cipher Function: ChaChaPoly AEAD_CHACHA20_POLY1305 as specified in [RFC-7539] section 2.8. 12 byte nonce, with the first 4 bytes set to zero. Identical to that in [NTCP2]. - Hash Function: SHA256 Standard 32-byte hash, already used extensively in I2P. Handshake Patterns ------------------ Handshakes use [Noise] handshake patterns. The following letter mapping is used: - e = one-time ephemeral key - s = static key - p = message payload The build request is identical to the Noise N pattern. This is also identical to the first (Session Request) message in the XK pattern used in [NTCP2]. <- s ... e es p -> Request encryption ----------------------- Build request records are created by the tunnel creator and asymmetrically encrypted to the individual hop. This asymmetric encryption of request records is currently ElGamal as defined in [Cryptography] and contains a SHA-256 checksum. This design is not forward-secret. The ECIES design uses the one-way Noise pattern "N" with ECIES-X25519 ephemeral-static DH, with an HKDF, and ChaCha20/Poly1305 AEAD for forward secrecy, integrity, and authentication. Alice is the tunnel build requestor. Each hop in the tunnel is a Bob. Reply encryption ----------------------- Build reply records are created by the hops creator and symmetrically encrypted to the creator. This symmetric encryption of ElGamal reply records is AES with a prepended SHA-256 checksum. and contains a SHA-256 checksum. This design is not forward-secret. ECIES replies use ChaCha20/Poly1305 AEAD for integrity, and authentication. Long Record Specification ========================= Build Request Records ------------------------------------- Encrypted BuildRequestRecords are 528 bytes for both ElGamal and ECIES, for compatibility. Request Record Unencrypted ``````````````````````````````````````` This is the specification of the tunnel BuildRequestRecord for ECIES-X25519 routers. Summary of changes: - Remove unused 32-byte router hash - Change request time from hours to minutes - Add expiration field for future variable tunnel time - Add more space for flags - Add Mapping for additional build options - AES-256 reply key and IV are not used for the hop's own reply record - Unencrypted record is longer because there is less encryption overhead The request record does not contain any ChaCha reply keys. Those keys are derived from a KDF. See below. All fields are big-endian. Unencrypted size: 464 bytes bytes 0-3: tunnel ID to receive messages as, nonzero bytes 4-7: next tunnel ID, nonzero bytes 8-39: next router identity hash bytes 40-71: AES-256 tunnel layer key bytes 72-103: AES-256 tunnel IV key bytes 104-135: AES-256 reply key bytes 136-151: AES-256 reply IV byte 152: flags bytes 153-155: more flags, unused, set to 0 for compatibility bytes 156-159: request time (in minutes since the epoch, rounded down) bytes 160-163: request expiration (in seconds since creation) bytes 164-167: next message ID bytes 168-x: tunnel build options (Mapping) bytes x-x: other data as implied by flags or options bytes x-463: random padding The flags field is the same as defined in [Tunnel-Creation] and contains the following:: Bit order: 76543210 (bit 7 is MSB) bit 7: if set, allow messages from anyone bit 6: if set, allow messages to anyone, and send the reply to the specified next hop in a Tunnel Build Reply Message bits 5-0: Undefined, must set to 0 for compatibility with future options Bit 7 indicates that the hop will be an inbound gateway (IBGW). Bit 6 indicates that the hop will be an outbound endpoint (OBEP). If neither bit is set, the hop will be an intermediate participant. Both cannot be set at once. The request exipration is for future variable tunnel duration. For now, the only supported value is 600 (10 minutes). The tunnel build options is a Mapping structure as defined in [Common]. This is for future use. No options are currently defined. If the Mapping structure is empty, this is two bytes 0x00 0x00. The maximum size of the Mapping (including the length field) is 296 bytes, and the maximum value of the Mapping length field is 294. Request Record Encrypted ````````````````````````````````````` All fields are big-endian except for the ephemeral public key which is little-endian. Encrypted size: 528 bytes bytes 0-15: Hop's truncated identity hash bytes 16-47: Sender's ephemeral X25519 public key bytes 48-511: ChaCha20 encrypted BuildRequestRecord bytes 512-527: Poly1305 MAC Build Reply Records ------------------------------------- Encrypted BuildReplyRecords are 528 bytes for both ElGamal and ECIES, for compatibility. Reply Record Unencrypted ````````````````````````````````````` This is the specification of the tunnel BuildReplyRecord for ECIES-X25519 routers. Summary of changes: - Add Mapping for build reply options - Unencrypted record is longer because there is less encryption overhead ECIES replies are encrypted with ChaCha20/Poly1305. All fields are big-endian. Unencrypted size: 512 bytes bytes 0-x: Tunnel Build Reply Options (Mapping) bytes x-x: other data as implied by options bytes x-510: Random padding byte 511: Reply byte The tunnel build reply options is a Mapping structure as defined in [Common]. This is for future use. No options are currently defined. If the Mapping structure is empty, this is two bytes 0x00 0x00. The maximum size of the Mapping (including the length field) is 511 bytes, and the maximum value of the Mapping length field is 509. The reply byte is one of the following values as defined in [Tunnel-Creation] to avoid fingerprinting: - 0x00 (accept) - 30 (TUNNEL_REJECT_BANDWIDTH) Reply Record Encrypted ``````````````````````````````````` Encrypted size: 528 bytes bytes 0-511: ChaCha20 encrypted BuildReplyRecord bytes 512-527: Poly1305 MAC After full transition to ECIES records, ranged padding rules are the same as for request records. Symmetric Encryption of Records -------------------------------------------------------- Mixed tunnels are allowed, and necessary, for the transition from ElGamal to ECIES. During the transitionary period, an increasing number of routers will be keyed under ECIES keys. Symmetric cryptography preprocessing will run in the same way: - "encryption": - cipher run in decryption mode - request records preemptively decrypted in preprocessing (concealing encrypted request records) - "decryption": - cipher run in encryption mode - request records encrypted (revealing next plaintext request record) by participant hops - ChaCha20 does not have "modes", so it is simply run three times: - once in preprocessing - once by the hop - once on final reply processing When mixed tunnels are used, tunnel creators will need to base the symmetric encryption of BuildRequestRecord on the current and previous hop's encryption type. Each hop will use its own encryption type for encrypting BuildReplyRecords, and the other records in the VariableTunnelBuildMessage (VTBM). On the reply path, the endpoint (sender) will need to undo the [Multiple-Encryption], using each hop's reply key. As a clarifying example, let's look at an outbound tunnel w/ ECIES surrounded by ElGamal: - Sender (OBGW) -> ElGamal (H1) -> ECIES (H2) -> ElGamal (H3) All BuildRequestRecords are in their encrypted state (using ElGamal or ECIES). AES256/CBC cipher, when used, is still used for each record, without chaining across multiple records. Likewise, ChaCha20 will be used to encrypt each record, not streaming across the entire VTBM. The request records are preprocessed by the Sender (OBGW): - H3's record is "encrypted" using: - H2's reply key (ChaCha20) - H1's reply key (AES256/CBC) - H2's record is "encrypted" using: - H1's reply key (AES256/CBC) - H1's record goes out without symmetric encryption Only H2 checks the reply encryption flag, and sees its followed by AES256/CBC. After being processed by each hop, the records are in a "decrypted" state: - H3's record is "decrypted" using: - H3's reply key (AES256/CBC) - H2's record is "decrypted" using: - H3's reply key (AES256/CBC) - H2's reply key (ChaCha20-Poly1305) - H1's record is "decrypted" using: - H3's reply key (AES256/CBC) - H2's reply key (ChaCha20) - H1's reply key (AES256/CBC) The tunnel creator, a.k.a. Inbound Endpoint (IBEP), postprocesses the reply: - H3's record is "encrypted" using: - H3's reply key (AES256/CBC) - H2's record is "encrypted" using: - H3's reply key (AES256/CBC) - H2's reply key (ChaCha20-Poly1305) - H1's record is "encrypted" using: - H3's reply key (AES256/CBC) - H2's reply key (ChaCha20) - H1's reply key (AES256/CBC) Request Record Keys ----------------------------------------------------------------------- These keys are explicitly included in ElGamal BuildRequestRecords. For ECIES BuildRequestRecords, the tunnel keys and AES reply keys are included, but the ChaCha reply keys are derived from the DH exchange. See [Prop156] for details of the router static ECIES keys. Below is a description of how to derive the keys previously transmitted in request records. KDF for Initial ck and h ```````````````````````` This is standard [NOISE] for pattern "N" with a standard protocol name. 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. KDF for Request Record ```````````````````````` ElGamal tunnel creators generate an ephemeral X25519 keypair for each ECIES hop in the tunnel, and use scheme above for encrypting their BuildRequestRecord. ElGamal tunnel creators will use the scheme prior to this spec for encrypting to ElGamal hops. ECIES tunnel creators will need to encrypt to each of the ElGamal hop's public key using the scheme defined in [Tunnel-Creation]. ECIES tunnel creators will use the above scheme for encrypting to ECIES hops. This means that tunnel hops will only see encrypted records from their same encryption type. For ElGamal and ECIES tunnel creators, they will generate unique ephemeral X25519 keypairs per-hop for encrypting to ECIES hops. **IMPORTANT**: Ephemeral keys must be unique per ECIES hop, and per build record. Failing to use unique keys opens an attack vector for colluding hops to confirm they are in the same tunnel. // Each hop'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 build requests // Sender generates an X25519 ephemeral keypair per ECIES hop in the VTBM (sesk, sepk) 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 Hop's static public key. // Each Hop, finds the record w/ their truncated identity hash, // and 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) // Save for Reply Record KDF 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) // Save for Reply Record KDF h = SHA256(h || ciphertext) ``replyKey``, ``layerKey`` and ``layerIV`` must still be included inside ElGamal records, and can be generated randomly. Reply Record Encryption -------------------------------------- The reply record is ChaCha20/Poly1305 encrypted. // AEAD parameters k = chainkey from build request n = 0 plaintext = 512 byte build reply record ad = h from build request ciphertext = ENCRYPT(k, n, plaintext, ad) Short Record Specification =========================== This specification uses two new I2NP tunnel build messages, Short Tunnel Build Message (type 25) and Outbound Tunnel Build Reply Message (type 26). The tunnel creator and all hops in the created tunnel must ECIES-X25519, and at least version 0.9.51. The hops in the reply tunnel (for an outbound build) or the outbound tunnel (for an inbound build) do not have any requirements. Encrypted request and reply records will be 218 bytes, compared to 528 bytes for all other build messages. The plaintext request records will be 154 bytes, compared to 222 bytes for ElGamal records, and 464 bytes for ECIES records as defined above. The plaintext response records will be 202 bytes, compared to 496 bytes for ElGamal records, and 512 bytes for ECIES records as defined above. The reply encryption will be ChaCha20/Poly1305 for the hop's own record, and ChaCha20 (NOT ChaCha20/Poly1305) for the other records in the build message. Request records will be made smaller by using HKDF to create the layer and reply keys, so they are not explicitly included in the request. Message Flow ------------------ STBM: Short tunnel build message (type 25) OTBRM: Outbound tunnel build reply message (type 26) Outbound Build A-B-C Reply through existing inbound D-E-F New Tunnel STBM STBM STBM Creator ------> A ------> B ------> C ---\ OBEP \ | Garlic wrapped (optional) | OTBRM | (TUNNEL delivery) | from OBEP to | creator Existing Tunnel / Creator <-------F---------E-------- D <--/ IBGW Inbound Build D-E-F Sent through existing outbound A-B-C Existing Tunnel Creator ------> A ------> B ------> C ---\ OBEP \ | Garlic wrapped (optional) | STBM | (ROUTER delivery) | from creator New Tunnel | to IBGW STBM STBM STBM / Creator <------ F <------ E <------ D <--/ IBGW Notes ````` Garlic wrapping of the messages hides them from the OBEP (for an inbound build) or the IBGW (for an outbound build). This is recommended but not required. If the OBEP and IBGW are the same router, it is not necessary. Short Build Request Records ------------------------------------- Short encrypted BuildRequestRecords are 218 bytes. Short Request Record Unencrypted ``````````````````````````````````````` Summary of changes from long records: - Change unencrypted length from 464 to 154 bytes - Change encrypted length from 528 to 218 bytes - Remove layer and reply keys and IVs, they will be generated from a KDF The request record does not contain any ChaCha reply keys. Those keys are derived from a KDF. See below. All fields are big-endian. Unencrypted size: 154 bytes. bytes 0-3: tunnel ID to receive messages as, nonzero bytes 4-7: next tunnel ID, nonzero bytes 8-39: next router identity hash byte 40: flags bytes 41-42: more flags, unused, set to 0 for compatibility byte 43: layer encryption type bytes 44-47: request time (in minutes since the epoch, rounded down) bytes 48-51: request expiration (in seconds since creation) bytes 52-55: next message ID bytes 56-x: tunnel build options (Mapping) bytes x-x: other data as implied by flags or options bytes x-153: random padding (see below) The flags field is the same as defined in [Tunnel-Creation] and contains the following:: Bit order: 76543210 (bit 7 is MSB) bit 7: if set, allow messages from anyone bit 6: if set, allow messages to anyone, and send the reply to the specified next hop in a Tunnel Build Reply Message bits 5-0: Undefined, must set to 0 for compatibility with future options Bit 7 indicates that the hop will be an inbound gateway (IBGW). Bit 6 indicates that the hop will be an outbound endpoint (OBEP). If neither bit is set, the hop will be an intermediate participant. Both cannot be set at once. Layer encryption type: 0 for AES (as in current tunnels); 1 for future (ChaCha?) The request exipration is for future variable tunnel duration. For now, the only supported value is 600 (10 minutes). The creator ephemeral public key is an ECIES key, big-endian. It is used for the KDF for the IBGW layer and reply keys and IVs. This is only included in the plaintext record in an Inbound Tunnel Build message. It is required because there is no DH at this layer for the build record. The tunnel build options is a Mapping structure as defined in [Common]. This is for future use. No options are currently defined. If the Mapping structure is empty, this is two bytes 0x00 0x00. The maximum size of the Mapping (including the length field) is 98 bytes, and the maximum value of the Mapping length field is 96. Short Request Record Encrypted ````````````````````````````````````` All fields are big-endian except for the ephemeral public key which is little-endian. Encrypted size: 218 bytes bytes 0-15: Hop's truncated identity hash bytes 16-47: Sender's ephemeral X25519 public key bytes 48-201: ChaCha20 encrypted ShortBuildRequestRecord bytes 202-217: Poly1305 MAC Short Build Reply Records ------------------------------------- Short encrypted BuildReplyRecords are 218 bytes. Short Reply Record Unencrypted ````````````````````````````````````` Summary of changes from long records: - Change unencrypted length from 512 to 202 bytes - Change encrypted length from 528 to 218 bytes ECIES replies are encrypted with ChaCha20/Poly1305. All fields are big-endian. Unencrypted size: 202 bytes. bytes 0-x: Tunnel Build Reply Options (Mapping) bytes x-x: other data as implied by options bytes x-200: Random padding (see below) byte 201: Reply byte The tunnel build reply options is a Mapping structure as defined in [Common]. This is for future use. No options are currently defined. If the Mapping structure is empty, this is two bytes 0x00 0x00. The maximum size of the Mapping (including the length field) is 201 bytes, and the maximum value of the Mapping length field is 199. The reply byte is one of the following values as defined in [Tunnel-Creation] to avoid fingerprinting: - 0x00 (accept) - 30 (TUNNEL_REJECT_BANDWIDTH) An additional reply value may be defined in the future to represent rejection for unsupported options. Short Reply Record Encrypted ``````````````````````````````````` Encrypted size: 218 bytes bytes 0-201: ChaCha20 encrypted ShortBuildReplyRecord bytes 202-217: Poly1305 MAC KDF --- We use the chaining key (ck) from Noise state after tunnel build record encryption/decrytion to derive following keys: reply key, AES layer key, AES IV key and garlic reply key/tag for the OBEP. Reply keys: Note that the KDF is slightly different for the OBEP and non-OBEP hops. Unlike long records we can't use left part of ck for reply key, because it's not last and will be used later. The reply key is used to encypt reply that record using AEAD/Chaha20/Poly1305 and Chacha20 to reply other records. Both use the same key. The nonce is the record's position in the message starting from 0. See below for details. keydata = HKDF(ck, ZEROLEN, "SMTunnelReplyKey", 64) replyKey = keydata[32:63] ck = keydata[0:31] AES Layer key: keydata = HKDF(ck, ZEROLEN, "SMTunnelLayerKey", 64) layerKey = keydata[32:63] IV key for non-OBEP record: ivKey = keydata[0:31] because it's last IV key for OBEP record: ck = keydata[0:31] keydata = HKDF(ck, ZEROLEN, "TunnelLayerIVKey", 64) ivKey = keydata[32:63] ck = keydata[0:31] OBEP garlic reply key/tag: keydata = HKDF(ck, ZEROLEN, "RGarlicKeyAndTag", 64) garlicReplyKey = keydata[32:63] garlicReplyTag = keydata[0:7] Note: The KDF for the IV key at the OBEP is different from that for the other hops, even if the reply is not garlic encrypted. Record Encryption ``````````````````````` The hop's own reply record is encrypted with ChaCha20/Poly1305. This is the same as for the long record specification above, EXCEPT that 'n' is the record number 0-7, instead of always being 0. See [RFC-7539]. // AEAD parameters k = replyKey from KDF above n = record number 0-7 plaintext = 202 byte build reply record ad = h from build request ciphertext = ENCRYPT(k, n, plaintext, ad) The other records are iteratively and symmetrically encrypted at each hop with ChaCha20 (NOT ChaCha20/Poly1305). This is different from the long record specification above, which uses AES and does not use the record number. The record number is put in the IV at byte 4, because ChaCha20 uses a 12-byte IV with a little-endian nonce at bytes 4-11. See [RFC-7539]. // Parameters k = replyKey from KDF above n = record number 0-7 iv = 12 bytes, all zeros except iv[4] = n plaintext = 218 byte encrypted record ciphertext = ENCRYPT(k, iv, plaintext) Garlic Encryption ``````````````````````` Garlic wrapping of the messages hides them from the OBEP (for an inbound build) or the IBGW (for an outbound build). This is recommended but not required. If the OBEP and IBGW are the same router, it is not necessary. Garlic encryption of an inbound Short Tunnel Build Message, by the creator, encrypted to the ECIES IBGW, uses Noise 'N' encryption, as defined in [ECIES-ROUTERS]. Garlic encryption of an Outbound Tunnel Build Reply Message, by the OBEP, encrypted to the creator, uses They are encrypted as Existing Session messages with the 32-byte garlic reply key and 8-byte garlic reply tag from the KDF above. The format is as specified for replies to Database Lookups in [I2NP], [ECIES-ROUTERS], and [ECIES-X25519]. Layer Encryption `````````````````` This specification includes a layer encryption type field in the build request record. The only layer encryption currently supported is type 0, which is AES. This is unchanged from previous specifications, except that the layer key and IV key are derived from the KDF above rather than being included in the build request record. Adding new layer encryption types, for example ChaCha20, is a topic for additional research, and is not currently a part of this specification. Implementation Notes ===================== * Older routers do not check the encryption type of the hop and will send ElGamal-encrypted records. Some recent routers are buggy and will send various types of malformed records. Implementers should detect and reject these records prior to the DH operation if possible, to reduce CPU usage. References ========== [Common] http://www.i2p2.de./spec/common-structures [Cryptography] http://www.i2p2.de./spec/cryptography [ECIES-ROUTERS] http://www.i2p2.de./spec/ecies-routers [ECIES-X25519] http://www.i2p2.de./spec/ecies [EncryptedLeaseSet] /en/docs/spec/encryptedleaseset [I2NP] http://www.i2p2.de./spec/i2np [NOISE] https://noiseprotocol.org/noise.html [NTCP2] http://www.i2p2.de./spec/ntcp2 [Prop119] http://www.i2p2.de./spec/proposals/119-bidirectional-tunnels [Prop143] http://www.i2p2.de./spec/proposals/143-build-message-options [Prop152] http://www.i2p2.de./spec/proposals/152-ecies-tunnels [Prop153] http://www.i2p2.de./spec/proposals/153-chacha20-layer-encryption [Prop156] http://www.i2p2.de./spec/proposals/156-ecies-routers [Prop157] http://www.i2p2.de./spec/proposals/157-new-tbm [Tunnel-Creation] http://www.i2p2.de./spec/tunnel-creation [Multiple-Encryption] https://en.wikipedia.org/wiki/Multiple_encryption [RFC-7539] https://tools.ietf.org/html/rfc7539 [RFC-7748] https://tools.ietf.org/html/rfc7748