Messages from clients to Kaetzchen use the following payload format in the forward Sphinx packet:

struct {
uint8_t flags;
uint8_t reserved; /* Set to 0x00. */
select (flags) {
case 0:
opaque padding[sizeof(SphinxSURB)];
case 1:
SphinxSURB surb;
}
opaque plaintext[];
} KaetzchenMessage;

The plaintext component of a KaetzchenMessage MUST be padded by appending “0x00” bytes to make the final total size of a KaetzchenMessage equal to that of a BlockSphinxPlaintext.

Messages (replies) from the Kaetzchen to client use the following payload format in the SURB generated packet:

struct {
opaque plaintext[];
} KaetzchenReply;

The plaintext component of a KaetzchenReply MUST be padded by appending “0x00” bytes to make the final total size of a KaetzchenReply equal to that of a BlockSphinxPlaintext

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.

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

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.

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

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
}

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

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 illucidate 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.

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:

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

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

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.

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.

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;

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.

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

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:

All packets processed by Mixes MUST contain the following commands.

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.

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:

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.

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

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:

There are two main constraints to Authority schedule:

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…

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.

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.

There are only two document types in this protocol:

Mix descriptor and directory documents MUST be properly signed.

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.

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 retreival. 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.

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 commited 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.

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 witholding 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.

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.

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

For each distinct mix identity in any vote directory:

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.

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

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":""
}

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

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.

Note: replace the following example with a JWS example

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

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:

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

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

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;

The post_descriptor command allows mixes to publish their descriptors.

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;

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.

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 */
}

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.

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

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.

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;

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.

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

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

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

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.

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.

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

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”.

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:

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:

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.

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:

Outputs:

The output packet_keys is calculated as follows:

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

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

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 = PER_HOP_RI_LENGTH * MAX_HOPS

HEADER_LENGTH = AD_LENGTH + GROUP_ELEMENT_LENGTH + ROUTING_INFO_LENGTH + MAC_LENGTH

PACKET_LENGTH = HEADER_LENGTH + PAYLOAD_LENGTH

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;

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.

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.

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:

Outputs: sphinx_header The resulting Sphinx Packet Header.

The Sphinx_Create_Header operation consists of the following steps:

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:

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.

/* 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. */
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.

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

Inputs:

Outputs:

The Sphinx_Create_Packet operation consists of the following steps:

sphinx_header, payload_keys =
Sphinx_Create_Header( additional_data, path )

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

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

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

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:

Outputs:

The Sphinx_Unwrap operation consists of the following steps:

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”).

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

keys = Sphinx_KDF( KDF_INFO, shared_secret )

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

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

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:

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

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

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

sphinx_packet.payload = sphinx_packet.payload[PAYLOAD_TAG_LENGTH:]

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;

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

sphinx_header, payload_keys =
Sphinx_Create_Header( additional_data, path )

final_key = RNG( SPRP_KEY_LENGTH )

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

Sphinx_Decrypt_SURB_Reply( decryption_token, payload ) -> message

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

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:]

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:

The Sphinx_Create_SURB_Reply operation consists of the following steps:

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

payload = SPRP_Encrypt( sphinx_surb.payload_key, payload )

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.

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”

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.

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:

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.

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:

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:

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.

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.

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.

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.