1 - Wire protocol

1.2 Key Encapsulation Mechanism

2. Core Protocol

2.1 Handshake Phase

2.1.1 Handshake Authentication

2.2 Data Transfer Phase

3. Predefined Commands

3.1 The no_op Command

3.2 The disconnect Command

3.3 The send_packet Command

4. Command Padding

5. Anonymity Considerations

6. Security Considerations

1.1 Conventions Used in This Document

The key words “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “MAY”, and “OPTIONAL” in this document are to be interpreted as described in the section called “References”.

The “C” style Presentation Language as described in the section called “References” Section 4 is used to represent data structures, except for cryptographic attributes, which are specified as opaque byte vectors.

x | y denotes the concatenation of x and y.

1. Introduction

The Katzenpost Mix Network Wire Protocol (KMNWP) is the custom wire protocol for all network communications to, from, and within the Katzenpost Mix Network. This protocol provides mutual authentication, and an additional layer of cryptographic security and forward secrecy.

1.2 Key Encapsulation Mechanism

This protocol uses ANY Key Encapsulation Mechanism. However it’s recommended that most users select a hybrid post quantum KEM such as Xwing. the section called “References”

2. Core Protocol

The protocol is based on Kyber and Trevor Perrin’s Noise Protocol Framework the section called “References” along with “Post Quantum Noise” paper PQNOISE. Older previous versions of our transport were based on NOISEHFS.

Our transport protocol begins with a prologue, Noise handshake, followed by a stream of Noise Transport messages in a minimal framing layer, over a TCP/IP connection.

Our Noise protocol is configurable via the KEM selection in the TOML configuration files, here’s an example PQ Noise protocol string:

Noise_pqXX_Xwing_ChaChaPoly_BLAKE2b

The protocol string is a very condensed description of our protocol. We use the pqXX two way Noise pattern which is described as follows:

pqXX: -> e <- ekem, s -> skem, s <- skem

The next part of the protocol string specifies the KEM, Xwing which is a hybrid KEM where the share secret outputs of both X25519 and MLKEM768 are combined.

Finally the ChaChaPoly_BLAKE2b parts of the protocol string indicate which stream cipher and hash function we are using.

As a non-standard modification to the Noise protocol, the 65535 byte message length limit is increased to 1300000 bytes. We send very large messages over our Noise protocol because of our using the Sphincs+ signature scheme which has signatures that are about 49k bytes.

It is assumed that all parties using the KMNWP protocol have a fixed long or short lived Xwing keypair XWING, the public component of which is known to the other party in advance. How such keys are distributed is beyond the scope of this document.

2.1 Handshake Phase

All sessions start in the Handshake Phase, in which an anonymous authenticated handshake is conducted.

The handshake is a unmodified Noise handshake, with a fixed prologue prefacing the initiator’s first Noise handshake message. This prologue is also used as the prologue input to the Noise HandshakeState Initialize() operation for both the initiator and responder.

The prologue is defined to be the following structure:

struct {
uint8_t protocol_version; /* 0x03 */
} Prologue;

As all Noise handshake messages are fixed sizes, no additional framing is required for the handshake.

Implementations MUST preserve the Noise handshake hash [h] for the purpose of implementing authentication (Section 2.3).

Implementations MUST reject handshake attempts by terminating the session immediately upon any Noise protocol handshake failure and when, as a responder, they receive a Prologue containing an unknown protocol_version value.

Implementations SHOULD impose reasonable timeouts for the handshake process, and SHOULD terminate sessions that are taking too long to handshake.

2.1.1 Handshake Authentication

Mutual authentication is done via exchanging fixed sized payloads as part of the pqXX handshake consisting of the following structure:

struct {
uint8_t ad_len;
opaque additional_data[ad_len];
opaque padding[255 - ad_len];
uint32_t unix_time;
} AuthenticateMessage;

Where:

ad_len - The length of the optional additional data.
additional_data - Optional additional data, such as a username, if any.
unix_time - 0 for the initiator, the approximate number of seconds since 1970-01-01 00:00:00 UTC for the responder.

The initiator MUST send the AuthenticateMessage after it has received the peer’s response (so after -> s, se in Noise parlance).

The contents of the optional additional_data field is deliberately left up to the implementation, however it is RECOMMENDED that implementations pad the field to be a consistent length regardless of contents to avoid leaking information about the authenticating identity.

To authenticate the remote peer given an AuthenticateMessage, the receiving peer must validate the s component of the Noise handshake (the remote peer’s long term public key) with the known value, along with any of the information in the additional_data field such as the user name, if any.

If the validation procedure succeeds, the peer is considered authenticated. If the validation procedure fails for any reason, the session MUST be terminated immediately.

Responders MAY add a slight amount (+- 10 seconds) of random noise to the unix_time value to avoid leaking precise load information via packet queueing delay.

2.2 Data Transfer Phase

Upon successfully concluding the handshake the session enters the Data Transfer Phase, where the initiator and responder can exchange KMNWP messages.

A KMNWP message is defined to be the following structure:

enum {
no_op(0),
disconnect(1),
send_packet(2),

(255),
} Command;

struct {
Command command;
uint8_t reserved;    /* MUST be '0x00' */
uint32_t msg_length; /* 0 <= msg_length <= 1048554) */
opaque message[msg_length];
opaque padding[];    /* length is implicit */
} Message;

Notes:

The padding field, if any MUST be padded with '0x00' bytes.

All outgoing Message(s) are encrypted and authenticated into a pair of Noise Transport messages, each containing one of the following structures:

struct {
uint32_t message_length;
} CiphertextHeader;

struct {
uint32_t message[ciphertext_length-16];
} Ciphertext;

Notes:

The ciphertext_length field includes the Noise protocol overhead of 16 bytes, for the Noise Transport message containing the Ciphertext.

All outgoing Message(s) are preceded by a Noise Transport Message containing a CiphertextHeader, indicating the size of the Noise Transport Message transporting the Message Ciphertext. After generating both Noise Transport Messages, the sender MUST call the Noise CipherState Rekey() operation.

To receive incoming Ciphertext messages, first the Noise Transport Message containing the CiphertextHeader is consumed off the network, authenticated and decrypted, giving the receiver the length of the Noise Transport Message containing the actual message itself. The second Noise Transport Message is consumed off the network, authenticated and decrypted, with the resulting message being returned to the caller for processing. After receiving both Noise Transport Messages, the receiver MUST call the Noise CipherState Rekey() operation.

Implementations MUST immediately terminate the session any of the DecryptWithAd() operations fails.

Implementations MUST immediately terminate the session if an unknown command is received in a Message, or if the Message is otherwise malformed in any way.

Implementations MAY impose a reasonable idle timeout, and terminate the session if it expires.

3. Predefined Commands

3.1 The no_op Command

The no_op command is a command that explicitly is a No Operation, to be used to implement functionality such as keep-alives and or application layer padding.

Implementations MUST NOT send any message payload accompanying this command, and all received command data MUST be discarded without interpretation.

3.2 The disconnect Command

The disconnect command is a command that is used to signal explicit session termination. Upon receiving a disconnect command, implementations MUST interpret the command as a signal from the peer that no additional commands will be sent, and destroy the cryptographic material in the receive CipherState.

While most implementations will likely wish to terminate the session upon receiving this command, any additional behavior is explicitly left up to the implementation and application.

Implementations MUST NOT send any message payload accompanying this command, and MUST not send any further traffic after sending a disconnect command.

3.3 The send_packet Command

The send_packet command is the command that is used by the initiator to transmit a Sphinx Packet over the network. The command’s message is the Sphinx Packet destined for the responder.

Initiators MUST terminate the session immediately upon reception of a send_packet command.

4. Command Padding

We use traffic padding to hide from a passive network observer which command has been sent or received.

Among the set of padded commands we exclude the Consensus command because it’s contents are a very large payload which is usually many times larger than our Sphinx packets. Therefore we only pad these commands:

GetConsensus NoOp Disconnect SendPacket RetrieveMessage MessageACK Message MessageEmpty

However we split them up into two directions, client to server and server to client because they differ in size due to the difference in size between SendPacket and Message:

Client to Server commands:

NoOp SendPacket Disconnect RetrieveMessage GetConsensus

Server to client commands:

Message MessageACK MessageEmpty

The GetConsensus command is a special case because we only want to pad it when it’s sent over the mixnet. We don’t want to pad it when sending to the dirauths. Although it would not be so terrible if it’s padded when sent to the dirauths… it would just needlessly take up bandwidth without providing any privacy benefits.

5. Anonymity Considerations

Adversaries being able to determine that two parties are communicating via KMNWP is beyond the threat model of this protocol. At a minimum, it is trivial to determine that a KMNWP handshake is being performed, due to the length of each handshake message, and the fixed positions of the various public keys.

6. Security Considerations

It is imperative that implementations use ephemeral keys for every handshake as the security properties of the Kyber KEM are totally lost if keys are ever reused.

Kyber was chosen as the KEM algorithm due to it’s conservative parameterization, simplicity of implementation, and high performance in software. It is hoped that the addition of a quantum resistant algorithm will provide forward secrecy even in the event that large scale quantum computers are applied to historical intercepts.

Acknowledgments

I would like to thank Trevor Perrin for providing feedback during the design of this protocol, and answering questions regarding Noise.

References

XWING

Manuel Barbosa, Deirdre Connolly, João Diogo Duarte, Aaron Kaiser, Peter Schwabe, Karoline Varner, Bas Westerbaan, “X-Wing: The Hybrid KEM You’ve Been Looking For”, https://eprint.iacr.org/2024/039.pdf.

NOISE

Perrin, T., “The Noise Protocol Framework”, May 2017, https://noiseprotocol.org/noise.pdf.

NOISEHFS

Weatherley, R., “Noise Extension: Hybrid Forward Secrecy”, https://github.com/noiseprotocol/noise_hfs_spec/blob/master/output/noise_hfs.pdf.

PQNOISE

Yawning Angel, Benjamin Dowling, Andreas Hülsing, Peter Schwabe and Florian Weber, “Post Quantum Noise”, September 2023, https://eprint.iacr.org/2022/539.pdf.

RFC2119

Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels”, BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, http://www.rfc-editor.org/info/rfc2119.

RFC5246

Dierks, T. and E. Rescorla, “The Transport Layer Security (TLS) Protocol Version 1.2”, RFC 5246, DOI 10.17487/RFC5246, August 2008, http://www.rfc-editor.org/info/rfc5246.

RFC7748

Langley, A., Hamburg, M., and S. Turner, “Elliptic Curves for Security”, RFC 7748, January 2016, https://www.rfc-editor.org/info/rfc7748.

2 - Sphinx cryptographic packet format

Sphinx cryptographic packet format

Yawning Angel

George Danezis

Claudia Diaz

Ania Piotrowska

David Stainton

Abstract

This document defines the Sphinx cryptographic packet format for decryption mix networks, and provides a parameterization based around generic cryptographic primitives types. This document does not introduce any new crypto, but is meant to serve as an implementation guide.

Terminology

The following terms are used in this specification.

message
A variable-length sequence of octets sent anonymously through the network. Short messages are sent in a single packet; long messages are fragmented across multiple packets.

packet
A Sphinx packet, of fixed length for each class of traffic, carrying a message payload and metadata for routing. Packets are routed anonymously through the mixnet and cryptographically transformed at each hop.

header
The packet header consisting of several components, which convey the information necessary to verify packet integrity and correctly process the packet.

payload
The fixed-length portion of a packet containing an encrypted message or part of a message, to be delivered anonymously.

group element
An individual element of the group.

group generator
A group element capable of generating any other element of the group, via repeated applications of the generator and the group operation.

Conventions Used in This Document

The C style Presentation Language as described in RFC5246 Section 4 is used to represent data structures, except for cryptographic attributes, which are specified as opaque byte vectors.

x | y denotes the concatenation of x and y.
x ^ y denotes the bitwise XOR of x and y.
byte an 8-bit octet.
x[a:b] denotes the sub-vector of x where a/b denote the start/end byte indexes (inclusive-exclusive); a/b may be omitted to signify the start/end of the vector x respectively.
x[y] denotes the y’th element of list x.
x.len denotes the length of list x.
ZEROBYTES(N) denotes N bytes of 0x00.
RNG(N) denotes N bytes of cryptographic random data.
LEN(N) denotes the length in bytes of N.
CONSTANT_TIME_CMP(x, y) denotes a constant time comparison between the byte vectors x and y, returning true iff x and y are equal.

1. Introduction

The Sphinx cryptographic packet format is a compact and provably secure design introduced by George Danezis and Ian Goldberg SPHINX09. It supports a full set of security features: indistinguishable replies, hiding the path length and relay position, detection of tagging attacks and replay attacks, as well as providing unlinkability for each leg of the packet’s journey over the network.

2. Cryptographic Primitives

This specification uses the following cryptographic primitives as the foundational building blocks for Sphinx:

H(M) - A cryptographic hash function which takes an octet array M to produce a digest consisting of a HASH_LENGTH byte octet array. H(M) MUST be pre-image and collision resistant.
MAC(K, M) - A cryptographic message authentication code function which takes a M_KEY_LENGTH byte octet array key K and arbitrary length octet array message M to produce an authentication tag consisting of a MAC_LENGTH byte octet array.
KDF(SALT, IKM) - A key derivation function which takes an arbitrary length octet array salt SALT and an arbitrary length octet array initial key IKM, to produce an octet array of arbitrary length.
S(K, IV) - A pseudo-random generator (stream cipher) which takes a S_KEY_LENGTH byte octet array key K and a S_IV_LENGTH byte octet array initialization vector IV to produce an octet array key stream of arbitrary length.
SPRP_Encrypt(K, M)/SPRP_Decrypt(K, M) - A strong pseudo-random permutation (SPRP) which takes a SPRP_KEY_LENGTH byte octet array key K and arbitrary length message M, and produces the encrypted ciphertext or decrypted plaintext respectively.

When used with the default payload authentication mechanism, the SPRP MUST be “fragile” in that any amount of modifications to M results in a large number of unpredictable changes across the whole message upon a SPRP_Encrypt() or SPRP_Decrypt() operation.
EXP(X, Y) - An exponentiation function which takes the GROUP_ELEMENT_LENGTH byte octet array group elements X and Y, and returns X ^^ Y as a GROUP_ELEMENT_LENGTH byte octet array.

Let G denote the generator of the group, and EXP_KEYGEN() return a GROUP_ELEMENT_LENGTH byte octet array group element usable as private key.

The group defined by G and EXP(X, Y) MUST satisfy the Decision Diffie-Hellman problem.
EXP_KEYGEN() - Returns a new “suitable” private key for EXP().

2.1 Sphinx Key Derivation Function

Sphinx Packet creation and processing uses a common Key Derivation Function (KDF) to derive the required MAC and symmetric cryptographic keys from a per-hop shared secret.

The output of the KDF is partitioned according to the following structure:

struct {
opaque header_mac[M_KEY_LENGTH];
opaque header_encryption[S_KEY_LENGTH];
opaque header_encryption_iv[S_IV_LENGTH];
opaque payload_encryption[SPRP_KEY_LENGTH]
opaque blinding_factor[GROUP_ELEMENT_LENGTH];
} SphinxPacketKeys;

Sphinx_KDF( info, shared_secret ) -> packet_keys

Inputs:

