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

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

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

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.

A CourierEnvelope carries an epoch field that identifies the replica epoch whose envelope key the client used to encrypt the MKEM ciphertext. Conforming couriers and storage replicas MUST accept epoch ∈ {current − 1, current, current + 1} where current is the courier’s / replica’s own view of the current replica epoch.

The current − 1 tolerance handles the grace window immediately after a replica-epoch boundary, when a client with a slightly stale PKI view still encrypts to the previous envelope public key. Combined with current, this gives a two replica-epoch data TTL — roughly two weeks — because the future replica-epoch key is by definition a key that hasn’t started being used yet, so current and current − 1 are the epochs where actual data flows.

The current + 1 tolerance handles the same boundary seen from the other side: a client whose clock or PKI view is slightly ahead of the courier / replica.

Envelopes outside this three-epoch window MUST be rejected, because by definition no replica still holds the matching decapsulation key:

Couriers SHOULD reject with a dedicated envelope-level error code (EnvelopeErrorInvalidEpoch) so clients can distinguish “stale encryption” from other courier-side rejections.

The maximum plaintext BACAP payload a single box can carry is derived backwards from the Sphinx UserForwardPayloadLength by subtracting every layer of framing and cryptographic overhead that sits between the Sphinx payload and the BACAP plaintext. The authoritative calculation is performed by NewGeometryFromSphinx in pigeonhole/geo/geometry.go.

Informally:

MaxPlaintextPayloadLength
  = UserForwardPayloadLength
    − CourierQuery framing (1 byte: query_type discriminator)
    − CourierEnvelope header (intermediate_replicas[2] + Dek1 + Dek2
                              + reply_index + epoch + sender_pubkey_len
                              + sender_pubkey + ciphertext_len)
    − MKEM AEAD overhead (28 bytes)
    − ReplicaInnerMessage framing (1 byte: message_type discriminator)
    − ReplicaWrite header (box_id + signature + payload_len = 100 bytes)
    − BACAP AEAD overhead (16 bytes)
    − BACAP length prefix (4 bytes)  

With a hybrid CTIDH-1024 × X25519 NIKE, the fixed per-packet overhead between UserForwardPayloadLength and the BACAP plaintext is on the order of 560 bytes; the exact figure depends on the configured NIKE scheme and should always be obtained from geometry.NewGeometryFromSphinx() rather than computed by hand.

The courier, upon unwrapping the Sphinx payload of a client’s packet, sees a CourierQuery whose content is a CourierEnvelope with the following layout:

struct courier_envelope {
    u8  intermediate_replicas[2];          // replica indices in the PKI
    u8  dek1[MKEM_DEK_SIZE];               // DEK encapsulation for replica 0
    u8  dek2[MKEM_DEK_SIZE];               // DEK encapsulation for replica 1
    u8  reply_index;                       // which replica's reply to prefer
    u64 epoch;                             // replica-epoch under which the
                                           //   MKEM ciphertext was produced
    u16 sender_pubkey_len;
    u8  sender_pubkey[sender_pubkey_len];  // client's ephemeral hybrid NIKE pk
    u32 ciphertext_len;
    u8  ciphertext[ciphertext_len];        // MKEM-encrypted ReplicaInnerMessage
} 

Notable points:

Once an intermediate replica decrypts the MKEM envelope, it obtains a ReplicaInnerMessage — a discriminated union over message_type:

struct replica_inner_message {
    u8 message_type IN [0, 1];    // 0 = read, 1 = write
    union content[message_type] {
        0: struct replica_read  read_msg;   // { box_id[32] }
        1: struct replica_write write_msg;  // { box_id[32], signature[64],
                                            //   payload_len[u32], payload[] }
    };
} 

A ReplicaWrite with payload_len == 0 is a tombstone.

A CourierQuery is the top-level discriminated union that a client places into a Sphinx packet payload for the courier:

struct courier_query {
    u8 query_type IN [0, 1];
    union content[query_type] {
        0: struct courier_envelope envelope;      // read or write a single box
        1: struct copy_command     copy_command;  // AllOrNothing copy
    };
}  

The symmetric reply is a CourierQueryReply:

struct courier_query_reply {
    u8 reply_type IN [0, 1];
    union content[reply_type] {
        0: struct courier_envelope_reply envelope_reply;
        1: struct copy_command_reply     copy_command_reply;
    };
}  

