cMixx Design Specification
Benjamin Wenger
Richard T. Carback III
David Stainton
version 0
Abstract
This document describes the xx network cMix design variations and implementation parameterizations; that is, our mixing strategy which is at the core design of our anonymous communication network.
Introduction
cMix is a verified batch mixing strategy which uses the cryptographic and partial homomorphic properties of the ElGamal encryption protocol, which is described at length in the published cMix paper. However this document will very likely be a much more approachable description of the core designs of the cMix mixing strategy.
One of the main motivations behind the cMix design is the computational efficiency of the real time mixing phase of the protocol which does not perform any public key operations. The real time phase is essentially a series of modular multiplications within a prime order cyclic group. This is made possible by the precomputation phase.
Ciphersuite
For our cMix implementation we are using the RFC 3526 specified 4096 bit Mod P cyclic group for our ElGamal/cMix encryption and homomorphic operations:
This prime is: 2^4096  2^4032  1 + 2^64 * { [2^3966 pi] + 240904 }
Its hexadecimal value is:
FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
15728E5A 8AAAC42D AD33170D 04507A33 A85521AB DF1CBA64
ECFB8504 58DBEF0A 8AEA7157 5D060C7D B3970F85 A6E1E4C7
ABF5AE8C DB0933D7 1E8C94E0 4A25619D CEE3D226 1AD2EE6B
F12FFA06 D98A0864 D8760273 3EC86A64 521F2B18 177B200C
BBE11757 7A615D6C 770988C0 BAD946E2 08E24FA0 74E5AB31
43DB5BFC E0FD108E 4B82D120 A9210801 1A723C12 A787E6D7
88719A10 BDBA5B26 99C32718 6AF4E23C 1A946834 B6150BDA
2583E9CA 2AD44CE8 DBBBC2DB 04DE8EF9 2E8EFC14 1FBECAA6
287C5947 4E6BC05D 99B2964F A090C3A2 233BA186 515BE7ED
1F612970 CEE2D7AF B81BDD76 2170481C D0069127 D5B05AA9
93B4EA98 8D8FDDC1 86FFB7DC 90A6C08F 4DF435C9 34063199
FFFFFFFF FFFFFFFF
The generator is: 2.
https://datatracker.ietf.org/doc/html/rfc3526#section5
Message Structure
Due to the nature of how ElGamal encryption works, the cMix payload in the paper
is the same size as the encryption keys. In the case of the xx network
we use two payloads (defined below as payloadA
and payloadB
), each are 4096 bits
in size as our keys are 4096 bits.
Message Structure (not to scale)
++
 Message 
 2*primeSize bits 
+++
 payloadA  payloadB 
 primeSize bits  primeSize bits 
+++++++++
 grpBitA  keyFP version Contents1  grpBitB  MAC  Contents2  ephemeralRID  SIH 
 1 bit  255 bits 1 byte  *below*  1 bit  255 b  *below*  64 bits  200 bits 
+ ++++++++
 Raw Contents 
 2*primeSize  recipientID bits 
++
* size: size in bits of the data which is stored
* Contents1 size = primeSize  grpBitASize  KeyFPLen  sizeSize  1
* Contents2 size = primeSize  grpBitBSize  MacLen  RecipientIDLen  timestampSize
* the size of the data in the two contents fields is stored within the "size" field
/////Adherence to the group/////////////////////////////////////////////////////
The first bits of keyFingerprint and MAC are enforced to be 0, thus ensuring
PayloadA and PayloadB are within the group
Contents1 and Contents2 are used to transmit the mix network client's payload whereas the other sections of the message have various other uses. Our source code represents this with a Message type in Go:
// Message structure stores all the data serially. Subsequent fields point to
// subsections of the serialised data.
type Message struct {
data []byte
// Note: These are mapped to locations in the data object
payloadA []byte
payloadB []byte
keyFP []byte
version []byte
contents1 []byte
mac []byte
contents2 []byte
ephemeralRID []byte // Ephemeral reception ID
sih []byte // Service Identification Hash
rawContents []byte
}
One byte is used to indicate the message format version because it's conceivable we could upgrade the message format in the future. The grpBitA and grpBitB bits are carefully set to avoid 0 vs 1 biasing which would allow for a probabalistic tagging attack:
SetGroupBits takes a message and a cyclic group and randomly sets
the highest order bit in its 2 sub payloads, defaulting to 0 if 1
would put the subpayload outside of the cyclic group.
WARNING: the behavior above results in 0 vs 1 biasing. in general, groups
used have many (100+) leading 1s, which as a result would cause
a bias of ~ 1:(12^numLeadingBits). with a high number of leading bits,
this is a non issue, but if a prime is chosen with few or no leading bits,
this will cease to solve the tagging attack it is meant to fix
Tagging attack: if the dumb solution of leaving the first bits as 0 is
chosen, it is possible for an attacker to 75% of the time (when one or
both leading bits flip to 1) identity a message they made multiplied
garbage into for a tagging attack. This fix makes the leading its
random in order to thwart that attack
Protocol Phases
Pseudo Code Cryptographic Function Glossary
The following sections are populated with pseudo code examples which are used to explain sections of our cryptographic protocols. It is hoped that this glossary will help you understand the pseudo code.

