ECIES-X25519-AEAD-Ratchet Encryption Specification

Overview

Purpose

ECIES-X25519-AEAD-Ratchet is I2P’s modern end-to-end encryption protocol, replacing the legacy ElGamal/AES+SessionTags system. It provides forward secrecy, authenticated encryption, and significant improvements in performance and security.

Key Improvements Over ElGamal/AES+SessionTags

• Smaller Keys: 32-byte keys vs 256-byte ElGamal public keys (87.5% reduction)
• Forward Secrecy: Achieved through DH ratcheting (not available in legacy protocol)
• Modern Cryptography: X25519 DH, ChaCha20-Poly1305 AEAD, SHA-256
• Authenticated Encryption: Built-in authentication via AEAD construction
• Bidirectional Protocol: Paired inbound/outbound sessions vs unidirectional legacy
• Efficient Tags: 8-byte session tags vs 32-byte tags (75% reduction)
• Traffic Obfuscation: Elligator2 encoding makes handshakes indistinguishable from random

Deployment Status

• Initial Release: Version 0.9.46 (May 25, 2020)
• Network Deployment: Complete as of 2020
• Current Status: Mature, widely deployed (5+ years in production)
• Router Support: Version 0.9.46 or higher required
• Floodfill Requirements: Near 100% adoption for encrypted lookups

Implementation Status

Fully Implemented:

• New Session (NS) messages with binding
• New Session Reply (NSR) messages
• Existing Session (ES) messages
• DH ratchet mechanism
• Session tag and symmetric key ratchets
• DateTime, NextKey, ACK, ACK Request, Garlic Clove, and Padding blocks

Not Implemented (as of version 0.9.50):

• MessageNumbers block (type 6)
• Options block (type 5)
• Termination block (type 4)
• Protocol-layer automatic responses
• Zero static key mode
• Multicast sessions

Note: Implementation status for versions 1.5.0 through 2.10.0 (2021-2025) requires verification as some features may have been added.

Protocol Foundation

Noise Protocol Framework

ECIES-X25519-AEAD-Ratchet is based on the Noise Protocol Framework (Revision 34, 2018-07-11), specifically the IK (Interactive, Known remote static key) handshake pattern with I2P-specific extensions.

Noise Protocol Identifier

Noise_IKelg2+hs2_25519_ChaChaPoly_SHA256

Identifier Components:

• Noise - Base framework
• IK - Interactive handshake pattern with Known remote static key
• elg2 - Elligator2 encoding for ephemeral keys (I2P extension)
• +hs2 - MixHash called before second message to mix in tag (I2P extension)
• 25519 - X25519 Diffie-Hellman function
• ChaChaPoly - ChaCha20-Poly1305 AEAD cipher
• SHA256 - SHA-256 hash function

Noise Handshake Pattern

IK Pattern Notation:

