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

Thin clients MUST randomize their abstract unix domain socket name otherwise the static name will prevent multiplexing because the kernel requires that the connection be between uniquely nameed socket pairs. The Katzenpost reference implementation of the thin client library selects a socket name with four random hex digits appended to the end of the name like so:

@katzenpost_golang_thin_client_DEADBEEF

The client2 daemon listens on an abstract unix domain socket with the following name:

@katzenpost

Note that there are two protocol message types and they are always CBOR encoded. We do not make use of any prefix length encoding because the socket type preserves message boundaries for us. Therefore we simply send over pure CBOR encoded messages.

The daemon sends the Response message which is defined in golang as a struct containing an app ID and one of four possible events:

type Response struct {
// AppID must be a unique identity for the client application
// that is receiving this Response.
AppID *[AppIDLength]byte `cbor:app_id`

ConnectionStatusEvent *ConnectionStatusEvent `cbor:connection_status_event`

NewPKIDocumentEvent *NewPKIDocumentEvent `cbor:new_pki_document_event`

MessageSentEvent *MessageSentEvent `cbor:message_sent_event`

MessageReplyEvent *MessageReplyEvent `cbor:message_reply_event`
}

type ConnectionStatusEvent struct {
IsConnected bool `cbor:is_connected`
Err error `cbor:err`
}

type NewPKIDocumentEvent struct {
Payload []byte `cbor:payload`
}

type MessageReplyEvent struct {
MessageID *[MessageIDLength]byte `cbor:message_id`
SURBID *[sConstants.SURBIDLength]byte `cbor:surbid`
Payload []byte `cbor:payload`
Err error `cbor:err`
}

type MessageSentEvent struct {
MessageID *[MessageIDLength]byte `cbor:message_id`
SURBID *[sConstants.SURBIDLength]byte `cbor:surbid`
SentAt time.Time `cbor:sent_at`
ReplyETA time.Duration `cbor:reply_eta`
Err error `cbor:err`
}

The client sends the Request message which is defined in golang as:

type Request struct {
// ID is the unique identifier with respect to the Payload.
// This is only used by the ARQ.
ID *[MessageIDLength]byte `cbor:id`

// WithSURB indicates if the message should be sent with a SURB
// in the Sphinx payload.
WithSURB bool `cbor:with_surb`

// SURBID must be a unique identity for each request.
// This field should be nil if WithSURB is false.
SURBID *[sConstants.SURBIDLength]byte `cbor:surbid`

// AppID must be a unique identity for the client application
// that is sending this Request.
AppID *[AppIDLength]byte `cbor:app_id`

// DestinationIdHash is 32 byte hash of the destination Provider's
// identity public key.
DestinationIdHash *[32]byte `cbor:destination_id_hash`

// RecipientQueueID is the queue identity which will receive the message.
RecipientQueueID []byte `cbor:recipient_queue_id`

// Payload is the actual Sphinx packet.
Payload []byte `cbor:payload`

// IsSendOp is set to true if the intent is to send a message through
// the mix network.
IsSendOp bool `cbor:is_send_op`

// IsARQSendOp is set to true if the intent is to send a message through
// the mix network using the naive ARQ error correction scheme.
IsARQSendOp bool `cbor:is_arq_send_op`

// IsEchoOp is set to true if the intent is to merely test that the unix
// socket listener is working properly; the Response payload will be
// contain the Request payload.
IsEchoOp bool `cbor:is_echo_op`

// IsLoopDecoy is set to true to indicate that this message shall
// be a loop decoy message.
IsLoopDecoy bool `cbor:is_loop_decoy`

// IsDropDecoy is set to true to indicate that this message shall
// be a drop decoy message.
IsDropDecoy bool `cbor:is_drop_decoy`
}

Upon connecting to the daemon socket the client must wait for two messages. The first message received must have it’s is_status field set to true. If so then it’s is_connected field indicates whether or not the daemon has a mixnet PQ Noise protocol connection to an entry node.

Next the client awaits the second message which contains the PKI document in it’s payload field. This marks the end of the initial connection sequence. Note that this PKI document is stripped of all cryptographic signatures.

In the next protocol phase, the client may send Request messages to the daemon in order to cause the daemon to encapsulate the given payload in a Sphinx packet and send it to the entry node. Likewise the daemon my send the client Response messages at any time during this protocol phase. These Response messages may indicated a connection status change, a new PKI document or a message sent or reply event.

There are several Request fields that we need to discuss.

Firstly, each Request message sent by a thin client needs to have the app_id field set to an ID that is unique among the applications using thin clients. The app_id is used by the daemon to route Response messages to the correct thin client socket.

The rest of the fields we are concerned with are the following:

If a one way message should be sent with no SURB then with_surb should be set to false and surbid may be nil. If however the thin client wishes to send a reliable message using the daemon’s ARQ, then the following fields must be set:

A thin client connection always begins with the daemon sendings the client two messages, a connection status followed by a PKI document.

After this connection sequence phase, the daemon may send the thin client a connection status or PKI document update at any time.

Thin clients recieve four possible events inside of Response messages:

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

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

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

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

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