: byte concatenation

H(x): H is a cryptographic hash function.

HMAC(key, data): HMAC uses the given key to compute an HMAC over the given data.

DH(my_private_key, partner_public_key):
Diffiehellman function used to calculate a shared secret. 
GenerateDHKeypair(): returns a DH keypair

E(key, payload): Streamcipher encrypt payload.

D(key, payload): Streamcipher decrypt payload.

Sign(private_key, payload): Returns a cryptographic signature.

Verify(public_key, data, signature): Returns a boolean which will be true if the
signature
is a signature ofdata
and is valid for the given public key.
Requisite Mathematical Considerations
You should be familiar with how the diffiehellman shared secret computation works. If not we recommend reading the Diffie–Hellmen wikipedia article.
Remember the transformations of exponents:
g^a * g^b = g^(a + b)
And also remember that just like addition and multiplication, exponentiation is also commutative:
g^a^b = g^b^a = g^(a*b)
And likewise we must remember multiplying the inverse of a term is equivalent to division by that term:
x^1 = 1/x
g^b = g^(a*b) * g^a^1
g^b = g^(a*b) / g^a
Requisite ElGamal Encryption Considerations
The cMix paper defines it's ElGamal encryption function like this:
func elgamal_encrypt(key, payload []byte) ([]byte, []byte) {
x = randKeyGen()
return g^x, payload * key^x
}
However we define it like this in our implementation:
func elgamal_encrypt(key, payload []byte) ([]byte, []byte) {
x = randKeyGen()
return payload * g^x % p, key^x % p
}
That is, in either case the elgamal_encrypt
function returns a
2tuple, however in our implementation the first element of this
2tuple contains the message ciphertext and the later element contains
the encrypted key.
In the above notation the p
is meant to be our prime order cyclic
group as defined above in the Ciphersuite section;
from now on the modulo will be implied and not explicitly written in
each expression and equation. In this ElGamal encryption example the
we generate a new key pair:
private_key = genKey()
public_key = g^private_key
In this next pseudo code sample we take x
to be the randomly generated
key within the above elgamal_encryption
function definition:
elgamal_encrypt(public_key, message)
// which is equivalent to either of these 2tuples:
= (message * g^x, public_key^x)
= (message * g^x, g^private_key^x)
Our strip function definition looks like this:
func strip(key, ciphertext []byte) []byte {
return (key^1) * ciphertext
}
Which works like this:
private_key = genKey()
public_key = g^private_key
// computes: (sent_message * g^x, public_key^x)
ciphertext, encrypted_key = elgamal_encrypt(public_key, sent_message)
message = strip(encrypted_key * private_key^1, ciphertext)
// which computes the message reveal:
strip(g^x, ciphertext)
// which is equivalent to:
strip(g^x, message * g^x)
// which could also be written like this:
(message * g^x) * g^x^1
Preparation Phase
Before sending a cMix message, the client needs to participate in a preparatory protocol phase by sending key requests and processing responses. This protocol interaction between the client and the Gateway is done so using the xx network's wire protocol, also known as gRPC/TLS/IP.
Each mix node is paired with one Gateway. The client is directly connected to an arbitrary Gateway. All gateways are capable of proxying the key requests to the correct Gateway. This Gateway in turn proxies the key request to the destination mix node. The mix node's reply takes the reverse of this route back to the client. This is a strict request/response protocol with essentially only two message types as we shall soon see.
The client composes a ClientKeyRequest
and then encapsulates it within
a SignedClientKeyRequest
along with a signature. Within the
ClientKeyRequest
itself there is a SignedRegistrationConfirmation
which also must be verified by the recipient. Here are the protobuf
definitions for ClientKeyRequest
and SignedClientKeyRequest
:
message ClientKeyRequest {
// Salt used to generate the Client ID
bytes Salt = 1;
// NOTE: The following entry becomes a pointer to the blockchain that denotes
// where to find the users public key. The node can then read the blockchain
// and verify that the registration was done properly there.
SignedRegistrationConfirmation ClientTransmissionConfirmation = 2;
// the timestamp of this request,
int64 RequestTimestamp = 3;
// timestamp of registration, tied to ClientRegistrationConfirmation
int64 RegistrationTimestamp = 4;
// The public key of the client for the purposes of creating the diffie helman sesskey
bytes ClientDHPubKey = 5;
}
message SignedClientKeyRequest {
// Wire serialized format of the ClientKeyRequest Object (above)
bytes ClientKeyRequest = 1;
// RSA signature signed by the client
messages.RSASignature ClientKeyRequestSignature = 2;
// Target Gateway/Node  used to proxy through an alternate gateway
bytes Target = 3;
}
That ClientKeyRequestSignature
is in fact not merely a signature of
the serialized ClientKeyRequest
because the signing algorithm is RSA
therefore the output will be the same size as the input which in this
case is the hash of the serialized ClientKeyRequest
. The client's DH
public key is cryptographically linked with this signature since it's
encapsulating message is serialized, hashed and then signed. This is
common practice when using RSA signatures.
Here's where the signature is created:
https://git.xx.network/elixxir/client//blob/release/network/node/register.go#L225
The response message is of type SignedKeyResponse
which encapsulates
ClientKeyResponse:
message ClientKeyResponse {
bytes EncryptedClientKey = 1;
bytes EncryptedClientKeyHMAC = 2;
bytes NodeDHPubKey = 3;
bytes KeyID = 4; // Currently unused and empty.
uint64 ValidUntil = 5; // Timestamp of when the key expires
}
message SignedKeyResponse {
bytes KeyResponse = 1;
messages.RSASignature KeyResponseSignedByGateway = 2;
bytes ClientGatewayKey = 3; // Stripped off by node gateway
string Error = 4;
}
However this message is proxied through the client's Gateway which
puts the ClientGatewayKey
into a database and then removes it from the
message. Therefore the client only receives the KeyResponse
and the
signature. As the field name implies, KeyResponseSignedByGateway
contains a signature computed by the Gateway.
Here we use pseudo code to show the cryptographic operations done by the mix node after verifying that the sender is the authenticated Gateway for this mix node:
func node_handle_key_request(request *SignedKeyRequest) (*SignedKeyResponse, error) {
if !Verify(registrationPubKey,
H(timestamp  request.ClientKeyRequest.ClientTransmissionConfirmation.RSAPubKey),
request.ClientKeyRequest.ClientTransmissionConfirmation.RegistrarSignature) {
return nil, SignatureVerificationFailure
}
key = request.ClientKeyRequest.ClientTransmissionConfirmation.RSAPubKey
data = H(request.ClientKeyRequest)
signature = request.ClientKeyRequestSignature
if !Verify(key, data, signature) {
return nil, SignatureVerificationFailure
}
encryption_key = DH(request.ClientKeyRequest.ClientDHPubKey, node_dh_priv_key)
client_key = H(node_secret  client_ID)
ciphertext = E(encryption_key, client_key)
client_gateway_key = H(client_key)
dh_pub_key, dh_priv_key = GenerateDHKeypair()
session_key = DH(request.ClientKeyRequest.ClientDHPubKey, dh_priv_key)
encrypted_key_hmac = HMAC(session_key, encrypted_key)
return &SignedKeyResponse{
ClientGatewayKey: client_gateway_key,
ClientKeyResponse: ClientKeyResponse{
EncryptedClientKey: encrypted_key,
EncryptedClientKeyHMAC: encrypted_key_hmac,
NodeDHPubKey: dh_pub_key,
},
}, nil
}
The SignedKeyResponse
is then proxied through the Gateway who signs
the message and removes the ClientGatewayKey
, roughly in pseudo code
like this:
func gateway_proxy_response(response *SignedKeyResponse) *SignedKeyResponse {
insert_into_database(response.ClientGatewayKey)
return &SignedKeyResponse{
KeyResponseSignedByGateway: Sign(gateway_private_key, H(response.ClientKeyResponse)),
ClientKeyResponse: response.ClientKeyResponse,
}
}
The client checks the response signature and then derives the
encryption_key
via a Diffiehellman computation and then decrypts the
key:
func client_handle_response(response *SignedKeyResponse) {
key = gateway_pub_key
data = response.ClientKeyResponse
signature = response.KeyResponseSignedByGateway
if !Verify(key, data, signature) {
return SignatureVerificationFailure
}
encryption_key = DH(client_dh_priv_key, response.ClientKeyResponse.NodeDHPubKey)
key = D(encryption_key, response.ClientKeyResponse.EncryptedClientKey)
do_stuff_with_key(key)
}
Message Encryption
For the given mix cascade which the client has selected to transport their message, the client must combine the set of mix keys by multiplying them together. The resulting key is then used to encrypt the cMix message payload.
cMix message encryption is simply modular multiplication as described in the ElGamal paper. The cMix paper defines it's ElGamal encryption function like this:
func elgamal_encrypt(key, payload []byte) ([]byte, []byte) {
x = randKeyGen()
return g^x % p, payload * key^x % p
}
However we define it like this in our implementation:
func elgamal_encrypt(key, payload []byte) ([]byte, []byte) {
x = randKeyGen()
return payload * g^x % p, key^x % p
}
That is, in either case the elgamal_encrypt
function returns a
2tuple, however in our implementation the first element of this
2tuple contains the message ciphertext and the later element contains
the encrypted key.
In the above notation the p
is meant to be our prime order cyclic
group from RFC 3526; from now on the modulo will be implied and not explicitly
written in each expression and equation.
As previously mentioned, the cMix message has two payloads. Therefore the function to encrypt our client cMix payloads looks like this:
func clientEncrypt(msg Message, salt []byte, roundID RoundID, baseKeys []Key) Message {
salt2 = H(salt)
keyEcrA = ClientKeyGen(grp, salt, roundID, baseKeys)
keyEcrB = ClientKeyGen(grp, salt2, roundID, baseKeys)
EcrPayloadA, _ = elgamal_encrypt(keyEcrA, msg.PayloadA)
EcrPayloadB, _ = elgamal_encrypt(keyEcrB, msg.PayloadB)
primeLen = p.Len()
encryptedMsg = NewMessage(primeLen)
encryptedMsg.SetPayloadA(EcrPayloadA.LeftpadBytes(uint64(primeLen)))
encryptedMsg.SetPayloadB(EcrPayloadB.LeftpadBytes(uint64(primeLen)))
return encryptedMsg
}
The keys to encrypt each payload are deterministically generated by iteratively hashing with Blake2b and then SHA256 each symmetric key along with the salt, cMix Round ID and the string "cmixClientNodeKeyGenerationSalt". The resulting 32 byte value is then feed into HKDF_SHA256, and expanded to the correct number of bytes for the prime order cyclic group.
func ClientKeyGen(salt []byte, roundID RoundID, symmetricKeys []*Key) *Key {
output = NewKey()
tmpKey = NewKey()
for _, symmetricKey = range symmetricKeys {
h = SHA256_Hash(
Blake2b_Hash(
symmetricKey  salt  roundID  "cmixClientNodeKeyGenerationSalt"))
hashFunc = func() goHash.Hash { return sha256.New() }
keyGen = hkdf.Expand(hashFunc, h, nil)
pBytes = make([]byte, p.Len())
tmpKey, err = csprng.GenerateInGroup(pBytes, len(p.Len()), keyGen)
if err != nil {
panic(err)
}
output = tmpKey * output % p
}
return Inverse(output)
}
You may recall from the ElGamal encryption protocol that the inverse of the encryption key is used to decrypt. And as mentioned previously, cMix makes use of the partial homomorphic properties of ElGamal to form the group computations. In particular, all the mix nodes in a given cascade perform their computations on the message to decrypt it.
We prevent the mix nodes from having to invert the key by having the client encrypt with the inverted key. That way, when the mix nodes deterministically compute their keys, they perform the exact same steps as the client except that they ommit the final inversion step. The generated key is the inverse of the key used to encrypt and therefore can be used to decrypt.
Likewise the GenerateInGroup
is designed specifically for generating
keys within a cyclic group for usage with ElGamal cryptosystems. You can
see the gory details in the code, here:
https://git.xx.network/xx_network/crypto//blob/release/csprng/source.go#L82186
Mix Node Slot
Here we have the protobuf definition of the Slot
message type. It
actually has two discrete uses. The first is for precomputation
fields and for that it's exchanged between mix nodes. The other use is
realtime mixing where the client sends the Slot
message to the Gateway
and it continues through the mix cascade.
// Represents a single encrypted message in a batch
message Slot {
// Index in batch this slot belongs in
uint32 Index = 1;
// Precomputation fields
bytes EncryptedPayloadAKeys = 2;
bytes EncryptedPayloadBKeys = 3;
bytes PartialPayloadACypherText = 4;
bytes PartialPayloadBCypherText = 5;
bytes PartialRoundPublicCypherKey = 6;
// Realtime/client fields
bytes SenderID = 7; // 256 bit Sender Id
bytes PayloadA = 8; // Len(Prime) bit length payload A (contains part of encrypted payload)
bytes PayloadB = 9; // Len(Prime) bit length payload B (contains part of encrypted payload, and associated data)
bytes Salt = 10; // Salt to identify message key
repeated bytes KMACs = 11; // Individual Key MAC for each node in network
}
Inbound Message Queueing
Clients send their messages to any Gateway which in turn proxies the message to the Gateway assigned to the chosen mix cascade. The cascade's assigned Gateway queues messages until either 1000 messages are accumulated or no more time is left to collect messages. The Gateway then sends the batch of 1000 messages to the first mix node. If less than 1000 messages were accumulated then the Gateway sends dummy messages in place of the missing messages.
Realtime Mix Node Message Processing
This section describes the cMix mixing strategy. Many of the mathematical details are described in the published cMix paper and assume an understanding of cryptographic protocol composition using ElGamal. However here we attempt a more approachable explanation of the cMix design.
Keep in mind that a batch mix strategy at minimum has two basic goals each time it mixes a batch of messages:

Bitwise message unlinkability: This means we use message encryption such that the input is transformed so that the output message is different. The two cannot be linked by their patterns of bits.

The output message slots are shuffled in relation to the input message slots.
An implied consequence of the fundamental design goals of mix networks is end to end encryption from the sending client to the last mix node in the mix cascade. This guarantees message authenticity and confidentiality all the way to the last node. After that point the contents of the message will not be protected by the mix network protocol.
Mix networks have an anytrust threat model which means that clients can rely on the mix cascade to provide anonymity privacy properties as long as any of the mix nodes in that mix cascade are honest and not compromised. See our threat model document for more discussion about our mix network threat model.
Each cMix message is composed of two payloads, PayloadA and PayloadB. The reason for this design is simple: In ElGamal, the message size is limited to the size of the cyclic group space. It turns out that our choice of 4096 bit cyclic group did not provide a big enough payload capacity for a few of our intended use cases. One of those use cases is the end to end ratchet encryption protocol described in our end to end protocol design document because it exchanges large SIDH keys.
Below we work an example for a single message traversing a mix cascade
composed of three mix nodes. However this can in principle be scaled
to N mix nodes per cascade. And likewise we attempt to simplify the
explanation of the cMix realtime protocol phase by only considering a
single message whereas our mix node implementation operates on 1000
messages per mix batch. Below we write our pseudo code notation using
the permute
function to denote using the Fisher Yates shuffling alogrithm.
Realtime Phase 1: Preprocessing and ReEncryption
Firstly, the cMix client makes use of the xx network's wire protocol, gRPC/TLS/TCP/IP,
and sends a Slot
message to the Gateway:
M * K1 * K2 * K3, senderID, salt, KMAC1, KMAC2, KMAC3
The KMACs fields are used to ensure that the ciphertext was composed of the expected symmetric keys. Each hop through the mix cascade results in one of the K values being removed and an R value being multiplied in.
If we describe all the transformations in this phase it would look like this for three hops:
// hop 1
[M * K1 * K2 * K3] * [k1^1 * R1] = [M * K2 * K3 * R1], senderID, salt, KMAC2, KMAC3
// hop 2
[M * K2 * K3 * R1] * [k2^1 * R2] = [M * K3 * R1 * R2], senderID, salt, KMAC3
// hop 3
[M * K3 * R1 * R2] * [k3^1 * R3] = [M * R1 * R2 * R3]
At hop 1, the mix node receives this message:
[M * K1 * K2 * K3], senderID, salt, KMAC1, KMAC2, KMAC3
Hop 1 compares HMAC(K1, K1) == KMAC1
, if not equal then the message
is discarded, else continue. Hop 1 removes the KMAC1 field from the
message. Hop 1 cryptographically transforms the payload portion of the
message by multiplying in R1
and by removing the K1
factor by
multiplying in it's inverse:
[M * K1 * K2 * K3] * [K1^1 * R1] = [M * K2 * K3 * R1]
Therefore the message transmitted from Hop 1 to Hop 2 is:
[M * K2 * K3 * R1], senderID, salt, KMAC2, KMAC3
Once all mixes process the message in this way, all the K values are
removed from the message and the R
values are multiplied in.
Additionally the SenderID, Salt, KMACs are stripped off the message
resulting in the following message ciphertext:
M * R1 * R2 * R3
Realtime Phase 2: Mixing
Every mix node reorders all messages in the batch and multiplies in blinding factor S.
For example the output of the first mix node includes the S1
factor:
permute{M * R1 * R2 * R3} * S1
And after traversing all the mix nodes in the cascade the message becomes:
permute{permute{permute{M * R1 * R2 * R3} * S1} * S2} * S3
Realtime Phase 3: Reveal
This precomputed value is used to reveal the message, M:
(permute{permute{permute{M * R1 * R2 * R3} * S1} * S2} * S3) * ((permute{permute{permute{R1 * R2 * R3} * S1} * S2} * S3)^1) = M
This last message reveal computation is performed by the last mix in the mix cascade.
Notice: The notation in the above mathematical expressions indicate the use of the permutation function before multiplying the terms together to make them easier to read. Our implimentation runs the permute function last because it was easier to implement that way. These are mathematically equivalent as long as they are done consistently throughout all protocol phases.
Cascade Mix Precomputation
The Precomputation phases of the protocol happens before the realtime mixing. The results of the precomputation in a mix cascade composed of three mix nodes is computed like this:
(permute{permute{permute{R1 * R2 * R3} * S1} * S2} * S3)^1
In our above notation each of the R1
and S1
variables indicate a random
value chosen by the first mix node. Each R
and S
value in turn is selected
by each mix in the cascade. It is a group computation which is achieved by
using the homomorphic properties of modular multiplication.
Setup Shared Public Key
A prerequisite for the precomputation protocol phases is the computation of
a shared secret among all the mix nodes in the given mix cascade. We
call this the multiparty diffiehellman
and it's computed like so:
 The first mix node generates a new key,
a
and raisesg
to the power ofa
and sends that to the next mix node:
g^a
 The second mix node generates a new key,
b
and receivesg^a
and raises this to the power ofb
and sends that to the next mix node:
g^a^b
 The last mix node generates a new key,
c
and receivesg^a^b
and raises this to the power ofc
and broadcasts this to all the other nodes:
g^a^b^c
The cMix paper mentions the
generation of this shared public key in the Setup
section on page 7
at the bottom of the page. Our implementation computes the shared
secret here:
The last mix node sends the shared public key to the rest of mix nodes in the cascade. Furthermore our code contains the assertion:
g^a^b^c == g^b^c^a == g^c^b^a == g^c^a^b == g^b^a^c == g^a^c^b
Precomputation Phase 1: Multiplying in the encrypted R values
In this phase of the protocol each mix node in turn multiplies
in it's encrypted R
value creating a new 2tuple to send to the
next mix node in the cascade.
We initialize with a 2tuple value of (1,1).
The computation performed at each mix node is simply:
Multiply the given 2tuple with the resulting 2tuple of the
ElGamal encryption of that node's R
value. In pseudo code it looks
like this where the initial 2tuple is passed into the function arguments:
func handle_phase1(encrypted_key, ciphertext []byte) ([]byte, []byte) {
new_ciphertext, new_encrypted_key = elgamal_encrypt(k, R)
return ciphertext * new_ciphertext, encrypted_key * new_encrypted_key
}
Here's what all the expanded calculations look like for each hop:
// Hop 1
previous_ciphertext = 1
previous_encrypted_key = 1
ciphertext, encrypted_key = elgamal_encrypt(Z, R1)
ciphertext = R1 * g^x1
encrypted_key = Z^x1
new_ciphertext = previous_ciphertext * ciphertext
new_ciphertext = 1 * ciphertext
new_ciphertext = 1 * R1 * g^x1
new_ciphertext = R1 * g^x1
new_encrypted_key = previous_encrypted_key * encrypted_key
new_encrypted_key = 1 * encrypted_key
new_encrypted_key = 1 * Z^x1
new_encrypted_key = Z^x1
// Hop 2
previous_ciphertext = new_ciphertext = R1 * g^x1
previous_encrypted_key = new_encrypted_key = Z^x1
ciphertext, encrypted_key = elgamal_encrypt(Z, R2)
ciphertext = R2 * g^x2
encrypted_key = Z^x2
new_ciphertext = previous_ciphertext * ciphertext
new_ciphertext = (R1 * g^x1) * ciphertext
new_ciphertext = (R1 * g^x1) * R2 * g^x2
new_ciphertext = R1 * R2 * g^x1 * g^x2
new_ciphertext = R1 * R2 * g^(x1 + x2)
new_encrypted_key = previous_encrypted_key * encrypted_key
new_encrypted_key = Z^x1 * encrypted_key
new_encrypted_key = Z^x1 * Z^x2
new_encrypted_key = Z^(x1 + x2)
// Hop 3
previous_ciphertext = new_ciphertext = (R1 * R2 * g^(x1 + x2)
previous_encrypted_key = new_encrypted_key = Z^(x1 + x2)
previous_ciphertext = R1 * R2 * g^(x1 + x2)
previous_encrypted_key = Z^(x1 + x2)
ciphertext, encrypted_key = elgamal_encrypt(Z, R3)
ciphertext = R3 * g^x3
encrypted_key = Z^x3
new_ciphertext = previous_ciphertext * ciphertext
new_ciphertext = R1 * R2 * g^(x1 + x2) * ciphertext
new_ciphertext = R1 * R2 * g^(x1 + x2) * R3 * g^x3
new_ciphertext = R1 * R2 * R3 * g^(x1 + x2) * g^x3
new_ciphertext = R1 * R2 * R3 * g^(x1 + x2 + x3)
new_encrypted_key = previous_encrypted_key * encrypted_key
new_encrypted_key = Z^(x1 + x2) * encrypted_key
new_encrypted_key = Z^(x1 + x2) * Z^x3
new_encrypted_key = Z^(x1 + x2 + x3)
The above protocol phase concludes with a ciphertext composed of:
previous_encrypted_payload = R1 * R2 * R3 * g^(x1 + x2 + x3)
And an encrypted key composed of:
previous_encrypted_key = Z^(x1 + x2 + x3)
The last mix node sends the computed 2tuple to the first mix node in the cascade so that it can be used to initialize the next protocol phase.
Precomputation Phase 2: Multiplying the S values and calculating the permutation
The first mix node in the cascade receives the 2tuple computed in the previous
protocol phase, that is, a ciphertext of R1 * R2 * R3 * g^(x1 + x2 + x3)
and an encrypted key of Z^(x1 + x2 + x3)
.
The following computation is performed:
encrypted_payload, encrypted_key = elgamal_encrypt(Z, S1)
encrypted_payload = permute{previous_encrypted_payload} * encrypted_payload
encrypted_key = previous_encrypted_key * encrypted_key
Each node in turn processes the received message with calculating the
permutation and then multiplying in the S
value:
// Hop 1
previous_encrypted_payload = R1 * R2 * R3 * g^(x1 + x2 + x3)
previous_encrypted_key = Z^(x1 + x2 + x3)
encrypted_payload, encrypted_key = elgamal_encrypt(Z, S1)
encrypted_payload = permute{previous_encrypted_payload} * encrypted_payload
encrypted_payload = permute{R1 * R2 * R3 * g^(x1 + x2 + x3)} * encrypted_payload
encrypted_payload = permute{R1 * R2 * R3 * g^(x1 + x2 + x3)} * (S1 * g^y1)
encrypted_payload = permute{R1 * R2 * R3} * S1 * g^(permute{x1 + x2 + x3} + y1)
encrypted_key = previous_encrypted_key * encrypted_key
encrypted_key = Z^(x1 + x2 + x3) * encrypted_key
encrypted_key = Z^(x1 + x2 + x3) * Z^y1
encrypted_key = Z^(permute{x1 + x2 + x3} + y1)
// Hop 2
previous_encrypted_payload = permute{R1 * R2 * R3 * g^(x1 + x2 + x3)} * (S1 * g^y1)
previous_encrypted_key = Z^(permute{x1 + x2 + x3} + y1)
encrypted_payload, encrypted_key = elgamal_encrypt(Z, S2)
encrypted_payload = permute{previous_encrypted_payload} * encrypted_payload
encrypted_payload = permute{permute{R1 * R2 * R3 * g^(x1 + x2 + x3)} * (S1 * g^y1)} * encrypted_payload
encrypted_payload = permute{permute{R1 * R2 * R3 * g^(x1 + x2 + x3)} * (S1 * g^y1)} * (S2 * g^y2)
encrypted_payload = permute{permute{R1 * R2 * R3} * S1} * S2 * g^(permute{permute{x1 + x2 + x3} + y1} + y2)
encrypted_key = previous_encrypted_key * encrypted_key
encrypted_key = Z^(permute{x1 + x2 + x3} + y1) * encrypted_key
encrypted_key = Z^(permute{x1 + x2 + x3} + y1) * permute{Z^y2}
encrypted_key = Z^(permute{permute{x1 + x2 + x3} + y1} + y2)
// Hop 3
previous_encrypted_payload = permute{permute{R1 * R2 * R3 * g^(x1 + x2 + x3)} * (S1 * g^y1)} * (S2 * g^y2)
previous_encrypted_key = Z^(permute{permute{x1 + x2 + x3} + y1} + y2)
encrypted_payload, encrypted_key = elgamal_encrypt(Z, S3)
encrypted_payload = permute{previous_encrypted_payload} * encrypted_payload
encrypted_payload = permute{permute{permute{R1 * R2 * R3 * g^(x1 + x2 + x3)} * (S1 * g^y1)} * (S2 * g^y2)} * encrypted_payload
encrypted_payload = permute{permute{permute{R1 * R2 * R3 * g^(x1 + x2 + x3)} * (S1 * g^y1)} * (S2 * g^y2)} * (S3 * g^y3)
encrypted_payload = permute{permute{permute{R1 * R2 * R3} * S1} * S2} * S3 * g^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
encrypted_key = previous_encrypted_key * encrypted_key
encrypted_key = Z^(x1 + x2 + x3) * Z^(y1 + y2) * encrypted_key
encrypted_key = Z^(x1 + x2 + x3) * Z^(y1 + y2) * Z^y3
encrypted_key = Z^(x1 + x2 + x3) * Z^(y1 + y2 + y3)
encrypted_key = Z^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
Precomputation Phase 3: Reveal
The reveal phase results in the following for our mix cascade composed of three mix nodes:
(permute{permute{permute{R1 * R2 * R3} * S1} * S2} * S3)^1
We operate on the encrypted key and the ciphertext computed from the previous protocol phase:
encrypted_key = Z^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
encrypted_payload = permute{permute{permute{R1 * R2 * R3} * S1} * S2} * S3 * g^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
Recall the definition of Z
:
Z = g^(z1 * z2 * z3)
This is done one mix node key at a time as the message ciphertext traverses the mix cascade:
// Hop 1
previous_encrypted_key = Z^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
encrypted_key = strip(z1, previous_encrypted_key)
encrypted_key = z1^1 * previous_encrypted_key
encrypted_key = z1^1 * Z^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
encrypted_key = z1^1 * g^(z1 * z2 * z3)^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
encrypted_key = g^(z2 * z3)^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
// Hop 2
previous_encrypted_key = encrypted_key
previous_encrypted_key = g^(z2 * z3)^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
encrypted_key = strip(z2, previous_encrypted_key)
encrypted_key = strip(z2, g^(z2 * z3)^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3))
encrypted_key = z2^1 * g^(z2 * z3)^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
encrypted_key = g^z3^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
// Hop 3
previous_encrypted_key = encrypted_key
previous_encrypted_key = g^z3^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
encrypted_key = strip(z3, previous_encrypted_key)
encrypted_key = strip(z3, g^z3^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3))
encrypted_key = z3^1 * g^z3^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3))
encrypted_key = g^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3))
The last mix node determines the result:
encrypted_payload = permute{permute{permute{R1 * R2 * R3} * S1} * S2} * S3 * g^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
encrypted_key = g^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3))
payload = encrypted_key^1 * encrypted_payload
payload = encrypted_key^1 * permute{permute{permute{R1 * R2 * R3} * S1} * S2} * S3 * g^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
payload = (g^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)))^1
* permute{permute{permute{R1 * R2 * R3} * S1} * S2} * S3
* g^(permute{permute{permute{x1 + x2 + x3} + y1} + y2} + y3)
payload = permute{permute{permute{R1 * R2 * R3} * S1} * S2} * S3
The decrypted value is:
(permute{permute{permute{R1 * R2 * R3} * S1} * S2} * S3)
We invert the value to achieve the final precomputation value:
(permute{permute{permute{R1 * R2 * R3} * S1} * S2} * S3)^1
Security Considerations
Anonymity Considerations

The design of the Auth protocol avoids leaking identity keys on the communications channel in plaintext.

The design of the message storage and retrieval deliberately avoids leaking identities to nonrecipients. Using deterministic message fingerprints to tag messages and avoid trial decryption.