The CourierEnvelope layout was given in the section called “The CourierEnvelope as seen by the courier”. The client constructs one CourierEnvelope per read or write. The courier performs the following actions.

ReplicaMessage is not a trunnel pigeonhole type; it is the core/wire/commands command sent from a courier to a replica. Its payload fields are copied verbatim from the matching CourierEnvelope:

// core/wire/commands
type ReplicaMessage struct {
    SenderEPubKey []byte     // copied from CourierEnvelope.sender_pubkey
    DEK           *[MKEM_DEK_SIZE]byte  // dek1 or dek2, depending on destination
    Ciphertext    []byte     // copied from CourierEnvelope.ciphertext
}

The recipient replica decapsulates the MKEM envelope using the replica-epoch key that corresponds to CourierEnvelope.epoch (trying each of the three keys in its tolerance window), yielding a padded ReplicaInnerMessage. The replica then dispatches on message_type to ReplicaRead or ReplicaWrite handling.

In response to a ReplicaMessage, the courier expects an asynchronous ReplicaMessageReply wire command from the replica:

// core/wire/commands
type ReplicaMessageReply struct {
    ErrorCode     uint8                 // see the replica error-code table below
    EnvelopeHash  *[HASH_SIZE]byte      // lets the courier demultiplex the reply
    EnvelopeReply []byte                // MKEM-encrypted ReplicaMessageReplyInnerMessage
}

The EnvelopeReply byte blob is produced by the replica via the MKEM scheme’s EnvelopeReply() method (see replica/handlers.go). It carries a ReplicaMessageReplyInnerMessage — a discriminated union over either a ReplicaReadReply or a ReplicaWriteReply — padded to ReplicaReplyInnerMessageReadSize() so that read replies and write replies are indistinguishable in size, and encrypted to the client’s ephemeral NIKE public key under the replica’s envelope keypair.

For each outstanding EnvelopeHash, the courier maintains an in-memory dedup entry. Its actual structure is:

// courier/server/plugin.go
type CourierBookKeeping struct {
    Epoch                uint64        // replica-epoch at cache insertion
    CreatedAt            time.Time     // for TTL eviction (~5 minutes)
    QueryType            uint8         // the query_type that produced this entry
    IntermediateReplicas [2]uint8
    EnvelopeReplies      [2]*commands.ReplicaMessageReply
}  

Note that the courier does not cache SURBs or SURB timestamps. A client’s SURB is consumed by the Sphinx-layer plugin infrastructure at the moment the courier emits a reply and is not retained by the courier’s Pigeonhole state. Should the client not receive that reply, it is expected to retransmit a fresh Sphinx packet carrying a fresh SURB but the identical CourierEnvelope body; the courier, recognising the EnvelopeHash, replies using the new SURB.

The dedup cache has a TTL of 5 minutes (DedupCacheTTL in courier/server/plugin.go).

The courier’s reply to a CourierEnvelope has the following trunnel layout:

struct courier_envelope_reply {
    u8  envelope_hash[HASH_SIZE];       // identifies the originating envelope
    u8  reply_index;                    // which intermediate replica's reply
                                        //   is being returned (may differ
                                        //   from the client's requested index)
    u8  reply_type IN [0, 1];           // 0 = ACK, 1 = PAYLOAD
    u32 payload_len;
    u8  payload[payload_len];           // the MKEM-encrypted EnvelopeReply,
                                        //   present iff reply_type == PAYLOAD
    u8  error_code;                     // see envelope error codes below
}

A reply_type of ACK (0) indicates the courier has received the envelope and dispatched it to the replicas but has not yet received a reply for the requested index. A reply_type of PAYLOAD (1) indicates the payload field carries the MKEM-encrypted EnvelopeReply produced by a replica.

Embedded inside the MKEM-encrypted ReplicaInnerMessage a client sends to a replica (via the courier) for a read operation.

struct replica_read {
    u8 box_id[BACAP_BOX_ID_SIZE];
}  

Embedded inside the MKEM-encrypted ReplicaMessageReplyInnerMessage a replica returns for a successful read. Padding is applied at the outer ReplicaMessageReplyInnerMessage level; this struct carries no padding of its own.

struct replica_read_reply {
    u8  error_code;
    u8  box_id[BACAP_BOX_ID_SIZE];
    u8  signature[BACAP_SIGNATURE_SIZE];
    u32 payload_len;
    u8  payload[payload_len];
}