info The optional context and application specific information.
shared_secret The per-hop shared secret derived from the Diffie-Hellman key exchange.

Outputs:

packet_keys The SphinxPacketKeys required to handle packet creation or processing.

The output packet_keys is calculated as follows:

kdf_out = KDF( info, shared_secret )
packet_keys = kdf_out[:LEN( SphinxPacketKeys )]

3. Sphinx Packet Parameters

3.1 Sphinx Parameter Constants

The Sphinx Packet Format is parameterized by the implementation based on the application and security requirements.

AD_LENGTH - The constant amount of per-packet unencrypted additional data in bytes.
PAYLOAD_TAG_LENGTH - The length of the message payload authentication tag in bytes. This SHOULD be set to at least 16 bytes (128 bits).
PER_HOP_RI_LENGTH - The length of the per-hop Routing Information (Section 4.1.1 <4.1.1>) in bytes.
NODE_ID_LENGTH - The node identifier length in bytes.
RECIPIENT_ID_LENGTH - The recipient identifier length in bytes.
SURB_ID_LENGTH - The Single Use Reply Block (Section 7 <7.0>) identifier length in bytes.
MAX_HOPS - The maximum number of hops a packet can traverse.
PAYLOAD_LENGTH - The per-packet message payload length in bytes, including a PAYLOAD_TAG_LENGTH byte authentication tag.
KDF_INFO - A constant opaque byte vector used as the info parameter to the KDF for the purpose of domain separation.

3.2 Sphinx Packet Geometry

The Sphinx Packet Geometry is derived from the Sphinx Parameter Constants Section 3.1. These are all derived parameters, and are primarily of interest to implementors.

ROUTING_INFO_LENGTH - The total length of the “routing information” Sphinx Packet Header component in bytes:

ROUTING_INFO_LENGTH = PER_HOP_RI_LENGTH * MAX_HOPS

HEADER_LENGTH - The length of the Sphinx Packet Header in bytes:

HEADER_LENGTH = AD_LENGTH + GROUP_ELEMENT_LENGTH + ROUTING_INFO_LENGTH + MAC_LENGTH

PACKET_LENGTH - The length of the Sphinx Packet in bytes:

PACKET_LENGTH = HEADER_LENGTH + PAYLOAD_LENGTH

4. The Sphinx Cryptographic Packet Structure

Each Sphinx Packet consists of two parts: the Sphinx Packet Header and the Sphinx Packet Payload:

struct {
opaque header[HEADER_LENGTH];
opaque payload[PAYLOAD_LENGTH];
} SphinxPacket;

header - The packet header consists of several components, which convey the information necessary to verify packet integrity and correctly process the packet.
payload - The application message data.

4.1 Sphinx Packet Header

The Sphinx Packet Header refers to the block of data immediately preceding the Sphinx Packet Payload in a Sphinx Packet.

The structure of the Sphinx Packet Header is defined as follows:

struct {
opaque additional_data[AD_LENGTH]; /* Unencrypted. */
opaque group_element[GROUP_ELEMENT_LENGTH];
opaque routing_information[ROUTING_INFO_LENGTH];
opaque MAC[MAC_LENGTH];
} SphinxHeader;

additional_data - Unencrypted per-packet Additional Data (AD) that is visible to every hop. The AD is authenticated on a per-hop basis.

As the additional_data is sent in the clear and traverses the network unaltered, implementations MUST take care to ensure that the field cannot be used to track individual packets.
group_element - An element of the cyclic group, used to derive the per-hop key material required to authenticate and process the rest of the SphinxHeader and decrypt a single layer of the Sphinx Packet Payload encryption.
routing_information - A vector of per-hop routing information, encrypted and authenticated in a nested manner. Each element of the vector consists of a series of routing commands, specifying all of the information required to process the packet.

The precise encoding format is specified in Section 4.1.1 <4.1.1>.
MAC - A message authentication code tag covering the additional_data, group_element, and routing_information.

4.1.1 Per-hop routing information

The routing_information component of the Sphinx Packet Header contains a vector of per-hop routing information. When processing a packet, the per hop processing is set up such that the first element in the vector contains the routing commands for the current hop.

The structure of the routing information is as follows:

struct {
RoutingCommand routing_commands<1..2^8-1>; /* PER_HOP_RI_LENGTH bytes */
opaque encrypted_routing_commands[ROUTING_INFO_LENGTH - PER_HOP_RI_LENGTH];
} RoutingInformation;

The structure of a single routing command is as follows:

struct {
RoutingCommandType command;
select (RoutingCommandType) {
case null:               NullCommand;
case next_node_hop:      NextNodeHopCommand;
case recipient:          RecipientCommand;
case surb_reply:         SURBReplyCommand;
};
} RoutingCommand;

The following routing commands are currently defined:

enum {
null(0),
next_node_hop(1),
recipient(2),
surb_reply(3),

/* Routing commands between 0 and 0x7f are reserved. */

(255)
} RoutingCommandType;

The null routing command structure is as follows:

struct {
opaque padding<0..PER_HOP_RI_LENGTH-1>;
} NullCommand;

The next_node_hop command structure is as follows:

struct {
opaque next_hop[NODE_ID_LENGTH];
opaque MAC[MAC_LENGTH];
} NextNodeHopCommand;

The recipient command structure is as follows:

struct {
opaque recipient[RECIPEINT_ID_LENGTH];
} RecipientCommand;

The surb_reply command structure is as follows:

struct {
opaque id[SURB_ID_LENGTH];
} SURBReplyCommand;

While the NullCommand padding field is specified as opaque, implementations SHOULD zero fill the padding. The choice of 0x00 as the terminal NullCommand is deliberate to ease implementation, as ZEROBYTES(N) produces a valid NullCommand RoutingCommand, resulting in “appending zero filled padding” producing valid output.

Implementations MUST pad the routing_commands vector so that it is exactly PER_HOP_RI_LENGTH bytes, by appending a terminal NullCommand if necessary.

Every non-terminal hop’s routing_commands MUST include a NextNodeHopCommand.

4.2 Sphinx Packet Payload

The Sphinx Packet Payload refers to the block of data immediately following the Sphinx Packet Header in a Sphinx Packet.

For most purposes the structure of the Sphinx Packet Payload can be treated as a single contiguous byte vector of opaque data.

Upon packet creation, the payload is repeatedly encrypted (unless it is a SURB Reply, see Section 7.0 via keys derived from the Diffie-Hellman key exchange between the packet’s group_element and the public key of each node in the path.

Authentication of packet integrity is done by prepending a tag set to a known value to the plaintext prior to the first encrypt operation. By virtue of the fragile nature of the SPRP function, any alteration to the encrypted payload as it traverses the network will result in an irrecoverably corrupted plaintext when the payload is decrypted by the recipient.

5. Sphinx Packet Creation

For the sake of brevity, the pseudocode for all of the operations will take a vector of the following PathHop structure as a parameter named path[] to specify the path a packet will traverse, along with the per-hop routing commands and per-hop public keys.

struct {
/* There is no need for a node_id here, as
routing_commands[0].next_hop specifies that
information for all non-terminal hops. */
opaque public_key[GROUP_ELEMENT_LENGTH];
RoutingCommand routing_commands<1...2^8-1>;
} PathHop;

It is assumed that each routing_commands vector except for the terminal entry contains at least a RoutingCommand consisting of a partially assembled NextNodeHopCommand with the next_hop element filled in with the identifier of the next hop.

5.1 Create a Sphinx Packet Header

Both the creation of a Sphinx Packet and the creation of a SURB requires the generation of a Sphinx Packet Header, so it is specified as a distinct operation.

Sphinx_Create_Header( additional_data, path[] ) -> sphinx_header,
               payload_keys

Inputs:

additional_data The Additional Data that is visible to every node along the path in the header.
path The vector of PathHop structures in hop order, specifying the node id, public key, and routing commands for each hop.

Outputs: sphinx_header The resulting Sphinx Packet Header.

payload_keys The vector of SPRP keys used to encrypt the Sphinx Packet Payload, in hop order.

The Sphinx_Create_Header operation consists of the following steps:

Derive the key material for each hop.

num_hops = route.len
route_keys = [ ]
route_group_elements = [ ]
priv_key = EXP_KEYGEN()

/* Calculate the key material for the 0th hop. */
group_element = EXP( G, priv_key )
route_group_elements += group_element
shared_secret = EXP( path[0].public_key, priv_key )
route_keys += Sphinx_KDF( KDF_INFO, shared_secret )
blinding_factor = keys[0].blinding_factor

/* Calculate the key material for rest of the hops. */
for i = 1; i < num_hops; ++i:
shared_secret = EXP( path[i].public_key, priv_key )
for j = 0; j < i; ++j:
shared_secret = EXP( shared_secret, keys[j].blinding_factor )
route_keys += Sphinx_KDF( KDF_INFO, shared_secret )
group_element = EXP( group_element, keys[i-1].blinding_factor )
route_group_elements += group_element

At the conclusion of the derivation process:

route_keys - A vector of per-hop SphinxKeys.
route_group_elements - A vector of per-hop group elements.

Derive the routing_information keystream and encrypted padding for each hop.

ri_keystream = [ ]
ri_padding = [ ]

for i = 0; i < num_hops; ++i:
keystream = ZEROBYTES( ROUTING_INFO_LENGTH + PER_HOP_RI_LENGTH ) ^
S( route_keys[i].header_encryption,
route_keys[i].header_encryption_iv )
ks_len = LEN( keystream ) - (i + 1) * PER_HOP_RI_LENGTH

padding = keystream[ks_len:]
if i > 0:
prev_pad_len = LEN( ri_padding[i-1] )
padding = padding[:prev_pad_len] ^ ri_padding[i-1] |
padding[prev_pad_len]

ri_keystream += keystream[:ks_len]
ri_padding += padding

At the conclusion of the derivation process:
ri_keystream - A vector of per-hop routing_information
encryption keystreams.
ri_padding   - The per-hop encrypted routing_information
padding.

Create the routing_information block.

/* Start with the terminal hop, and work backwards. */
i = num_hops - 1

/* Encode the terminal hop's routing commands. As the
terminal hop can never have a NextNodeHopCommand, there
are no per-hop alterations to be made. */
ri_fragment = path[i].routing_commands |
ZEROBYTES( PER_HOP_RI_LENGTH - LEN( path[i].routing_commands ) )

/* Encrypt and MAC. */
ri_fragment ^= ri_keystream[i]
mac = MAC( route_keys[i].header_mac, additional_data |
route_group_elements[i] | ri_fragment |
ri_padding[i-1] )
routing_info = ri_fragment
if num_hops < MAX_HOPS:
pad_len = (MAX_HOPS - num_hops) * PER_HOP_RI_LENGTH
routing_info = routing_info | RNG( pad_len )

/* Calculate the routing info for the rest of the hops. */
for i = num_hops - 2; i >= 0; --i:
cmds_to_encode = [ ]

/* Find and finalize the NextNodeHopCommand. */
for j = 0; j < LEN( path[i].routing_commands; j++:
cmd = path[i].routing_commands[j]
if cmd.command == next_node_hop:
/* Finalize the NextNodeHopCommand. */
cmd.MAC = mac
cmds_to_encode = cmds_to_encode + cmd /* Append */

/* Append a terminal NullCommand. */
ri_fragment = cmds_to_encode |
ZEROBYTES( PER_HOP_RI_LENGTH - LEN( cmds_to_encode ) )

/* Encrypt and MAC */
routing_info = ri_fragment | routing_info /* Prepend. */
routing_info ^= ri_keystream[i]
if i > 0:
mac = MAC( route_keys[i].header_mac, additional_data |
route_group_elements[i] | routing_info |
ri_padding[i-1] )
else:
mac = MAC( route_keys[i].header_mac, additional_data |
route_group_elements[i] | routing_info )

At the conclusion of the derivation process:
routing_info - The completed routing_info block.
mac          - The MAC for the 0th hop.

Assemble the completed Sphinx Packet Header and Sphinx Packet Payload SPRP key vector.

/* Assemble the completed Sphinx Packet Header. */
SphinxHeader sphinx_header
sphinx_header.additional_data = additional_data
sphinx_header.group_element = route_group_elements[0] /* From step 1. */
sphinx_header.routing_info = routing_info   /* From step 3. */
sphinx_header.mac = mac                     /* From step 3. */

/* Preserve the Sphinx Payload SPRP keys, to return to the
caller. */
payload_keys = [ ]
for i = 0; i < nr_hops; ++i:
payload_keys += route_keys[i].payload_encryption

At the conclusion of the assembly process:
sphinx_header - The completed sphinx_header, to be returned.
payload_keys  - The vector of SPRP keys, to be returned.

5.2 Create a Sphinx Packet

Sphinx_Create_Packet( additional_data, path[], payload ) -> sphinx_packet

Inputs:

additional_data The Additional Data that is visible to every node along the path in the header.
path The vector of PathHop structures in hop order, specifying the node id, public key, and routing commands for each hop.
payload The packet payload message plaintext.

Outputs:

sphinx_packet The resulting Sphinx Packet.

The Sphinx_Create_Packet operation consists of the following steps:

Create the Sphinx Packet Header and SPRP key vector.

sphinx_header, payload_keys =
Sphinx_Create_Header( additional_data, path )

Prepend the authentication tag, and append padding to the payload.

payload = ZERO_BYTES( PAYLOAD_TAG_LENGTH ) | payload
payload = payload | ZERO_BYTES( PAYLOAD_LENGTH - LEN( payload ) )

Encrypt the payload.

for i = nr_hops - 1; i >= 0; --i:
payload = SPRP_Encrypt( payload_keys[i], payload )

Assemble the completed Sphinx Packet.

SphinxPacket sphinx_packet
sphinx_packet.header = sphinx_header
sphinx_packet.payload = payload

6. Sphinx Packet Processing

Mix nodes process incoming packets first by performing the Sphinx_Unwrap operation to authenticate and decrypt the packet, and if applicable prepare the packet to be forwarded to the next node.

If Sphinx_Unwrap returns an error for any given packet, the packet MUST be discarded with no additional processing.

After a packet has been unwrapped successfully, a replay detection tag is checked to ensure that the packet has not been seen before. If the packet is a replay, the packet MUST be discarded with no additional processing.

The routing commands for the current hop are interpreted and executed, and finally the packet is forwarded to the next mix node over the network or presented to the application if the current node is the final recipient.

6.1 Sphinx_Unwrap Operation

The Sphinx_Unwrap operation is the majority of the per-hop packet processing, handling authentication, decryption, and modifying the packet prior to forwarding it to the next node.

Sphinx_Unwrap( routing_private_key, sphinx_packet ) -> sphinx_packet,
                  routing_commands,
                  replay_tag

Inputs:

private_routing_key A group element GROUP_ELEMENT_LENGTH bytes in length, that serves as the unwrapping Mix’s private key.
sphinx_packet A Sphinx packet to unwrap.

Outputs:

error Indicating a unsuccessful unwrap operation if applicable.
sphinx_packet The resulting Sphinx packet.
routing_commands A vector of RoutingCommand, specifying the post unwrap actions to be taken on the packet.
replay_tag A tag used to detect whether this packet was processed before.

The Sphinx_Unwrap operation consists of the following steps:

(Optional) Examine the Sphinx Packet Header’s Additional Data.

If the header’s additional_data element contains information required to complete the unwrap operation, such as specifying the packet format version or the cryptographic primitives used examine it now.

Implementations MUST NOT treat the information in the additional_data element as trusted until after the completion of Step 3 (“Validate the Sphinx Packet Header”).

Calculate the hop’s shared secret, and replay_tag.

hdr = sphinx_packet.header
shared_secret = EXP( hdr.group_element, private_routing_key )
replay_tag = H( shared_secret )

Derive the various keys required for packet processing.

keys = Sphinx_KDF( KDF_INFO, shared_secret )

Validate the Sphinx Packet Header.

derived_mac = MAC( keys.header_mac, hdr.additional_data |
hdr.group_element |
hdr.routing_information )
if !CONSTANT_TIME_CMP( derived_mac, hdr.MAC):
/* MUST abort processing if the header is invalid. */
return ErrorInvalidHeader

Extract the per-hop routing commands for the current hop.

/* Append padding to preserve length-invariance, as the routing
commands for the current hop will be removed. */
padding = ZEROBYTES( PER_HOP_RI_LENGTH )
B = hdr.routing_information | padding

/* Decrypt the entire routing_information block. */
B = B ^ S( keys.header_encryption, keys.header_encryption_iv )

Parse the per-hop routing commands.

cmd_buf = B[:PER_HOP_RI_LENGTH]
new_routing_information = B[PER_HOP_RI_LENGTH:]

next_mix_command_idx = -1
routing_commands = [ ]
for idx = 0; idx < PER_HOP_RI_LENGTH {
/* WARNING: Bounds checking omitted for brevity. */
cmd_type = b[idx]
cmd = NULL
switch cmd_type {
case null: goto done  /* No further commands. */

case next_node_hop:
cmd = RoutingCommand( B[idx:idx+1+LEN( NextNodeHopCommand )] )
next_mix_command_idx = i /* Save for step 7. */
idx += 1 + LEN( NextNodeHopCommand )
break

case recipient:
cmd = RoutingCommand( B[idx:idx+1+LEN( FinalDestinationCommand )] )
idx += 1 + LEN( RecipientCommand )
break

case surb_reply:
cmd = RoutingCommand( B[idx:idx+1+LEN( SURBReplyCommand )] )
idx += 1 + LEN( SURBReplyCommand )
break

default:
/* MUST abort processing on unrecognized commands. */
return ErrorInvalidCommand
}
routing_commands += cmd /* Append cmd to the tail of the list. */
}
done:

At the conclusion of the parsing step:

routing_commands - A vector of SphinxRoutingCommand, to be applied at this hop.
new_routing_information - The routing_information block to be sent to the next hop if any.

Decrypt the Sphinx Packet Payload.

payload = sphinx_packet.payload
payload = SPRP_Decrypt( key.payload_encryption, payload )
sphinx_packet.payload = payload

Transform the packet for forwarding to the next mix, if the routing commands vector included a NextNodeHopCommand.

if next_mix_command_idx != -1:
cmd = routing_commands[next_mix_command_idx]
hdr.group_element = EXP( hdr.group_element, keys.blinding_factor )
hdr.routing_information = new_routing_information
hdr.mac = cmd.MAC
sphinx_packet.hdr = hdr

6.2 Post Sphinx_Unwrap Processing

Upon the completion of the Sphinx_Unwrap operation, implementations MUST take several additional steps. As the exact behavior is mostly implementation specific, pseudocode will not be provided for most of the post processing steps.

Apply replay detection to the packet.

The replay_tag value returned by Sphinx_Unwrap MUST be unique across all packets processed with a given private_routing_key.

The exact specifics of how to detect replays is left up to the implementation, however any replays that are detected MUST be discarded immediately.

Act on the routing commands, if any.

The exact specifics of how implementations chose to apply routing commands is deliberately left unspecified, however in general:

If there is a NextNodeHopCommand, the packet should be forwarded to the next node based on the next_hop field upon completion of the post processing.

The lack of a NextNodeHopCommand indicates that the packet is destined for the current node.
If there is a SURBReplyCommand, the packet should be treated as a SURBReply destined for the current node, and decrypted accordingly (See Section 7.2)
If the implementation supports multiple recipients on a single node, the RecipientCommand command should be used to determine the correct recipient for the packet, and the payload delivered as appropriate.

It is possible for both a RecipientCommand and a NextNodeHopCommand to be present simultaneously in the routing commands for a given hop. The behavior when this situation occurs is implementation defined.

Authenticate the packet if required.

If the packet is destined for the current node, the integrity of the payload MUST be authenticated.

The authentication is done as follows:

derived_tag = sphinx_packet.payload[:PAYLOAD_TAG_LENGTH]
expected_tag = ZEROBYTES( PAYLOAD_TAG_LENGTH )
if !CONSTANT_TIME_CMP( derived_tag, expected_tag ):
/* Discard the packet with no further processing. */
return ErrorInvalidPayload

Remove the authentication tag before presenting the payload to the application.

sphinx_packet.payload = sphinx_packet.payload[PAYLOAD_TAG_LENGTH:]

7. Single Use Reply Block (SURB) Creation

A Single Use Reply Block (SURB) is a delivery token with a short lifetime, that can be used by the recipient to reply to the initial sender.

SURBs allow for anonymous replies, when the recipient does not know the sender of the message. Usage of SURBs guarantees anonymity properties but also makes the reply messages indistinguishable from forward messages both to external adversaries as well as the mix nodes.

When a SURB is created, a matching reply block Decryption Token is created, which is used to decrypt the reply message that is produced and delivered via the SURB.

The Sphinx SURB wire encoding is implementation defined, but for the purposes of illustrating creation and use, the following will be used:

struct {
SphinxHeader sphinx_header;
opaque first_hop[NODE_ID_LENGTH];
opaque payload_key[SPRP_KEY_LENGTH];
} SphinxSURB;

7.1 Create a Sphinx SURB and Decryption Token

Structurally a SURB consists of three parts, a pre-generated Sphinx Packet Header, a node identifier for the first hop to use when using the SURB to reply, and cryptographic keying material by which to encrypt the reply’s payload. All elements must be securely transmitted to the recipient, perhaps as part of a forward Sphinx Packet’s Payload, but the exact specifics on how to accomplish this is left up to the implementation.

When creating a SURB, the terminal routing_commands vector SHOULD include a SURBReplyCommand, containing an identifier to ensure that the payload can be decrypted with the correct set of keys (Decryption Token). The routing command is left optional, as it is conceivable that implementations may chose to use trial decryption, and or limit the number of outstanding SURBs to solve this problem.

Sphinx_Create_SURB( additional_data, first_hop, path[] ) ->
             sphinx_surb,
             decryption_token

Inputs:

additional_data The Additional Data that is visible to every node along the path in the header.
first_hop The node id of the first hop the recipient must use when replying via the SURB.
path The vector of PathHop structures in hop order, specifying the node id, public key, and routing commands for each hop.

Outputs:

sphinx_surb The resulting Sphinx SURB.
decryption_token The Decryption Token associated with the SURB.

The Sphinx_Create_SURB operation consists of the following steps:

Create the Sphinx Packet Header and SPRP key vector.

sphinx_header, payload_keys =
Sphinx_Create_Header( additional_data, path )

Create a key for the final layer of encryption.

final_key = RNG( SPRP_KEY_LENGTH )

Build the SURB and Decryption Token.

SphinxSURB sphinx_surb;
sphinx_surb.sphinx_header = sphinx_header
sphinx_surb.first_hop = first_hop
sphinx_surb.payload_key = final_key

decryption_token = final_key + payload_keys /* Prepend */

7.2 Decrypt a Sphinx Reply Originating from a SURB

A Sphinx Reply packet that was generated using a SURB is externally indistinguishable from a forward Sphinx Packet as it traverses the network. However, the recipient of the reply has an additional decryption step, the packet starts off unencrypted, and accumulates layers of Sphinx Packet Payload decryption as it traverses the network.

Determining which decryption token to use when decrypting the SURB reply can be done via the SURBReplyCommand’s id field, if one is included at the time of the SURB’s creation.

Sphinx_Decrypt_SURB_Reply( decryption_token, payload ) -> message

Inputs:

decryption_token The vector of keys allowing a client to decrypt the reply ciphertext payload. This decryption_token is generated when the SURB is created.
payload The Sphinx Packet ciphertext payload.

Outputs:

error Indicating a unsuccessful unwrap operation if applicable.
message The plaintext message.

The Sphinx_Decrypt_SURB_Reply operation consists of the following steps:

Encrypt the message to reverse the decrypt operations the payload acquired as it traversed the network.

for i = LEN( decryption_token ) - 1; i > 0; --i:
payload = SPRP_Encrypt( decryption_token[i], payload )

Decrypt and authenticate the message ciphertext.

message = SPRP_Decrypt( decryption_token[0], payload )

derived_tag = message[:PAYLOAD_TAG_LENGTH]
expected_tag = ZEROBYTES( PAYLOAD_TAG_LENGTH )
if !CONSTANT_TIME_CMP( derived_tag, expected_tag ):
return ErrorInvalidPayload

message = message[PAYLOAD_TAG_LENGTH:]

8. Single Use Reply Block Replies

The process for using a SURB to reply anonymously is slightly different from the standard packet creation process, as the Sphinx Packet Header is already generated (as part of the SURB), and there is an additional layer of Sphinx Packet Payload encryption that must be performed.

Sphinx_Create_SURB_Reply( sphinx_surb, payload ) -> sphinx_packet

Inputs:

sphinx_surb The SphinxSURB structure, decoded from the implementation defined wire encoding.
payload The packet payload message plaintext.

The Sphinx_Create_SURB_Reply operation consists of the following steps:

Prepend the authentication tag, and append padding to the payload.

payload = ZERO_BYTES( PAYLOAD_TAG_LENGTH ) | payload
payload = payload | ZERO_BYTES( PAYLOAD_LENGTH - LEN( payload ) )

Encrypt the payload.

payload = SPRP_Encrypt( sphinx_surb.payload_key, payload )

Assemble the completed Sphinx Packet.

SphinxPacket sphinx_packet
sphinx_packet.header = sphinx_surb.sphinx_header
sphinx_packet.payload = payload

The completed sphinx_packet MUST be sent to the node specified via sphinx_surb.node_id, as the entire reply sphinx_packet’s header is pre-generated.

9. Anonymity Considerations

9.1 Optional Non-constant Length Sphinx Packet Header Padding

Depending on the mix topology, there is no hard requirement that the per-hop routing info is padded to one fixed constant length.

For example, assuming a layered topology (referred to as stratified topology in the literature) MIXTOPO10, where the layer of any given mix node is public information, as long as the following two invariants are maintained, there is no additional information available to an adversary:

All packets entering any given mix node in a certain layer are uniform in length.
All packets leaving any given mix node in a certain layer are uniform in length.

The only information available to an external or internal observer is the layer of any given mix node (via the packet length), which is information they are assumed to have by default in such a design.

9.2 Additional Data Field Considerations

The Sphinx Packet Construct is crafted such that any given packet is bitwise unlinkable after a Sphinx_Unwrap operation, provided that the optional Additional Data (AD) facility is not used. This property ensures that external passive adversaries are unable to track a packet based on content as it traverses the network. As the on-the-wire AD field is static through the lifetime of a packet (ie: left unaltered by the Sphinx_Unwrap operation), implementations and applications that wish to use this facility MUST NOT transmit AD that can be used to distinctly identify individual packets.

9.3 Forward Secrecy Considerations

Each node acting as a mix MUST regenerate their asymmetric key pair relatively frequently. Upon key rotation the old private key MUST be securely destroyed. As each layer of a Sphinx Packet is encrypted via key material derived from the output of an ephemeral/static Diffie-Hellman key exchange, without the rotation, the construct does not provide Perfect Forward Secrecy. Implementations SHOULD implement defense-in-depth mitigations, for example by using strongly forward-secure link protocols to convey Sphinx Packets between nodes.

This frequent mix routing key rotation can limit SURB usage by directly reducing the lifetime of SURBs. In order to have a strong Forward Secrecy property while maintaining a higher SURB lifetime, designs such as forward secure mixes SFMIX03 could be used.

9.4 Compulsion Threat Considerations

Reply Blocks (SURBs), forward and reply Sphinx packets are all vulnerable to the compulsion threat, if they are captured by an adversary. The adversary can request iterative decryptions or keys from a series of honest mixes in order to perform a deanonymizing trace of the destination.

While a general solution to this class of attacks is beyond the scope of this document, applications that seek to mitigate or resist compulsion threats could implement the defenses proposed in COMPULS05 via a series of routing command extensions.

9.5 SURB Usage Considerations for Volunteer Operated Mix Networks

Given a hypothetical scenario where Alice and Bob both wish to keep their location on the mix network hidden from the other, and Alice has somehow received a SURB from Bob, Alice MUST not utilize the SURB directly because in the volunteer operated mix network the first hop specified by the SURB could be operated by Bob for the purpose of deanonymizing Alice.

This problem could be solved via the incorporation of a “cross-over point” such as that described in MIXMINION, for example by having Alice delegating the transmission of a SURB Reply to a randomly selected crossover point in the mix network, so that if the first hop in the SURB’s return path is a malicious mix, the only information gained is the identity of the cross-over point.

10. Security Considerations

10.1 Sphinx Payload Encryption Considerations

The payload encryption’s use of a fragile (non-malleable) SPRP is deliberate and implementations SHOULD NOT substitute it with a primitive that does not provide such a property (such as a stream cipher based PRF). In particular there is a class of correlation attacks (tagging attacks) targeting anonymity systems that involve modification to the ciphertext that are mitigated if alterations to the ciphertext result in unpredictable corruption of the plaintext (avalanche effect).

Additionally, as the PAYLOAD_TAG_LENGTH based tag-then-encrypt payload integrity authentication mechanism is predicated on the use of a non-malleable SPRP, implementations that substitute a different primitive MUST authenticate the payload using a different mechanism.

Alternatively, extending the MAC contained in the Sphinx Packet Header to cover the Sphinx Packet Payload will both defend against tagging attacks and authenticate payload integrity. However, such an extension does not work with the SURB construct presented in this specification, unless the SURB is only used to transmit payload that is known to the creator of the SURB.

References

COMPULS05

Danezis, G., Clulow, J., “Compulsion Resistant Anonymous Communications”, Proceedings of Information Hiding Workshop, June 2005, https://www.freehaven.net/anonbib/cache/ih05-danezisclulow.pdf.

MIXMINION

Danezis, G., Dingledine, R., Mathewson, N., “Mixminion: Design of a Type III Anonymous Remailer Protocol”, https://www.mixminion.net/minion-design.pdf.

MIXTOPO10

Diaz, C., Murdoch, S., Troncoso, C., “Impact of Network Topology on Anonymity and Overhead in Low-Latency Anonymity Networks”, PETS, July 2010, https://www.esat.kuleuven.be/cosic/publications/article-1230.pdf.

RFC2119

Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels”, BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, http://www.rfc-editor.org/info/rfc2119.

RFC5246

Dierks, T. and E. Rescorla, “The Transport Layer Security (TLS) Protocol Version 1.2”, RFC 5246, DOI 10.17487/RFC5246, August 2008, http://www.rfc-editor.org/info/rfc5246.

SFMIX03

Danezis, G., “Forward Secure Mixes”, Proceedings of 7th Nordic Workshop on Secure IT Systems, 2002, https://www.freehaven.net/anonbib/cache/Dan:SFMix03.pdf.

SPHINX09

Danezis, G., Goldberg, I., “Sphinx: A Compact and Provably Secure Mix Format”, DOI 10.1109/SP.2009.15, May 2009, https://cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf.

3 - Sphinx packet replay detection

Sphinx packet replay detection

David Stainton

Abstract

This document defines the replay detection for any protocol that uses Sphinx cryptographic packet format. This document is meant to serve as an implementation guide and document the existing replay protect for deployed mix networks.

Table of Contents

2. Sphinx Cryptographic Primitives

2.1 Sphinx Parameter Constants

3. System Overview

4. Sphinx Packet Replay Cache

4.1 Sphinx Replay Tag Composition

4.2 Sphinx Replay Tag Caching

4.3 Epoch Boundaries

4.4 Cost Of Checking Replays

5. Concurrent Processing of Sphinx Packet Replay Tags

5.1 PKI Updates

Terminology

The following terms are used in this specification.

epoch
A fixed time interval defined in section 4.2 Sphinx Mix and Provider Key Rotation. The epoch is currently set to 20 minutes. A new PKI document containing public key material is published for each epoch and is valid only for that epoch.

header
The packet header consisting of several components, which convey the information necessary to verify packet integrity and correctly process the packet.

payload
The fixed-length portion of a packet containing an encrypted message or part of a message, to be delivered anonymously.

group
A finite set of elements and a binary operation that satisfy the properties of closure, associativity, invertability, and the presence of an identity element.

group element
An individual element of the group.

group generator
A group element capable of generating any other element of the group, via repeated applications of the generator and the group operation.

SEDA
Staged Event Driven Architecture. 1. A highly parallelizable computation model. 2. A computational pipeline composed of multiple stages connected by queues utilizing active queue management algorithms that can evict items from the queue based on dwell time or other criteria where each stage is a thread pool. 3. The only correct way to efficiently implement a software based router on general purpose computing hardware.

Conventions Used in This Document

1. Introduction

The Sphinx cryptographic packet format is a compact and provably secure design introduced by George Danezis and Ian Goldberg SPHINX09. Although it supports replay detection, the exact mechanism of replay detection is neither described in SPHINX09 nor is it described in our SPHINXSPEC. Therefore we shall describe in detail how to efficiently detect Sphinx packet replay attacks.

2. Sphinx Cryptographic Primitives

This specification borrows the following cryptographic primitives constants from our SPHINXSPEC:

H(M) - A cryptographic hash function which takes an byte array M to produce a digest consisting of a HASH_LENGTH byte array. H(M) MUST be pre-image and collision resistant.
EXP(X, Y) - An exponentiation function which takes the GROUP_ELEMENT_LENGTH byte array group elements X and Y, and returns X ^^ Y as a GROUP_ELEMENT_LENGTH byte array.

Let G denote the generator of the group, and EXP_KEYGEN() return a GROUP_ELEMENT_LENGTH byte array group element usable as private key.

The group defined by G and EXP(X, Y) MUST satisfy the Decision Diffie-Hellman problem.

2.1 Sphinx Parameter Constants

HASH_LENGTH - 32 bytes. Katzenpost currently uses SHA-512/256. RFC6234
GROUP_ELEMENT_LENGTH - 32 bytes. Katzenpost currently uses X25519. RFC7748

3. System Overview

Mixes as currently deployed, have two modes of operation:

Sphinx routing keys and replay caches are persisted to disk
Sphinx routing keys and replay caches are persisted to memory

These two modes of operation fundamentally represent a tradeoff between mix server availability and notional compulsion attack resistance. Ultimately it will be the mix operator’s decision to make since they affect the security and availability of their mix servers. In particular since mix networks are vulnerable to the various types of compulsion attacks (see SPHINXSPEC section 9.4 Compulsion Threat Considerations) and therefore there is some advantage to NOT persisting the Sphinx routing keys to disk. The mix operator can simply poweroff the mix server before seizure rather than physically destroying the disk in order to prevent capture of the Sphinx routing keys. An argument can be made for the use of full disk encryption, however this may not be practical for servers hosted in remote locations.

On the other hand, persisting Sphinx routing keys and replay caches to disk is useful because it allows mix operators to shutdown their mix server for maintenance purposes without loosing these Sphinx routing keys and replay caches. This means that as soon as the maintenance operation is completed the mix server is able to rejoin the network. Our current PKI system KATZMIXPKI does NOT provide a mechanism to notify Directory Authorities of such an outage or maintenance period. Therefore if there is loss of Sphinx routing keys this results in a mix outage until the next epoch.

The two modes of operation both completely prevent replay attacks after a system restart. In the case of the disk persistence, replay attacks are prevented because all packets traversing the mix have their replay tags persisted to disk cache. This cache is therefore once again used to prevent replays after a system restart. In the case of memory persistence replays are prevented upon restart because the Sphinx routing keys are destroyed and therefore the mix will not participant in the network until at least the next epoch rotation. However availability of the mix may require two epoch rotations because in accordance with KATZMIXPKI mixes publish future epoch keys so that Sphinx packets flowing through the network can seamlessly straddle the epoch boundaries.

4. Sphinx Packet Replay Cache

4.1 Sphinx Replay Tag Composition

The following excerpt from our SPHINXSPEC shows how the replay tag is calculated.

hdr = sphinx_packet.header
shared_secret = EXP( hdr.group_element, private_routing_key )
replay_tag = H( shared_secret )

However this tag is not utilized in replay detection until the rest of the Sphinx packet is fully processed and it’s header MAC verified as described in SPHINXSPEC.

4.2 Sphinx Replay Tag Caching

It would be sufficient to use a key value store or hashmap to detect the presence of a duplicate replay tag however we additionally employ a bloom filter to increase performance. Sphinx keys must periodically be rotated and destroyed to mitigate compulsion attacks and therefore our replay caches must likewise be rotated. This kind of key erasure scheme limits the window of time that an adversary can perform a compulsion attack. See our PKI specification KATZMIXPKI for more details regarding epoch key rotation and the grace period before and after the epoch boundary.

We tune our bloom filter for line-speed; that is to say the bloom filter for a given replay cache is tuned for the maximum number of Sphinx packets that can be sent on the wire during the epoch duration of the Sphinx routing key. This of course has to take into account the size of the Sphinx packets as well as the maximum line speed of the network interface. This is a conservative tuning heuristic given that there must be more than this maximum number of Sphinx packets in order for there to be duplicate packets.

Our bloomfilter with hashmap replay detection cache looks like this:

Figure 1. replay cache

replay cache

Note that this diagram does NOT express the full complexity of the replay caching system. In particular it does not describe how entries are entered into the bloom filter and hashmap. Upon either bloom filter mismatch or hashmap mismatch both data structures must be locked and the replay tag inserted into each.

For the disk persistence mode of operation the hashmap can simply be replaced with an efficient key value store. Persistent stores may use a write back cache and other techniques for efficiency.

4.3 Epoch Boundaries

Since mixes publish future epoch keys (see KATZMIXPKI) so that Sphinx packets flowing through the network can seamlessly straddle the epoch boundaries, our replay detection forms a special kind of double bloom filter system. During the epoch grace period mixes perform trial decryption of Sphinx packets. The replay cache used will be the one that is associated with the Sphinx routing key which was successfully used to decrypt (unwrap transform) the Sphinx packet. This is not a double bloom filter in the normal sense of this term since each bloom filter used is distinct and associated with it’s own cache, furthermore, replay tags are only ever inserted into one cache and one bloom filter.

4.4 Cost Of Checking Replays

The cost of checking a replay tag from a single replay cache is the sum of the following operations:

Sphinx packet unwrap operation
A bloom filter lookup
A hashmap or cache lookup

Therefore these operations are roughly O(1) in complexity. However Sphinx packets processed near epoch boundaries will not be constant time due to trial decryption with two Sphinx routing keys as mentioned above in section “3.3 Epoch Boundaries”.

5. Concurrent Processing of Sphinx Packet Replay Tags

The best way to implement a software based router is with a SEDA computational pipeline. We therefore need a mechanism to allow multiple threads to reference our rotating Sphinx keys and associated replay caches. Here we shall describe a shadow memory system which the mix server uses such that the individual worker threads shall always have a reference to the current set of candidate mix keys and associates replay caches.

5.1 PKI Updates

The mix server periodically updates it’s knowledge of the network by downloading a new consensus document as described in KATZMIXPKI. The individual threads in the “cryptoworker” thread pool which process Sphinx packets make use of a MixKey data structure which consists of:

Sphinx routing key material (public and private X25519 keys)
Replay Cache
Reference Counter

Each of these “cryptoworker” thread pool has it’s own hashmap associating epochs to a reference to the MixKey. The mix server PKI threat maintains a single hashmap which associates the epochs with the corresponding MixKey. We shall refer to this hashmap as MixKeys. After a new MixKey is added to MixKeys, a “reshadow” operation is performed for each “cryptoworker” thread. The “reshadow” operation performs two tasks:

Removes entries from each “cryptoworker” thread’s hashmap that are no longer present in MixKeys and decrements the MixKey reference counter.
Adds entries present in MixKeys but are not present in the thread’s hashmap and increments the MixKey reference counter.

Once a given MixKey reference counter is decremented to zero, the MixKey and it’s associated on disk data is purged. Note that we do not discuss synchronization primitives, however it should be obvious that updating the replay cache should likely make use of a mutex or similar primitive to avoid data races between “cryptoworker” threads.

References

COMPULS05

Danezis, G., Clulow, J., “Compulsion Resistant Anonymous Communications”, Proceedings of Information Hiding Workshop, June 2005, https://www.freehaven.net/anonbib/cache/ih05-danezisclulow.pdf.

KATZMIXNET

Angel, Y., Danezis, G., Diaz, C., Piotrowska, A., Stainton, D., “Katzenpost Mix Network Specification”, June 2017, https://katzenpost.network/docs/specs/pdf/mixnet.pdf.

KATZMIXPKI

Angel, Y., Piotrowska, A., Stainton, D., “Katzenpost Mix Network Public Key Infrastructure Specification”, December 2017, https://katzenpost.network/docs/specs/pdf/pki.pdf.

RFC2119

Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels”, BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, http://www.rfc-editor.org/info/rfc2119.

RFC6234

Eastlake 3rd, D. and T. Hansen, “US Secure Hash Algorithms (SHA and SHA-based HMAC and HKDF)”, RFC 6234, DOI 10.17487/RFC6234, May 2011, https://www.rfc-editor.org/info/rfc6234.

RFC7748

Langley, A., Hamburg, M., and S. Turner, “Elliptic Curves for Security”, RFC 7748, January 2016, https://www.rfc-editor.org/info/rfc7748.

SEDA

Welsh, M., Culler, D., Brewer, E., “SEDA: An Architecture for Well-Conditioned, Scalable Internet Services”, 2001, ACM Symposium on Operating Systems Principles, http://www.sosp.org/2001/papers/welsh.pdf.

SPHINX09

Danezis, G., Goldberg, I., “Sphinx: A Compact and Provably Secure Mix Format”, DOI 10.1109/SP.2009.15, May 2009, https://cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf.

SPHINXSPEC

Angel, Y., Danezis, G., Diaz, C., Piotrowska, A., Stainton, D., “Sphinx Mix Network Cryptographic Packet Format Specification”, July 2017, https://katzenpost.network/docs/specs/pdf/sphinx.pdf.

4 - Public key infrastructure

Public key infrastructure

Yawning Angel

Claudia Diaz

Ania Piotrowska

David Stainton

Masala

Abstract

Table of Contents

Conventions used in this document

1.2 Security properties overview

1.3 Differences from Tor and Mixminion directory authority systems

2. Overview of mix PKI interaction

2.1 PKI protocol schedule

2.1.1 Directory authority server schedule

2.1.2 Mix schedule

3. Voting for consensus protocol

3.1 Protocol messages

3.1.1 Mix descriptor and directory signing

3.2 Vote exchange

3.3 Reveal exchange

3.4 Cert exchange

3.5 Vote tabulation for consensus computation

3.6 Signature collection

3.7 Publication

4. PKI Protocol data structures

4.1 Mix descriptor format

4.1.1 Scheduling mix downtime

4.2 Directory format

4.3 Shared random value structure

5. PKI wire protocol

5.1 Mix descriptor publication

5.1.1 The post_descriptor command

5.1.2 The post_descriptor_status command

6. Voting

6.1. The vote command

6.2. The vote_status command

6.3. The get_vote command

7. Retrieval of consensus

7.1 The get_consensus command

7.2 The consensus command

7.3. The Cert command

7.4. The CertStatus command

8. Signature exchange

8.1. The sig command

8.2. The sig_status command

9. Scalability considerations

10. Future work

11. Anonymity considerations

12. Security considerations

Acknowledgements

Terminology

The following terms are used in this specification.

PKI
Public key infrastructure

directory authority system
Refers to specific PKI schemes used by Mixminion and Tor.

MSL
Maximum segment lifetime, currently set to 120 seconds.

mix descriptor
A database record which describes a component mix.

family
Identifier of security domains or entities operating one or more mixes in the network. This is used to inform the path selection algorithm.

nickname
A nickname string that is unique in the consensus document, see Katzenpost Mix Network Specification section 2.2. Network Topology.

layer
The layer indicates which network topology layer a particular mix resides in.

provider
A service operated by a third party that Clients communicate directly with to communicate with the Mixnet. It is responsible for Client authentication, forwarding outgoing messages to the Mixnet, and storing incoming messages for the Client. The Provider MUST have the ability to perform cryptographic operations on the relayed messages.

Conventions used in this document

The “C” style Presentation Language as described in RFC5246 Section 4 is used to represent data structures for additional cryptographic wire protocol commands. KATZMIXWIRE

1. Introduction

Mixnets are designed with the assumption that a Public Key Infrastructure (PKI) exists and it gives each client the same view of the network. This specification is inspired by the Tor and Mixminion Directory Authority systems MIXMINIONDIRAUTH TORDIRAUTH whose main features are precisely what we need for our PKI. These are decentralized systems meant to be collectively operated by multiple entities.

The mix network directory authority system (PKI) is essentially a cooperative decentralized database and voting system that is used to produce network consensus documents which mix clients periodically retrieve and use for their path selection algorithm when creating Sphinx packets. These network consensus documents are derived from a voting process between the Directory Authority servers.

This design prevents mix clients from using only a partial view of the network for their path selection so as to avoid fingerprinting and bridging attacks FINGERPRINTING, BRIDGING, and LOCALVIEW.

The PKI is also used by Authority operators to specify network-wide parameters, for example in the Katzenpost Decryption Mix Network KATZMIXNET the Poisson mix strategy is used and, therefore, all clients must use the same lambda parameter for their exponential distribution function when choosing hop delays in the path selection. The Mix Network Directory Authority system, aka PKI, SHALL be used to distribute such network-wide parameters in the network consensus document that have an impact on security and performance.

1.2 Security properties overview

This Directory Authority system has the following feature goals and security properties:

All Directory Authority servers must agree with each other on the set of Directory Authorities.
All Directory Authority servers must agree with each other on the set of mixes.
This system is intentionally designed to provide identical network consensus documents to each mix client. This mitigates epistemic attacks against the client path selection algorithm such as fingerprinting and bridge attacks FINGERPRINTING BRIDGING.
This system is NOT byzantine-fault-tolerant, it instead allows for manual intervention upon consensus fault by the Directory Authority operators. Further, these operators are responsible for expelling bad acting operators from the system.
This system enforces the network policies such as mix join policy wherein intentionally closed mixnets will prevent arbitrary hosts from joining the network by authenticating all descriptor signatures with a list of allowed public keys.
The Directory Authority system for a given mix network is essentially the root of all authority.

1.3 Differences from Tor and Mixminion directory authority systems

In this document we specify a Directory Authority system which is different from that of Tor’s and Mixminion’s in a number of ways:

The list of valid mixes is expressed in an allowlist. For the time being there is no specified “bandwidth authority” system which verifies the health of mixes (Further research required in this area).
There’s no non-directory channel to inform clients that a node is down, so it will end up being a lot of packet loss, since clients will continue to include the missing node in their path selection until keys published by the node expire and it falls out of the consensus.
The schema of the mix descriptors is different from that used in Mixminion and Tor, including a change which allows our mix descriptor to express n Sphinx mix routing public keys in a single mix descriptor whereas in the Tor and Mixminion Directory Authority systems, n descriptors are used.
The serialization format of mix descriptors is different from that used in Mixminion and Tor.
The shared random number computation is performed every voting round, and is required for a vote to be accepted by each authority. The shared random number is used to deterministically generate the network topology.

2. Overview of mix PKI interaction

Each Mix MUST rotate the key pair used for Sphinx packet processing periodically for forward secrecy reasons and to keep the list of seen packet tags short. SPHINX09 SPHINXSPEC The Katzenpost Mix Network uses a fixed interval (epoch), so that key rotations happen simultaneously throughout the network, at predictable times.

Each Directory Authority server MUST use some time synchronization protocol in order to correctly use this protocol. This Directory Authority system requires time synchronization to within a few minutes.

Let each epoch be exactly 1200 seconds (20 minutes) in duration, and the 0th Epoch begin at 2017-06-01 00:00 UTC.

To facilitate smooth operation of the network and to allow for delays that span across epoch boundaries, Mixes MUST publish keys to the PKI for at least 3 epochs in advance, unless the mix will be otherwise unavailable in the near future due to planned downtime.

At an epoch boundary, messages encrypted to keys from the previous epoch are accepted for a grace period of 2 minutes.

Thus, at any time, keys for all Mixes for the Nth through N + 2nd epoch will be available, allowing for a maximum round trip (forward message + SURB) delay + transit time of 40 minutes. SURB lifetime is limited to a single epoch because of the key rotation epoch, however this shouldn’t present any usability problems since SURBs are only used for sending ACK messages from the destination Provider to the sender.

2.1 PKI protocol schedule

There are two main constraints to Authority schedule:

There MUST be enough key material extending into the future so that clients are able to construct Sphinx packets with a forward and reply paths.
All participants should have enough time to participate in the protocol; upload descriptors, vote, generate documents, download documents, establish connections for user traffic.

The epoch duration of 20 minutes is more than adequate for these two constraints.

NOTE: perhaps we should make it shorter? but first let’s do some scaling and bandwidth calculations to see how bad it gets…

2.1.1 Directory authority server schedule

Directory Authority server interactions are conducted according to the following schedule, where T is the beginning of the current epoch, and P is the length of the epoch period.

T - Epoch begins
T + P/2 - Vote exchange
T + (5/8)*P - Reveal exchange
T + (6/8)*P - Tabulation and signature exchange
T + (7/8)*P - Publish consensus

2.1.2 Mix schedule

Mix PKI interactions are conducted according to the following schedule, where T is the beginning of the current epoch.

T + P/8 - Deadline for publication of all mixes documents for the next epoch.

T + (7/8)*P - This marks the beginning of the period where mixes perform staggered fetches of the PKI consensus document.

T + (8/9)*P - Start establishing connections to the new set of relevant mixes in advance of the next epoch.

T + P - 1MSL - Start accepting new Sphinx packets encrypted to the next epoch’s keys.

T + P + 1MSL - Stop accepting new Sphinx packets encrypted to the previous epoch’s keys, close connections to peers no longer listed in the PKI documents and erase the list of seen packet tags.

Mix layer changes are controlled by the Directory Authorities and therefore a mix can be reassigned to a different layer in our stratified topology at any new epoch. Mixes will maintain incoming and outgoing connections to the various nodes until all mix keys have expired, iff the node is still listed anywhere in the current document.

3. Voting for consensus protocol

In our Directory Authority protocol, all the actors conduct their behavior according to a common schedule as outlined in section “2.1 PKI Protocol Schedule”. The Directory Authority servers exchange messages to reach consensus about the network. Other tasks they perform include collecting mix descriptor uploads from each mix for each key rotation epoch, voting, shared random number generation, signature exchange and publishing of the network consensus documents.

3.1 Protocol messages

There are only two document types in this protocol:

mix_descriptor: A mix descriptor describes a mix.
directory: A directory contains a list of descriptors and other information that describe the mix network.

Mix descriptor and directory documents MUST be properly signed.

3.1.1 Mix descriptor and directory signing

Mixes MUST compose mix descriptors which are signed using their private identity key, an ed25519 key. Directories are signed by one or more Directory Authority servers using their authority key, also an ed25519 key. In all cases, signing is done using JWS RFC7515.

3.2 Vote exchange

As described in section “2.1 PKI Protocol Schedule”, the Directory Authority servers begin the voting process 1/8 of an epoch period after the start of a new epoch. Each Authority exchanges vote directory messages with each other.

Authorities archive votes from other authorities and make them available for retrieval. Upon receiving a new vote, the authority examines it for new descriptors and includes any valid descriptors in its view of the network.

Each Authority includes in its vote a hashed value committing to a choice of a random number for the vote. See section 4.3 for more details.

3.2.1 Voting Wire Protocol Commands

The Katzenpost Wire Protocol as described in KATZMIXWIRE is used by Authorities to exchange votes. We define additional wire protocol commands for sending votes:

enum {

:   vote(22), vote_status(23),

} Command;

The structures of these commands are defined as follows:

struct {
:   uint64_t epoch_number; opaque public_key[ED25519_KEY_LENGTH];
opaque payload[];

} VoteCommand;

struct {
:   uint8 error_code;

} VoteStatusCommand;

3.2.2 The vote Command

The vote command is used to send a PKI document to a peer Authority during the voting period of the PKI schedule.

The payload field contains the signed and serialized PKI document representing the sending Authority’s vote. The public_key field contains the public identity key of the sending Authority which the receiving Authority can use to verify the signature of the payload. The epoch_number field is used by the receiving party to quickly check the epoch for the vote before deserializing the payload.

Each authority MUST include its commit value for the shared random computation in this phase along with its signed vote. This computation is derived from the Tor Shared Random Subsystem, TORSRV.

3.2.3 The vote_status Command

The vote_status command is used to reply to a vote command. The error_code field indicates if there was a failure in the receiving of the PKI document.

enum {

:   vote_ok(0), /\* None error condition. */ vote_too_early(1), /*
The Authority should try again later. */ vote_too_late(2), /*
This round of voting was missed. \*/
}

The epoch_number field of the vote struct is compared with the epoch that is currently being voted on. vote_too_early and vote_too_late are replied back to the voter to report that their vote was not accepted.

3.3 Reveal exchange

As described in section “2.1 PKI Protocol Schedule”, the Directory Authority servers exchange the reveal values after they have exchanged votes which contain a commit value. Each Authority exchanges reveal messages with each other.

3.3.1 Reveal Wire Protocol Commands

The Katzenpost Wire Protocol as described in KATZMIXWIRE is used by Authorities to exchange reveal values previously committed to in their votes. We define additional wire protocol commands for exchanging reveals:

enum {
:   reveal(25), reveal_status(26),
} Command;

The structures of these commands are defined as follows:

struct {
:   uint64_t epoch_number; opaque public_key[ED25519_KEY_LENGTH];
opaque payload[];

} RevealCommand;

struct {
:   uint8 error_code;

} RevealStatusCommand;

3.3.2 The reveal Command

The reveal command is used to send a reveal value to a peer authority during the reveal period of the PKI schedule.

The payload field contains the signed and serialized reveal value. The public_key field contains the public identity key of the sending Authority which the receiving Authority can use to verify the signature of the payload. The epoch_number field is used by the receiving party to quickly check the epoch for the reveal before deserializing the payload.

3.3.3 The reveal_status Command

The reveal_status command is used to reply to a reveal command. The error_code field indicates if there was a failure in the receiving of the shared random reveal value.

enum {

:   reveal_ok(8), /* None error condition. */ reveal_too_early(9), 
/* The Authority should try again later. */
reveal_not_authorized(10), /* The Authority was rejected. */
reveal_already_received(11), /* The Authority has already revealed
this round. */ reveal_too_late(12) /* This round of revealing was
missed. */

} Errorcodes;

The epoch_number field of the reveal struct is compared with the epoch that is currently being voted on. reveal_too_early and reveal_too_late are replied back to the authority to report their reveal was not accepted. The status code reveal_not_authorized is used if the Authority is rejected. The reveal_already_received is used to report that a valid reveal command was already received for this round.

3.4 Cert exchange

The Cert command is the same as a Vote but contains the set of Reveal values as seen by the voting peer. In order to ensure that a misconfigured or malicious Authority operator cannot amplify their ability to influence the threshold voting process, after Reveal messages have been exchanged, Authorities vote again, including the Reveals seen by them. Authorities may not introduce new MixDescriptors at this phase in the protocol.

Otherwise, a consensus partition can be obtained by withholding Reveal values from a threshold number of Peers. In the case of an even-number of Authorities, a denial of service by a single Authority was observed.

3.5 Vote tabulation for consensus computation

The main design constraint of the vote tabulation algorithm is that it MUST be a deterministic process that produces the same result for each directory authority server. This result is known as a network consensus file.

A network consensus file is a well formed directory struct where the status field is set to consensus and contains 0 or more descriptors, the mix directory is signed by 0 or more directory authority servers. If signed by the full voting group then this is called a fully signed consensus.

Validate each vote directory:

that the liveness fields correspond to the following epoch
status is vote
version number matches ours

Compute a consensus directory:

Here we include a modified section from the Mixminion PKI spec MIXMINIONDIRAUTH:

For each distinct mix identity in any vote directory:

If there are multiple nicknames for a given identity, do not include any descriptors for that identity.
If half or fewer of the votes include the identity, do not include any descriptors for the identity. This also guarantees that there will be only one identity per nickname.
If we are including the identity, then for each distinct descriptor that appears in any vote directory:
- Do not include the descriptor if it will have expired on the date the directory will be published.
- Do not include the descriptor if it is superseded by other descriptors for this identity.
- Do not include the descriptor if it not valid in the next epoch.
- Otherwise, include the descriptor.
Sort the list of descriptors by the signature field so that creation of the consensus is reproducible.
Set directory status field to consensus.

Compute a shared random number from the values revealed in the “Reveal” step. Authorities whose reveal value does not verify their commit value MUST be excluded from the consensus round. Authorities ensure that their peers MUST participate in Commit-and-Reveal, and MUST use correct Reveal values obtained from other Peers as part of the “Cert” exchange.
Generate or update the network topology using the shared random number as a seed to a deterministic random number generator that determines the order that new mixes are placed into the topology.

3.6 Signature collection

Each Authority signs their view of consensus, and exchanges detached Signatures with each other. Upon receiving each Signature it is added to the signatures on the Consensus if it validates the Consensus. The Authority SHOULD warn the administrator if network partition is detected.

If there is disagreement about the consensus directory, each authority collects signatures from only the servers which it agrees with about the final consensus.

// TODO: consider exchanging peers votes amongst authorities (or hashes thereof) to // ensure that an authority has distributed one and only unique vote amongst its peers.

3.7 Publication

If the consensus is signed by a majority of members of the voting group then it’s a valid consensus and it is published.

4. PKI Protocol data structures

4.1 Mix descriptor format

Note that there is no signature field. This is because mix descriptors are serialized and signed using JWS. The IdentityKey field is a public ed25519 key. The MixKeys field is a map from epoch to public X25519 keys which is what the Sphinx packet format uses.

	Note
	XXX David: replace the following example with a JWS example:

{
"Version": 0,
"Name": "",
"Family": "",
"Email": "",
"AltContactInfo":"",
"IdentityKey": "",
"LinkKey":"",
"MixKeys": {
"Epoch": "EpochPubKey",
},
"Addresses": ["IP:Port"],
"Layer": 0,
"LoadWeight":0,
"AuthenticationType":""
}

4.1.1 Scheduling mix downtime

Mix operators can publish a half empty mix descriptor for future epochs to schedule downtime. The mix descriptor fields that MUST be populated are:

Version
Name
Family
Email
Layer
IdentityKey
MixKeys

The map in the field called “MixKeys” should reflect the scheduled downtime for one or more epochs by not have those epochs as keys in the map.

4.2 Directory format

Note: replace the following example with a JWS example

{
"Signatures": [],
"Version": 0,
"Status": "vote",
"Lambda" : 0.274,
"MaxDelay" : 30,
"Topology" : [],
"Providers" : [],
}

4.3 Shared random value structure

Katzenpost’s Shared Random Value computation is inspired by Tor’s Shared Random Subsystem TORSRV.

Each voting round a commit value is included in the votes sent to other authorities. These are produced as follows:

H = blake2b-256

COMMIT = Uint64(epoch) | H(REVEAL) REVEAL = Uint64(epoch) | H(RN)

After the votes are collected from the voting round, and before signature exchange, the Shared Random Value field of the consensus document is the output of H over the input string calculated as follows:

Validated Reveal commands received including the authorities own reveal are sorted by reveal value in ascending order and appended to the input in format IdentityPublicKeyBytes_n | RevealValue_n

However instead of the Identity Public Key bytes we instead encode the Reveal with the blake2b 256 bit hash of the public key bytes.

If a SharedRandomValue for the previous epoch exists, it is appended to the input string, otherwise 32 NUL (x00) bytes are used.

REVEALS = ID_a \| R_a \| ID_b \| R_b \| \... SharedRandomValue =
H("shared-random" | Uint64(epoch) | REVEALS | PREVIOUS_SRV)

5. PKI wire protocol

The Katzenpost Wire Protocol as described in KATZMIXWIRE is used by both clients and by Directory Authority peers. In the following section we describe additional wire protocol commands for publishing mix descriptors, voting and consensus retrieval.

5.1 Mix descriptor publication

The following commands are used for publishing mix descriptors and setting mix descriptor status:

enum {
/* Extending the wire protocol Commands. */
post_descriptor(20),
post_descriptor_status(21),
}

The structures of these command are defined as follows:

struct {
uint64_t epoch_number;
opaque payload[];
} PostDescriptor;

struct {
uint8 error_code;
} PostDescriptorStatus;

5.1.1 The post_descriptor command

The post_descriptor command allows mixes to publish their descriptors.

5.1.2 The post_descriptor_status command

The post_descriptor_status command is sent in response to a post_descriptor command, and uses the following error codes:

enum {
descriptor_ok(0),
descriptor_invalid(1),
descriptor_conflict(2),
descriptor_forbidden(3),
} ErrorCodes;

6. Voting

The following commands are used by Authorities to exchange votes:

enum {
vote(22),
vote_status(23),
get_vote(24),
} Command;

The structures of these commands are defined as follows:

struct {
uint64_t epoch_number;
opaque public_key[ED25519_KEY_LENGTH];
opaque payload[];
} VoteCommand;

struct {
uint8 error_code;
} VoteStatusCommand;

6.1. The vote command

The vote command is used to send a PKI document to a peer Authority during the voting period of the PKI schedule.

6.2. The vote_status command

The vote_status command is used to reply to a vote command. The error_code field indicates if there was a failure in the receiving of the PKI document.

enum {
vote_ok(0),               /* None error condition. */
vote_too_early(1),        /* The Authority should try again later. */
vote_too_late(2),         /* This round of voting was missed. */
vote_not_authorized(3),   /* The voter's key is not authorized. */
vote_not_signed(4),       /* The vote signature verification failed */
vote_malformed(5),        /* The vote payload was invalid */
vote_already_received(6), /* The vote was already received */
vote_not_found(7),        /* The vote was not found */
}

6.3. The get_vote command

The get_vote command is used to request a PKI document (vote) from a peer Authority. The epoch field contains the epoch from which to request the vote, and the public_key field contains the public identity key of the Authority of the requested vote. A successful query is responded to with a vote command, and queries that fail are responded to with a vote_status command with error_code vote_not_found(7).

7. Retrieval of consensus

Providers in the Katzenpost mix network system KATZMIXNET may cache validated network consensus files and serve them to clients over the mix network’s link layer wire protocol KATZMIXWIRE. We define additional wire protocol commands for requesting and sending PKI consensus documents:

enum {
/* Extending the wire protocol Commands. */
get_consensus(18),
consensus(19),
} Command;

The structures of these commands are defined as follows:

struct {
uint64_t epoch_number;
} GetConsensusCommand;

struct {
uint8 error_code;
opaque payload[];
} ConsensusCommand;

7.1 The get_consensus command

The get_consensus command is a command that is used to retrieve a recent consensus document. If a given get_consensus command contains an Epoch value that is either too big or too small then a reply consensus command is sent with an empty payload. Otherwise if the consensus request is valid then a consensus command containing a recent consensus document is sent in reply.

Initiators MUST terminate the session immediately upon reception of a get_consensus command.

7.2 The consensus command

The consensus command is a command that is used to send a recent consensus document. The error_code field indicates if there was a failure in retrieval of the PKI consensus document.

enum {
consensus_ok(0),        /* None error condition and SHOULD be accompanied with
a valid consensus payload. */
consensus_not_found(1), /* The client should try again later. */
consensus_gone(2),      /* The consensus will not be available in the future. */
} ErrorCodes;

7.3. The Cert command

The cert command is used to send a PKI document to a peer Authority during the voting period of the PKI schedule. It is the same as the vote command, but must contain the set of SharedRandomCommit and SharedRandomReveal values as seen by the Authority during the voting process.

7.4. The CertStatus command

The cert_status command is the response to a cert command, and is the same as a vote_status response, other than the command identifier. Responses are CertOK, CertTooEarly, CertNotAuthorized, CertNotSigned, CertAlreadyReceived, CertTooLate

8. Signature exchange

Signatures exchange is the final round of the consensus protocol and consists of the Sig and SigStatus commands.

8.1. The sig command

The sig command contains a detached Signature from PublicKey of Consensus for Epoch.

8.2. The sig_status command

The sig_status command is the response to a sig command. Responses are SigOK, SigNotAuthorized, SigNotSigned, SigTooEarly, SigTooLate, SigAlreadyReceived, and SigInvalid.

9. Scalability considerations

TODO: notes on scaling, bandwidth usage etc.

10. Future work

byzantine fault tolerance
PQ crypto signatures for all PKI documents: mix descriptors and directories. SPHINCS256 could be used, we already have a golang implementation: https://github.com/Yawning/sphincs256/
Make a Bandwidth Authority system to measure health of the network. Also perform load balancing as described in PEERFLOW?
Implement byzantine attack defenses as described in MIRANDA and MIXRELIABLE where mix link performance proofs are recorded and used in a reputation system.
Choose a different serialization/schema language?
Use a append only merkle tree instead of this voting protocol.

11. Anonymity considerations

This system is intentionally designed to provide identical network consensus documents to each mix client. This mitigates epistemic attacks against the client path selection algorithm such as fingerprinting and bridge attacks FINGERPRINTING, BRIDGING.
If consensus has failed and thus there is more than one consensus file, clients MUST NOT use this compromised consensus and refuse to run.
We try to avoid randomizing the topology because doing so splits the anonymity sets on each mix into two. That is, packets belonging to the previous topology versus the current topology are trivially distinguishable. On the other hand if enough mixes fall out of consensus eventually the mixnet will need to be rebalanced to avoid an attacker compromised path selection. One example of this would be the case where the adversary controls the only mix is one layer of the network topology.

12. Security considerations

The Directory Authority / PKI system for a given mix network is essentially the root of all authority in the system. The PKI controls the contents of the network consensus documents that mix clients download and use to inform their path selection. Therefore if the PKI as a whole becomes compromised then so will the rest of the system in terms of providing the main security properties described as traffic analysis resistance. Therefore a decentralized voting protocol is used so that the system is more resilient when attacked, in accordance with the principle of least authority. SECNOTSEP
Short epoch durations make it is more practical to make corrections to network state using the PKI voting rounds.
Fewer epoch keys published in advance is a more conservative security policy because it implies reduced exposure to key compromise attacks.
A bad acting Directory Authority who lies on each vote and votes inconsistently can trivially cause a denial of service for each voting round.

Acknowledgements

We would like to thank Nick Mathewson for answering design questions and thorough design review.

References

BRIDGING

Danezis, G., Syverson, P., “Bridging and Fingerprinting: Epistemic Attacks on Route Selection”, Proceedings of PETS 2008, Leuven, Belgium, July 2008, https://www.freehaven.net/anonbib/cache/danezis-pet2008.pdf.

FINGERPRINTING

Danezis, G., Clayton, R., “Route Finger printing in Anonymous Communications”, https://www.cl.cam.ac.uk/~rnc1/anonroute.pdf.

KATZMIXNET

Angel, Y., Danezis, G., Diaz, C., Piotrowska, A., Stainton, D., “Katzenpost Mix Network Specification”, June 2017, https://katzenpost.network/docs/specs/pdf/mixnet.pdf.

KATZMIXWIRE

Angel, Y., “Katzenpost Mix Network Wire Protocol Specification”, June 2017, https://katzenpost.network/docs/specs/pdf/wire.pdf.

LOCALVIEW

Gogolewski, M., Klonowski, M., Kutylowsky, M., “Local View Attack on Anonymous Communication”, https://cs.pwr.edu.pl/kutylowski/articles/LocalView-WWW.pdf.

MIRANDA

Leibowitz, H., Piotrowska, A., Danezis, G., Herzberg, A., “No right to remain silent: Isolating Malicious Mixes”, 2017, https://eprint.iacr.org/2017/1000.pdf.

MIXMINIONDIRAUTH

Danezis, G., Dingledine, R., Mathewson, N., “Type III (Mixminion) Mix Directory Specification”, December 2005, https://www.mixminion.net/dir-spec.txt.

MIXRELIABLE

Dingledine, R., Freedman, M., Hopwood, D., Molnar, D., “A Reputation System to Increase MIX-Net Reliability”, 2001, Information Hiding, 4th International Workshop, https://www.freehaven.net/anonbib/cache/mix-acc.pdf.

PEERFLOW

Johnson, A., Jansen, R., Segal, A., Syverson, P., “PeerFlow: Secure Load Balancing in Tor”, July 2017, Proceedings on Privacy Enhancing Technologies, https://petsymposium.org/2017/papers/issue2/paper12-2017-2-source.pdf.

RFC2119

Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels”, BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, http://www.rfc-editor.org/info/rfc2119.

RFC5246

Dierks, T. and E. Rescorla, “The Transport Layer Security (TLS) Protocol Version 1.2”, RFC 5246, DOI 10.17487/RFC5246, August 2008, http://www.rfc-editor.org/info/rfc5246.

RFC7515

Jones, M., Bradley, J., Sakimura, N., “JSON Web Signature (JWS)”, May 2015, https://www.rfc-editor.org/info/rfc7515.

SECNOTSEP

Miller, M., Tulloh, B., Shapiro, J., “The Structure of Authority: Why Security Is not a Separable Concer”, http://www.erights.org/talks/no-sep/secnotsep.pdf.

SPHINCS256

Bernstein, D., Hopwood, D., Hulsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schwabe, P., Wilcox O’Hearn, Z., “SPHINCS: practical stateless hash-based signatures”, http://sphincs.cr.yp.to/sphincs-20141001.pdf.

SPHINX09

Danezis, G., Goldberg, I., “Sphinx: A Compact and Provably Secure Mix Format”, DOI 10.1109/SP.2009.15, May 2009, https://cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf.

SPHINXSPEC

Angel, Y., Danezis, G., Diaz, C., Piotrowska, A., Stainton, D., “Sphinx Mix Network Cryptographic Packet Format Specification”, July 2017, https://katzenpost.network/docs/specs/pdf/sphinx.pdf.

TORDIRAUTH

“Tor directory protocol, version 3”, https://spec.torproject.org/dir-spec/index.html.

TORSRV

“Tor Shared Random Subsystem Specification”, https://spec.torproject.org/srv-spec/index.html.

5 - Mix network design

Mix network specification

Yawning Angel

George Danezis

Claudia Diaz

Ania Piotrowska

David Stainton

Abstract

This document describes the high level architecture and detailed protocols and behavior required of mix nodes participating in the Katzenpost Mix Network.

Table of Contents

3. Packet Format Overview

3.1 Sphinx Cryptographic Primitives

3.2 Sphinx Packet Parameters

3.3 Sphinx Per-hop Routing Information Extensions

4. Mix Node Operation

4.1 Link Layer Connection Management

4.2 Sphinx Mix and Provider Key Rotation

4.3 Sphinx Packet Processing

5. Anonymity Considerations

5.1 Topology

5.2 Mixing strategy

6. Security Considerations

Terminology

The following terms are used in this specification.

KiB
Defined as 1024 8 bit octets.

mixnet
A mixnet also known as a mix network is a network of mixes that can be used to build various privacy preserving protocols.

mix
A cryptographic router that is used to compose a mixnet. Mixes use a cryptographic operation on messages being routed which provides bitwise unlinkability with respect to input versus output messages. Katzenpost is a decryption mixnet that uses the Sphinx cryptographic packet format.

node
Clients are NOT considered nodes in the mix network. However note that network protocols are often layered; in our design documents we describe “mixnet hidden services” which can be operated by mixnet clients. Therefore if you are using node in some adherence to mathematical terminology one could conceivably designate a client as a node. That having been said, it would not be appropriate to the discussion of our core mixnet protocol to refer to the clients as nodes.

entry mix, entry node
A mix that has some additional features:

An entry mix is always the first hop in routes where the message originates from a client.
An entry mix authenticates client’s direct connections via the mixnet’s wire protocol.
An entry mix queues reply messages and allows clients to retrieve them later.

service mix
A service mix is a mix that has some additional features:

A service mix is always the last hop in routes where the message originates from a client.
A service mix runs mixnet services which use a Sphinx SURB based protocol.

user
An agent using the Katzenpost system.

client
Software run by the User on its local device to participate in the Mixnet. Again let us reiterate that a client is not considered a “node in the network” at the level of analysis where we are discussing the core mixnet protocol in this here document.

Katzenpost
A project to design many improved decryption mixnet protocols.

classes of traffic
We distinguish the following classes of traffic:

SURB Replies (also sometimes referred to as ACKs)
Forward messages

payload
The fixed-length portion of a packet containing an encrypted message or part of a message, to be delivered anonymously.

message
A variable-length sequence of octets sent anonymously through the network. Short messages are sent in a single packet; long messages are fragmented across multiple packets.

MSL
Maximum segment lifetime, currently set to 120 seconds.

Conventions Used in This Document

1. Introduction

This specification provides the design of a mix network meant provide an anonymous messaging protocol between clients and public mixnet services.

Various system components such as client software, end to end messaging protocols, Sphinx cryptographic packet format and wire protocol are described in their own specification documents.

2. System Overview

The presented system design is based on LOOPIX Below, we present the system overview.

The entry mixes are responsible for authenticating clients, accepting packets from the client, and forwarding them to the mix network, which then relays packets to the destination service mix. Our network design uses a strict topology where forward message traverse the network from entry mix to service mix. Service mixes can optionally reply if the forward message contained a Single Use Reply Block (see SPHINXSPEC.

The PKI system that handles the distribution of various network wide parameters, and information required for each participant to participate in the network such as IP address/port combinations that each node can be reached at, and cryptographic public keys. The specification for the PKI is beyond the scope of this document and is instead covered in KATZMIXPKI.

The mix network provides neither reliable nor in-order delivery semantics. The described mix network is neither a user facing messaging system nor is it an application. It is intended to be a low level protocol which can be composed to form more elaborate mixnet protocols with stronger more useful privacy notions.

2.1 Threat Model

Here we cannot present the threat model to the higher level mixnet protocols. However this low level core mixnet protocol does have it’s own threat model which we attempt to elucidate here.

We assume that the clients only talk to mixnet services. These services make use of a client provided delivery token known as a SURB (Single Use Reply Block) to send their replies to the client without knowing the client’s entry mix. This system guarantees third-party anonymity, meaning that no parties other than client and the service are able to learn that the client and service are communicating. Note that this is in contrast with other designs, such as Mixminion, which provide sender anonymity towards recipients as well as anonymous replies.

Mixnet clients will randomly select an entry node to use and may reconnect if disconnected for under a duration threshold. The entry mix can determine the approximate message volume originating from and destined to a given client. We consider the entry mix follows the protocol and might be an honest-but-curious adversary.

External local network observers can not determine the number of Packets traversing their region of the network because of the use of decoy traffic sent by the clients. Global observers will not be able to de-anonymize packet paths if there are enough packets traversing the mix network. Longer term statistical disclosure attacks are likely possible in order to link senders and receivers.

A malicious mix only has the ability to remember which input packets correspond to the output packets. To discover the entire path all of the mixes in the path would have to be malicious. Moreover, the malicious mixes can drop, inject, modify or delay the packets for more or less time than specified.

2.2 Network Topology

The Katzenpost Mix Network uses a layered topology consisting of a fixed number of layers, each containing a set of mixes. At any given time each Mix MUST only be assigned to one specific layer. Each Mix in a given layer N is connected to every other Mix in the previous and next layer, and or every participating Provider in the case of the mixes in layer 0 or layer N (first and last layer). :

Layer 0          Layer 1        Layer 2        Layer 3           Layer 4
+-----------+      +-------+      +-------+      +-------+      +-------------+
+-> | entry mix | -+-> |  Mix  | -+-> |  Mix  | -+-> |  Mix  | -+-> | service mix |
|   +-----------+  |   +-------+  |   +-------+  |   +-------+  |   +-------------+
|                  |              |              |              |
|   +-----------+  |   +-------+  |   +-------+  |   +-------+  |   +-------------+
+-> | entry mix | -+-> |  Mix  | -+-> |  Mix  | -+-> |  Mix  | -+-> | service mix |
|   +-----------+  |   +-------+  |   +-------+  |   +-------+  |   +-------------+
|                  |              |              |              |
|                  |   +-------+  |   +-------+  |   +-------+  |   +-------------+
|                  +-> |  Mix  | -+-> |  Mix  | -+-> |  Mix  | -+-> | service mix |
|                      +-------+      +-------+      +-------+  |   +-------------+
|                                                               |
+---------------------------------------------------------------+

Note: Multiple distinct connections are collapsed in the figure for sake of brevity/clarity.

The network topology MUST also maximize the number of security domains traversed by the packets. This can be achieved by not allowing mixes from the same security domain to be in different layers.

Requirements for the topology:

Should allow for non-uniform throughput of each mix (Get bandwidth weights from the PKI).
Should maximize distribution among security domains, in this case the mix descriptor specified family field would indicate the security domain or entity operating the mix.
Other legal jurisdictional region awareness for increasing the cost of compulsion attacks.

3. Packet Format Overview

For the packet format of the transported messages we use the Sphinx cryptographic packet format. The detailed description of the packet format, construction, processing and security / anonymity considerations see SPHINXSPEC, “The Sphinx Mix Network Cryptographic Packet Format Specification”.

As the Sphinx packet format is generic, the Katzenpost Mix Network must provide a concrete instantiation of the format, as well as additional Sphinx per-hop routing information commands.

3.1 Sphinx Cryptographic Primitives

For the current version of the Katzenpost Mix Network, let the following cryptographic primitives be used as described in the Sphinx specification.

H(M) - As the output of this primitive is only used locally to a Mix, any suitable primitive may be used.
MAC(K, M) - HMAC-SHA256 RFC6234, M_KEY_LENGTH of 32 bytes (256 bits), and MAC_LENGTH of 32 bytes (256 bits).
KDF(SALT, IKM) - HKDF-SHA256, HKDF-Expand only, with SALT used as the info parameter.
S(K, IV) - CTR-AES256 [SP80038A], S_KEY_LENGTH of 32 bytes (256 bits), and S_IV_LENGTH of 12 bytes (96 bits), using a 32 bit counter.
SPRP_Encrypt(K, M)/SPRP_Decrypt(K, M) - AEZv5 AEZV5, SPRP_KEY_LENGTH of 48 bytes (384 bits). As there is a disconnect between AEZv5 as specified and the Sphinx usage, let the following be the AEZv5 parameters:
- nonce - 16 bytes, reusing the per-hop Sphinx header IV.
- additional_data - Unused.
- tau - 0 bytes.
EXP(X, Y) - X25519 RFC7748 scalar multiply, GROUP_ELEMENT_LENGTH of 32 bytes (256 bits), G is the X25519 base point.

3.2 Sphinx Packet Parameters

The following parameters are used as for the Katzenpost Mix Network instantiation of the Sphinx Packet Format:

AD_SIZE - 2 bytes.
SECURITY_PARAMETER - 32 bytes. (except for our SPRP which we plan to upgrade)
PER_HOP_RI_SIZE - (XXX/ya: Addition is hard, let’s go shopping.)
NODE_ID_SIZE - 32 bytes, the size of the Ed25519 public key, used as Node identifiers.
RECIPIENT_ID_SIZE - 64 bytes, the maximum size of local-part component in an e-mail address.
SURB_ID_SIZE - Single Use Reply Block ID size, 16 bytes.
MAX_HOPS - 5, the ingress provider, a set of three mixes, and the egress provider.
PAYLOAD_SIZE - (XXX/ya: Subtraction is hard, let’s go shopping.)
KDF_INFO - The byte string Katzenpost-kdf-v0-hkdf-sha256.

The Sphinx Packet Header additional_data field is specified as follows:

struct {
uint8_t version;  /* 0x00 */
uint8_t reserved; /* 0x00 */
} KatzenpostAdditionalData;

Double check to ensure that this causes the rest of the packet header to be 4 byte aligned, when wrapped in the wire protocol command and framing. This might need to have 3 bytes reserved instead.

All nodes MUST reject Sphinx Packets that have additional_data that is not as specified in the header.

Design decision.

We can eliminate a trial decryption step per packet around the epoch transitions by having a command that rewrites the AD on a per-hop basis and including an epoch identifier.

I am uncertain as to if the additional complexity is worth it for a situation that can happen for a few minutes out of every epoch.

3.3 Sphinx Per-hop Routing Information Extensions

The following extensions are added to the Sphinx Per-Hop Routing Information commands.

Let the following additional routing commands be defined in the extension RoutingCommandType range (0x80 - 0xff):

enum {
mix_delay(0x80),
} KatzenpostCommandType;

The mix_delay command structure is as follows:

struct {
uint32_t delay_ms;
} NodeDelayCommand;

4. Mix Node Operation

All Mixes behave in the following manner:

Accept incoming connections from peers, and open persistent connections to peers as needed Section 4.1 <4.1>.
Periodically interact with the PKI to publish Identity and Sphinx packet public keys, and to obtain information about the peers it should be communicating with, along with periodically rotating the Sphinx packet keys for forward secrecy Section 4.2 <4.2>.
Process inbound Sphinx Packets, delay them for the specified time and forward them to the appropriate Mix and or Provider Section 4.3 <4.3>.

All Nodes are identified by their link protocol signing key, for the purpose of the Sphinx packet source routing hop identifier.

All Nodes participating in the Mix Network MUST share a common view of time, via NTP or similar time synchronization mechanism.

4.1 Link Layer Connection Management

All communication to and from participants in the Katzenpost Mix Network is done via the Katzenpost Mix Network Wire Protocol KATZMIXWIRE.

Nodes are responsible for establishing the connection to the next hop, for example, a mix in layer 0 will accept inbound connections from all Providers listed in the PKI, and will proactively establish connections to each mix in layer 1.

Nodes MAY accept inbound connections from unknown Nodes, but MUST not relay any traffic until they became known via listing in the PKI document, and MUST terminate the connection immediately if authentication fails for any other reason.

Nodes MUST impose an exponential backoff when reconnecting if a link layer connection gets terminated, and the minimum retry interval MUST be no shorter than 5 seconds.

Nodes MAY rate limit inbound connections as required to keep load and or resource use at a manageable level, but MUST be prepared to handle at least one persistent long lived connection per potentially eligible peer at all times.

4.2 Sphinx Mix and Provider Key Rotation

Each Node MUST rotate the key pair used for Sphinx packet processing periodically for forward secrecy reasons and to keep the list of seen packet tags short. The Katzenpost Mix Network uses a fixed interval (epoch), so that key rotations happen simultaneously throughout the network, at predictable times.

Let each epoch be exactly 10800 seconds (3 hours) in duration, and the 0th Epoch begin at 2017-06-01 00:00 UTC. For more details see our “Katzenpost Mix Network Public Key Infrastructure Specification” document. KATZMIXPKI

4.3 Sphinx Packet Processing

The detailed processing of the Sphinx packet is described in the Sphinx specification: “The Sphinx Mix Network Cryptographic Packet Format Specification”. Below, we present an overview of the steps which the node is performing upon receiving the packet:

Records the time of reception.
Perform a Sphinx_Unwrap operation to authenticate and decrypt a packet, discarding it immediately if the operation fails.
Apply replay detection to the packet, discarding replayed packets immediately.
Act on the routing commands.

All packets processed by Mixes MUST contain the following commands.

NextNodeHopCommand, specifying the next Mix or Provider that the packet will be forwarded to.
NodeDelayCommand, specifying the delay in milliseconds to be applied to the packet, prior to forwarding it to the Node specified by the NextNodeHopCommand, as measured from the time of reception.

Mixes MUST discard packets that have any commands other than a NextNodeHopCommand or a NodeDelayCommand. Note that this does not apply to Providers or Clients, which have additional commands related to recipient and SURB (Single Use Reply Block) processing.

Nodes MUST continue to accept the previous epoch’s key for up to 1MSL past the epoch transition, to tolerate latency and clock skew, and MUST start accepting the next epoch’s key 1MSL prior to the epoch transition where it becomes the current active key.

Upon the final expiration of a key (1MSL past the epoch transition), Nodes MUST securely destroy the private component of the expired Sphinx packet processing key along with the backing store used to maintain replay information associated with the expired key.

Nodes MAY discard packets at any time, for example to keep congestion and or load at a manageable level, however assuming the Sphinx_Unwrap operation was successful, the packet MUST be fed into the replay detection mechanism.

Nodes MUST ensure that the time a packet is forwarded to the next Node is around the time of reception plus the delay specified in NodeDelayCommand. Since exact millisecond processing is unpractical, implementations MAY tolerate a small window around that time for packets to be forwarded. That tolerance window SHOULD be kept minimal.

Nodes MUST discard packets that have been delayed for significantly more time than specified by the NodeDelayCommand.

5. Anonymity Considerations

5.1 Topology

Layered topology is used because it offers the best level of anonymity and ease of analysis, while being flexible enough to scale up traffic. Whereas most mixnet papers discuss their security properties in the context of a cascade topology, which does not scale well, or a free-route network, which quickly becomes intractable to analyze when the network grows, while providing slightly worse anonymity than a layered topology. MIXTOPO10

Important considerations when assigning mixes to layers, in order of decreasing importance, are:

Security: do not allow mixes from one security domain to be in different layers to maximise the number of security domains traversed by a packet
Performance: arrange mixes in layers to maximise the capacity of the layer with the lowest capacity (the bottleneck layer)
Security: arrange mixes in layers to maximise the number of jurisdictions traversed by a packet (this is harder to do really well than it seems, requires understanding of legal agreements such as MLATs).

5.2 Mixing strategy

As a mixing technique the Poisson mix strategy LOOPIX and KESDOGAN98 is used, which REQUIRES that a packet at each hop in the route is delayed by some amount of time, randomly selected by the sender from an exponential distribution. This strategy allows to prevent the timing correlation of the incoming and outgoing traffic from each node. Additionally, the parameters of the distribution used for generating the delay can be tuned up and down depending on the amount of traffic in the network and the application for which the system is deployed.

6. Security Considerations

The source of all authority in the mixnet system comes from the Directory Authority system which is also known as the mixnet PKI. This system gives the mixes and clients a consistent view of the network while allowing human intervention when needed. All public mix key material and network connection information is distributed by this Directory Authority system.

References

AEZV5

Hoang, V., Krovetz, T., Rogaway, P., “AEZ v5: Authenticated Encryption by Enciphering”, March 2017, http://web.cs.ucdavis.edu/~rogaway/aez/aez.pdf.

KATZMIXPKI

Angel, Y., Piotrowska, A., Stainton, D., “Katzenpost Mix Network Public Key Infrastructure Specification”, December 2017, https://katzenpost.network/docs/specs/pdf/pki.pdf.

KATZMIXWIRE

Angel, Y., “Katzenpost Mix Network Wire Protocol Specification”, June 2017, https://katzenpost.network/docs/specs/pdf/wire.pdf.

KESDOGAN98

Kesdogan, D., Egner, J., and Büschkes, R., “Stop-and-Go-MIXes Providing Probabilistic Anonymity in an Open System”, Information Hiding, 1998, https://www.freehaven.net/anonbib/cache/stop-and-go.pdf.

LOOPIX

Piotrowska, A., Hayes, J., Elahi, T., Meiser, S., Danezis, G., “The Loopix Anonymity System”USENIX, August 2017, https://arxiv.org/pdf/1703.00536.pdf.

MIXTOPO10

RFC2119

Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels”, BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, http://www.rfc-editor.org/info/rfc2119.

RFC5246

Dierks, T. and E. Rescorla, “The Transport Layer Security (TLS) Protocol Version 1.2”, RFC 5246, DOI 10.17487/RFC5246, August 2008, http://www.rfc-editor.org/info/rfc5246.

RFC6234

Eastlake 3rd, D. and T. Hansen, “US Secure Hash Algorithms (SHA and SHA-based HMAC and HKDF)”, RFC 6234, DOI 10.17487/RFC6234, May 2011, https://www.rfc-editor.org/info/rfc6234.

RFC7748

Langley, A., Hamburg, M., and S. Turner, “Elliptic Curves for Security”, RFC 7748, January 2016, https://www.rfc-editor.org/info/rfc7748.

SP80038A

Dworkin, M., “Recommendation for Block Cipher Modes of Operation”, SP800-38A, 10.6028/NIST.SP.800, December 2001, https://doi.org/10.6028/NIST.SP.800-38A.

SPHINXSPEC

Angel, Y., Danezis, G., Diaz, C., Piotrowska, A., Stainton, D., “Sphinx Mix Network Cryptographic Packet Format Specification”, July 2017, https://katzenpost.network/docs/specs/pdf/sphinx.pdf.

6 - Mix decoy loop

Propagation of mix decoy loop statistics

David Stainton

Eva Infeld

Leif Ryge

Abstract

In the context of continuous time mixing strategies such as the memoryless mix used by Katzenpost, n-1 attacks may use strategic packetloss. Nodes can also fail for benign reasons. Determining whether or not it’s an n-1 attack is outside the scope of this work.

This document describes how we will communicate statistics from mix nodes to mix network directory authorities which tells them about the packetloss they are observing.

Table of Contents

2. Tracking packet loss and detecting faulty mixes

1. Design Overview

3. Uploading Stats to Dirauths

Terminology

The following terms are used in this specification.

Wire protocol
Refers to our PQ Noise based protocol which currently uses TCP but in the near future will optionally use QUIC. This protocol has messages known as wire protocol commands, which are used for various mixnet functions such as sending or retrieving a message, dirauth voting etc. For more information, please see our design doc: wire protocol specification

Providers
Refers to a set of node on the edge of the network which have two roles, handle incoming client connections and run mixnet services. Soon we should get rid of Providers and replace it with two different sets, gateway nodes and service nodes.

Epoch
The Katzenpost epoch is currently set to a 20 minute duration. Each new epoch there is a new PKI document published containing public key material that will only be valid for that epoch.

1. Design Overview

Nodes (mixes, gateways, and providers) need to upload packet-loss statistics to the directory authorities, so that authorities can label malfunctioning nodes as such in the consensus in the next epoch.

Nodes currently sign and upload a Descriptor in each epoch.

In the future, they would instead upload an UploadDescStats containing:

Descriptor
Stats
Signature

Contains a map from pairs-of-mixes to the ratio of count-of-loops-sent vs. count-of-loops-received.

2. Tracking packet loss and detecting faulty mixes

Katzenpost lets different elements in the network track whether other elements are functioning correctly. A node A will do this by sending packets in randomly generated loops through the network, and tracking whether the loop comes back or not. When it comes back, it will mark that as evidence, that the nodes on the path of that loop are functioning correctly.

Experimental setup, node A:

Data: each network node A collects a record of emitted test loops in a certain epoch, their paths and whether they returned or not. Importantly, each loop is the same length and includes l steps.
A segment is defined as a possible connection from a device in the network to another, for example from a node in the layer k to a node in the layer k+1. Each loop is a sequence of such segments.
Each node A will create 3 hashmaps, sent_loops_A, completed_loops_A and ratios_A. Each of these will use a pair of concatenated mixnode ID’s as the key. The ordering of the ID’s will be from lesser topology layer to greater, e.g. the two-tuple (n, n+1) which is represented here as a 64 byte array:
```
var sent_loops_A map[[64]byte]int
var completed_loops_A map[[64]byte]int
var ratios_A map[[64]byte]float64
```

Every time the node A sends out a test loop, for each segment in the loop path, it will increment the value in sent_loops_A.
When a test loop returns, for each step in the loop path, it will increment the value in completed_loops_A.
Generate a new map entry in ratios_A for each mix-node-pair p, if sent_loops_A[p]==0 set ratios_A[p]=1. Else ratios_A[p] = completed_loops_A[p]/sent_loops_A[p]
Plot the resulting distribution, and calculate the standard deviation to detect anomalies. Have the node report significant anomalies after a sufficient time period as to not leak information on the route of individual loops.
Anomalies may have to be discarded if the corresponding sent_loops_A[p] is small.

You would expect the distribution of values in completed_loops to approximate a binomial distribution. In an absence of faulty nodes, ratios should be 1, and when there are some faulty nodes values at faulty nodes should approach 0 (if the node doesn’t work at all), and be binomially distributed at nodes that can share a loop with faulty nodes.

Therefore each mix node generates a statistics report to upload to the dirauth nodes, of the struct type:

type LoopStats struct {
Epoch           uint64
MixIdentityHash *[32]byte
Ratios          map[[64]byte]float64
}

The report is subsequently uploaded to the directory authorities, which combine the reports of individual nodes into a health status of the network and arrive at a consensus decision about the topology of the network.

3. Uploading Stats to Dirauths

Stats reports are uploaded along with the mix descriptor every Epoch. A cryptographic signature covers both of these fields:

type UploadDescStats struct {
Descriptor []byte
StatsReport []byte
Signature []byte
}

Statistics reports collected during the XXX period of time, that is, the time between descriptor N+1 upload and descriptor N+2 upload, are what will affect the topology choices in epoch N+2 if the dirauths collectively decide to act on the very latest statistics reports in order to determine for example if a mix node should be removed from the network:

| ---------------- epoch N ---------------- | ---------------- epoch N+1 ---------------- | ---------------- epoch N+2 ---------------- |
| ----------- UD_N+1 ---------------------- | ------------ UD N+2 ----------------------- | ----------- UD N+3 ------------------------ |             | ------------------ XXX ---------------- |

7 - KEMSphinx

KEMSphinx

David Stainton

Abstract

Here I present a modification of the Sphinx cryptographic packet format that uses a KEM instead of a NIKE whilst preserving the properties of bitwise unlinkability, constant packet size and route length hiding.

Table of Contents

2. Post Quantum Hybrid KEM

2.1 NIKE to KEM adapter

2.2 KEM Combiner

3. KEMSphinx Header Design

4. KEMSphinx Unwrap Operation

Self-authenticating BACAP payload

1. Introduction

We’ll express our KEM Sphinx header in pseudo code. The Sphinx body will be exactly the same as the section called “References” Our basic KEM API has three functions:

PRIV_KEY, PUB_KEY = GEN_KEYPAIR(RNG)
ct, ss = ENCAP(PUB_KEY) - Encapsulate generates a shared secret, ss, for the public key and encapsulates it into a ciphertext.
ss = DECAP(PRIV_KEY, ct) - Decapsulate computes the shared key, ss, encapsulated in the ciphertext, ct, for the private key.

Additional notation includes:

|| = concatenate two binary blobs together
PRF = pseudo random function, a cryptographic hash function, e.g. Blake2b.

Therefore we must embed these KEM ciphertexts in the KEMSphinx header, one KEM ciphertext per mix hop.

2. Post Quantum Hybrid KEM

Special care must be taken in order correctly compose a hybrid post quantum KEM that is IND-CCA2 robust.

The hybrid post quantum KEMs found in Cloudflare’s circl library are suitable to be used with Noise or TLS but not with KEM Sphinx because they are not IND-CCA2 robust. Noise and TLS achieve IND-CCA2 security by mixing in the public keys and ciphertexts into the hash object and therefore do not require an IND-CCA2 KEM.

Firstly, our post quantum KEM is IND-CCA2 however we must specifically take care to make our NIKE to KEM adapter have semantic security. Secondly, we must make a security preserving KEM combiner.

2.1 NIKE to KEM adapter

We easily achieve our IND-CCA2 security by means of hashing together the DH shared secret along with both of the public keys:

func ENCAPSULATE(their_pubkey publickey) ([]byte, []byte) {
my_privkey, my_pubkey = GEN_KEYPAIR(RNG)
ss = DH(my_privkey, their_pubkey)
ss2 = PRF(ss || their_pubkey || my_pubkey)
return my_pubkey, ss2
}

func DECAPSULATE(my_privkey, their_pubkey) []byte {
s = DH(my_privkey, their_pubkey)
shared_key = PRF(ss || my_pubkey || their_pubkey)
return shared_key
}

2.2 KEM Combiner

The KEM Combiners paper ??? makes the observation that if a KEM combiner is not security preserving then the resulting hybrid KEM will not have IND-CCA2 security if one of the composing KEMs does not have IND-CCA2 security. Likewise the paper points out that when using a security preserving KEM combiner, if only one of the composing KEMs has IND-CCA2 security then the resulting hybrid KEM will have IND-CCA2 security.

Our KEM combiner uses the split PRF design from the paper when combining two KEM shared secrets together we use a hash function to also mix in the values of both KEM ciphertexts. In this pseudo code example we are hashing together the two shared secrets from the two underlying KEMs, ss1 and ss2. Additionally the two ciphertexts from the underlying KEMs, cct1 and cct2, are also hashed together:

func SplitPRF(ss1, ss2, cct1, cct2 []byte) []byte {
cct := cct1 || cct2
return PRF(ss1 || cct) XOR PRF(ss2 || cct)
}

Which simplifies to:

SplitPRF := PRF(ss1 || cct2) XOR PRF(ss2 || cct1)

The Split PRF can be used to combine an arbitrary number of KEMs. Here’s what it looks like with three KEMs:

func SplitPRF(ss1, ss2, ss3, cct1, cct2, cct3 []byte) []byte {
cct := cct1 || cct2 || cct3
return PRF(ss1 || cct) XOR PRF(ss2 || cct) XOR PRF(ss3 || cct)
}

3. KEMSphinx Header Design

NIKE Sphinx header elements:

Version number (MACed but not encrypted)
Group element
Encrypted per routing commands
MAC for this hop (authenticates header fields 1 thru 4)

KEM Sphinx header elements:

Version number (MACed but not encrypted)
One KEM ciphertext for use with the next hop
Encrypted per routing commands AND KEM ciphertexts, one for each additional hop
MAC for this hop (authenticates header fields 1 thru 4)

We can say that KEMSphinx differs from NIKE Sphinx by replacing the header’s group element (e.g. an X25519 public key) field with the KEM ciphertext. Subsequent KEM ciphertexts for each hop are stored inside the Sphinx header “routing information” section.

First we must have a data type to express a mix hop, and we can use lists of these hops to express a route:

type PathHop struct {
public_key kem.PublicKey
routing_commands Commands
}

Here’s how we construct a KEMSphinx packet header where path is a list of PathHop, and indicates the route through the network:

Derive the KEM ciphertexts for each hop.

route_keys = []
route_kems = []
for i := 0; i < num_hops; i++ {
kem_ct, ss := ENCAP(path[i].public_key)
route_kems += kem_ct
route_keys += ss
}

Derive the routing_information keystream and encrypted padding for each hop.

Same as in the section called “References” except for the fact that each routing info slot is now increased by the size of the KEM ciphertext.

Create the routing_information block.

Here we modify the Sphinx implementation to pack the next KEM ciphertext into each routing information block. Each of these blocks is decrypted for each mix mix hop which will decrypt the KEM ciphertext for the next hop in the route.

Assemble the completed Sphinx Packet Header and Sphinx Packet Payload SPRP key vector. Same as in SPHINXSPEC except the kem_element field is set to the first KEM ciphertext, route_kems[0]:

var sphinx_header SphinxHeader
sphinx_header.additional_data = version
sphinx_header.kem_element = route_kems[0]
sphinx_header.routing_info = routing_info
sphinx_header.mac = mac

4. KEMSphinx Unwrap Operation

Most of the design here will be exactly the same as in SPHINXSPEC. However there are a few notable differences:

The shared secret is derived from the KEM ciphertext instead of a DH.
Next hop’s KEM ciphertext stored in the encrypted routing information.

Acknowledgments

I would like to thank Peter Schwabe for the original idea of simply replacing the Sphinx NIKE with a KEM and for answering all my questions. I’d also like to thank Bas Westerbaan for answering questions.

References

KEMCOMB

Federico Giacon, Felix Heuer, Bertram Poettering, “KEM Combiners”, 2018, https://link.springer.com/chapter/10.1007/978-3-319-76578-5_7

SPHINX09

Danezis, G., Goldberg, I., “Sphinx: A Compact and Provably Secure Mix Format”, DOI 10.1109/SP.2009.15, May 2009, https://cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf.

SPHINXSPEC

Angel, Y., Danezis, G., Diaz, C., Piotrowska, A., Stainton, D., “Sphinx Mix Network Cryptographic Packet Format Specification”, July 2017, https://katzenpost.network/docs/specs/pdf/sphinx.pdf.

8 - Contact Voucher Design

Contact Voucher Design

Threebit Hacker

Leif Ryge

Abstract

Table of Contents

Voucher Design

Voucher Design

In order to join or initiate a conversation, participants need to exchange cryptographic key material. To address this problem we have a slightly unusual design: Contact vouchers.

In many systems, invites to conversations flow from an existing member of the conversation to the user being invited. In our “Contact Voucher” protocol this flow is reversed: A member wishing to join a conversation hands a “Contact Voucher” (out of band) to the existing member, who then inducts the new member into the group.

This design mitigates two potential problem with the former way of doing it:

If the Contact Voucher is observed by a third-party, the third-party does not get to read neither participants’ actual messages.
- Passive adversaries learn that the voucher was spent, but do not get to observe further interactions.
- Active adversaries can create a new fake group to induct the member into but does not learn anything about the existing group.
  - In the future to prevent this one-way impersonation we could allow a “both parties bring something on paper to the meeting”:
    
    Bob brings Contact Voucher
    
    Alice brings fingerprint for the VoucherReplyPublicKey (thwarts the active attacker)
Only one thing needs to delivered out of band to achieve a 2-pass protocol (instead of a 3-pass protocol).

Only one of the parties need to bring key material to a meeting in order to establish contact.

Self-authenticating BACAP payload

The first message sent (The VoucherPayload) is authenticated in the following manner:

The VoucherPayload is computed (first).
A cryptographic hash of the VoucherPayload is computed. This hash is the Voucher*.
The Voucher is then used to derive a BACAP read/write capability set.
The VoucherPayload is uploaded to the sequence described by the capability (at index 0).
Anyone who intercepts the Voucher can read and write the sequence.
But: Since the Voucher is a hash over the VoucherPayload, writing the sequence with anything but the VoucherPayload will be detectable by the recipient.
This means that the contents cannot be undetectably be modified by the interceptor.

9 - Certificate format

Certificate format

David Stainton

Abstract

This document proposes a certificate format that Katzenpost mix server, directory authority server and clients will use.

Table of Contents

1.3. Certificate Key Types

1.1. Document Format

1.2 Certificate Types

2. Golang API

https://www.rfc-editor.org/rfc/rfc8032.

Terminology

The following terms are used in this specification.

Conventions Used in This Document

1. Introduction

Mixes and Directory Authority servers need to have key agility in the sense of operational abilities such as key rotation and key revocation. That is, we wish for mixes and authorities to periodically utilize a long-term signing key for generating certificates for new short-term signing keys.

Yet another use-case for these certificate is to replace the use of JOSE RFC7515 in the voting Directory Authority system KATZMIXPKI for the multi-signature documents exchanged for voting and consensus.

1.1. Document Format

The CBOR RFC7049 serialization format is used to serialize certificates:

Signature is a cryptographic signature which has an associated signer ID.

type Signature struct {
// Identity is the identity of the signer.
Identity []byte
// Signature is the actual signature value.
Signature []byte
}

Certificate structure for serializing certificates.

type certificate struct {
// Version is the certificate format version.
Version uint32

// Expiration is seconds since Unix epoch.
Expiration int64

// KeyType indicates the type of key
// that is certified by this certificate.
KeyType string

// Certified is the data that is certified by
// this certificate.
Certified []byte

// Signatures are the signature of the certificate.
Signatures []Signature
}

That is, one or more signatures sign the certificate. However the Certified field is not the only information that is signed. The Certified field along with the other non-signature fields are all concatenated together and signed. Before serialization the signatures are sorted by their identity so that the output is binary deterministic.

1.2 Certificate Types

The certificate type field indicates the type of certificate. So far we have only two types:

identity key certificate
directory authority certificate

Both mixes and directory authority servers have a secret, long-term identity key. This key is ideally stored encrypted and offline, it’s used to sign key certificate documents. Key certificates contain a medium-term signing key that is used to sign other documents. In the case of an “authority signing key”, it is used to sign vote and consensus documents whereas the “mix singing key” is used to sign mix descriptors which are uploaded to the directory authority servers.

1.3. Certificate Key Types

It’s more practical to continue using Ed25519 ED25519 keys but it’s also possible that in the future we could upgrade to a stateless hash based post quantum cryptographic signature scheme such as SPHINCS-256 or SPHINCS+. SPHINCS256

2. Golang API

https://godoc.org/github.com/katzenpost/katzenpost/core/crypto/cert

Our golang implementation is agnostic to the specific cryptographic signature scheme which is used. Cert can handle single and multiple signatures per document and has a variety of helper functions that ease use for multi signature use cases.

Acknowledgments

This specification was inspired by Tor Project’s certificate format specification document:

https://gitweb.torproject.org/torspec.git/tree/cert-spec.txt

References

RFC7049

C. Bormann, P. Hoffman, “Concise Binary Object Representation (CBOR)”, Internet Engineering Task Force (IETF), October 2013, https://www.rfc-editor.org/info/rfc7049.

RFC7515

Jones, M., Bradley, J., Sakimura, N., “JSON Web Signature (JWS)”, May 2015, https://www.rfc-editor.org/info/rfc7515.

KATZMIXPKI

Angel, Y., Piotrowska, A., Stainton, D., “Katzenpost Mix Network Public Key Infrastructure Specification”, December 2017, https://katzenpost.network/docs/specs/pdf/pki.pdf.

RFC2119

Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels”, BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, http://www.rfc-editor.org/info/rfc2119.

RFC7693

Saarinen, M-J., Ed., and J-P. Aumasson, “The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC)”, RFC 7693, DOI 10.17487/RFC7693, November 2015, http://www.rfc-editor.org/info/rfc7693.

ED25519

SPHINCS256

10 - Provider-side autoresponder extension

Provider-side autoresponder extension (Kaetzchen)

Yawning Angel

Kali Kaneko

David Stainton

Abstract

This interface is meant to provide support for various autoresponder agents “Kaetzchen” that run on Katzenpost provider instances, thus bypassing the need to run a discrete client instance to provide functionality. The use-cases for such agents include, but are not limited to, user identity key lookup, a discard address, and a loop-back responder for the purpose of cover traffic.

Table of Contents

3. Anonymity Considerations

1. Extension Overview

1.1 Agent Requirements

1.2 Mix Message Formats

2. PKI Extensions

4. Security Considerations