<- s                    (Bob's static key known to Alice)
...
-> e, es, s, ss         (Alice sends ephemeral, DH es, static key, DH ss)
<- e, ee, se            (Bob sends ephemeral, DH ee, DH se)

Token Meanings:

• e - Ephemeral key transmission
• s - Static key transmission
• es - DH between Alice’s ephemeral and Bob’s static
• ss - DH between Alice’s static and Bob’s static
• ee - DH between Alice’s ephemeral and Bob’s ephemeral
• se - DH between Bob’s static and Alice’s ephemeral

Noise Security Properties

Using Noise terminology, the IK pattern provides:

Authentication Levels:

• Level 1: Payload is authenticated as belonging to the sender’s static key owner, but vulnerable to Key Compromise Impersonation (KCI)
• Level 2: Resistant to KCI attacks after NSR

Confidentiality Levels:

• Level 2: Forward secrecy if sender’s static key is later compromised
• Level 4: Forward secrecy if sender’s ephemeral key is later compromised
• Level 5: Full forward secrecy after both ephemeral keys are deleted

IK vs XK Differences

The IK pattern differs from the XK pattern used in NTCP2 and SSU2:

1. Four DH Operations: IK uses 4 DH operations (es, ss, ee, se) vs 3 for XK
2. Immediate Authentication: Alice is authenticated in the first message (Authentication Level 1)
3. Faster Forward Secrecy: Full forward secrecy (Level 5) achieved after second message (1-RTT)
4. Trade-off: First message payload is not forward-secret (vs XK where all payloads are forward-secret)

Summary: IK enables 1-RTT delivery of Bob’s response with full forward secrecy, at the cost of the initial request not being forward-secret.

Signal Double Ratchet Concepts

ECIES incorporates concepts from the Signal Double Ratchet Algorithm:

• DH Ratchet: Provides forward secrecy by periodically exchanging new DH keys
• Symmetric Key Ratchet: Derives new session keys for each message
• Session Tag Ratchet: Generates one-time-use session tags deterministically

Key Differences from Signal:

• Less Frequent Ratcheting: I2P ratchets only when needed (near tag exhaustion or by policy)
• Session Tags Instead of Header Encryption: Uses deterministic tags rather than encrypted headers
• Explicit ACKs: Uses in-band ACK blocks rather than relying solely on reverse traffic
• Separate Tag and Key Ratchets: More efficient for receiver (can defer key calculation)

I2P Extensions to Noise

1. Elligator2 Encoding: Ephemeral keys encoded to be indistinguishable from random
2. Tag Prepended to NSR: Session tag added before NSR message for correlation
3. Defined Payload Format: Block-based payload structure for all message types
4. I2NP Encapsulation: All messages wrapped in I2NP Garlic Message headers
5. Separate Data Phase: Transport messages (ES) diverge from standard Noise data phase

Cryptographic Primitives

X25519 Diffie-Hellman

Specification: RFC 7748

Key Properties:

• Private Key Size: 32 bytes
• Public Key Size: 32 bytes
• Shared Secret Size: 32 bytes
• Endianness: Little-endian
• Curve: Curve25519

Operations:

X25519 GENERATE_PRIVATE()

Generates a random 32-byte private key:

privkey = CSRNG(32)

X25519 DERIVE_PUBLIC(privkey)

Derives the corresponding public key:

pubkey = curve25519_scalarmult_base(privkey)

Returns 32-byte little-endian public key.

X25519 DH(privkey, pubkey)

Performs Diffie-Hellman key agreement:

sharedSecret = curve25519_scalarmult(privkey, pubkey)

Returns 32-byte shared secret.

Security Note: Implementers must validate that the shared secret is not all zeros (weak key). Reject and abort handshake if this occurs.

ChaCha20-Poly1305 AEAD

Specification: RFC 7539 section 2.8

Parameters:

• Key Size: 32 bytes (256 bits)
• Nonce Size: 12 bytes (96 bits)
• MAC Size: 16 bytes (128 bits)
• Block Size: 64 bytes (internal)

Nonce Format:

Byte 0-3:   0x00 0x00 0x00 0x00  (always zero)
Byte 4-11:  Little-endian counter (message number N)

AEAD Construction:

The AEAD combines ChaCha20 stream cipher with Poly1305 MAC:

1. Generate ChaCha20 keystream from key and nonce
2. Encrypt plaintext via XOR with keystream
3. Compute Poly1305 MAC over (associated data || ciphertext)
4. Append 16-byte MAC to ciphertext

ChaCha20-Poly1305 ENCRYPT(k, n, plaintext, ad)

Encrypts plaintext with authentication:

# Inputs
k = 32-byte cipher key
n = 12-byte nonce (first 4 bytes zero, last 8 bytes = message number)
plaintext = data to encrypt (0 to 65519 bytes)
ad = associated data (optional, used in MAC calculation)

# Output
ciphertext = chacha20_encrypt(k, n, plaintext)
mac = poly1305(ad || ciphertext, poly1305_key_gen(k, n))
return ciphertext || mac  # Total length = len(plaintext) + 16

Properties:

• Ciphertext is same length as plaintext (stream cipher)
• Output is plaintext_length + 16 bytes (includes MAC)
• Entire output is indistinguishable from random if key is secret
• MAC authenticates both associated data and ciphertext

ChaCha20-Poly1305 DECRYPT(k, n, ciphertext, ad)

Decrypts and verifies authentication:

# Split ciphertext and MAC
ct_without_mac = ciphertext[0:-16]
received_mac = ciphertext[-16:]

# Verify MAC
expected_mac = poly1305(ad || ct_without_mac, poly1305_key_gen(k, n))
if not constant_time_compare(received_mac, expected_mac):
    raise AuthenticationError("MAC verification failed")

# Decrypt
plaintext = chacha20_decrypt(k, n, ct_without_mac)
return plaintext

Critical Security Requirements:

• Nonces MUST be unique for each message with the same key
• Nonces MUST NOT be reused (catastrophic failure if reused)
• MAC verification MUST use constant-time comparison to prevent timing attacks
• Failed MAC verification MUST result in complete message rejection (no partial decryption)

SHA-256 Hash Function

Specification: NIST FIPS 180-4

Properties:

• Output Size: 32 bytes (256 bits)
• Block Size: 64 bytes (512 bits)
• Security Level: 128 bits (collision resistance)

Operations:

SHA-256 H(p, d)

SHA-256 hash with personalization string:

H(p, d) := SHA256(p || d)

Where || denotes concatenation, p is personalization string, d is data.

SHA-256 MixHash(d)

Updates running hash with new data:

h = SHA256(h || d)

Used throughout Noise handshake to maintain transcript hash.

HKDF Key Derivation

Specification: RFC 5869

Description: HMAC-based Key Derivation Function using SHA-256

Parameters:

• Hash Function: HMAC-SHA256
• Salt Length: Up to 32 bytes (SHA-256 output size)
• Output Length: Variable (up to 255 * 32 bytes)

HKDF Function:

def HKDF(salt, ikm, info, length):
    """
    Args:
        salt: Salt value (32 bytes max for SHA-256)
        ikm: Input key material (any length)
        info: Context-specific info string
        length: Desired output length in bytes
    
    Returns:
        output: Derived key material (length bytes)
    """
    # Extract phase
    prk = HMAC-SHA256(salt, ikm)
    
    # Expand phase
    n = ceil(length / 32)
    t = b''
    okm = b''
    for i in range(1, n + 1):
        t = HMAC-SHA256(prk, t || info || byte(i))
        okm = okm || t
    
    return okm[0:length]

Common Usage Patterns:

# Generate two keys (64 bytes total)
keydata = HKDF(chainKey, sharedSecret, "KDFDHRatchetStep", 64)
nextRootKey = keydata[0:31]
chainKey = keydata[32:63]

# Generate session tag (8 bytes)
tagdata = HKDF(chainKey, CONSTANT, "SessionTagKeyGen", 64)
nextChainKey = tagdata[0:31]
sessionTag = tagdata[32:39]

# Generate symmetric key (32 bytes)
keydata = HKDF(chainKey, ZEROLEN, "SymmetricRatchet", 64)
nextChainKey = keydata[0:31]
sessionKey = keydata[32:63]

Info Strings Used in ECIES:

• "KDFDHRatchetStep" - DH ratchet key derivation
• "TagAndKeyGenKeys" - Initialize tag and key chain keys
• "STInitialization" - Session tag ratchet initialization
• "SessionTagKeyGen" - Session tag generation
• "SymmetricRatchet" - Symmetric key generation
• "XDHRatchetTagSet" - DH ratchet tagset key
• "SessionReplyTags" - NSR tagset generation
• "AttachPayloadKDF" - NSR payload key derivation

Elligator2 Encoding

Purpose: Encode X25519 public keys to be indistinguishable from uniform random 32-byte strings.

Specification: Elligator2 Paper

Problem: Standard X25519 public keys have recognizable structure. An observer can identify handshake messages by detecting these keys, even if content is encrypted.

Solution: Elligator2 provides a bijective mapping between ~50% of valid X25519 public keys and random-looking 254-bit strings.

Key Generation with Elligator2:

Elligator2 GENERATE_PRIVATE_ELG2()

Generates a private key that maps to an Elligator2-encodable public key:

while True:
    privkey = CSRNG(32)
    pubkey = DERIVE_PUBLIC(privkey)
    
    # Test if public key is Elligator2-encodable
    try:
        encoded = ENCODE_ELG2(pubkey)
        # Success - this key pair is suitable
        return privkey
    except NotEncodableError:
        # Try again with new random key
        continue

Important: Approximately 50% of randomly generated private keys will produce non-encodable public keys. These must be discarded and regeneration attempted.

Performance Optimization: Generate keys in advance in a background thread to maintain a pool of suitable key pairs, avoiding delays during handshake.

Elligator2 ENCODE_ELG2(pubkey)

Encodes a public key to 32 random-looking bytes:

def ENCODE_ELG2(pubkey):
    """
    Encodes X25519 public key using Elligator2.
    
    Args:
        pubkey: 32-byte X25519 public key (little-endian)
    
    Returns:
        encoded: 32-byte encoded key indistinguishable from random
    
    Raises:
        NotEncodableError: If pubkey cannot be encoded
    """
    # Perform Elligator2 representative calculation
    # Returns 254-bit value (31.75 bytes)
    encodedKey = elligator2_encode(pubkey)
    
    # Add 2 random bits to MSB to make full 32 bytes
    randomByte = CSRNG(1)
    encodedKey[31] |= (randomByte & 0xc0)
    
    return encodedKey

Encoding Details:

• Elligator2 produces 254 bits (not full 256)
• Top 2 bits of byte 31 are random padding
• Result is uniformly distributed across 32-byte space
• Successfully encodes approximately 50% of valid X25519 public keys

Elligator2 DECODE_ELG2(encodedKey)

Decodes back to original public key:

def DECODE_ELG2(encodedKey):
    """
    Decodes Elligator2-encoded key back to X25519 public key.
    
    Args:
        encodedKey: 32-byte encoded key
    
    Returns:
        pubkey: 32-byte X25519 public key (little-endian)
    """
    # Mask out 2 random padding bits from MSB
    encodedKey[31] &= 0x3f
    
    # Perform Elligator2 representative inversion
    pubkey = elligator2_decode(encodedKey)
    
    return pubkey

Security Properties:

• Encoded keys are computationally indistinguishable from random bytes
• No statistical tests can reliably detect Elligator2-encoded keys
• Decoding is deterministic (same encoded key always produces same public key)
• Encoding is bijective for the ~50% of keys in the encodable subset

Implementation Notes:

• Store encoded keys in generation phase to avoid re-encoding during handshake
• Unsuitable keys from Elligator2 generation can be used for NTCP2 (which doesn’t require Elligator2)
• Background key generation is essential for performance
• Average generation time doubles due to 50% rejection rate

Message Formats

Overview

ECIES defines three message types:

1. New Session (NS): Initial handshake message from Alice to Bob
2. New Session Reply (NSR): Bob’s handshake reply to Alice
3. Existing Session (ES): All subsequent messages in both directions

All messages are encapsulated in I2NP Garlic Message format with additional encryption layers.

I2NP Garlic Message Container

All ECIES messages are wrapped in standard I2NP Garlic Message headers:

+----+----+----+----+----+----+----+----+
|type|      msg_id       |  expiration   |
+----+----+----+----+----+----+----+----+
                         |  size   |chks|
+----+----+----+----+----+----+----+----+
|      length       |                   |
+----+----+----+----+                   +
|          encrypted data               |
~                                       ~

Fields:

• type: 0x26 (Garlic Message)
• msg_id: 4-byte I2NP message ID
• expiration: 8-byte Unix timestamp (milliseconds)
• size: 2-byte payload size
• chks: 1-byte checksum
• length: 4-byte encrypted data length
• encrypted data: ECIES-encrypted payload

Purpose: Provides I2NP-layer message identification and routing. The length field allows receivers to know the total encrypted payload size.

New Session (NS) Message

The New Session message initiates a new session from Alice to Bob. It comes in three variants:

1. With Binding (1b): Includes Alice’s static key for bidirectional communication
2. Without Binding (1c): Omits static key for one-way communication
3. One-Time (1d): Single-message mode with no session establishment

NS Message with Binding (Type 1b)

Use Case: Streaming, repliable datagrams, any protocol requiring replies

Total Length: 96 + payload_length bytes

Format:

+----+----+----+----+----+----+----+----+
|                                       |
+                                       +
|   New Session Ephemeral Public Key    |
+             32 bytes                  +
|     Encoded with Elligator2           |
+                                       +
|                                       |
+----+----+----+----+----+----+----+----+
|                                       |
+         Static Key Section            +
|       ChaCha20 encrypted data         |
+            32 bytes                   +
|                                       |
+                                       +
|                                       |
+----+----+----+----+----+----+----+----+
|  Poly1305 Message Authentication Code |
+    (MAC) for Static Key Section       +
|             16 bytes                  |
+----+----+----+----+----+----+----+----+
|                                       |
+            Payload Section            +
|       ChaCha20 encrypted data         |
~          Variable length              ~
|                                       |
+                                       +
|                                       |
+----+----+----+----+----+----+----+----+
|  Poly1305 Message Authentication Code |
+         (MAC) for Payload Section     +
|             16 bytes                  |
+----+----+----+----+----+----+----+----+

Field Details:

Ephemeral Public Key (32 bytes, cleartext):

• Alice’s one-time X25519 public key
• Encoded with Elligator2 (indistinguishable from random)
• Generated fresh for each NS message (never reused)
• Little-endian format

Static Key Section (32 bytes encrypted, 48 bytes with MAC):

• Contains Alice’s X25519 static public key (32 bytes)
• Encrypted with ChaCha20
• Authenticated with Poly1305 MAC (16 bytes)
• Used by Bob to bind session to Alice’s destination

Payload Section (variable length encrypted, +16 bytes MAC):

• Contains garlic cloves and other blocks
• Must include DateTime block as first block
• Usually includes Garlic Clove blocks with application data
• May include NextKey block for immediate ratchet
• Encrypted with ChaCha20
• Authenticated with Poly1305 MAC (16 bytes)

Security Properties:

• Ephemeral key provides forward secrecy component
• Static key authenticates Alice (binding to destination)
• Both sections have separate MACs for domain separation
• Total handshake performs 2 DH operations (es, ss)

NS Message without Binding (Type 1c)

Use Case: Raw datagrams where no reply is expected or desired

Total Length: 96 + payload_length bytes

Format:

+----+----+----+----+----+----+----+----+
|                                       |
+                                       +
|   New Session Ephemeral Public Key    |
+             32 bytes                  +
|     Encoded with Elligator2           |
+                                       +
|                                       |
+----+----+----+----+----+----+----+----+
|                                       |
+           Flags Section               +
|       ChaCha20 encrypted data         |
+            32 bytes                   +
|           All zeros                   |
+                                       +
|                                       |
+----+----+----+----+----+----+----+----+
|  Poly1305 Message Authentication Code |
+         (MAC) for above section       +
|             16 bytes                  |
+----+----+----+----+----+----+----+----+
|                                       |
+            Payload Section            +
|       ChaCha20 encrypted data         |
~          Variable length              ~
|                                       |
+                                       +
|                                       |
+----+----+----+----+----+----+----+----+
|  Poly1305 Message Authentication Code |
+         (MAC) for Payload Section     +
|             16 bytes                  |
+----+----+----+----+----+----+----+----+

Key Difference: Flags Section contains 32 bytes of zeros instead of static key.

Detection: Bob determines message type by decrypting the 32-byte section and checking if all bytes are zero:

• All zeros → Unbound session (type 1c)
• Non-zero → Bound session with static key (type 1b)

Properties:

• No static key means no binding to Alice’s destination
• Bob cannot send replies (no destination known)
• Performs only 1 DH operation (es)
• Follows Noise “N” pattern rather than “IK”
• More efficient when replies are never needed

Flags Section (reserved for future use): Currently all zeros. May be used for feature negotiation in future versions.

NS One-Time Message (Type 1d)

Use Case: Single anonymous message with no session or reply expected

Total Length: 96 + payload_length bytes

Format: Identical to NS without binding (type 1c)

Distinction:

• Type 1c may send multiple messages in the same session (ES messages follow)
• Type 1d sends exactly one message with no session establishment
• In practice, implementations may treat these identically initially

Properties:

• Maximum anonymity (no static key, no session)
• No session state retained by either party
• Follows Noise “N” pattern
• Single DH operation (es)

New Session Reply (NSR) Message

Bob sends one or more NSR messages in response to Alice’s NS message. NSR completes the Noise IK handshake and establishes bidirectional session.

Total Length: 72 + payload_length bytes

Format:

+----+----+----+----+----+----+----+----+
|       Session Tag   8 bytes           |
+----+----+----+----+----+----+----+----+
|                                       |
+        Ephemeral Public Key           +
|                                       |
+            32 bytes                   +
|     Encoded with Elligator2           |
+                                       +
|                                       |
+----+----+----+----+----+----+----+----+
|  Poly1305 Message Authentication Code |
+  (MAC) for Key Section (empty)        +
|             16 bytes                  |
+----+----+----+----+----+----+----+----+
|                                       |
+            Payload Section            +
|       ChaCha20 encrypted data         |
~          Variable length              ~
|                                       |
+                                       +
|                                       |
+----+----+----+----+----+----+----+----+
|  Poly1305 Message Authentication Code |
+         (MAC) for Payload Section     +
|             16 bytes                  |
+----+----+----+----+----+----+----+----+

Field Details:

Session Tag (8 bytes, cleartext):

• Generated from NSR tagset (see KDF sections)
• Correlates this reply with Alice’s NS message
• Allows Alice to identify which NS this NSR responds to
• One-time use (never reused)

Ephemeral Public Key (32 bytes, cleartext):

• Bob’s one-time X25519 public key
• Encoded with Elligator2
• Generated fresh for each NSR message
• Must be different for each NSR sent

Key Section MAC (16 bytes):

• Authenticates empty data (ZEROLEN)
• Part of Noise IK protocol (se pattern)
• Uses hash transcript as associated data
• Critical for binding NSR to NS

Payload Section (variable length):

• Contains garlic cloves and blocks
• Usually includes application-layer replies
• May be empty (ACK-only NSR)
• Maximum size: 65519 bytes (65535 - 16 byte MAC)

Multiple NSR Messages:

Bob may send multiple NSR messages in response to one NS:

• Each NSR has unique ephemeral key
• Each NSR has unique session tag
• Alice uses first NSR received to complete handshake
• Other NSRs are redundancy (in case of packet loss)

Critical Timing:

• Alice must receive one NSR before sending ES messages
• Bob must receive one ES message before sending ES messages
• NSR establishes bidirectional session keys via split() operation

Security Properties:

• Completes Noise IK handshake
• Performs 2 additional DH operations (ee, se)
• Total 4 DH operations across NS+NSR
• Achieves mutual authentication (Level 2)
• Provides weak forward secrecy (Level 4) for NSR payload

Existing Session (ES) Message

All messages after the NS/NSR handshake use the Existing Session format. ES messages are used bidirectionally by both Alice and Bob.

Total Length: 8 + payload_length + 16 bytes (minimum 24 bytes)

Format:

+----+----+----+----+----+----+----+----+
|       Session Tag   8 bytes           |
+----+----+----+----+----+----+----+----+
|                                       |
+            Payload Section            +
|       ChaCha20 encrypted data         |
~          Variable length              ~
|                                       |
+                                       +
|                                       |
+----+----+----+----+----+----+----+----+
|  Poly1305 Message Authentication Code |
+              (MAC)                    +
|             16 bytes                  |
+----+----+----+----+----+----+----+----+

Field Details:

Session Tag (8 bytes, cleartext):

• Generated from current outbound tagset
• Identifies the session and message number
• Receiver looks up tag to find session key and nonce
• One-time use (each tag used exactly once)
• Format: First 8 bytes of HKDF output

Payload Section (variable length):

• Contains garlic cloves and blocks
• No required blocks (may be empty)
• Common blocks: Garlic Clove, NextKey, ACK, ACK Request, Padding
• Maximum size: 65519 bytes (65535 - 16 byte MAC)

MAC (16 bytes):

• Poly1305 authentication tag
• Computed over entire payload
• Associated data: the 8-byte session tag
• Must verify correctly or message is rejected

Tag Lookup Process:

1. Receiver extracts 8-byte tag
2. Looks up tag in all current inbound tagsets
3. Retrieves associated session key and message number N
4. Constructs nonce: [0x00, 0x00, 0x00, 0x00, N (8 bytes little-endian)]
5. Decrypts payload using AEAD with tag as associated data
6. Removes tag from tagset (one-time use)
7. Processes decrypted blocks

Session Tag Not Found:

If tag is not found in any tagset:

• May be an NS message → attempt NS decryption
• May be NSR message → attempt NSR decryption
• May be out-of-order ES → wait briefly for tagset update
• May be replay attack → reject
• May be corrupted data → reject

Empty Payload:

ES messages may have empty payloads (0 bytes):

• Serves as explicit ACK when ACK Request was received
• Provides protocol-layer response without application data
• Still consumes a session tag
• Useful when higher layer has no immediate data to send

Security Properties:

• Full forward secrecy (Level 5) after NSR received
• Authenticated encryption via AEAD
• Tag acts as additional associated data
• Maximum 65535 messages per tagset before ratchet required

Key Derivation Functions

This section documents all KDF operations used in ECIES, showing the complete cryptographic derivations.

Notation and Constants

Constants:

• ZEROLEN - Zero-length byte array (empty string)
• || - Concatenation operator

Variables:

• h - Running hash transcript (32 bytes)
• chainKey - Chaining key for HKDF (32 bytes)
• k - Symmetric cipher key (32 bytes)
• n - Nonce / message number

Keys:

• ask / apk - Alice’s static private/public key
• aesk / aepk - Alice’s ephemeral private/public key
• bsk / bpk - Bob’s static private/public key
• besk / bepk - Bob’s ephemeral private/public key

NS Message KDFs

KDF 1: Initial Chain Key

Performed once at protocol initialization (can be precalculated):

# Protocol name (40 bytes, ASCII, no null termination)
protocol_name = "Noise_IKelg2+hs2_25519_ChaChaPoly_SHA256"

# Initialize hash
h = SHA256(protocol_name)

# Initialize chaining key
chainKey = h

# MixHash with empty prologue
h = SHA256(h)

# State: chainKey and h initialized
# Can be precalculated for all outbound sessions

Result:

• chainKey = Initial chaining key for all subsequent KDFs
• h = Initial hash transcript

KDF 2: Bob’s Static Key Mixing

Bob performs this once (can be precalculated for all inbound sessions):

# Bob's static keys (published in LeaseSet)
bsk = GENERATE_PRIVATE()
bpk = DERIVE_PUBLIC(bsk)

# Mix Bob's public key into hash
h = SHA256(h || bpk)

# State: h updated with Bob's identity
# Can be precalculated by Bob for all inbound sessions

KDF 3: Alice’s Ephemeral Key Generation

Alice generates fresh keys for each NS message:

# Generate ephemeral key pair suitable for Elligator2
aesk = GENERATE_PRIVATE_ELG2()
aepk = DERIVE_PUBLIC(aesk)

# Mix ephemeral public key into hash
h = SHA256(h || aepk)

# Elligator2 encode for transmission
elg2_aepk = ENCODE_ELG2(aepk)

# State: h updated with Alice's ephemeral key
# Send elg2_aepk as first 32 bytes of NS message

KDF 4: NS Static Key Section (es DH)

Derives keys for encrypting Alice’s static key:

# Perform first DH (ephemeral-static)
sharedSecret = DH(aesk, bpk)  # Alice computes
# Equivalent: sharedSecret = DH(bsk, aepk)  # Bob computes

# Derive cipher key from shared secret
keydata = HKDF(chainKey, sharedSecret, "", 64)
chainKey = keydata[0:31]
k = keydata[32:63]

# AEAD encryption parameters
nonce = 0
associated_data = h  # Current hash transcript

# Encrypt static key section
if binding_requested:
    plaintext = apk  # Alice's static public key (32 bytes)
else:
    plaintext = bytes(32)  # All zeros for unbound

ciphertext = ENCRYPT(k, nonce, plaintext, associated_data)
# ciphertext = 32 bytes encrypted + 16 bytes MAC = 48 bytes

# Mix ciphertext into hash
h = SHA256(h || ciphertext)

# State: Static key section encrypted, h updated
# Send ciphertext (48 bytes) as next part of NS message

KDF 5: NS Payload Section (ss DH, bound only)

For bound sessions, perform second DH for payload encryption:

if binding_requested:
    # Alice's static keys
    ask = GENERATE_PRIVATE()  # Alice's long-term key
    apk = DERIVE_PUBLIC(ask)
    
    # Perform second DH (static-static)
    sharedSecret = DH(ask, bpk)  # Alice computes
    # Equivalent: sharedSecret = DH(bsk, apk)  # Bob computes
    
    # Derive cipher key
    keydata = HKDF(chainKey, sharedSecret, "", 64)
    chainKey = keydata[0:31]
    k = keydata[32:63]
    
    nonce = 0
    associated_data = h
else:
    # Unbound: reuse keys from static key section
    # chainKey and k unchanged
    nonce = 1  # Increment nonce (reusing same key)
    associated_data = h

# Encrypt payload
payload = build_payload()  # DateTime + Garlic Cloves + etc.
ciphertext = ENCRYPT(k, nonce, payload, associated_data)

# Mix ciphertext into hash
h = SHA256(h || ciphertext)

# State: Payload encrypted, h contains complete NS transcript
# Save chainKey and h for NSR processing
# Send ciphertext as final part of NS message

Important Notes:

1. Bound vs Unbound:

   • Bound performs 2 DH operations (es + ss)
   • Unbound performs 1 DH operation (es only)
   • Unbound increments nonce instead of deriving new key

2. Key Reuse Safety:

   • Different nonces (0 vs 1) prevent key/nonce reuse
   • Different associated data (h is different) provides domain separation

3. Hash Transcript:

   • h now contains: protocol_name, empty prologue, bpk, aepk, static_key_ciphertext, payload_ciphertext
   • This transcript binds all parts of NS message together

NSR Reply Tagset KDF

Bob generates tags for NSR messages:

# Chain key from NS payload section
# chainKey = final chainKey from NS KDF

# Generate tagset key
tagsetKey = HKDF(chainKey, ZEROLEN, "SessionReplyTags", 32)

# Initialize NSR tagset (see DH_INITIALIZE below)
tagset_nsr = DH_INITIALIZE(chainKey, tagsetKey)

# Get tag for this NSR
tagsetEntry = tagset_nsr.GET_NEXT_ENTRY()
tag = tagsetEntry.SESSION_TAG  # 8 bytes

# State: tag available for NSR message
# Send tag as first 8 bytes of NSR

NSR Message KDFs

KDF 6: NSR Ephemeral Key Generation

Bob generates fresh ephemeral key for each NSR:

# Mix tag into hash (I2P extension to Noise)
h = SHA256(h || tag)

# Generate ephemeral key pair
besk = GENERATE_PRIVATE_ELG2()
bepk = DERIVE_PUBLIC(besk)

# Mix ephemeral public key into hash
h = SHA256(h || bepk)

# Elligator2 encode for transmission
elg2_bepk = ENCODE_ELG2(bepk)

# State: h updated with tag and Bob's ephemeral key
# Send elg2_bepk as bytes 9-40 of NSR message

KDF 7: NSR Key Section (ee and se DH)

Derives keys for NSR key section:

# Perform third DH (ephemeral-ephemeral)
sharedSecret_ee = DH(aesk, bepk)  # Alice computes
# Equivalent: sharedSecret_ee = DH(besk, aepk)  # Bob computes

# Mix ee into chain
keydata = HKDF(chainKey, sharedSecret_ee, "", 32)
chainKey = keydata[0:31]

# Perform fourth DH (static-ephemeral)
sharedSecret_se = DH(ask, bepk)  # Alice computes
# Equivalent: sharedSecret_se = DH(besk, apk)  # Bob computes

# Derive cipher key from se
keydata = HKDF(chainKey, sharedSecret_se, "", 64)
chainKey = keydata[0:31]
k = keydata[32:63]

# AEAD encryption of empty data (key section has no payload)
nonce = 0
associated_data = h
ciphertext = ENCRYPT(k, nonce, ZEROLEN, associated_data)
# ciphertext = 16 bytes (MAC only, no plaintext)

# Mix ciphertext into hash
h = SHA256(h || ciphertext)

# State: Key section encrypted, chainKey contains all 4 DH results
# Send ciphertext (16 bytes MAC) as bytes 41-56 of NSR

Critical: This completes the Noise IK handshake. chainKey now contains contributions from all 4 DH operations (es, ss, ee, se).

KDF 8: NSR Payload Section

Derives keys for NSR payload encryption:

# Split chainKey into bidirectional keys
keydata = HKDF(chainKey, ZEROLEN, "", 64)
k_ab = keydata[0:31]   # Alice → Bob key
k_ba = keydata[32:63]  # Bob → Alice key

# Initialize ES tagsets for both directions
tagset_ab = DH_INITIALIZE(chainKey, k_ab)  # Alice → Bob
tagset_ba = DH_INITIALIZE(chainKey, k_ba)  # Bob → Alice

# Derive NSR payload key (Bob → Alice)
k_nsr = HKDF(k_ba, ZEROLEN, "AttachPayloadKDF", 32)

# Encrypt NSR payload
nonce = 0
associated_data = h  # Binds payload to entire NSR
payload = build_payload()  # Usually application reply
ciphertext = ENCRYPT(k_nsr, nonce, payload, associated_data)

# State: Bidirectional ES sessions established
# tagset_ab and tagset_ba ready for ES messages
# Send ciphertext as bytes 57+ of NSR message

Important Notes:

1. Split Operation:

   • Creates independent keys for each direction
   • Prevents key reuse between Alice→Bob and Bob→Alice

2. NSR Payload Binding:

   • Uses h as associated data to bind payload to handshake
   • Separate KDF (“AttachPayloadKDF”) provides domain separation

3. ES Readiness:

   • After NSR, both parties can send ES messages
   • Alice must receive NSR before sending ES
   • Bob must receive ES before sending ES

ES Message KDFs

ES messages use pre-generated session keys from tagsets:

# Sender gets next tag and key
tagsetEntry = outbound_tagset.GET_NEXT_ENTRY()
tag = tagsetEntry.SESSION_TAG     # 8 bytes
k = tagsetEntry.SESSION_KEY       # 32 bytes
N = tagsetEntry.INDEX             # Message number

# Construct nonce (12 bytes)
nonce = [0x00, 0x00, 0x00, 0x00] + little_endian_8_bytes(N)

# AEAD encryption
associated_data = tag  # Tag is associated data
payload = build_payload()
ciphertext = ENCRYPT(k, nonce, payload, associated_data)

# Send: tag || ciphertext (8 + len(ciphertext) bytes)

Receiver Process:

# Extract tag
tag = message[0:8]

# Look up tag in inbound tagsets
tagsetEntry = inbound_tagset.GET_SESSION_KEY(tag)
if tagsetEntry is None:
    # Not an ES message, try NS/NSR decryption
    return try_handshake_decryption(message)

k = tagsetEntry.SESSION_KEY
N = tagsetEntry.INDEX

# Construct nonce
nonce = [0x00, 0x00, 0x00, 0x00] + little_endian_8_bytes(N)

# AEAD decryption
associated_data = tag
ciphertext = message[8:]
try:
    payload = DECRYPT(k, nonce, ciphertext, associated_data)
except AuthenticationError:
    # MAC verification failed, reject message
    return reject_message()

# Process payload blocks
process_payload(payload)

# Remove tag from tagset (one-time use)
inbound_tagset.remove(tag)

DH_INITIALIZE Function

Creates a tagset for a single direction:

def DH_INITIALIZE(rootKey, k):
    """
    Initializes a tagset with session tag and symmetric key ratchets.
    
    Args:
        rootKey: Chain key from previous DH ratchet (32 bytes)
        k: Key material from split() or DH ratchet (32 bytes)
    
    Returns:
        tagset: Initialized tagset object
    """
    # Derive next root key and chain key
    keydata = HKDF(rootKey, k, "KDFDHRatchetStep", 64)
    nextRootKey = keydata[0:31]
    chainKey_tagset = keydata[32:63]
    
    # Derive separate chain keys for tags and keys
    keydata = HKDF(chainKey_tagset, ZEROLEN, "TagAndKeyGenKeys", 64)
    sessTag_ck = keydata[0:31]   # Session tag chain key
    symmKey_ck = keydata[32:63]  # Symmetric key chain key
    
    # Create tagset object
    tagset = Tagset()
    tagset.nextRootKey = nextRootKey
    tagset.sessTag_chainKey = sessTag_ck
    tagset.symmKey_chainKey = symmKey_ck
    tagset.lastIndex = -1
    
    return tagset

Usage Contexts:

1. NSR Tagset: DH_INITIALIZE(chainKey_from_NS, tagsetKey_NSR)
2. ES Tagsets: DH_INITIALIZE(chainKey_from_NSR, k_ab or k_ba)
3. Ratcheted Tagsets: DH_INITIALIZE(nextRootKey_from_previous, tagsetKey_from_DH)

Ratchet Mechanisms

ECIES uses three synchronized ratchet mechanisms to provide forward secrecy and efficient session management.

Ratchet Overview

Three Ratchet Types:

1. DH Ratchet: Performs Diffie-Hellman key exchanges to generate new root keys
2. Session Tag Ratchet: Derives one-time-use session tags deterministically
3. Symmetric Key Ratchet: Derives session keys for message encryption

Relationship:

DH Ratchet (periodic)
    ↓
Creates new tagset
    ↓
Session Tag Ratchet (per message) ← synchronized → Symmetric Key Ratchet (per message)
    ↓                                                      ↓
Session Tags (8 bytes each)                      Session Keys (32 bytes each)

Key Properties:

• Sender: Generates tags and keys on-demand (no storage needed)
• Receiver: Pre-generates tags for look-ahead window (storage required)
• Synchronization: Tag index determines key index (N_tag = N_key)
• Forward Secrecy: Achieved through periodic DH ratchet
• Efficiency: Receiver can defer key calculation until tag is received

DH Ratchet

The DH ratchet provides forward secrecy by periodically exchanging new ephemeral keys.

DH Ratchet Frequency

Required Ratchet Conditions:

• Tag set approaching exhaustion (tag 65535 is maximum)
• Implementation-specific policies:
  • Message count threshold (e.g., every 4096 messages)
  • Time threshold (e.g., every 10 minutes)
  • Data volume threshold (e.g., every 100 MB)

Recommended First Ratchet: Around tag number 4096 to avoid reaching limit

Maximum Values:

• Maximum tag set ID: 65535
• Maximum key ID: 32767
• Maximum messages per tag set: 65535
• Theoretical maximum data per session: ~6.9 TB (64K tag sets × 64K messages × 1730 bytes avg)

DH Ratchet Tag and Key IDs

Initial Tag Set (post-handshake):

• Tag set ID: 0
• No NextKey blocks have been sent yet
• No key IDs assigned

After First Ratchet:

• Tag set ID: 1 = (1 + Alice’s key ID + Bob’s key ID) = (1 + 0 + 0)
• Alice sends NextKey with key ID 0
• Bob replies with NextKey with key ID 0

Subsequent Tag Sets:

• Tag set ID = 1 + sender’s key ID + receiver’s key ID
• Example: Tag set 5 = (1 + sender_key_2 + receiver_key_2)

Tag Set Progression Table:

* = New key generated this ratchet

Key ID Rules:

• IDs are sequential starting from 0
• IDs increment only when new key is generated
• Maximum key ID is 32767 (15 bits)
• After key ID 32767, new session required

DH Ratchet Message Flow

Roles:

• Tag Sender: Owns the outbound tag set, sends messages
• Tag Receiver: Owns the inbound tag set, receives messages

Pattern: Tag sender initiates ratchet when tag set is nearly exhausted.

Message Flow Diagram:

Tag Sender                         Tag Receiver

       ... using tag set #0 ...

(Tag set #0 approaching exhaustion)
(Generate new key #0)

NextKey forward, request reverse, with key #0  -------->
(Repeat until NextKey ACK received)
                                   (Generate new key #0)
                                   (Perform DH: sender_key_0 × receiver_key_0)
                                   (Create inbound tag set #1)

        <---------------           NextKey reverse, with key #0
                                   (Repeat until tag from tag set #1 received)

(Receive NextKey with key #0)
(Perform DH: sender_key_0 × receiver_key_0)
(Create outbound tag set #1)


       ... using tag set #1 ...


(Tag set #1 approaching exhaustion)
(Generate new key #1)

NextKey forward, with key #1        -------->
(Repeat until NextKey ACK received)
                                   (Reuse existing key #0)
                                   (Perform DH: sender_key_1 × receiver_key_0)
                                   (Create inbound tag set #2)

        <--------------            NextKey reverse, id 0 (ACK)
                                   (Repeat until tag from tag set #2 received)

(Receive NextKey with id 0)
(Perform DH: sender_key_1 × receiver_key_0)
(Create outbound tag set #2)


       ... using tag set #2 ...


(Tag set #2 approaching exhaustion)
(Reuse existing key #1)

NextKey forward, request reverse, id 1  -------->
(Repeat until NextKey received)
                                   (Generate new key #1)
                                   (Perform DH: sender_key_1 × receiver_key_1)
                                   (Create inbound tag set #3)

        <--------------            NextKey reverse, with key #1

(Receive NextKey with key #1)
(Perform DH: sender_key_1 × receiver_key_1)
(Create outbound tag set #3)


       ... using tag set #3 ...

       (Pattern repeats: even-numbered tag sets
        use forward key, odd-numbered use reverse key)

Ratchet Patterns:

Creating Even-Numbered Tag Sets (2, 4, 6, …):

1. Sender generates new key
2. Sender sends NextKey block with new key
3. Receiver sends NextKey block with old key ID (ACK)
4. Both perform DH with (new sender key × old receiver key)

Creating Odd-Numbered Tag Sets (3, 5, 7, …):

1. Sender requests reverse key (sends NextKey with request flag)
2. Receiver generates new key
3. Receiver sends NextKey block with new key
4. Both perform DH with (old sender key × new receiver key)

NextKey Block Format

See Payload Format section for detailed NextKey block specification.

Key Elements:

• Flags byte:
  • Bit 0: Key present (1) or ID only (0)
  • Bit 1: Reverse key (1) or forward key (0)
  • Bit 2: Request reverse key (1) or no request (0)
• Key ID: 2 bytes, big-endian (0-32767)
• Public Key: 32 bytes X25519 (if bit 0 = 1)

Example NextKey Blocks:

# Sender initiates ratchet with new key (key ID 0, tag set 1)
NextKey(flags=0x01, key_id=0, pubkey=sender_key_0)

# Receiver replies with new key (key ID 0, tag set 1)
NextKey(flags=0x03, key_id=0, pubkey=receiver_key_0)

# Sender ratchets again with new key (key ID 1, tag set 2)
NextKey(flags=0x01, key_id=1, pubkey=sender_key_1)

# Receiver ACKs with old key ID (tag set 2)
NextKey(flags=0x02, key_id=0)

# Sender requests reverse key (tag set 3)
NextKey(flags=0x04, key_id=1)

# Receiver sends new reverse key (key ID 1, tag set 3)
NextKey(flags=0x03, key_id=1, pubkey=receiver_key_1)

DH Ratchet KDF

When new keys are exchanged:

# Tag sender generates or reuses key
if generating_new:
    sender_sk = GENERATE_PRIVATE()
    sender_pk = DERIVE_PUBLIC(sender_sk)
else:
    # Reuse existing key pair
    sender_pk = existing_sender_pk

# Tag receiver generates or reuses key
if generating_new:
    receiver_sk = GENERATE_PRIVATE()
    receiver_pk = DERIVE_PUBLIC(receiver_sk)
else:
    # Reuse existing key pair
    receiver_pk = existing_receiver_pk

# Both parties perform DH
sharedSecret = DH(sender_sk, receiver_pk)

# Derive tagset key
tagsetKey = HKDF(sharedSecret, ZEROLEN, "XDHRatchetTagSet", 32)

# Get next root key from previous tagset
rootKey = previous_tagset.nextRootKey

# Initialize new tagset
new_tagset = DH_INITIALIZE(rootKey, tagsetKey)

# Tag sender: outbound tagset
# Tag receiver: inbound tagset

Critical Timing:

Tag Sender:

• Creates new outbound tag set immediately
• Begins using new tags immediately
• Deletes old outbound tag set

Tag Receiver:

• Creates new inbound tag set
• Retains old inbound tag set for grace period (3 minutes)
• Accepts tags from both old and new tag sets during grace period
• Deletes old inbound tag set after grace period

DH Ratchet State Management

Sender State:

• Current outbound tag set
• Tag set ID and key IDs
• Next root key (for next ratchet)
• Message count in current tag set

Receiver State:

• Current inbound tag set(s) (may have 2 during grace period)
• Previous messages numbers (PN) for gap detection
• Look-ahead window of pre-generated tags
• Next root key (for next ratchet)

State Transition Rules:

1. Before First Ratchet:

   • Using tag set 0 (from NSR)
   • No key IDs assigned

2. Initiating Ratchet:

   • Generate new key (if sender is generating this round)
   • Send NextKey block in ES message
   • Wait for NextKey reply before creating new outbound tag set

3. Receiving Ratchet Request:

   • Generate new key (if receiver is generating this round)
   • Perform DH with received key
   • Create new inbound tag set
   • Send NextKey reply
   • Retain old inbound tag set for grace period

4. Completing Ratchet:

   • Receive NextKey reply
   • Perform DH
   • Create new outbound tag set
   • Begin using new tags

Session Tag Ratchet

The session tag ratchet generates one-time-use 8-byte session tags deterministically.

Session Tag Ratchet Purpose

• Replaces explicit tag transmission (ElGamal sent 32-byte tags)
• Enables receiver to pre-generate tags for look-ahead window
• Sender generates on-demand (no storage required)
• Synchronizes with symmetric key ratchet via index

Session Tag Ratchet Formula

Initialization:

# From DH_INITIALIZE
sessTag_ck = initial_chain_key  # 32 bytes

# Initialize session tag ratchet
keydata = HKDF(sessTag_ck, ZEROLEN, "STInitialization", 64)
sessTag_chainKey = keydata[0:31]    # First chain key
SESSTAG_CONSTANT = keydata[32:63]   # Constant for all tags in this tagset

Tag Generation (for tag N):

# Generate tag N
keydata = HKDF(sessTag_chainKey_(N-1), SESSTAG_CONSTANT, "SessionTagKeyGen", 64)
sessTag_chainKey_N = keydata[0:31]  # Chain key for next tag
tag_N = keydata[32:39]              # Session tag (8 bytes)

# Chain continues for each tag
# tag_0, tag_1, tag_2, ..., tag_65535

Complete Sequence:

# Tag 0
keydata_0 = HKDF(sessTag_chainKey, SESSTAG_CONSTANT, "SessionTagKeyGen", 64)
sessTag_chainKey_0 = keydata_0[0:31]
tag_0 = keydata_0[32:39]

# Tag 1
keydata_1 = HKDF(sessTag_chainKey_0, SESSTAG_CONSTANT, "SessionTagKeyGen", 64)
sessTag_chainKey_1 = keydata_1[0:31]
tag_1 = keydata_1[32:39]

# Tag N
keydata_N = HKDF(sessTag_chainKey_(N-1), SESSTAG_CONSTANT, "SessionTagKeyGen", 64)
sessTag_chainKey_N = keydata_N[0:31]
tag_N = keydata_N[32:39]

Session Tag Ratchet Sender Implementation

class OutboundTagset:
    def __init__(self, sessTag_ck):
        # Initialize
        keydata = HKDF(sessTag_ck, ZEROLEN, "STInitialization", 64)
        self.chainKey = keydata[0:31]
        self.constant = keydata[32:63]
        self.index = -1
    
    def get_next_tag(self):
        # Increment index
        self.index += 1
        
        if self.index > 65535:
            raise TagsetExhausted("Ratchet required")
        
        # Generate tag
        keydata = HKDF(self.chainKey, self.constant, "SessionTagKeyGen", 64)
        self.chainKey = keydata[0:31]
        tag = keydata[32:39]
        
        return (tag, self.index)

Sender Process:

1. Call get_next_tag() for each message
2. Use returned tag in ES message
3. Store index N for potential ACK tracking
4. No tag storage required (generated on-demand)

Session Tag Ratchet Receiver Implementation

class InboundTagset:
    def __init__(self, sessTag_ck, look_ahead=32):
        # Initialize
        keydata = HKDF(sessTag_ck, ZEROLEN, "STInitialization", 64)
        self.chainKey = keydata[0:31]
        self.constant = keydata[32:63]
        self.index = -1
        self.look_ahead = look_ahead
        self.tags = {}  # Dictionary: tag -> index
        
        # Pre-generate initial tags
        self.extend(look_ahead)
    
    def extend(self, count):
        """Generate 'count' more tags"""
        for _ in range(count):
            self.index += 1
            
            if self.index > 65535:
                return  # Cannot exceed maximum
            
            # Generate tag
            keydata = HKDF(self.chainKey, self.constant, "SessionTagKeyGen", 64)
            self.chainKey = keydata[0:31]
            tag = keydata[32:39]
            
            # Store tag
            self.tags[tag] = self.index
    
    def lookup_tag(self, tag):
        """Look up tag and return index"""
        if tag in self.tags:
            index = self.tags[tag]
            # Remove tag (one-time use)
            del self.tags[tag]
            return index
        return None
    
    def check_and_extend(self):
        """Extend if tag count is low"""
        current_count = len(self.tags)
        if current_count < self.look_ahead // 2:
            # Extend to restore window
            self.extend(self.look_ahead - current_count)

Receiver Process:

1. Pre-generate tags for look-ahead window (e.g., 32 tags)
2. Store tags in hash table or dictionary
3. When message arrives, look up tag to get index N
4. Remove tag from storage (one-time use)
5. Extend window if tag count drops below threshold

Session Tag Look-Ahead Strategy

Purpose: Balance memory usage vs. out-of-order message handling

Recommended Look-Ahead Sizes:

Adaptive Look-Ahead:

# Dynamic look-ahead based on highest tag received
look_ahead = min(tsmax, tsmin + N // 4)

# Example:
# tsmin = 24, tsmax = 160
# N = 0:   look_ahead = min(160, 24 + 0/4) = 24
# N = 100: look_ahead = min(160, 24 + 100/4) = 49
# N = 500: look_ahead = min(160, 24 + 500/4) = 149
# N = 544: look_ahead = min(160, 24 + 544/4) = 160

Trim Behind:

# Trim tags far behind highest received
trim_behind = look_ahead // 2

# If highest received tag is N=100, trim tags below N=50

Memory Calculation:

# Per tag: 8 bytes (tag) + 2 bytes (index) + overhead ≈ 16 bytes
# Look-ahead of 160 tags ≈ 2.5 KB per inbound tagset

# With multiple sessions:
# 100 inbound sessions × 2.5 KB = 250 KB total

Session Tag Out-of-Order Handling

Scenario: Messages arrive out of order

Expected: tag_5, tag_6, tag_7, tag_8
Received: tag_5, tag_7, tag_6, tag_8

Receiver Behavior:

1. Receive tag_5:

   • Look up: found at index 5
   • Process message
   • Remove tag_5
   • Highest received: 5

2. Receive tag_7 (out of order):

   • Look up: found at index 7
   • Process message
   • Remove tag_7
   • Highest received: 7
   • Note: tag_6 still in storage (not yet received)

3. Receive tag_6 (delayed):

   • Look up: found at index 6
   • Process message
   • Remove tag_6
   • Highest received: 7 (unchanged)

4. Receive tag_8:

   • Look up: found at index 8
   • Process message
   • Remove tag_8
   • Highest received: 8

Window Maintenance:

• Keep track of highest received index
• Maintain list of missing indices (gaps)
• Extend window based on highest index
• Optional: Expire old gaps after timeout

Symmetric Key Ratchet

The symmetric key ratchet generates 32-byte encryption keys synchronized with session tags.

Symmetric Key Ratchet Purpose

• Provides unique encryption key for each message
• Synchronized with session tag ratchet (same index)
• Sender can generate on-demand
• Receiver can defer generation until tag is received

Symmetric Key Ratchet Formula

Initialization:

# From DH_INITIALIZE
symmKey_ck = initial_chain_key  # 32 bytes

# No additional initialization needed
# Unlike session tag ratchet, no constant is derived

Key Generation (for key N):

# Generate key N
SYMMKEY_CONSTANT = ZEROLEN  # Empty string
keydata = HKDF(symmKey_chainKey_(N-1), SYMMKEY_CONSTANT, "SymmetricRatchet", 64)
symmKey_chainKey_N = keydata[0:31]  # Chain key for next key
key_N = keydata[32:63]              # Session key (32 bytes)

Complete Sequence:

# Key 0
keydata_0 = HKDF(symmKey_ck, ZEROLEN, "SymmetricRatchet", 64)
symmKey_chainKey_0 = keydata_0[0:31]
key_0 = keydata_0[32:63]

# Key 1
keydata_1 = HKDF(symmKey_chainKey_0, ZEROLEN, "SymmetricRatchet", 64)
symmKey_chainKey_1 = keydata_1[0:31]
key_1 = keydata_1[32:63]

# Key N
keydata_N = HKDF(symmKey_chainKey_(N-1), ZEROLEN, "SymmetricRatchet", 64)
symmKey_chainKey_N = keydata_N[0:31]
key_N = keydata_N[32:63]

Symmetric Key Ratchet Sender Implementation

class OutboundKeyRatchet:
    def __init__(self, symmKey_ck):
        self.chainKey = symmKey_ck
        self.index = -1
    
    def get_key(self, index):
        """Generate key for specific index"""
        # Fast-forward to desired index if needed
        while self.index < index:
            self.index += 1
            keydata = HKDF(self.chainKey, ZEROLEN, "SymmetricRatchet", 64)
            self.chainKey = keydata[0:31]
            if self.index == index:
                return keydata[32:63]
        
        # Should not reach here if called correctly
        raise ValueError("Key already generated")

Sender Process:

1. Get next tag and its index N
2. Generate key for index N
3. Use key to encrypt message
4. No key storage required

Symmetric Key Ratchet Receiver Implementation

Strategy 1: Deferred Generation (Recommended)

class InboundKeyRatchet:
    def __init__(self, symmKey_ck):
        self.chainKey = symmKey_ck
        self.index = -1
        self.cache = {}  # Optional: cache recently used keys
    
    def get_key(self, index):
        """Generate key for specific index"""
        # Check cache first (optional optimization)
        if index in self.cache:
            key = self.cache[index]
            del self.cache[index]
            return key
        
        # Fast-forward to desired index
        while self.index < index:
            self.index += 1
            keydata = HKDF(self.chainKey, ZEROLEN, "SymmetricRatchet", 64)
            self.chainKey = keydata[0:31]
            
            if self.index == index:
                return keydata[32:63]
        
        raise ValueError("Index already passed")

Deferred Generation Process:

1. Receive ES message with tag
2. Look up tag to get index N
3. Generate keys 0 through N (if not already generated)
4. Use key N to decrypt message
5. Chain key now positioned at index N

Advantages:

• Minimal memory usage
• Keys generated only when needed
• Simple implementation

Disadvantages:

• Must generate all keys from 0 to N on first use
• Cannot handle out-of-order messages without caching

Strategy 2: Pre-generation with Tag Window (Alternative)

class InboundKeyRatchet:
    def __init__(self, symmKey_ck):
        self.chainKey = symmKey_ck
        self.index = -1
        self.keys = {}  # Dictionary: index -> key
    
    def extend(self, count):
        """Pre-generate 'count' more keys"""
        for _ in range(count):
            self.index += 1
            keydata = HKDF(self.chainKey, ZEROLEN, "SymmetricRatchet", 64)
            self.chainKey = keydata[0:31]
            key = keydata[32:63]
            self.keys[self.index] = key
    
    def get_key(self, index):
        """Retrieve pre-generated key"""
        if index in self.keys:
            key = self.keys[index]
            del self.keys[index]
            return key
        return None

Pre-generation Process:

1. Pre-generate keys matching tag window (e.g., 32 keys)
2. Store keys indexed by message number
3. When tag is received, look up corresponding key
4. Extend window as tags are used

Advantages:

• Handles out-of-order messages naturally
• Fast key retrieval (no generation delay)

Disadvantages:

• Higher memory usage (32 bytes per key vs 8 bytes per tag)
• Must keep keys synchronized with tags

Memory Comparison:

# Look-ahead of 160:
# Tags only:  160 × 16 bytes = 2.5 KB
# Tags+Keys:  160 × (16 + 32) bytes = 7.5 KB
# 
# For 100 sessions:
# Tags only:  250 KB
# Tags+Keys:  750 KB

Symmetric Ratchet Synchronization with Session Tags

Critical Requirement: Session tag index MUST equal symmetric key index

# Sender
tag, index = outbound_tagset.get_next_tag()
key = outbound_keyratchet.get_key(index)  # Same index
nonce = construct_nonce(index)
ciphertext = ENCRYPT(key, nonce, payload, tag)

# Receiver
index = inbound_tagset.lookup_tag(tag)
key = inbound_keyratchet.get_key(index)  # Same index
nonce = construct_nonce(index)
plaintext = DECRYPT(key, nonce, ciphertext, tag)

Failure Modes:

If synchronization breaks:

• Wrong key used for decryption
• MAC verification fails
• Message rejected

Prevention:

• Always use same index for tag and key
• Never skip indices in either ratchet
• Handle out-of-order messages carefully

Symmetric Ratchet Nonce Construction

Nonce is derived from message number:

def construct_nonce(index):
    """
    Construct 12-byte nonce for ChaCha20-Poly1305
    
    Args:
        index: Message number (0-65535)
    
    Returns:
        nonce: 12-byte nonce
    """
    # First 4 bytes are always zero
    nonce = bytearray(12)
    nonce[0:4] = b'\x00\x00\x00\x00'
    
    # Last 8 bytes are little-endian message number
    nonce[4:12] = index.to_bytes(8, byteorder='little')
    
    return bytes(nonce)

Examples:

index = 0:     nonce = 0x00000000 0000000000000000
index = 1:     nonce = 0x00000000 0100000000000000
index = 255:   nonce = 0x00000000 FF00000000000000
index = 256:   nonce = 0x00000000 0001000000000000
index = 65535: nonce = 0x00000000 FFFF000000000000

Important Properties:

• Nonces are unique for each message in a tagset
• Nonces never repeat (one-time-use tags ensure this)
• 8-byte counter allows for 2^64 messages (we only use 2^16)
• Nonce format matches RFC 7539 counter-based construction

Session Management

Session Context

All inbound and outbound sessions must belong to a specific context:

1. Router Context: Sessions for the router itself
2. Destination Context: Sessions for a specific local destination (client application)

Critical Rule: Sessions MUST NOT be shared among contexts to prevent correlation attacks.

Implementation:

class SessionKeyManager:
    """Context for managing sessions (router or destination)"""
    def __init__(self, context_id):
        self.context_id = context_id
        self.inbound_sessions = {}   # far_end_dest -> [sessions]
        self.outbound_sessions = {}  # far_end_dest -> session
        self.static_keypair = generate_keypair()  # Context's identity
    
    def get_outbound_session(self, destination):
        """Get or create outbound session to destination"""
        if destination not in self.outbound_sessions:
            self.outbound_sessions[destination] = create_outbound_session(destination)
        return self.outbound_sessions[destination]
    
    def add_inbound_session(self, session, destination=None):
        """Add inbound session, optionally bound to destination"""
        if destination:
            if destination not in self.inbound_sessions:
                self.inbound_sessions[destination] = []
            self.inbound_sessions[destination].append(session)
        else:
            # Unbound session
            self.inbound_sessions[None].append(session)

Java I2P Implementation:

In Java I2P, the SessionKeyManager class provides this functionality:

• One SessionKeyManager per router
• One SessionKeyManager per local destination
• Separate management of ECIES and ElGamal sessions within each context

Session Binding

Binding associates a session with a specific far-end destination.

Bound Sessions

Characteristics:

• Include sender’s static key in NS message
• Recipient can identify sender’s destination
• Enables bidirectional communication
• Single outbound session per destination
• May have multiple inbound sessions (during transitions)

Use Cases:

• Streaming connections (TCP-like)
• Repliable datagrams
• Any protocol requiring request/response

Binding Process:

# Alice creates bound outbound session
outbound_session = OutboundSession(
    destination=bob_destination,
    static_key=alice_static_key,
    bound=True
)

# Alice sends NS with static key
ns_message = build_ns_message(
    ephemeral_key=alice_ephemeral_key,
    static_key=alice_static_key,  # Included for binding
    payload=data
)

# Bob receives NS
bob_receives_ns(ns_message)
# Bob extracts Alice's static key
alice_static_key = decrypt_static_key_section(ns_message)

# Bob looks up Alice's destination (from bundled LeaseSet)
alice_destination = lookup_destination_by_static_key(alice_static_key)

# Bob creates bound inbound session
inbound_session = InboundSession(
    destination=alice_destination,
    bound=True
)

# Bob pairs with outbound session
outbound_session = OutboundSession(
    destination=alice_destination,
    bound=True
)

Benefits:

1. Ephemeral-Ephemeral DH: Reply uses ee DH (full forward secrecy)
2. Session Continuity: Ratchets maintain binding to same destination
3. Security: Prevents session hijacking (authenticated by static key)
4. Efficiency: Single session per destination (no duplication)

Unbound Sessions

Characteristics:

• No static key in NS message (flags section is all zeros)
• Recipient cannot identify sender
• One-way communication only
• Multiple sessions to same destination allowed

Use Cases:

• Raw datagrams (fire-and-forget)
• Anonymous publishing
• Broadcast-style messaging

Properties:

• More anonymous (no sender identification)
• More efficient (1 DH vs 2 DH in handshake)
• No replies possible (recipient doesn’t know where to reply)
• No session ratcheting (one-time or limited use)

Session Pairing

Pairing connects an inbound session with an outbound session for bidirectional communication.

Creating Paired Sessions

Alice’s Perspective (initiator):

# Create outbound session to Bob
outbound_session = create_outbound_session(bob_destination)

# Create paired inbound session
inbound_session = create_inbound_session(
    paired_with=outbound_session,
    bound_to=bob_destination
)

# Link them
outbound_session.paired_inbound = inbound_session
inbound_session.paired_outbound = outbound_session

# Send NS message
send_ns_message(outbound_session, payload)

Bob’s Perspective (responder):

# Receive NS message
ns_message = receive_ns_message()

# Create inbound session
inbound_session = create_inbound_session_from_ns(ns_message)

# If NS contains static key (bound):
if ns_message.has_static_key():
    alice_destination = extract_destination(ns_message)
    inbound_session.bind_to(alice_destination)
    
    # Create paired outbound session
    outbound_session = create_outbound_session(alice_destination)
    
    # Link them
    outbound_session.paired_inbound = inbound_session
    inbound_session.paired_outbound = outbound_session

# Send NSR
send_nsr_message(inbound_session, outbound_session, payload)

Session Pairing Benefits

1. In-band ACKs: Can acknowledge messages without separate clove
2. Efficient Ratcheting: Both directions ratchet together
3. Flow Control: Can implement back-pressure across paired sessions
4. State Consistency: Easier to maintain synchronized state

Session Pairing Rules

• Outbound session may be unpaired (unbound NS)
• Inbound session for bound NS should be paired
• Pairing occurs at session creation, not after
• Paired sessions have same destination binding
• Ratchets occur independently but are coordinated

Session Lifecycle

Session Lifecycle: Creation Phase

Outbound Session Creation (Alice):

def create_outbound_session(destination, bound=True):
    session = OutboundSession()
    session.destination = destination
    session.bound = bound
    session.state = SessionState.NEW
    session.created_time = now()
    
    # Generate keys for NS message
    session.ephemeral_keypair = generate_elg2_keypair()
    if bound:
        session.static_key = context.static_keypair.public_key
    
    # Will be populated after NSR received
    session.outbound_tagset = None
    session.inbound_tagset = None
    
    return session

Inbound Session Creation (Bob):

def create_inbound_session_from_ns(ns_message):
    session = InboundSession()
    session.state = SessionState.ESTABLISHED
    session.created_time = now()
    
    # Extract from NS
    session.remote_ephemeral_key = ns_message.ephemeral_key
    session.remote_static_key = ns_message.static_key
    
    if session.remote_static_key:
        session.bound = True
        session.destination = lookup_destination(session.remote_static_key)
    else:
        session.bound = False
        session.destination = None
    
    # Generate keys for NSR
    session.ephemeral_keypair = generate_elg2_keypair()
    
    # Create tagsets from KDF
    session.inbound_tagset = create_tagset_from_nsr()
    session.outbound_tagset = create_tagset_from_nsr()
    
    return session

Session Lifecycle: Active Phase

State Transitions:

NEW (outbound only)
  ↓
  NS sent
  ↓
PENDING_REPLY (outbound only)
  ↓
  NSR received
  ↓
ESTABLISHED
  ↓
  ES messages exchanged
  ↓
ESTABLISHED (ongoing)
  ↓
  (optional) RATCHETING
  ↓
ESTABLISHED

Active Session Maintenance:

def maintain_active_session(session):
    # Update last activity time
    session.last_activity = now()
    
    # Check for ratchet needed
    if session.outbound_tagset.needs_ratchet():
        initiate_ratchet(session)
    
    # Check for incoming ratchet
    if received_nextkey_block():
        process_ratchet(session)
    
    # Trim old tags from inbound tagset
    session.inbound_tagset.expire_old_tags()
    
    # Check session health
    if session.idle_time() > SESSION_TIMEOUT:
        mark_session_idle(session)

Session Lifecycle: Expiration Phase

Session Timeout Values:

Expiration Logic:

def check_session_expiration():
    for session in active_sessions:
        # Outbound session expiration (sender)
        if session.is_outbound():
            if session.idle_time() > 8 * 60:  # 8 minutes
                expire_outbound_session(session)
        
        # Inbound session expiration (receiver)
        else:
            if session.idle_time() > 10 * 60:  # 10 minutes
                expire_inbound_session(session)
    
    # Old tagsets (after ratchet)
    for tagset in old_tagsets:
        if tagset.age() > 3 * 60:  # 3 minutes
            delete_tagset(tagset)

Critical Rule: Outbound sessions MUST expire before inbound sessions to prevent desynchronization.

Graceful Termination:

def terminate_session(session, reason=0):
    # Send Termination block (if implemented)
    send_termination_block(session, reason)
    
    # Mark session for deletion
    session.state = SessionState.TERMINATED
    
    # Keep session briefly for final messages
    schedule_deletion(session, delay=30)  # 30 seconds
    
    # Notify paired session
    if session.paired_session:
        session.paired_session.mark_remote_terminated()

Multiple NS Messages

Scenario: Alice’s NS message is lost or NSR reply is lost.

Alice’s Behavior:

class OutboundSession:
    def __init__(self):
        self.ns_messages_sent = []
        self.ns_timer = None
        self.max_ns_attempts = 5
    
    def send_ns_message(self, payload):
        # Generate new ephemeral key for each NS
        ephemeral_key = generate_elg2_keypair()
        
        ns_message = build_ns_message(
            ephemeral_key=ephemeral_key,
            static_key=self.static_key,
            payload=payload
        )
        
        # Store state for this NS
        ns_state = {
            'ephemeral_key': ephemeral_key,
            'chainkey': compute_chainkey(ns_message),
            'hash': compute_hash(ns_message),
            'tagset': derive_nsr_tagset(ns_message),
            'sent_time': now()
        }
        self.ns_messages_sent.append(ns_state)
        
        # Send message
        send_message(ns_message)
        
        # Set timer for retry
        if not self.ns_timer:
            self.ns_timer = set_timer(1.0, self.on_ns_timeout)
    
    def on_ns_timeout(self):
        if len(self.ns_messages_sent) >= self.max_ns_attempts:
            # Give up
            fail_session("No NSR received after {self.max_ns_attempts} attempts")
            return
        
        # Retry with new NS message
        send_ns_message(self.payload)
    
    def on_nsr_received(self, nsr_message):
        # Cancel timer
        cancel_timer(self.ns_timer)
        
        # Find which NS this NSR responds to
        tag = nsr_message.tag
        for ns_state in self.ns_messages_sent:
            if tag in ns_state['tagset']:
                # This NSR corresponds to this NS
                self.active_ns_state = ns_state
                break
        
        # Process NSR and complete handshake
        complete_handshake(nsr_message, self.active_ns_state)
        
        # Discard other NS states
        self.ns_messages_sent = []

Important Properties:

1. Unique Ephemeral Keys: Each NS uses different ephemeral key
2. Independent Handshakes: Each NS creates separate handshake state
3. NSR Correlation: NSR tag identifies which NS it responds to
4. State Cleanup: Unused NS states discarded after successful NSR

Attack Prevention:

To prevent resource exhaustion:

# Limit NS sending rate
max_ns_rate = 5 per 10 seconds per destination

# Limit total NS attempts
max_ns_attempts = 5

# Limit total pending NS states
max_pending_ns = 10 per context

Multiple NSR Messages

Scenario: Bob sends multiple NSRs (e.g., reply data split across multiple messages).

Bob’s Behavior:

class InboundSession:
    def send_nsr_replies(self, payload_chunks):
        # One NS received, multiple NSRs to send
        for chunk in payload_chunks:
            # Generate new ephemeral key for each NSR
            ephemeral_key = generate_elg2_keypair()
            
            # Get next tag from NSR tagset
            tag = self.nsr_tagset.get_next_tag()
            
            nsr_message = build_nsr_message(
                tag=tag,
                ephemeral_key=ephemeral_key,
                payload=chunk
            )
            
            send_message(nsr_message)
        
        # Wait for ES message from Alice
        self.state = SessionState.AWAITING_ES

Alice’s Behavior:

class OutboundSession:
    def on_nsr_received(self, nsr_message):
        if self.state == SessionState.PENDING_REPLY:
            # First NSR received
            complete_handshake(nsr_message)
            self.state = SessionState.ESTABLISHED
            
            # Create ES sessions
            self.es_outbound_tagset = derive_es_outbound_tagset()
            self.es_inbound_tagset = derive_es_inbound_tagset()
            
            # Send ES message (ACK)
            send_es_message(empty_payload)
        
        elif self.state == SessionState.ESTABLISHED:
            # Additional NSR received
            # Decrypt and process payload
            payload = decrypt_nsr_payload(nsr_message)
            process_payload(payload)
            
            # These NSRs are from other NS attempts, ignore handshake

Bob’s Cleanup:

class InboundSession:
    def on_es_received(self, es_message):
        # First ES received from Alice
        # This confirms which NSR Alice used
        
        # Clean up other handshake states
        for other_ns_state in self.pending_ns_states:
            if other_ns_state != self.active_ns_state:
                delete_ns_state(other_ns_state)
        
        # Delete unused NSR tagsets
        for tagset in self.nsr_tagsets:
            if tagset != self.active_nsr_tagset:
                delete_tagset(tagset)
        
        self.state = SessionState.ESTABLISHED

Important Properties:

1. Multiple NSRs Allowed: Bob can send multiple NSRs per NS
2. Different Ephemeral Keys: Each NSR should use unique ephemeral key
3. Same NSR Tagset: All NSRs for one NS use same tagset
4. First ES Wins: Alice’s first ES determines which NSR succeeded
5. Cleanup After ES: Bob discards unused states after ES received

Session State Machine

Complete State Diagram:

                    Outbound Session                    Inbound Session

                         NEW
                          |
                     send NS
                          |
                   PENDING_REPLY -------------------- receive NS ---> ESTABLISHED
                          |                                                |
                   receive NSR                                        send NSR
                          |                                                |
                    ESTABLISHED <---------- receive ES ------------- AWAITING_ES
                          |                     |                          |
                    ┌─────┴─────┐               |                    receive ES
                    |           |               |                          |
              send ES      receive ES           |                    ESTABLISHED
                    |           |               |                          |
                    └─────┬─────┘               |                ┌─────────┴─────────┐
                          |                     |                |                   |
                          |                     |          send ES              receive ES
                          |                     |                |                   |
                          |                     |                └─────────┬─────────┘
                          |                     |                          |
                          └─────────────────────┴──────────────────────────┘
                                              ACTIVE
                                                |
                                         idle timeout
                                                |
                                             EXPIRED

State Descriptions:

• NEW: Outbound session created, no NS sent yet
• PENDING_REPLY: NS sent, awaiting NSR
• AWAITING_ES: NSR sent, awaiting first ES from Alice
• ESTABLISHED: Handshake complete, can send/receive ES
• ACTIVE: Actively exchanging ES messages
• RATCHETING: DH ratchet in progress (subset of ACTIVE)
• EXPIRED: Session timed out, pending deletion
• TERMINATED: Session explicitly terminated

Payload Format

The payload section of all ECIES messages (NS, NSR, ES) uses a block-based format similar to NTCP2.

Block Structure

General Format:

+----+----+----+----+----+----+----+----+
|blk |  size   |       data             |
+----+----+----+                        +
|                                       |
~               ...                     ~
|                                       |
+----+----+----+----+----+----+----+----+
|blk |  size   |       data             |
+----+----+----+                        +
|                                       |
~               ...                     ~
|                                       |
+----+----+----+----+----+----+----+----+

Fields:

• blk: 1 byte - Block type number
• size: 2 bytes - Big-endian size of data field (0-65516)
• data: Variable length - Block-specific data

Constraints:

• Maximum ChaChaPoly frame: 65535 bytes
• Poly1305 MAC: 16 bytes
• Maximum total blocks: 65519 bytes (65535 - 16)
• Maximum single block: 65519 bytes (including 3-byte header)
• Maximum single block data: 65516 bytes

Block Types

Defined Block Types:

Unknown Block Handling:

Implementations MUST ignore blocks with unknown type numbers and treat them as padding. This ensures forward compatibility.

Block Ordering Rules

NS Message Ordering

Required:

• DateTime block MUST be first

Allowed:

• Garlic Clove (type 11)
• Options (type 5) - if implemented
• Padding (type 254)

Prohibited:

• NextKey, ACK, ACK Request, Termination, MessageNumbers

Example Valid NS Payload:

DateTime (0) | Garlic Clove (11) | Garlic Clove (11) | Padding (254)

NSR Message Ordering

Required:

• None (payload may be empty)

Allowed:

• Garlic Clove (type 11)
• Options (type 5) - if implemented
• Padding (type 254)

Prohibited:

• DateTime, NextKey, ACK, ACK Request, Termination, MessageNumbers

Example Valid NSR Payload:

Garlic Clove (11) | Garlic Clove (11) | Padding (254)

or

(empty - ACK only)

ES Message Ordering

Required:

• None (payload may be empty)

Allowed (any order):

• Garlic Clove (type 11)
• NextKey (type 7)
• ACK (type 8)
• ACK Request (type 9)
• Termination (type 4) - if implemented
• MessageNumbers (type 6) - if implemented
• Options (type 5) - if implemented
• Padding (type 254)

Special Rules:

• Termination MUST be last block (except Padding)
• Padding MUST be last block
• Multiple Garlic Cloves allowed
• Up to 2 NextKey blocks allowed (forward and reverse)
• Multiple Padding blocks NOT allowed

Example Valid ES Payloads:

Garlic Clove (11) | ACK (8) | Padding (254)

NextKey (7) | Garlic Clove (11) | Garlic Clove (11)

NextKey (7) forward | NextKey (7) reverse | Garlic Clove (11)

ACK Request (9) | Garlic Clove (11) | Termination (4) | Padding (254)

DateTime Block (Type 0)

Purpose: Timestamp for replay prevention and clock skew validation

Size: 7 bytes (3 byte header + 4 byte data)

Format:

+----+----+----+----+----+----+----+
| 0  |    4    |     timestamp     |
+----+----+----+----+----+----+----+

Fields:

• blk: 0
• size: 4 (big-endian)
• timestamp: 4 bytes - Unix timestamp in seconds (unsigned, big-endian)

Timestamp Format:

timestamp = int(time.time())  # Seconds since 1970-01-01 00:00:00 UTC
# Wraps around in year 2106 (4-byte unsigned maximum)

Validation Rules:

MAX_CLOCK_SKEW_PAST = 5 * 60      # 5 minutes
MAX_CLOCK_SKEW_FUTURE = 2 * 60    # 2 minutes

def validate_datetime(timestamp):
    now = int(time.time())
    age = now - timestamp
    
    if age < -MAX_CLOCK_SKEW_FUTURE:
        return False  # Too far in future
    
    if age > MAX_CLOCK_SKEW_PAST:
        return False  # Too old
    
    return True

Replay Prevention:

class ReplayFilter:
    def __init__(self, duration=5*60):
        self.duration = duration  # 5 minutes
        self.seen_messages = BloomFilter(size=100000, false_positive_rate=0.001)
        self.cleanup_timer = RepeatTimer(60, self.cleanup)
    
    def check_replay(self, ephemeral_key, timestamp):
        # Check timestamp validity
        if not validate_datetime(timestamp):
            return False
        
        # Check if ephemeral key seen recently
        if ephemeral_key in self.seen_messages:
            return False  # Replay attack
        
        # Add to seen messages
        self.seen_messages.add(ephemeral_key)
        return True
    
    def cleanup(self):
        # Expire old entries (Bloom filter automatically ages out)
        pass

Implementation Notes:

1. NS Messages: DateTime MUST be first block
2. NSR/ES Messages: DateTime typically not included
3. Replay Window: 5 minutes is minimum recommended
4. Bloom Filter: Recommended for efficient replay detection
5. Clock Skew: Allow 5 minutes past, 2 minutes future

Garlic Clove Block (Type 11)

Purpose: Encapsulates I2NP messages for delivery

Format:

+----+----+----+----+----+----+----+----+
| 11 |  size   |                        |
+----+----+----+                        +
|      Delivery Instructions            |
~                                       ~
|                                       |
+----+----+----+----+----+----+----+----+
|type|  Message_ID       | Expiration  |
+----+----+----+----+----+----+----+----+
     |      I2NP Message body           |
+----+                                  +
~                                       ~
|                                       |
+----+----+----+----+----+----+----+----+

Fields:

• blk: 11
• size: Total size of clove (variable)
• Delivery Instructions: As specified in I2NP spec
• type: I2NP message type (1 byte)
• Message_ID: I2NP message ID (4 bytes)
• Expiration: Unix timestamp in seconds (4 bytes)
• I2NP Message body: Variable length message data

Delivery Instruction Formats:

Local Delivery (1 byte):

+----+
|0x00|
+----+

Destination Delivery (33 bytes):

+----+----+----+----+----+----+----+----+
|0x01|                                  |
+----+        Destination Hash         +
|              32 bytes                 |
+                                       +
|                                       |
+----+----+----+----+----+----+----+----+

Router Delivery (33 bytes):

+----+----+----+----+----+----+----+----+
|0x02|                                  |
+----+         Router Hash              +
|              32 bytes                 |
+                                       +
|                                       |
+----+----+----+----+----+----+----+----+

Tunnel Delivery (37 bytes):

+----+----+----+----+----+----+----+----+
|0x03|         Tunnel ID                |
+----+----+----+----+----+              +
|           Router Hash                 |
+              32 bytes                 +
|                                       |
+                                       +
|                                       |
+----+----+----+----+----+----+----+----+

I2NP Message Header (9 bytes total):

+----+----+----+----+----+----+----+----+
|type|      msg_id       |  expiration   |
+----+----+----+----+----+----+----+----+
     |                                   |

• type: I2NP message type (Database Store, Database Lookup, Data, etc.)
• msg_id: 4-byte message identifier
• expiration: 4-byte Unix timestamp (seconds)

Important Differences from ElGamal Clove Format:

1. No Certificate: Certificate field omitted (unused in ElGamal)
2. No Clove ID: Clove ID omitted (was always 0)
3. No Clove Expiration: Uses I2NP message expiration instead
4. Compact Header: 9-byte I2NP header vs larger ElGamal format
5. Each Clove is Separate Block: No CloveSet structure

Multiple Cloves:

# Multiple Garlic Cloves in one message
payload = [
    build_datetime_block(),
    build_garlic_clove(i2np_message_1),
    build_garlic_clove(i2np_message_2),
    build_garlic_clove(i2np_message_3),
    build_padding_block()
]

Common I2NP Message Types in Cloves:

Clove Processing:

def process_garlic_clove(clove_data):
    # Parse delivery instructions
    delivery_type = clove_data[0]
    
    if delivery_type == 0x00:
        # Local delivery
        offset = 1
    elif delivery_type == 0x01:
        # Destination delivery
        dest_hash = clove_data[1:33]
        offset = 33
    elif delivery_type == 0x02:
        # Router delivery
        router_hash = clove_data[1:33]
        offset = 33
    elif delivery_type == 0x03:
        # Tunnel delivery
        tunnel_id = struct.unpack('>I', clove_data[1:5])[0]
        router_hash = clove_data[5:37]
        offset = 37
    
    # Parse I2NP header
    i2np_type = clove_data[offset]
    msg_id = struct.unpack('>I', clove_data[offset+1:offset+5])[0]
    expiration = struct.unpack('>I', clove_data[offset+5:offset+9])[0]
    
    # Extract I2NP body
    i2np_body = clove_data[offset+9:]
    
    # Process message
    process_i2np_message(i2np_type, msg_id, expiration, i2np_body)

NextKey Block (Type 7)

Purpose: DH ratchet key exchange

Format (Key Present - 38 bytes):

+----+----+----+----+----+----+----+----+
| 7  |   35    |flag|  key ID |         |
+----+----+----+----+----+----+         +
|                                       |
+     Next DH Ratchet Public Key        +
|              32 bytes                 |
+                                       +
|                                       |
+                             +----+----+
|                             |
+----+----+----+----+----+----+

Format (Key ID Only - 6 bytes):

+----+----+----+----+----+----+
| 7  |    3    |flag|  key ID |
+----+----+----+----+----+----+

Fields:

• blk: 7
• size: 3 (ID only) or 35 (with key)
• flag: 1 byte - Flag bits
• key ID: 2 bytes - Big-endian key identifier (0-32767)
• Public Key: 32 bytes - X25519 public key (little-endian), if flag bit 0 = 1

Flag Bits:

Bit 7 6 5 4 3 2 1 0
    | | | | | | | |
    | | | | | | | +-- Bit 0: Key present (1) or ID only (0)
    | | | | | | +---- Bit 1: Reverse key (1) or forward key (0)
    | | | | | +------ Bit 2: Request reverse key (1) or no request (0)
    | | | | |
    +-+-+-+-+-------- Bits 3-7: Reserved (set to 0)

Flag Examples:

# Forward key present
flags = 0x01  # Binary: 00000001

# Reverse key present
flags = 0x03  # Binary: 00000011

# Forward key ID only (ACK)
flags = 0x00  # Binary: 00000000

# Reverse key ID only (ACK)
flags = 0x02  # Binary: 00000010

# Forward key ID with reverse request
flags = 0x04  # Binary: 00000100

Key ID Rules:

• IDs are sequential: 0, 1, 2, …, 32767
• ID increments only when new key generated
• Same ID used for multiple messages until next ratchet
• Maximum ID is 32767 (must start new session after)

Usage Examples:

# Initiating ratchet (sender generates new key)
nextkey = NextKeyBlock(
    flags=0x01,           # Key present, forward
    key_id=0,
    public_key=sender_new_pk
)

# Replying to ratchet (receiver generates new key)
nextkey = NextKeyBlock(
    flags=0x03,           # Key present, reverse
    key_id=0,
    public_key=receiver_new_pk
)

# Acknowledging ratchet (no new key from sender)
nextkey = NextKeyBlock(
    flags=0x02,           # ID only, reverse
    key_id=0
)

# Requesting reverse ratchet
nextkey = NextKeyBlock(
    flags=0x04,           # Request reverse, forward ID
    key_id=1
)

Processing Logic:

def process_nextkey_block(block):
    flags = block.flags
    key_id = block.key_id
    
    key_present = (flags & 0x01) != 0
    is_reverse = (flags & 0x02) != 0
    request_reverse = (flags & 0x04) != 0
    
    if key_present:
        public_key = block.public_key
        
        if is_reverse:
            # Reverse key received
            perform_dh_ratchet(receiver_key=public_key, key_id=key_id)
            # Sender should ACK with own key ID
        else:
            # Forward key received
            perform_dh_ratchet(sender_key=public_key, key_id=key_id)
            # Receiver should reply with reverse key
            send_reverse_key(generate_new_key())
    
    else:
        # Key ID only (ACK)
        if is_reverse:
            # Reverse key ACK
            confirm_reverse_ratchet(key_id)
        else:
            # Forward key ACK
            confirm_forward_ratchet(key_id)
    
    if request_reverse:
        # Sender requests receiver to generate new key
        send_reverse_key(generate_new_key())

Multiple NextKey Blocks:

A single ES message may contain up to 2 NextKey blocks when both directions are ratcheting simultaneously:

# Both directions ratcheting
payload = [
    NextKeyBlock(flags=0x01, key_id=2, public_key=forward_key),  # Forward
    NextKeyBlock(flags=0x03, key_id=1, public_key=reverse_key),  # Reverse
    build_garlic_clove(data)
]

ACK Block (Type 8)

Purpose: Acknowledge received messages in-band

Format (Single ACK - 7 bytes):

+----+----+----+----+----+----+----+
| 8  |    4    |tagsetid |   N     |
+----+----+----+----+----+----+----+

Format (Multiple ACKs):

+----+----+----+----+----+----+----+----+
| 8  |  size   |tagsetid |   N     |    |
+----+----+----+----+----+----+----+    +
|            more ACKs                  |
~               ...                     ~
|                                       |
+----+----+----+----+----+----+----+----+

Fields:

• blk: 8
• size: 4 * number of ACKs (minimum 4)
• For each ACK:
  • tagsetid: 2 bytes - Big-endian tag set ID (0-65535)
  • N: 2 bytes - Big-endian message number (0-65535)

Tag Set ID Determination:

# Tag set 0 (initial, after NSR)
tagset_id = 0

# After first ratchet (tag set 1)
# Both Alice and Bob sent key ID 0
tagset_id = 1 + 0 + 0 = 1

# After second ratchet (tag set 2)
# Alice sent key ID 1, Bob still using key ID 0
tagset_id = 1 + 1 + 0 = 2

# After third ratchet (tag set 3)
# Alice still using key ID 1, Bob sent key ID 1
tagset_id = 1 + 1 + 1 = 3

Single ACK Example:

# ACK message from tag set 5, message number 127
ack_block = ACKBlock(
    tagset_id=5,
    message_number=127
)

# Wire format (7 bytes):
# 08 00 04 00 05 00 7F
# |  |  |  |  |  |  |
# |  |  |  |  |  |  +-- N (127)
# |  |  |  |  +--------- N high byte
# |  |  |  +------------ tagset_id (5)
# |  |  +--------------- tagset_id high byte
# |  +------------------ size (4)
# +--------------------- type (8)

Multiple ACKs Example:

# ACK three messages
ack_block = ACKBlock([
    (tagset_id=3, N=42),
    (tagset_id=3, N=43),
    (tagset_id=4, N=0)
])

# Wire format (15 bytes):
# 08 00 0C 00 03 00 2A 00 03 00 2B 00 04 00 00
#                (ts=3, N=42) (ts=3, N=43) (ts=4, N=0)

Processing:

def process_ack_block(block):
    num_acks = block.size // 4
    
    for i in range(num_acks):
        offset = i * 4
        tagset_id = struct.unpack('>H', block.data[offset:offset+2])[0]
        message_num = struct.unpack('>H', block.data[offset+2:offset+4])[0]
        
        # Mark message as acknowledged
        mark_acked(tagset_id, message_num)
        
        # May trigger retransmission timeout cancellation
        cancel_retransmit_timer(tagset_id, message_num)

When to Send ACKs:

1. Explicit ACK Request: Always respond to ACK Request block
2. LeaseSet Delivery: When sender includes LeaseSet in message
3. Session Establishment: May ACK NS/NSR (though protocol prefers implicit ACK via ES)
4. Ratchet Confirmation: May ACK NextKey receipt
5. Application Layer: As required by higher layer protocol (e.g., Streaming)

ACK Timing:

class ACKManager:
    def __init__(self):
        self.pending_acks = []
        self.ack_timer = None
    
    def request_ack(self, tagset_id, message_num):
        self.pending_acks.append((tagset_id, message_num))
        
        if not self.ack_timer:
            # Delay ACK briefly to allow higher layer to respond
            self.ack_timer = set_timer(0.1, self.send_acks)  # 100ms
    
    def send_acks(self):
        if self.pending_acks and not has_outbound_data():
            # No higher layer data, send explicit ACK
            send_es_message(build_ack_block(self.pending_acks))
        
        # Otherwise, ACK will piggyback on next ES message
        self.pending_acks = []
        self.ack_timer = None

ACK Request Block (Type 9)

Purpose: Request in-band acknowledgment of current message

Format:

+----+----+----+----+
| 9  |    1    |flg |
+----+----+----+----+

Fields:

• blk: 9
• size: 1
• flg: 1 byte - Flags (all bits currently unused, set to 0)

Usage:

# Request ACK for this message
payload = [
    build_ack_request_block(),
    build_garlic_clove(important_data)
]

Receiver Response:

When ACK Request is received:

1. With Immediate Data: Include ACK block in immediate response
2. Without Immediate Data: Start timer (e.g., 100ms) and send empty ES with ACK if timer expires
3. Tag Set ID: Use current inbound tagset ID
4. Message Number: Use message number associated with received session tag

Processing:

def process_ack_request(message):
    # Extract message identification
    tagset_id = message.tagset_id
    message_num = message.message_num
    
    # Schedule ACK
    schedule_ack(tagset_id, message_num)
    
    # If no data to send immediately, start timer
    if not has_pending_data():
        set_timer(0.1, lambda: send_ack_only(tagset_id, message_num))

When to Use ACK Request:

1. Critical Messages: Messages that must be acknowledged
2. LeaseSet Delivery: When bundling a LeaseSet
3. Session Ratchet: After sending NextKey block
4. End of Transmission: When sender has no more data to send but wants confirmation

When NOT to Use:

1. Streaming Protocol: Streaming layer handles ACKs
2. High Frequency Messages: Avoid ACK Request on every message (overhead)
3. Unimportant Datagrams: Raw datagrams typically don’t need ACKs

Termination Block (Type 4)

Status: UNIMPLEMENTED

Purpose: Gracefully terminate session

Format:

+----+----+----+----+----+----+----+----+
| 4  |  size   | rsn|     addl data     |
+----+----+----+----+                   +
~               ...                     ~
+----+----+----+----+----+----+----+----+

Fields:

• blk: 4
• size: 1 or more bytes
• rsn: 1 byte - Reason code
• addl data: Optional additional data (format depends on reason)

Reason Codes:

Usage (when implemented):

# Normal session close
termination = TerminationBlock(
    reason=0,
    additional_data=b''
)

# Session termination due to received termination
termination = TerminationBlock(
    reason=1,
    additional_data=b''
)

Rules:

• MUST be last block except for Padding
• Padding MUST follow Termination if present
• Not allowed in NS or NSR messages
• Only allowed in ES messages

Options Block (Type 5)

Status: UNIMPLEMENTED

Purpose: Negotiate session parameters

Format:

+----+----+----+----+----+----+----+----+
| 5  |  size   |ver |flg |STL |STimeout |
+----+----+----+----+----+----+----+----+
|  SOTW   |  RITW   |tmin|tmax|rmin|rmax|
+----+----+----+----+----+----+----+----+
|  tdmy   |  rdmy   |  tdelay |  rdelay |
+----+----+----+----+----+----+----+----+
|              more_options             |
~               ...                     ~
|                                       |
+----+----+----+----+----+----+----+----+

Fields:

• blk: 5
• size: 21 or more bytes
• ver: 1 byte - Protocol version (must be 0)
• flg: 1 byte - Flags (all bits currently unused)
• STL: 1 byte - Session tag length (must be 8)
• STimeout: 2 bytes - Session idle timeout in seconds (big-endian)
• SOTW: 2 bytes - Sender Outbound Tag Window (big-endian)
• RITW: 2 bytes - Receiver Inbound Tag Window (big-endian)
• tmin, tmax, rmin, rmax: 1 byte each - Padding parameters (4.4 fixed-point)
• tdmy: 2 bytes - Max dummy traffic willing to send (bytes/sec, big-endian)
• rdmy: 2 bytes - Requested dummy traffic (bytes/sec, big-endian)
• tdelay: 2 bytes - Max intra-message delay willing to insert (msec, big-endian)
• rdelay: 2 bytes - Requested intra-message delay (msec, big-endian)
• more_options: Variable - Future extensions

Padding Parameters (4.4 Fixed-Point):

def encode_padding_ratio(ratio):
    """
    Encode padding ratio as 4.4 fixed-point
    
    ratio: 0.0 to 15.9375
    returns: 0x00 to 0xFF
    """
    return int(ratio * 16)

def decode_padding_ratio(encoded):
    """
    Decode 4.4 fixed-point to ratio
    
    encoded: 0x00 to 0xFF
    returns: 0.0 to 15.9375
    """
    return encoded / 16.0

# Examples:
# 0x00 = 0.0 (no padding)
# 0x01 = 0.0625 (6.25% padding)
# 0x10 = 1.0 (100% padding - double traffic)
# 0x80 = 8.0 (800% padding - 9x traffic)
# 0xFF = 15.9375 (1593.75% padding)

Tag Window Negotiation:

# SOTW: Sender's recommendation for receiver's inbound window
# RITW: Sender's declaration of own inbound window

# Receiver calculates actual inbound window:
inbound_window = calculate_window(
    sender_suggestion=SOTW,
    own_constraints=MAX_INBOUND_TAGS,
    own_resources=available_memory()
)

# Sender uses:
# - RITW to know how far ahead receiver will accept
# - Own SOTW to hint optimal window size

Default Values (when Options not negotiated):

DEFAULT_OPTIONS = {
    'version': 0,
    'session_tag_length': 8,
    'session_timeout': 600,  # 10 minutes
    'sender_outbound_tag_window': 160,
    'receiver_inbound_tag_window': 160,
    'tmin': 0x00,  # No minimum padding
    'tmax': 0x10,  # Up to 100% padding
    'rmin': 0x00,  # No minimum requested
    'rmax': 0x10,  # Up to 100% requested
    'tdmy': 0,     # No dummy traffic
    'rdmy': 0,     # No dummy traffic requested
    'tdelay': 0,   # No delay
    'rdelay': 0    # No delay requested
}

MessageNumbers Block (Type 6)

Status: UNIMPLEMENTED

Purpose: Indicate last message sent in previous tag set (enables gap detection)

Format:

+----+----+----+----+----+
| 6  |    2    |  PN    |
+----+----+----+----+----+

Fields:

• blk: 6
• size: 2
• PN: 2 bytes - Previous tag set last message number (big-endian, 0-65535)

PN (Previous Number) Definition:

PN is the index of the last tag sent in the previous tag set.

Usage (when implemented):

# After ratcheting to new tag set
# Old tag set: sent messages 0-4095
# New tag set: sending first message

payload = [
    MessageNumbersBlock(PN=4095),
    build_garlic_clove(data)
]

Receiver Benefits:

def process_message_numbers(pn_value):
    # Receiver can now:
    
    # 1. Determine if any messages were skipped
    highest_received_in_old_tagset = 4090
    if pn_value > highest_received_in_old_tagset:
        missing_count = pn_value - highest_received_in_old_tagset
        # 5 messages were never received
    
    # 2. Delete tags higher than PN from old tagset
    for tag_index in range(pn_value + 1, MAX_TAG_INDEX):
        delete_tag(old_tagset, tag_index)
    
    # 3. Expire tags ≤ PN after grace period (e.g., 2 minutes)
    schedule_deletion(old_tagset, delay=120)

Rules:

• MUST NOT be sent in tag set 0 (no previous tag set)
• Only sent in ES messages
• Only sent in first message(s) of new tag set
• PN value is from sender’s perspective (last tag sender sent)

Relationship to Signal:

In Signal Double Ratchet, PN is in the message header. In ECIES, it’s in the encrypted payload and is optional.

Padding Block (Type 254)

Purpose: Traffic analysis resistance and message size obfuscation

Format:

+----+----+----+----+----+----+----+----+
|254 |  size   |      padding           |
+----+----+----+                        +
|                                       |
~               ...                     ~
|                                       |
+----+----+----+----+----+----+----+----+

Fields:

• blk: 254
• size: 0-65516 bytes (big-endian)
• padding: Random or zero data

Rules:

• MUST be last block in message
• Multiple Padding blocks NOT allowed
• May be zero length (3-byte header only)
• Padding data may be zeros or random bytes

Default Padding:

DEFAULT_PADDING_MIN = 0
DEFAULT_PADDING_MAX = 15

def generate_default_padding():
    size = random.randint(DEFAULT_PADDING_MIN, DEFAULT_PADDING_MAX)
    data = random.bytes(size)  # or zeros
    return PaddingBlock(size, data)

Traffic Analysis Resistance Strategies:

Strategy 1: Random Size (Default)

# Add 0-15 bytes random padding to each message
padding_size = random.randint(0, 15)
padding_block = PaddingBlock(padding_size, random.bytes(padding_size))

Strategy 2: Round to Multiple

# Round total message size to next multiple of 64
target_size = ((message_size + 63) // 64) * 64
padding_size = target_size - message_size - 3  # -3 for block header
padding_block = PaddingBlock(padding_size, random.bytes(padding_size))

Strategy 3: Fixed Message Sizes

# Always send 1KB messages
TARGET_MESSAGE_SIZE = 1024
padding_size = TARGET_MESSAGE_SIZE - message_size - 3
padding_block = PaddingBlock(padding_size, random.bytes(padding_size))

Strategy 4: Negotiated Padding (Options block)

# Calculate padding based on negotiated parameters
# tmin, tmax from Options block
min_padding = int(payload_size * tmin_ratio)
max_padding = int(payload_size * tmax_ratio)
padding_size = random.randint(min_padding, max_padding)
padding_block = PaddingBlock(padding_size, random.bytes(padding_size))

Padding-Only Messages:

Messages may consist entirely of padding (no application data):

# Dummy traffic message
payload = [
    PaddingBlock(random.randint(100, 500), random.bytes(...))
]

Implementation Notes:

1. All-Zero Padding: Acceptable (will be encrypted by ChaCha20)
2. Random Padding: Provides no additional security after encryption but uses more entropy
3. Performance: Random padding generation may be expensive; consider using zeros
4. Memory: Large padding blocks consume bandwidth; be cautious with maximum size

Implementation Guide

Prerequisites

Cryptographic Libraries:

• X25519: libsodium, NaCl, or Bouncy Castle
• ChaCha20-Poly1305: libsodium, OpenSSL 1.1.0+, or Bouncy Castle
• SHA-256: OpenSSL, Bouncy Castle, or built-in language support
• Elligator2: Limited library support; may require custom implementation

Elligator2 Implementation:

Elligator2 is not widely implemented. Options:

1. OBFS4: Tor’s obfs4 pluggable transport includes Elligator2 implementation
2. Custom Implementation: Based on Elligator2 paper
3. kleshni/Elligator: Reference implementation on GitHub

Java I2P Note: Java I2P uses net.i2p.crypto.eddsa library with custom Elligator2 additions.

Recommended Implementation Order

Phase 1: Core Cryptography

1. X25519 DH key generation and exchange
2. ChaCha20-Poly1305 AEAD encryption/decryption
3. SHA-256 hashing and MixHash
4. HKDF key derivation
5. Elligator2 encoding/decoding (can use test vectors initially)

Phase 2: Message Formats

1. NS message (unbound) - simplest format
2. NS message (bound) - adds static key
3. NSR message
4. ES message
5. Block parsing and generation

Phase 3: Session Management

1. Session creation and storage
2. Tag set management (sender and receiver)
3. Session tag ratchet
4. Symmetric key ratchet
5. Tag lookup and window management

Phase 4: DH Ratcheting

1. NextKey block handling
2. DH ratchet KDF
3. Tag set creation after ratchet
4. Multiple tag set management

Phase 5: Protocol Logic

1. NS/NSR/ES state machine
2. Replay prevention (DateTime, Bloom filter)
3. Retransmission logic (multiple NS/NSR)
4. ACK handling

Phase 6: Integration

1. I2NP Garlic Clove processing
2. LeaseSet bundling
3. Streaming protocol integration
4. Datagram protocol integration

Sender Implementation

Outbound Session Lifecycle:

class OutboundSession:
    def __init__(self, destination, bound=True):
        self.destination = destination
        self.bound = bound
        self.state = SessionState.NEW
        
        # Keys for NS message
        self.ephemeral_keypair = generate_elg2_keypair()
        if bound:
            self.static_key = context.static_keypair
        
        # Will be populated after NSR
        self.outbound_tagset = None
        self.outbound_keyratchet = None
        self.inbound_tagset = None
        self.inbound_keyratchet = None
        
        # Timing
        self.created_time = now()
        self.last_activity = now()
        
        # Retransmission
        self.ns_attempts = []
        self.ns_timer = None
    
    def send_initial_message(self, payload):
        """Send NS message"""
        # Build NS message
        ns_message = self.build_ns_message(payload)
        
        # Send
        send_to_network(self.destination, ns_message)
        
        # Track for retransmission
        self.ns_attempts.append({
            'message': ns_message,
            'time': now(),
            'ephemeral_key': self.ephemeral_keypair,
            'kdf_state': self.save_kdf_state()
        })
        
        # Start timer
        self.ns_timer = set_timer(1.0, self.on_ns_timeout)
        self.state = SessionState.PENDING_REPLY
    
    def build_ns_message(self, payload):
        """Construct NS message"""
        # KDF initialization
        chainKey, h = self.initialize_kdf()
        
        # Ephemeral key section
        elg2_ephemeral = ENCODE_ELG2(self.ephemeral_keypair.public_key)
        h = SHA256(h || self.destination.static_key)
        h = SHA256(h || self.ephemeral_keypair.public_key)
        
        # es DH
        es_shared = DH(self.ephemeral_keypair.private_key, 
                       self.destination.static_key)
        keydata = HKDF(chainKey, es_shared, "", 64)
        chainKey = keydata[0:31]
        k_static = keydata[32:63]
        
        # Encrypt static key section
        if self.bound:
            static_section = self.static_key.public_key
        else:
            static_section = bytes(32)
        
        static_ciphertext = ENCRYPT(k_static, 0, static_section, h)
        h = SHA256(h || static_ciphertext)
        
        # ss DH (if bound)
        if self.bound:
            ss_shared = DH(self.static_key.private_key, 
                          self.destination.static_key)
            keydata = HKDF(chainKey, ss_shared, "", 64)
            chainKey = keydata[0:31]
            k_payload = keydata[32:63]
            nonce = 0
        else:
            k_payload = k_static
            nonce = 1
        
        # Build payload blocks
        payload_data = self.build_ns_payload(payload)
        
        # Encrypt payload
        payload_ciphertext = ENCRYPT(k_payload, nonce, payload_data, h)
        h = SHA256(h || payload_ciphertext)
        
        # Save KDF state for NSR processing
        self.ns_chainkey = chainKey
        self.ns_hash = h
        
        # Assemble message
        return elg2_ephemeral + static_ciphertext + payload_ciphertext
    
    def build_ns_payload(self, application_data):
        """Build NS payload blocks"""
        blocks = []
        
        # DateTime block (required, first)
        blocks.append(build_datetime_block())
        
        # Garlic Clove(s) with application data
        blocks.append(build_garlic_clove(application_data))
        
        # Optionally bundle LeaseSet
        if should_send_leaseset():
            blocks.append(build_garlic_clove(build_leaseset_store()))
        
        # Padding
        blocks.append(build_padding_block(random.randint(0, 15)))
        
        return encode_blocks(blocks)
    
    def on_nsr_received(self, nsr_message):
        """Process NSR and establish ES session"""
        # Cancel retransmission timer
        cancel_timer(self.ns_timer)
        
        # Parse NSR
        tag = nsr_message[0:8]
        elg2_bob_ephemeral = nsr_message[8:40]
        key_section_mac = nsr_message[40:56]
        payload_ciphertext = nsr_message[56:]
        
        # Find corresponding NS attempt
        ns_state = self.find_ns_by_tag(tag)
        if not ns_state:
            raise ValueError("NSR tag doesn't match any NS")
        
        # Restore KDF state
        chainKey = ns_state['chainkey']
        h = ns_state['hash']
        
        # Decode Bob's ephemeral key
        bob_ephemeral = DECODE_ELG2(elg2_bob_ephemeral)
        
        # Mix tag and Bob's ephemeral into hash
        h = SHA256(h || tag)
        h = SHA256(h || bob_ephemeral)
        
        # ee DH
        ee_shared = DH(self.ephemeral_keypair.private_key, bob_ephemeral)
        keydata = HKDF(chainKey, ee_shared, "", 32)
        chainKey = keydata[0:31]
        
        # se DH
        se_shared = DH(self.static_key.private_key, bob_ephemeral)
        keydata = HKDF(chainKey, se_shared, "", 64)
        chainKey = keydata[0:31]
        k_key_section = keydata[32:63]
        
        # Verify key section MAC
        try:
            DECRYPT(k_key_section, 0, key_section_mac, h)
        except AuthenticationError:
            raise ValueError("NSR key section MAC verification failed")
        
        h = SHA256(h || key_section_mac)
        
        # Split for bidirectional ES
        keydata = HKDF(chainKey, ZEROLEN, "", 64)
        k_ab = keydata[0:31]  # Alice → Bob
        k_ba = keydata[32:63]  # Bob → Alice
        
        # Initialize ES tagsets
        self.outbound_tagset = DH_INITIALIZE(chainKey, k_ab)
        self.inbound_tagset = DH_INITIALIZE(chainKey, k_ba)
        
        # Decrypt NSR payload
        k_nsr = HKDF(k_ba, ZEROLEN, "AttachPayloadKDF", 32)
        try:
            payload = DECRYPT(k_nsr, 0, payload_ciphertext, h)
        except AuthenticationError:
            raise ValueError("NSR payload MAC verification failed")
        
        # Process NSR payload blocks
        self.process_payload_blocks(payload)
        
        # Session established
        self.state = SessionState.ESTABLISHED
        self.last_activity = now()
        
        # Send ES message (implicit ACK)
        self.send_es_ack()
    
    def send_es_message(self, payload):
        """Send ES message"""
        if self.state != SessionState.ESTABLISHED:
            raise ValueError("Session not established")
        
        # Get next tag and key
        tag, index = self.outbound_tagset.get_next_tag()
        key = self.outbound_keyratchet.get_key(index)
        
        # Construct nonce
        nonce = construct_nonce(index)
        
        # Build payload blocks
        payload_data = self.build_es_payload(payload)
        
        # AEAD encryption
        ciphertext = ENCRYPT(key, nonce, payload_data, tag)
        
        # Assemble message
        es_message = tag + ciphertext
        
        # Send
        send_to_network(self.destination, es_message)
        
        # Update activity
        self.last_activity = now()
        
        # Check if ratchet needed
        if self.outbound_tagset.should_ratchet():
            self.initiate_ratchet()

Receiver Implementation

Inbound Session Lifecycle:

class InboundSession:
    def __init__(self):
        self.state = None
        self.bound = False
        self.destination = None
        
        # Keys
        self.remote_ephemeral_key = None
        self.remote_static_key = None
        self.ephemeral_keypair = None
        
        # Tagsets
        self.inbound_tagset = None
        self.outbound_tagset = None
        
        # Timing
        self.created_time = None
        self.last_activity = None
        
        # Paired session
        self.paired_outbound = None
    
    @staticmethod
    def try_decrypt_ns(message):
        """Attempt to decrypt as NS message"""
        # Parse NS structure
        elg2_ephemeral = message[0:32]
        static_ciphertext = message[32:80]  # 32 + 16
        payload_ciphertext = message[80:]
        
        # Decode ephemeral key
        try:
            alice_ephemeral = DECODE_ELG2(elg2_ephemeral)
        except:
            return None  # Not a valid Elligator2 encoding
        
        # Check replay
        if is_replay(alice_ephemeral):
            return None
        
        # KDF initialization
        chainKey, h = initialize_kdf()
        
        # Mix keys
        h = SHA256(h || context.static_keypair.public_key)
        h = SHA256(h || alice_ephemeral)
        
        # es DH
        es_shared = DH(context.static_keypair.private_key, alice_ephemeral)
        keydata = HKDF(chainKey, es_shared, "", 64)
        chainKey = keydata[0:31]
        k_static = keydata[32:63]
        
        # Decrypt static key section
        try:
            static_data = DECRYPT(k_static, 0, static_ciphertext, h)
        except AuthenticationError:
            return None  # Not a valid NS message
        
        h = SHA256(h || static_ciphertext)
        
        # Check if bound or unbound
        if static_data == bytes(32):
            # Unbound
            alice_static_key = None
            k_payload = k_static
            nonce = 1
        else:
            # Bound - perform ss DH
            alice_static_key = static_data
            ss_shared = DH(context.static_keypair.private_key, alice_static_key)
            keydata = HKDF(chainKey, ss_shared, "", 64)
            chainKey = keydata[0:31]
            k_payload = keydata[32:63]
            nonce = 0
        
        # Decrypt payload
        try:
            payload = DECRYPT(k_payload, nonce, payload_ciphertext, h)
        except AuthenticationError:
            return None
        
        h = SHA256(h || payload_ciphertext)
        
        # Create session
        session = InboundSession()
        session.state = SessionState.ESTABLISHED
        session.created_time = now()
        session.last_activity = now()
        session.remote_ephemeral_key = alice_ephemeral
        session.remote_static_key = alice_static_key
        session.bound = (alice_static_key is not None)
        session.ns_chainkey = chainKey
        session.ns_hash = h
        
        # Extract destination if bound
        if session.bound:
            session.destination = extract_destination_from_payload(payload)
        
        # Process payload
        session.process_payload_blocks(payload)
        
        return session
    
    def send_nsr_reply(self, reply_payload):
        """Send NSR message"""
        # Generate NSR tagset
        tagsetKey = HKDF(self.ns_chainkey, ZEROLEN, "SessionReplyTags", 32)
        nsr_tagset = DH_INITIALIZE(self.ns_chainkey, tagsetKey)
        
        # Get tag
        tag, _ = nsr_tagset.get_next_tag()
        
        # Mix tag into hash
        h = SHA256(self.ns_hash || tag)
        
        # Generate ephemeral key
        self.ephemeral_keypair = generate_elg2_keypair()
        bob_ephemeral = self.ephemeral_keypair.public_key
        elg2_bob_ephemeral = ENCODE_ELG2(bob_ephemeral)
        
        # Mix ephemeral key
        h = SHA256(h || bob_ephemeral)
        
        chainKey = self.ns_chainkey
        
        # ee DH
        ee_shared = DH(self.ephemeral_keypair.private_key, 
                      self.remote_ephemeral_key)
        keydata = HKDF(chainKey, ee_shared, "", 32)
        chainKey = keydata[0:31]
        
        # se DH
        se_shared = DH(context.static_keypair.private_key, 
                      self.remote_ephemeral_key)
        keydata = HKDF(chainKey, se_shared, "", 64)
        chainKey = keydata[0:31]
        k_key_section = keydata[32:63]
        
        # Encrypt key section (empty)
        key_section_ciphertext = ENCRYPT(k_key_section, 0, ZEROLEN, h)
        h = SHA256(h || key_section_ciphertext)
        
        # Split for bidirectional ES
        keydata = HKDF(chainKey, ZEROLEN, "", 64)
        k_ab = keydata[0:31]  # Alice → Bob
        k_ba = keydata[32:63]  # Bob → Alice
        
        # Initialize ES tagsets
        self.inbound_tagset = DH_INITIALIZE(chainKey, k_ab)
        self.outbound_tagset = DH_INITIALIZE(chainKey, k_ba)
        
        # Build reply payload
        payload_data = build_payload_blocks(reply_payload)
        
        # Encrypt payload
        k_nsr = HKDF(k_ba, ZEROLEN, "AttachPayloadKDF", 32)
        payload_ciphertext = ENCRYPT(k_nsr, 0, payload_data, h)
        
        # Assemble NSR
        nsr_message = tag + elg2_bob_ephemeral + key_section_ciphertext + payload_ciphertext
        
        # Send
        send_to_network(self.destination, nsr_message)
        
        # Wait for ES
        self.state = SessionState.AWAITING_ES
        self.last_activity = now()
    
    def on_es_received(self, es_message):
        """Process first ES message"""
        if self.state == SessionState.AWAITING_ES:
            # First ES received, confirms session
            self.state = SessionState.ESTABLISHED
        
        # Process ES message
        self.process_es_message(es_message)
    
    def process_es_message(self, es_message):
        """Decrypt and process ES message"""
        # Extract tag
        tag = es_message[0:8]
        ciphertext = es_message[8:]
        
        # Look up tag
        index = self.inbound_tagset.lookup_tag(tag)
        if index is None:
            raise ValueError("Tag not found")
        
        # Get key
        key = self.inbound_keyratchet.get_key(index)
        
        # Construct nonce
        nonce = construct_nonce(index)
        
        # Decrypt
        try:
            payload = DECRYPT(key, nonce, ciphertext, tag)
        except AuthenticationError:
            raise ValueError("ES MAC verification failed")
        
        # Process blocks
        self.process_payload_blocks(payload)
        
        # Update activity
        self.last_activity = now()