Used both (a) embedded inside the MKEM-encrypted ReplicaInnerMessage for a client write, and (b) carried directly as a core/wire/commands command between replicas during replication.

struct replica_write {
    u8  box_id[BACAP_BOX_ID_SIZE];
    u8  signature[BACAP_SIGNATURE_SIZE];
    u32 payload_len;
    u8  payload[payload_len];
}

A ReplicaWrite with payload_len == 0 is a tombstone. Replicas treat tombstone writes as overwrites: an existing box at the same box_id is replaced by the tombstone, and subsequent reads return ReplicaErrorTombstone.

Embedded inside a ReplicaMessageReplyInnerMessage on the client reply path, and also used as the core/wire/commands reply to inter-replica replication.

struct replica_write_reply {
    u8 error_code;
}

Returned by a replica in ReplicaMessageReply.ErrorCode, ReplicaReadReply.error_code, and ReplicaWriteReply.error_code.

Codes 1, 10 and 11 are “expected outcomes” — they correspond to normal protocol states rather than faults. The thin-client helper thin.IsExpectedOutcome(err) treats these three codes as non-errors.

Returned by the courier in CourierEnvelopeReply.error_code.

Returned by the courier in CopyCommandReply.status (see below).

Returned by the courier in the status field of a CopyCommandReply. (See the section called “CopyCommandReply” for more information.)

The client uploads a temporary Pigeonhole stream.

The stream is sequence of CourierEnvelopes. Each CourierEnvelope is serialized and prefixed with a single 4-byte (u32) length field giving the size of that one envelope; the resulting length-prefixed blobs are concatenated back-to-back into one continuous byte stream.

That byte stream is then split across the BACAP Boxes of the temporary stream. A serialized CourierEnvelope is strictly larger than the maximum BACAP box payload (it wraps a full box payload plus its own metadata), so a single envelope does not fit in one box and the concatenated stream necessarily spans several boxes. Envelope boundaries therefore do not align with box boundaries. The precise framing is given in the section called “Temporary stream data format”.

The client sends a random courier the copy command which encapsulates the write capability to the temporary Pigeonhole stream written in Step 1 above. When the courier receives this copy command it extracts the ReadCap from the given WriteCap and uses it to read the stream of data. The courier then reads a box at a time and tries to extract 0 or 1 envelopes from each accumulation of stream segments.

After processing the command, the courier then overwrites the temporary stream with tombstones.

Each box in the temporary stream is a serialized CopyStreamElement. Defined in trunnel as:

// CopyStreamElement - wraps a CourierEnvelope chunk with stream position flags.
// Overhead: 1 byte (flags) + 4 bytes (envelope_len) = 5 bytes
struct copy_stream_element {
    // Flags: bit 0 = isStart, bit 1 = isFinal
    u8 flags;
  
    // The CourierEnvelope serialized bytes
    u32 envelope_len;
    u8 envelope_data[envelope_len];
}

Here it is in golang:

type CopyStreamElement struct {
    Flags        uint8
    EnvelopeLen  uint32
    EnvelopeData []uint8
}

The purpose of this specific format is to use the isStart and isFinal flags to tell the courier the first box and last box of the stream to process. The payload encapsulated within the EnvelopeData fields of many of these CopyStreamElements is itself a stream of data which contains CourierEnvelopes with four-byte prefixes.

A key property of this encoding is that envelope boundaries do not align with box boundaries. Each BACAP box payload has a maximum size of N bytes, but a serialized CourierEnvelope (which contains a full box payload plus metadata) exceeds N bytes. Therefore envelopes are serialized into a continuous byte stream and split across multiple boxes in the temporary copy stream:

TEMPORARY COPY STREAM BOXES (each holds N bytes):
┌─────────────┐ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐
│    Box 0    │ │    Box 1    │ │    Box 2    │ │    Box 3    │ │    Box 4    │
└─────────────┘ └─────────────┘ └─────────────┘ └─────────────┘ └─────────────┘
SERIALIZED ENVELOPE DATA (envelope boundaries don't align with box boundaries):
┌─────────────────────────┐┌────────────────────┐┌──────────────────────────┐
│       Envelope 1        ││     Envelope 2     ││       Envelope 3         │
└─────────────────────────┘└────────────────────┘└──────────────────────────┘
|         |         |         |         |         |
     Box 0     Box 1     Box 2     Box 3     Box 4

The courier reads the stream box by box, accumulating data until it can extract complete envelopes. The isStart and isFinal flags on the CopyStreamElement wrappers tell the courier where the stream begins and ends.

Each embedded CourierEnvelope is processed as a normal write and results in a ReplicaMessage being dispatched to the intermediate replicas over the wire protocol.

The courier does NOT need to keep track of the EnvelopeHash for each contained CourierEnvelope for the purpose of replying to the client (the “client” of these envelopes being, in this case, the courier itself), but it does need to keep resending them until the intermediate replicas have ACKed them.

The courier MUST keep track of the hash of the CopyCommand (computed as BLAKE2b-256(write_cap)) and MUST NOT process a given command more than once. This dedup cache has a TTL of 30 minutes (CopyDedupCacheTTL in courier/server/plugin.go).

CopyCommand is sent by a client to its chosen courier after the client has successfully uploaded every box of the temporary stream. The trunnel layout is:

struct copy_command {
    u32 write_cap_len;
    u8  write_cap[write_cap_len];   // serialized BACAP BoxOwnerCap
}

On receipt, the courier:

Replica error handling during a CopyCommand is classified as temporary or permanent by courier/server/copy_errors.go: transient errors (storage full, database failure, internal error, replication failed, box-ID not found) trigger bounded retries against the same shard before failover; permanent errors (invalid box ID, invalid signature, invalid payload, invalid epoch, box already exists, tombstone) cause immediate failover or abort.

The courier’s reply to a CopyCommand has the following trunnel layout:

struct copy_command_reply {
    u8  status;                   // CopyStatus{Succeeded, InProgress, Failed}
    u8  error_code;               // replica error code (meaningful iff status == Failed)
    u64 failed_envelope_index;    // 1-based sequential position in the
                                  //   CourierEnvelope stream at which processing
                                  //   stopped (meaningful iff status == Failed)
}  

The status codes are enumerated in “Copy command status codes” above. failed_envelope_index counts envelopes within the stream, not boxes: the first envelope in the first box of the temporary stream is index 1.

A client receiving CopyStatusInProgress should continue polling — i.e. resend the same CopyCommand via a fresh SURB after a short interval (CopyPollInterval, currently 5 seconds) — until it receives either CopyStatusSucceeded or CopyStatusFailed. Because the courier’s copy dedup cache keys on BLAKE2b-256(write_cap), these repeated polls will not cause the CopyCommand to be processed more than once.

In no particular order:

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

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. The reveal_too_early and reveal_too_late codes 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 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.

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.

{
"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.

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 value of vote_not_found.

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 its header is MAC-verified as described in SPHINXSPEC.

Since mix servers publish future epoch keys, our replay detection forms a special kind of double-bloom-filter system. During the epoch grace period, servers perform a trial decryption of Sphinx packets. The replay cache used is the one associated with the Sphinx routing key that was successfully used to decrypt (unwrap transform) the Sphinx packet. This is not a double-bloom filter in the normal sense of the term since each bloom filter used is distinct and associated with its own cache. Furthermore, replay tags are only 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:

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 the section called “Epoch boundaries”.

The mix server periodically updates its knowledge of the network by downloading a new consensus document as described in KATZMIXPKI. The individual threads in the cryptoworker thread pool that process Sphinx packets make use of a MixKey data structure consisting of the following:

Each of these cryptoworker threads has its own hashmap associating epochs with a reference to the MixKey. The mix server PKI thread maintains a single hashmap which associates the epochs with the corresponding MixKey. We 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 its associated on-disk data are purged.

Although we do not discuss synchronization primitives, 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 the section called “Sphinx parameter constants”. These are all derived parameters, and are primarily of interest to implementers.

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 RoutingCommand 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 NullCommand structure is as follows:

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

The NextNodeHopCommand structure is as follows:

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

The RecipientCommand structure is as follows:

struct {
opaque recipient[RECIPEINT_ID_LENGTH];
} RecipientCommand;

The SURBReplyCommand 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 NullCommandRoutingCommand, resulting in “appending zero filled padding” producing valid output.

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

Every non-terminal hop’s RoutingCommands 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 as described in the section called “Single-use reply block (SURB) creation”) using 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:

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:

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

Inputs:

Outputs:

The Sphinx_Create_Packet operation consists of the following steps: