Cryptographic Primitives

No new cryptographic primitives are introduced. The primitives required to implement this proposal are:

• AES-256-CBC as in [Cryptography]
• 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]

Goals

• Increase speed of crypto operations
• Replace ElGamal + AES256/CBC with ECIES primitives for tunnel BuildRequestRecords and BuildReplyRecords.
• No change to size of encrypted BuildRequestRecords and BuildReplyRecords (528 bytes) for compatibility
• No new I2NP messages
• Maintain encrypted build record size for compatibility
• Add forward secrecy for Tunnel Build Messages.
• Add authenticated encryption
• Detect hops reordering BuildRequestRecords
• Increase resolution of timestamp so that Bloom filter size may be reduced
• Add field for tunnel expiration so that varying tunnel lifetimes will be possible (all-ECIES tunnels only)
• Add extensible options field for future features
• Reuse existing cryptographic primitives
• Improve tunnel build message security where possible while maintaining compatibility
• Support tunnels with mixed ElGamal/ECIES peers
• Improve defenses against "tagging" attacks on build messages
• Hops do not need to know the encryption type of the next hop before processing the build message, as they may not have the next hop's RI at that time
• Maximize compatibility with current network
• No change to tunnel build AES request/reply encryption for ElGamal routers
• No change to tunnel AES "layer" encryption, for that see [Prop153]
• Continue to support both 8-record TBM/TBRM and variable-size VTBM/VTBRM
• Do not require "flag day" upgrade to entire network

Non-Goals

• Complete redesign of tunnel build messages requiring a "flag day".
• Shrinking tunnel build messages (requires all-ECIES hops and a new proposal)
• Use of tunnel build options as defined in [Prop143], only required for small messages
• Bidirectional tunnels - for that see [Prop119]
• Smaller tunnel build messages - for that see [Prop157]

Design Goals

• No hops are able to determine the originator of the tunnel.
• Middle hops must not be able to determine the direction of the tunnel or their position in the tunnel.
• No hops can read any contents of other request or reply records, except for truncated router hash and ephemeral key for next hop
• No member of reply tunnel for outbound build can read any reply records.
• No member of outbound tunnel for inbound build can read any request records, except that OBEP can see truncated router hash and ephemeral key for IBGW

Tagging Attacks

A major goal of the tunnel building design is to make it harder for colluding routers X and Y to know that they are in a single tunnel. If router X is at hop m and router Y is at hop m+1, they obviously will know. But if router X is at hop m and router Y is at hop m+n for n>1, this should be much harder.

Tagging attacks are where middle-hop router X alters the tunnel build message in such a way that router Y can detect the alteration when the build message gets there. The goal is for any altered message is dropped by a router between X and Y before it gets to router Y. For modifications that are not dropped before router Y, the tunnel creator should detect the corruption in the reply and discard the tunnel.

Possible attacks:

• Alter a build record
• Replace a build record
• Add or remove a build record
• Reorder the build records

TODO: Does the current design prevent all these attacks?

Noise Protocol Framework

This proposal 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.

This proposal 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 new design will use 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.

(Payload Security Properties)

N:                      Authentication   Confidentiality
  -> e, es                  0                2

  Authentication: None (0).
  This payload may have been sent by any party, including an active attacker.

  Confidentiality: 2.
  Encryption to a known recipient, forward secrecy for sender compromise
  only, vulnerable to replay.  This payload is encrypted based only on DHs
  involving the recipient's static key pair.  If the recipient's static
  private key is compromised, even at a later date, this payload can be
  decrypted.  This message can also be replayed, since there's no ephemeral
  contribution from the recipient.

  "e": Alice generates a new ephemeral key pair and stores it in the e
       variable, writes the ephemeral public key as cleartext into the
       message buffer, and hashes the public key along with the old h to
       derive a new h.

  "es": A DH is performed between the Alice's ephemeral key pair and the
        Bob's static key pair.  The result is hashed along with the old ck to
        derive a new ck and k, and n is set to zero.

Reply encryption

Build reply records are created by the hops creator and symmetrically encrypted to the creator. This symmetric encryption of reply records is currently AES with a prepended SHA-256 checksum. and contains a SHA-256 checksum. This design is not forward-secret.

The new design will use ChaCha20/Poly1305 AEAD for integrity, and authentication.

Justification

The ephemeral public key in the request does not need to be obfuscated with AES or Elligator2. The previous hop is the only one that can see it, and that hop knows that the next hop is ECIES.

Reply records do not need full asymmetric encryption with another DH.

Build Request Records

Encrypted BuildRequestRecords are 528 bytes for both ElGamal and ECIES, for compatibility.

bytes     0-3: tunnel ID to receive messages as, nonzero
bytes    4-35: local router identity hash
bytes   36-39: next tunnel ID, nonzero
bytes   40-71: next router identity hash
bytes  72-103: AES-256 tunnel layer key
bytes 104-135: AES-256 tunnel IV key
bytes 136-167: AES-256 reply key
bytes 168-183: AES-256 reply IV
byte      184: flags
bytes 185-188: request time (in hours since the epoch, rounded down)
bytes 189-192: next message ID
bytes 193-221: uninterpreted / random padding

bytes    0-15: Hop's truncated identity hash
bytes  16-528: ElGamal encrypted BuildRequestRecord

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

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

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.

bytes   0-31: SHA-256 Hash of bytes 32-527
bytes 32-526: random data
byte     527: reply

total length: 528

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

bytes   0-511: ChaCha20 encrypted BuildReplyRecord
bytes 512-527: Poly1305 MAC

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 (ECIES)

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.

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.

// 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)

Request Record Encryption (ElGamal)

As defined in [Tunnel-Creation]. There are no changes to encryption for ElGamal hops.

Reply Record Encryption (ECIES)

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)

Reply Record Encryption (ElGamal)

As defined in [Tunnel-Creation]. There are no changes to encryption for ElGamal hops.

Security Analysis

ElGamal does not provide forward secrecy for Tunnel Build Messages.

AES256/CBC is in slightly better standing, only being vulnerable to a theoretical weakening from a known plaintext biclique attack.

The only known practical attack against AES256/CBC is a padding oracle attack, when the IV is known to the attacker.

An attacker would need to break the next hop's ElGamal encryption to gain the AES256/CBC key info (reply key and IV).

ElGamal is significantly more CPU-intensive than ECIES, leading to potential resource exhaustion.

ECIES, used with new ephemeral keys per-BuildRequestRecord or VariableTunnelBuildMessage, provides forward-secrecy.

ChaCha20Poly1305 provides AEAD encryption, allowing the recipient to verify message integrity before attempting decryption.