Sphinx: A Compact and Provably Secure Mix Format
George Danezis
Microsoft Research
Cambridge, UK
gdane@microsoft.com

Abstract
Sphinx is a cryptographic message format used torelay anonymized messages within a mix network. It
is more compact than any comparable scheme, andsupports a full set of security features: indistinguishable replies, hiding the path length and relay position,
as well as providing unlinkability for each leg of themessage’s journey over the network. We prove thefull cryptographic security of Sphinx in the random
oracle model, and we describe how it can be used as
an efficient drop-in replacement in deployed remailer
systems.

1. Introduction
Mix networks were proposed by David Chaum [7]in 1981 as an efficient means to achieve anonymous
communications. A mix (or a mix node) is simply
a message relay that accepts a batch of encrypted
messages, decrypts them and sends them on theirway. An observer of a mix node should be unable tolink incoming and outgoing messages; this provides
anonymity to the users of the network. A number oftheoretical [12], [15], [9], [5], [21] as well as deployedsystems [16], [8] have been proposed that further
develop the idea of mixes. The Mixmaster network [16]is currently composed of about 25 reliable remailers,
while the newer Mixminion [8], adding the ability to
reply anonymously to messages, is composed of about
20 reliable nodes.
Anonymizing messages through a mix network
comes at a cost: the messages are batched and therefore
delayed, as well as padded to a standard length toprevent traffic analysis. Furthermore, multiple encryption layers have to be used to encapsulate the routing
information necessary to relay the message through asequence of mixes. The cryptographic mechanism used
to deliver this routing information to each intermediatemix, as well as to transform the message as it travels
through the network, is called the cryptographic packet

Ian Goldberg
University of Waterloo
Waterloo, ON, Canada
iang@cs.uwaterloo.ca
format. The cryptographic mechanism is to some extent independent from other traffic analysis protections
offered by the mix network, as long as they guaranteethat some aspects of the routing information, such as
path length or position in the path, are not leaked [4].
The minimum overhead introduced by the cryptographic packet format impacts the types of traffic thatcan realistically be anonymized. Previous work, like
Mixminion [8] and Minx [9] added an overhead of
at least a full RSA ciphertext (at least 256 additional
bytes for modern 128-bit security levels). Provable
designs, such as the ones proposed by Möller [15], Camenish and Lysyanskaya [5] or Shimshock et al. [21],use multiple RSA-sized ciphertexts to relay information for each stage of the mixing, making the header
necessary for anonymization many kilobytes long.
Such formats may be acceptable for relaying large
email messages, but add a significant overhead to shortmessages, the length of Instant Messaging or SMS
messages (that are up to 160 characters.) It is thereforeof great importance to devise cryptographic schemesthat are compact to efficiently anonymize those classesof traffic. Furthermore, anonymous replies rely on
cryptographic addresses that are of similar size to theheaders required to route messages thought the network. Compact packet formats directly lead to compact
addresses and thus to cheaper receiver anonymity.
Traditionally, cryptographic packet formats havebeen based on heuristic security arguments. From earlyon it became apparent that these complex cryptographic systems are difficult to get right: the originalscheme by Chaum [7] was shown to have cryptographic weaknesses by Pfitzmann and Pfitzmann [18]and Minx [9] leaked information which theoreticallyallowed an adversary to extract the full plaintext of
messages [21]. As a result several authors proposed
provably secure packet formats. Some of them only
provide the bare minimum functionality [15], [5], andin particular no provision for anonymous replies, whileothers suffer a significant transmission overhead [21].
It has so far been an open problem to devise a compact

and provably secure packet format.
Our key contribution is Sphinx: a cryptographic
packet format that can be used to route messages overa mix network. Sphinx provides all features expectedby modern remailer applications:
It provides bitwise unlinkability, making it cryptographically difficult to link incoming and outgoing messages from a mix. This is the basic
property all packet formats provide.
• It allows for paths up to an arbitrary maximum
length, while hiding the number of hops a message has travelled so far, as well as the actual
number of mixes on the path of a message.
These are hidden even from the mixes that areprocessing the messages.
• The processing of reply messages is indistinguishable from the processing of normal “forward”
messages. The anonymity sets of both types oftraffic are therefore confounded, providing greater
protection for both.
• It resists any active tagging attacks, where theadversary modifies and re-injects messages toextract information about their destinations orcontent.
• It is compact: for 128-bit security, the overhead
is only 32 bytes plus a single group element(not one per hop) plus 32 bytes of routing andintegrity protection information per hop. The sizeof the group element can be as small as 32 bytes
using Dan Bernstein’s Curve25519 elliptic curve
library [3]; the element is the x-coordinate (inGF (2255 −19)) of a point on an elliptic curve. For
example, the header of a Sphinx message with amaximum path length of 5 mixes can be encodedin as little as 224 bytes.
•

From a systems perspective, Sphinx is designed asa drop-in replacement for the Mixminion packet format [8]. It makes the same systems and security
assumptions as Mixminion, but is more compact andcryptographically provably secure. This means that
Sphinx can be easily integrated with the Mixminion
software to take advantage of the thousands of lines ofrobust client and server code. Our reference implementation of Sphinx, which provides all of the functionality
needed for clients, mix nodes, and the nymserver, andwhich works either over a 2048-bit prime field or
Curve25519, is less than 600 lines of Python code(including simple tests).
Our description of Sphinx will proceed in the following fashion: section 2 provides an overview of
the threat model, requirements and design rationale of
Sphinx; sections 3 and 4 provide a formal definitionof the cryptographic format and the associated proofsof security respectively. In section 5 we discuss theefficiency of the scheme and compare it with other proposals. Finally we provide some concluding remarks in
section 6.

2. Design overview
Mix networks achieve anonymity by relaying messages over a sequence of mixes, called the path. The
sender cryptographically encodes a message, which ispartially decoded by each mix along the path. As longas a single mix in the path is honest, meaning thatit does not share its secrets with an adversary, themessage will benefit from some anonymity.

2.1. Threat Model & Requirements
It is traditional to consider the security of cryptographic packet formats against an active adversary thatis able to observe all traffic in the network, as well as
to intercept and inject arbitrary messages. Furthermore,
we assume that some, but not all, of the mixes in thepath of a relayed message are corrupt; i.e., under the
direct control of an adversary that knows all their keys,
and other secrets, and is able to fully control theirfunctioning. The principal aim of the adversary is to
extract some information about the ultimate destinationof mixed messages through inferring the final addressor some of their contents. The security properties ofcryptographic mix packet formats prevent or tightly
control any such information leakage.
Specifically, Sphinx needs to ensure that if multiple
messages enter an honest mix and are batched together,
it is not feasible to link an output message to any
input message with probability significantly higher
than uniform. This is the fundamental requirement ofany packet format. Yet modern packet formats also
control the amount of information leaked to mixes(including dishonest mixes) along the path. A dishonestmix should not be able to infer either the full lengthof the path of a particular message, or its own positionon that path. Simple traffic analysis detects if a mix isfirst or last on the path, so we do not consider this acompromise.
An advantage of mix networks is that they provide a unified mechanism for both sender and receiver anonymity. Alice may encode a single-use reply
block [8] and attach it to an anonymous message
destined to Bob. Bob cannot know that the originatorof the message is Alice, but can use the reply blockcontained in the message as an address to send a reply.
The reply is then routed through the network untilit reaches Alice. In both cases Alice benefits fromanonymity properties, first as the sender of the message(sender anonymity) and the second time as the anonymous receiver of a message (receiver anonymity).
Nymservers [14] have been developed as services thatmake use of anonymous replies to bridge the worldof mix networks with traditional email. Users cansend normal email to pseudonymous email addresses,
which are then routed through the mix network using
anonymous reply blocks. We note that the network
does not attempt to keep it a secret that Bob is talking
to some particular pseudonym; we assume Bob’s emailcommunication is likely to be unencrypted (thoughorthogonal end-to-end encryption mechanisms can ofcourse also be used). What it does protect is the factthat that pseudonym belongs to Alice.
To increase the security of both sender- and receiveranonymous messages, the two kinds of messages
should use the same network and the same relay
mechanisms. Hence it is a requirement of the cryptographic packet format that forward and reply messages
be cryptographically indistinguishable; this makes thetask of engineering packet formats more difficult. Traditional methods for achieving non-malleability (suchas providing a MAC over the full header and body of
the relayed message) are not readily available, as the
reply message body is unknown at the time the reply
block is created.
Finally, Sphinx is required to be resistant to active
attacks: an adversary can use any corrupt node to inject
arbitrary messages into honest nodes in an attempt
to extract information. Sphinx protects against replay
attacks—where the adversary reinjects a previously
seen message verbatim—and tagging attacks—where
the adversary modifies a message before reinjecting it
into the network. In neither event will Sphinx allow
the adversary to learn any information about the finaldestination of the message or its contents. Other denialof-service and flooding attacks (n − 1 attacks) [20] are
not considered in the threat model, since they are notcryptographic in nature and are handled by orthogonalmechanisms [12], [13]. Similarly, active traffic analysis
attacks, such as those based on dropping messages orflooding links and nodes to perform remote network
measurements, cannot be fixed by the cryptographic
format alone, and must be dealt with by the high-levelmix strategies.

2.2. Design Rationale
Sphinx is based on the idea that a mix packet format
should encapsulate enough information to cryptographically secure a confidential and integrity-protectedchannel to each of the mixes on a message’s path. Thisrequires keys to be shared, or distributed, securely toeach of the mixes on the path, in order that they may
decode the routing information, as well as other partsof the message. Traditionally, this has been done with
RSA [19] encryption, while Sphinx instead uses DiffieHellman [10].
At the heart of the Sphinx key distribution strategy
lies a single element of a cyclic group of prime ordersatisfying the decisional Diffie-Hellman assumption.
This element is used by each mix on the path to derivea secret that is shared with the original sender of themessage—a set of keys that can be used for encryption,
integrity protection, etc. are further extracted from thisshared secret. The element used for key derivation
cannot be transported unaltered throughout the path,however, as this would lead to linkable messages. To
avoid this, the element is blinded at each mixing stepto make it indistinguishable from any other output
element. The blinding factors are extracted from theshared secrets, and so both senders and mixes canperform all operations necessary to extract keys used
at each hop of the mix message processing. There
are many possible choices for the cyclic group; twocommon ones are a subgroup of the multiplicative
group of a prime field, and an elliptic curve group. The
latter in particular leads to a very compact design, sincefor 128-bit security, group elements can be expressedin just 32 bytes, as opposed to 256–384 bytes for aprime field of similar strength.
Besides extracting the shared key, each mix has tobe provided with authentic and confidential routing
information to direct the message to the subsequentmix, or to its final destination. We achieve this bya simple encrypt-then-MAC mechanism. A secure
stream cipher or AES in counter mode is used forencryption, and a secure MAC (with some strong but
standard properties) is used to ensure no part of themessage header containing routing information has
been modified. Some padding has to be added at eachmix stage, in order to keep the length of the message
invariant at each hop.
The steps involved in decoding and routing themessage at each mix are rather simple. Their fulltechnical description is provided in section 3.6 and is
illustrated in the corresponding Figure 3. In summary:1) The mix receives the message and, using theelement from the cyclic group and its private key,
extracts a set of shared session keys.
2) The MAC of the message is checked to ensurethat the header has not been modified.
3) Some padding (of all zeros) is added at the endof the message to keep the length invariant.

4) The header of the message is decrypted (including the newly added padding), the element
blinded and the payload of the message decrypted.
5) The routing information and next MAC are extracted from the decrypted header, and the resulting message is forwarded to the next destination.
Senders encode a message by deriving all session
keys, wrapping the message in multiple layers ofencryption, and calculating the correct message authentication codes for each stage of the journey. Calculating
the correct MACs is not a trivial task: the successive
layers of padding that are encrypted at each stage ofthe mixing have to be included in the integrity check.
The MACs ensure that a modified header is detected
immediately.
The payload of the message is kept separate from themix header used to perform the routing. It is decryptedat each stage of mixing using a block cipher witha large block size (the size of the entire message),such as LIONESS [1]. In case the adversary modifies
the payload in transit, any information contained init becomes irrecoverable. Sender-anonymous messages
contain the final address of the message, as well as
the message itself as part of the payload, and so any
modification destroys this information.
Anonymous replies are equally simple to construct:
the intended receiver of the reply (who will benefit
from the anonymity properties) builds a mix header
addressed back to herself with no payload. This header
acts as an anonymous reply address, and can be
included in a message to give anyone the ability to
reply. Some additional information, such as the addressof the first mix hop, is also needed.
A reply is built by attaching a message to the reply
address and routing it through the mix network. The
processing of the reply message is identical to theprocessing of forward messages, leading to simplicity
of implementation and larger anonymity sets.

3. Formal protocol description
3.1. Notation
Let κ be a security parameter. An adversary will
have to do about 2κ work to break the security of
Sphinx with nonnegligible probability. We suggest
using κ = 128.
Let r be the maximum number of nodes that a
Sphinx mix message will traverse before being delivered to its destination. We suggest r = 5.
Define the following:

G: A prime-order cyclic group satisfying the Decisional Diffie-Hellman Assumption. G ∗ is the setof non-identity elements of G. The element g is a
generator of G, and q is the (prime) order of G, withq ≈ 22κ .
A number of hash functions, which we model byrandom oracles:
hμ : G ∗ → {0, 1}κ, used to key μ, below∗κ• hρ : G → {0, 1} , used to key ρ, below∗κ• hπ : G → {0, 1} , used to key π, below∗
2κ• hτ : G → {0, 1} , used to identify previously
seen elements of G ∗∗∗∗• hb : G × G → Zq , used to compute blinding
factors•

We implement these functions with appropriately truncated SHA-256 hash functions.
μ : {0, 1}κ × {0, 1}∗ → {0, 1}κ: a Message
Authentication Code (MAC). We normally model μ
as a pseudo-random function (PRF). However, in one
part of the proof (section 4.2), the adversary gets toknow the key to the MAC. In this case, simply beinga PRF guarantees nothing, whereas we still want μwith a known key to behave like a hash function. For
this reason, we model μ as a random oracle in that
section (which of course is stronger than a PRF). In arealistic implementation, we would use a MAC basedon a hash function, such as SHA256-HMAC-128.
ρ : {0, 1}κ → {0, 1}(2r+3)κ: a pseudo-random
generator (PRG). A PRG is the basis for any stream
cipher: the key is fed as an input to the PRG, which
outputs a long pseudorandom string. This string is
XORed with the plaintext to yield the ciphertext, orwith the ciphertext to recover the plaintext. As above,in section 4.2 the adversary will be able to know the
input to the PRG, which removes all of the PRG’s
security properties. So again, for that section, we
model ρ as a random oracle. We can implement ρ withany secure stream cipher, or any secure block cipher
in counter mode, which operates in the same way.
π : {0, 1}κ × {0, 1}π → {0, 1}π : a family ofpseudo-random permutations (PRPs). π will be thesize of the message bodies that can be transmitted
over Sphinx (plus κ bits of overhead). Given any(k, x) ∈ {0, 1}κ ×{0, 1}π , both π(k, x) and π −1 (k, x)
should be easy to compute. (The latter is the uniquevalue y ∈ {0, 1}π such that π(k, y) = x.) π −1 should
also be a family of pseudo-random permutations. We
use the LIONESS [1] PRP to implement π.
N ⊂ {0, 1}κ: a set of mix node identifiers. Eachnode n ∈ N has a private key xn ∈R Z∗q and a public
key yn = g xn ∈ G ∗ . We assume the presence of a PKI
that publishes an authenticated list of all (n, yn ) pairs.

Figure 1. Construction of the filler strings φi forν = r = 4. Here, ρi is the final 2(i + 1)κ bits ofρ(hρ (si )).
D ⊂ {0, 1}≤2rκ: a set of destination addresses,
usually normal email addresses. It must be the casethat N ∩ D = ∅ and that N ∪ D is prefix-free. Notethat N ∩ D = ∅ does not imply that end users of
Sphinx cannot themselves run Sphinx nodes; it is justthat the identifier for their node (in N ) will be different
from their email address. One of the elements ∗ ∈ D
is distinguished.
The notation 0a means the string of 0 bits of lengtha, x[a..b] means the substring of x consisting of bitsa through b, inclusive (the leftmost bit of x is bit 0),
denotes concatenation, |s| is the length of string s,and  is the empty string.

3.2. Creating a mix header
This section describes the procedure to create a
Sphinx mix message header. It is used as a subroutine for the procedures to create forward messages
and single-use reply blocks in sections 3.3 and 3.4,
respectively.
Input: a destination address Δ ∈ D, an identifier I ∈ {0, 1}κ and a sequence of mix nodes{n0 , n1 , . . . , nν−1 } with ν ≤ r. It must also be thecase that |Δ| ≤ (2(r − ν) + 2)κ.
Pick a random x ∈R Z∗q .
Computeasequenceofν
tuples(α0 , s0 , b0 ), . . . , (αν−1 , sν−1 , bν−1 ) as follows:xx• α0 = g , s0 = yn0 , b0 = hb (α0 , s0 )xb
xb
• α1 = g 0 , s1 = yn10 , b1 = hb (α1 , s1 )• ...

Figure 2. Construction of (β0 , γ0 ) for a Sphinx mix
header, with ν = r = 4. The construction of φ3 from
Figure 1 ensures that the truncated part of βi+1
equals the truncated part of ρ(hρ (si )), indicated by
the dotted lines and shading, for each 0 ≤ i < ν.

•

xb b ···bν−20 1
αν−1 = g xb0 b1 ···bν−2 , sν−1 = ynν−1bν−1 = hb (αν−1 , sν−1 ),The αi are the group elements, the si are the DiffieHellman shared secrets, and the bi are the blinding
factors.
Compute the filler strings φ0 , . . . , φν−1 :••φ0 = 
For
i−1 02κ } ⊕ 0 < i < ν, φi = {φρ(hρ (si−1 ))[(2(r−i)+3)κ..(2r+3)κ−1]

Note that |φi | = 2iκ. This step is illustrated in
Figure 1.
Computeasequenceofmix
headersMν−1 , Mν−2 , . . . , M0 as follows: Mi = (αi , βi , γi ) ∈G ∗ × {0, 1}(2r+1)κ × {0, 1}κ where:• βν−1=
Δ I 0(2(r−ν)+2)κ−|Δ|⊕ρ(hρ (sν−1 ))[0..(2(r−ν)+3)κ−1]
φν−1


⊕
=
ni+1 γi+1 βi+1 [0..(2r−1)κ−1]• βi
ρ(hρ (si ))[0..(2r+1)κ−1] for 0 ≤ i < ν − 1• γi = μ(hμ (si ), βi ) for 0 ≤ i ≤ ν − 1
The above step is illustrated in Figure 2.
Output: the mix header M0 and the sequence ofshared secrets s0 , . . . , sν−1 .

3.3. Creating a forward message
This section gives the procedure used to create
a forward message to be sent through the Sphinx
network.
Input: a message m, a destination address Δ and asequence of mix nodes {n0 , n1 , . . . , nν−1 } with ν ≤ r.
Compute the mix header M0 and the sequenceof shared secrets s0 , . . . , sν−1 as above, passing thedistinguished element ∗ ∈ D as the destination address
and 0κ as I. Compute:••δν−1 = π(hπ (sν−1 ), 0κ Δ m)
δi = π(hπ (si ), δi+1 ) for i = ν − 2, . . . , 0

Output: the pair (M0 , δ0 )The forward message is this pair (M0 , δ0 ), andshould be sent to n0 .

3.4. Creating a single-use reply block
This procedure is used to create a single-use reply
block.
Input: a destination address Δ and a sequence ofmix nodes {n0 , n1 , . . . , nν−1 } with ν ≤ r. Δ shouldbe the user’s own address.
Pick a random identifier I ∈R {0, 1}κ and computethe mix header M0 and the sequence of shared secrets
s0 , . . . , sν−1 as above.
Pick a random key k̃ ∈R {0, 1}κ.
Output: I, the tuple (k̃, hπ (s0 ), . . . , hπ (sν−1 )), andthe tuple (n0 , M0 , k̃).
Store the tuple (k̃, hπ (s0 ), . . . , hπ (sν−1 )) in a local
table indexed by I. Send (n0 , M0 , k̃) to the nymserver
over a secure channel, to be indexed under the user’s
pseudonym. This can be done, for example, by encrypting it with the nymserver’s public key, signing it withthe pseudonym’s private key, and sending the message
to the nymserver using the Sphinx forward channel.

3.5. Using a single-use reply block
When the nymserver receives a message m destinedfor a pseudonym, it will look up a previously unused(n0 , M0 , k̃) tuple indexed by that pseudonym. It willthen send (M0 , π(k̃, 0κ m)) to n0 and remove thetuple from its index.

3.6. Message processing by mix nodes
Messages received by mix nodes are of the form(M, δ) = ((α, β, γ), δ) ∈ G ∗ × {0, 1}(2r+1)κ ×{0, 1}κ × {0, 1}π . (The node should ensure that themessage is in this form; in particular, that α ∈ G ∗ .)When mix node n, with private key xn , receives sucha message, it proceeds as follows:
Compute the shared secret s = αxn . If hτ (s) isalready in this node’s table of seen message tags,
discard the message. (Note that this table can be
flushed whenever the node rotates its private key.)
Otherwise, continue by comparing γ to μ(hμ (s), β).
If they do not match, discard the message. Otherwise,
store hτ (s) in the table of seen message tag, andcontinue by decrypting the suitably padded β (as astream cipher, XORing the output of the PRG ρ) to
get B = {β 02κ } ⊕ ρ(hρ (s)).
Use the prefix-freeness of N ∪ D to uniquely parsea prefix of B as n ∈ N ∪ D. (If this is not possible,
the message is discarded.)
If n ∈ N is found: This message is destinedfor another Sphinx node. Compute the blinding factor
b = hb (α, s), and let α = αb . Let γ  = B[κ..2κ−1] ,β  = B[2κ..(2r+3)κ−1] , and δ  = π −1 (hπ (s), δ). Send((α , β  , γ  ), δ  ) to n. Figure 3 illustrates the processing
steps involved in this case, as an example of how thedecoding process works.
If n = ∗ is found: The current node is the exit
node for a forward message. Let δ  = π −1 (hπ (s), δ).
If δ  [0..κ−1] = 0κ , parse δ  [κ..π −1] as Δ m for Δ ∈ Dusing the prefix-freeness of D. If this is successful,m should be a plaintext message, and is sent to Δ.
Otherwise, the message has been tampered with and is
discarded.
Otherwise, if n ∈ D\{∗} is found: The current
node is the exit node for a reply message, and n is theowner of a pseudonym. Let I = B[|n|..|n|+κ−1] andδ  = π −1 (hπ (s), δ). Send (I, δ  ) to n.

3.7. Reply message processing by pseudonymownersUpon receiving (I, δ), a pseudonym owner looksup (and subsequently removes) (k̃, k0 , . . . , kν−1 )Figure 3. The processing of a Sphinx message ((α, β, γ), δ) into ((α , β  , γ  ), δ  ) at Mix n.
in itsδ = table indexed by I, and computes
−1πk̃, π (k0 , π (k1 , · · · π (kν−1 , δ) · · ·)) and m =δ [κ..π −1] . If δ  [0..κ−1] = 0κ then accept m as thereceived message.

4. Proof of security
From a cryptographic point of view, mix protocols
like Sphinx share many properties with onion routing
protocols. At a minimum, we desire our mix protocol
to have all of the security properties of onion routing.
In [5], Camenisch and Lysyanskaya give four properties of an onion routing protocol: correctness, integrity, wrap-resistence, and security, all detailed below. They show that any onion routing protocol having
all of these properties realizes ideal onion routing functionality in the Universal Composability model [6].
This means that an adversary against a protocol withthese four properties has no better chance of successthan an adversary against an ideal protocol; that is, ata high level, one in which adversaries (even ones that
control some of the mix nodes) have no access to theunderlying cryptographic implementation, but rather
can observe only opaque identifiers for messages.
For our mix network, we would like, in addition to
the above properties, that adversaries in the middle of apath should be unable to distinguish forward messages
from replies (unlike the situation in [5]). It is clearthat adversary nodes at the edges of the network—that is, nodes that deliver messages to users who are
not themselves nodes—are necessarily able to distinguish forward from reply messages: outgoing forward
messages are in plaintext, since messages should bedeliverable to arbitrary parties on the Internet who
have no special software installed; on the other hand,outgoing reply messages to the pseudonym owner are
encrypted. Entry nodes also receive forward messages
from arbitrary end users, but receive reply messages
from the nymserver (the forward and reply messages
are cryptographically indistinguishable, however). But
between the entry and the exit, nodes should be unable
to distinguish the two cases.
Formally, under the assumptions on the components
given in section 3.1, Sphinx realizes ideal onion routing
functionality in the Universal Composability model (asdefined in [5]), and also makes forward and reply
messages indistinguishable to middle mix nodes. We
prove this result in the following four sections.

4.1. Correctness
It is straightforward by inspection that the protocol
works correctly in the absence of an adversary; thatis, it processes the mix messages correctly, sends theright intermediate mix messages to the right mixes, andfinally sends the right message to the right destination.

4.2. Integrity
The second requirement of [5] is that an adversary
cannot construct a mix message that will travel througha path of more than N honest nodes, for some fixedbound N , except with negligible probability. We showthat Sphinx satisfies this requirement, with N = r + 1,
even if we allow the adversary to know all private keys
xn in the system. (Note that the adversary knows thenodes’ private keys, but the nodes still behave honestly,
according to the protocol.) This last adversarial power
is what necessitates modelling μ and ρ as somethingstronger than the usual PRF and PRG notions. Again,
for the purposes of this section, we treat them as
random oracles.
Note that although the Sphinx protocol specifies thatno more than r node identifiers get embedded into a
Sphinx header, it is in fact possible to embed up to r+1
such identifiers, as long as the embedded Δ = ∗ and isvery short (less than κ bits). This means an adversary
can indeed construct a mix message that will have path
length r + 1. This is not a problem for our proof, since
the proof only requires that there is some upper boundon the path length. We show that an adversary cannot
construct a mix message that results in a path length
greater than N = r + 1, and that is sufficient.
We assume the adversary does significantly less than2κ work, and show that the probability of producing arequisite mix message is negligible.
Let a mix message constructed by the adversarybe ((α0 , β0 , γ0 ), δ0 ), and sent to node n0 . That node
processes it to produce ((α1 , β1 , γ1 ), δ1 ), which is sent
to n1 , etc.
Node ni will successfully process a message andsend it on to the next node if and only if the following
all hold:• ni has never before (during the life of its current
private key xni ) processed a mix message with thexnsame αi (since the map αi → αi i is bijective
and hτ is collision-resistant) xn• γi = μ hμ αi i , βi
xni
• there is a prefix of Bi = {βi 02κ } ⊕ ρ(hρ (αi ))which is in N ∪ D; this will be ni+1 if it is inN.
If these hold, then the first κ bits of Bi will be ni+1
itself, the next κ bits will be γi+1 , and the remaining(2r = + 1)κ bits will be βi+1 . Note that βi+1xni
βi
⊕ ρ(hρ (αi ))[2κ..(2r+1)κ−1] [2κ..(2r+1)κ−1]
xni
ρ(hρ (αi ))[(2r+1)κ..(2r+3)κ−1] . In particular, theleftmost 2κ bits of βi are used to construct ni+1 andthe MAC γi+1 ; the remaining (2r − 1)κ bits of βi are
shifted left to form (after decryption by XORing witha substring of an output of ρ) the leftmost (2r − 1)κ
bits of βi+1 ; the rightmost 2κ bits of βi+1 are simply
a substring of an output of ρ.
Consider the following problem P: Let
f0 , f1 , . . . , f2κ −1 be a family of random oracleswith range {0, 1}κ. Let ρ̂ and ρ0 be other random
oracles with range {0, 1}κ. (The domains do notmatter.) The problem is to find x and y such that
ρ̂(x) = fρ0 (x) (y). We claim that an adversary has

only a negligible chance of solving problem P if heperforms significantly less than 2κ work.
Proof: For each i ∈ {0, 1}m, let ri be the number oftimes the adversary called ρ0 and had it output i, and
let Fi be the number of times he called fi . (We canassume the adversary never calls ρ̂ on an input unlesshe also calls ρ0 on that input.) Then the adversary has
i ri Fi chances to solve problem P, and each chance
is successful with probability 2−κ . Let A be the total
number of calls the adversary makes to ρ0 , and leti∗ be the most common output, occurring A∗ of the A
times. To maximize i ri Fi while holding i (ri +Fi )constant, the adversary should only query fi∗ , and not
any of the other fi . Suppose he does so B times. Then∗
his probability of success is bounded above by A2κ·B ,having done A + B work.
1
If A = B ≈ 2κ(1− w ) for some w, then we expect tofind w-collisions in the A outputs of ρ0 , but not w + 1collisions [17], so we expect A∗ = w. Then the success∗κ
probability is bounded above by A2κ·B = w · 2− w . Ifκ, and this probability
A = B ≈ 2m , then w = κ−mκm−κ, as required.
bound is κ−m · 2
Note the difference between this problem and astandard collision problem (such as ρ̂(x) = f (y)),
which would have success probability 22m−κ for doing
2m work, and to a standard search problem (such asρ̂(x) = f (x, y)), which would have success probability2m−κ for doing 2m work.
Now suppose an adversary can construct a mix message ((α0 , β0 , γ0 ), δ0 ) which is successfully processedby mix nodes n0 , n1 , . . . , nN , whose private keys xi
are known to the adversary. We will show that thismeans that the adversary can solve the above problem
P.
Given such a message, the adversary can process it in the manner of each mix node in turn,to generate ((α1 , β1 , γ1 ), δ1 ), ((α2 , β2 , γ2 ), δ2 ), . . . ,((αN , βN , γN ), δN ). Now since node nN successfully
processes this last message, it must be the case thatγN = μ(hμ (αxNN ), βN ).
For notational convenience, for 0 ≤ i ≤ r, define ρi (x) to be ρ(x)[(2(r−i)+2)κ..(2r+3)κ−1] 02(r−i)κ ;that is, the last (2i + 1)κ bits of ρ(x), followedby 2(r − i)κ bits of zeros. Also define ρ̂i (x) to be
ρ(x)[(2(r−i)+1)κ..(2(r−i)+2)κ−1] ; that is, the block of κ
bits of ρ(x) immediately preceding the bits selectedfor ρi (x). Finally, for 1 ≤ i ≤ r + 1, define ρ̃i (x) tobe ρ(x)[(2i−1)κ..(2i+1)κ−1] .
A careful, but straightforward, calculation showsthat γN = a0 ⊕ a1 ⊕ · · · ⊕ aN −1 , where aj =xρ̂j (hρ (αj j )).
Similarly, βN = b0 ⊕ b1 ⊕ · · · ⊕ bN −1 , where bj =x
ρj (hρ (αj j )).

Nowconsiderthefunction
,
k
,
k
,
.
.
.
,
k
,
k
)
=
g(p
0
1
2
N
−1
μ



N −1
μ kμ , (p0 02rκ ) ⊕. We claim
i=1 ρi (ki )that the adversary who does less than 2κ work
cannot distinguish this g from a truly randomfunction which takes the same inputs. Why is this?
Since μ is a random oracle, the only way theadversary could distinguish the situations is if it could
generate a pair of inputs (p0 , k1 , k2 , . . . , kN −1 , kμ )and (p0 , k1 , k2 , . . . , kN
which cause the−1 , kμ )corresponding arguments of the call to μ to be equal.
Clearly we must have kμ = kμ .
N −1
Let B = (p0 02rκ) ⊕ρ(k)
and B  =
i
i

 i=1
N −1

(p0 02rκ ) ⊕i=1 ρi (ki ) . Note that the last 2κ
bits of B are just ρ̃N −1 (kN −1 ), the last 2κ bits.
of ρ(kN −1 ). If B = B  , then ρ̃N −1 (kN −1 ) =ρ̃N −1 (kN−1 ). Since the adversary has done less thanκ
2 work, he has only a negligible chance of findingkN −1 = kN−1 with the last 2κ bits of ρ(kN −1 ) andρ(kN −1 ) equal. Thus, except with negligible probabil
ity, kN −1 = kN
−1 .
Now consider the block of 2κ bits before the final
block of 2κ bits of B. This is just ρ̃N −2 (kN −1 ) ⊕ρ̃N −1 (kN −2 ). So if B = B  , and kN −1 = kN
−1
as above, then we must have that ρ̃N −1 (kN −2 ) =ρ̃N −1 (kN−2 ), and as above, kN −2 = kN −2 . Continuing in this way, we get that (k1 , k2 , . . . , kN −1 , kμ ) =(k1 , k2 , . . . , kN
−1 , kμ ) except with negligible probability.
Note that this logic would not have extended to k0 ,had it been included, since only κ, and not 2κ, bits ofρ(hρ (αx0 0 )) are included in βN .
Finally, if B = B  and (k1 , k2 , . . . , kN −1 , kμ ) =(k1 , k2 , . . . , kN
−1 , kμ ), then clearly p0 = p0 .
Let k = (k1 , . . . , kN −1 , kμ ). Then we just showedthat the function g(p0 , k) is indistinguishable from atrue random oracle with less than 2κ work. Now let
fp0 (k) = g(p0 , k)⊕ ρ̂1 (k1 )⊕· · ·⊕ ρ̂N −1 (kN −1 ). Sincethe ρ̂i do not call the random oracle μ, this is also
indistinguishable from a true random oracle.
But if the adversary constructed a mix message
which was successfully processed by n0 , . . . , nN ,then he has a solution to ρ̂0 (k0 ) = fρ0 (k0 ) (k),where ρ0 (x) = ρ(x)[(2r+2)κ..(2r+3)κ−1] ; namely, ki =hρ (αxi i ) and kμ = hμ (αxNN ). But this is just problem
P.
Therefore, since he has only a negligible probabilityof finding a solution to problem P with considerably
less than 2κ work, he also has only a negligible
chance of constructing a mix message which will be
successfully processed by N + 1 nodes, and the result

is proven.
It is instructive to note where this proof relieson the fact that N > r. The key is that fori ≤ r, the computation of γi contains bits fromxj
r−1
β0 . For example, γr =j=0 ρ̂j+1 (hρ (αj )) ⊕β0 [(2r+1)κ..(2r+2)κ] . [Compare this to γN , above,xj
N −1
which equalled
j=0 ρ̂j (hρ (αj )), with no component from β0 .]Since the computation of βr does not involve
xr−1
these bits of β0 , it is easy to find αx0 0 , . . . , αr−1xr
and β0 that satisfy γr = μ(hμ (αr ), βr ). Just
xr−1
pick any αx0 0 , . . . , αr−1
, compute βr , and=μ(hμ (αxr r ), βr ) ⊕let
β
0 [(2r+1)κ..(2r+2)κ]


xj
r−1
j=0 ρ̂j+1 (hρ (αj )).

4.3. Wrap-resistence
We need to show that given a mix message((α , β  , γ  ), δ  ), an adversary is unable to wrap it;that is, the adversary cannot produce a mix message((α, β, γ), δ) such that a mix node (even one whose
private key x the adversary can select) processing((α, β, γ), δ) will yield ((α , β  , γ  ), δ  ).
In order for the adversary to succeed, it is necessarythat αhb (α,s) = α where s = αx . We will show that anadversary which makes c queries to the random oracle
hb can find such an (α, x) pair with probability at mostcκq−1 ; for an adversary that does less than 2 work, thisis negligible.
The proof is simple: if the adversary outputs acorrect (α, x) pair, then she must have queried therandom oracle with (α, αx ). But each (α, s) query to
the oracle yields a random value b ∈R Z∗q . Since α isa generator of G ∗ , the probability that αb equals the1, and the result follows.
given α is q−1

4.4. Security and Indistinguishability of Forward and Reply Messages
We need to show that an adversary controlling all
nodes except one particular node, N, cannot distinguishmix messages entering node N, where each contains a(Δ, m) pair of the adversary’s choice, each has a pathfollowing node N of the adversary’s choice, and themessages can each be either forward or reply messages,
as the adversary likes. Additionally, the adversary cansee how N reacts to any mix message except one witha header matching the challenge message.
In particular, this would not only prove that the
security property of [5] is satisfied, but also thatforward and reply messages are indistinguishable toany party that does not know the exit node’s private
key.
Formally: consider the following game G. The adversary selects a sequence of mix nodes n0 , . . . , nν−1with ν ≤ r. One of these, nj , is the challenge node N.
The adversary can select the private keys xni ∈ Z∗q
for all i = j, but does not know xnj (he does
know the public key ynj ). The adversary also selects a
destination address Δ ∈ D\{∗}, a message m, and a
bit f that indicates whether this message should be a
forward message (f = 1) or a reply message (f = 0).
The adversary then selects a second setn0 , . . . , nν  −1 with ν  ≤ r, and Δ ∈ D\{∗},m , and f  . It must be the case that(n0 , n1 , . . . , nj ) = (n0 , n1 , . . . , nj ), but it neednot be the case that the list of subsequent nodes
after nj = nj = N is the same (or even of the samelength).
The challenger randomly chooses a bit b and constructs one of two mix messages as follows:
If b=0 and f=0: The challenger passes Δ and{n0 , . . . , nν−1 } to the procedure of section 3.4 tocreate a single-use reply block. There is no need tostore values in the local table, or to send (n0 , M0 , k̃)
to the nymserver. However, M0 and k̃ are used, alongwith m, in the procedure of section 3.5 to construct themix message ((α0 , β0 , γ0 ), δ0 ) which it would send ton0 . 1
If b=0 and f=1: The challenger passes Δ, m, and{n0 , . . . , nν−1 } to the procedure of section 3.3. This
procedure returns the mix message ((α0 , β0 , γ0 ), δ0 ).
If b=1: The challenger performs the same actions asabove, but uses the primed values n0 , . . . , nν  −1 , Δ ,m and f  instead of their unprimed counterparts.
((α0 , β0 , γ0 ), δ0 ) is given to the adversary, whose
job it is to determine b. The adversary can also give
any mix message ((α , β  , γ  ), δ  ) to the challenge node
nj to see how it reacts, so long as (α , β  , γ  ) =
1. Following section 3.5, we assume for simplicity that all reply
messages are delivered using the nymserver. However, this assumption is not essential. If Alice wishes to send a reply block directly
to Bob, for Bob’s use in replying to her, she just modifies theprocedure of section 3.4 to send him (n0 , M0 ), omits k̃ fromthe tuple in her local table, and omits the π −1 (k̃, ·) step fromthe procedure of section 3.7. The proof then need only have one
additional part: to show that an adversary cannot cryptographicallydistinguish replies output by the nymserver from replies output by afirst node n0 whose private key the adversary does not know. (Here,“cryptographically distinguish” excludes distinuguishing based on
traffic analysis; that is, observing the origin of the message.) The
remaining path in the two reply blocks should be the same, and theadversary is allowed to know all other nodes’ private keys. This isstraightforward: the only salient difference between the messages isthat the payload in the nymserver message is π(k̃, 0κ m) and in theother is π −1 (hπ (sn0 ), 0κ m). Both of these are indistinguishable
from a random string to an adversary that knows neither k̃ nor sn0 .

(αj , βj , γj ). Here, as in [5, §4.2], we only care about
uniqueness of the header, not of the message body.
We will show that the adversary cannot determine
the value of b with significantly better chance thanrandom guessing. Once we have proven this, we notethat the ability of the adversary to individually selectwhether each of the two messages is a forward message
or a reply message also implies our desired property
that the adversary cannot distinguish forward messages
from replies. This holds so long as there is even asingle node yet to process the message whose private
key the adversary does not know.
The advantage of the adversary is the difference
between 1/2 and the probability the adversary guesses
b correctly. We wish to show that the advantage for anadversary that does significantly less than 2κ work is
negligible.
We use the usual method of hybrid games. We firstnote that since the adversary can select the private
keys xn0 , . . . , xnj−1 , without loss of generality, we canassume that j = 0.
Game G1 is the same as G except that s0 (in theprocedure of section 3.2, called from section 3.3 in thecase of a forward message or section 3.4 in the case ofa reply message) is selected uniformly at random fromG ∗ , as opposed to being calulated as s0 = ynx0 . An
adversary that can distinguish game G from G1 caneasily be used to distinguish (yn0 , α0 = g x , s0 = ynx0 )from (yn0 , α0 , z) for a random z ∈R G ∗ , thus solving
the DDH problem in G ∗ , contrary to our choice ofG ∗ . Here it is important that the adversary should not
be allowed to query N with the challenge (α0 , β0 , γ0 )header, since N would not be able to process it. Thatxγ must be a MAC on β with key hμ (α0 n0 ) ensuresthat (α0 , β, γ) = (α0 , β0 , γ0 ) will be rejected by N
except with negligible probability. If any (α, β, γ) is
submitted to N with α = α0 such that N successfully
processes the message, then the success of the MAC
ensures that, again except with negligible probability,x
the adversary knew the MAC key hμ (α0 n0 ). Since hμ
is a random oracle, the adversary must have queried itxwith α0 n0 . But if the adversary knows that last value,
he can process the message just as well as N can, andthe ability to query N does not help him.
Game G2 is the same as G1 except that β0 , γ0 ,and δ0 are selected uniformly at random from theirrespective domains. If the adversary can distinguishgames G1 and G2 , then he can distinguish (with lesswork than 2κ ) the output of ρ with a random input froma random string, or μ with a random key from a randomfunction, or π with a random key (hπ (s0 )—with s0
being the randomly selected value from game G1 —in
the case of forward messages, or k̃ in the case of replymessages) from a random permutation, which he cando with only negligible probability, by our choice of
ρ, μ, and π.
In game G2 , since α0 is independent of the bit b,
and β0 , γ0 , and δ0 are all random (and independent ofb), it is clear the adversary’s advantage is 0. Since eachgame is indistinguishable from the one before to theadversary, except with negligible probability, we seethat the adversary’s advantage in the original game G
is negligible, as required.

5. Performance and Space Efficiency
In this section we give a brief overview of established cryptographic packet formats, and comparethem to Sphinx both in terms of functionality as wellas message size overhead. Throughout this section
p denotes the size of any public key element in apacket format, s denotes the size of the symmetrickey elements (per hop), and r denotes the maximum
number of hops that messages can be routed through(all sizes are in bytes). When comparing overhead
sizes, we will attempt to match the 128-bit security
offered by Sphinx. Some older designs only supplied
80-bit security, using 1024-bit RSA keys, for example.
We will be generous to the competing formats andstipulate that an RSA or Diffie-Hellman modulus of
2048 bits (256 bytes) is sufficient to offer 128-bit
security, even though NIST [2] suggests that 3072-bit
moduli are more appropriate for that security level.
In the elliptic curve setting, we use the usual figureof 256-bit (32-byte) elements (assuming only the xcoordinate of the elliptic curve point is required, orpoint compression is used) in order to achieve 128-bit
security.
The Sphinx packet format relies on a single public
key element, blinded at each stage of mixing, and foreach hop a message authentication code and the appropriate routing information. The cryptographic overheadsums to p + (2r + 1)s bytes in total for the header,and an additional s bytes for integrity of the payload.
The most costly operations involved in building apacket are the 2r public key operations. Relaying a
Sphinx message requires only two public key operations (the Diffie-Hellman and blinding operations),
plus the check that α ∈ G ∗ , for some choices of G ∗ . (InCurve25519, for example, this check does not involvea public-key operation, but in Z∗p , it does.)
Mixmaster [16] is an established remailer infrastructure, with about 25 nodes with over 90% reliability
according to Echolot statistics2 as of November 2008.
2. http://www.palfrader.org/echolot/

The main cryptographic shortcoming of the format is
the lack of support for anonymous replies. The nowaging design uses 1024-bit RSA for the asymmetricencryption part, encapsulating routing information anda 3-DES key to be used in CBC mode (with a changing
IV). Integrity is ensured through the use of an MD5
hash. The standard supports relaying messages over 20
hops—each hop adding a fixed 512 bytes of overhead.
In total the equivalent of the routing header occupies 10240 bytes. Abstracting away from the concrete
cryptographic mechanisms employed the length of a
mixmaster header is (1 + p + 8 + 8s + 31)r + s bytes(including a version number, an IV and padding). The
Sphinx header is shorter since it does not require apublic key element for each hop, and does not requirean IV, since each key is used only once.
The first provable cryptographic packet format was
proposed by Möller [15] and provided very similar functionality to the Mixmaster format—it supports sender-anonymous messages but not replies.
The scheme makes use of multiple layers of
DHAES/DSIES encryption. This requires an elementof a cyclic group on which the Decisional DiffieHellman problem is hard, and a message authentication
code per hop of mixing. To achieve a similar levelof security to Sphinx this introduces an overhead of
272 bytes (256 bytes for the group element and 16
bytes for the MAC) per hop in addition to any routing
information. The length of a packet header can be
abstracted as (p + s)r. As for Mixmaster the format
length suffers from the fact that a separate public key
element has to be included for each stage of mixing.
Camenisch and Lysyanskaya [5] provided formal
definitions in the Universal Composability model, anda concrete, provably secure, packet format for mixing
forward messages, which we call the CL05 format. The
CL05 scheme separates the messages into a header anda payload. The header is composed of asymmetricallyencrypted ciphertexts containing the address of thenext hop. They rely on a CCA2-secure encryption
scheme with tags, and the bulk of the encryption is
performed using a pseudorandom permutation (that is,a block cipher). The length of the header in the CL05
scheme is rp + (r + 1)s—unsurprisingly very similar
to Möller [15], given the shared design philosophy. It
is worth noting that the CL05 scheme does support
replies, with a very similar cost, but those are distinguishable from sender anonymous messages.
Mixminion [8] was the first packet format to propose
indistinguishable anonymous replies. Its cryptographic
design is based on two headers which are swapped
midway along the path. The headers are constructedusing layers of asymmetric encryption (2048-bit RSA-

SchemeOverhead Length

Mixmaster [16]Möller [15]Mixminion [8]CL05 [5]Minx [9]SSH08 [21]Sphinx(1 + p + 8 + 8s + 31)r + s(p + s)r2[p + (2s + 2s)(r − 1)] + s
rp + (r + 1)s
p + (s + 2)(r − 1)prp + (2r + 2)sIndistin.
Replies
no
no
yes
no
yes
yes
yes

Securityheuristic
provableheuristic
provablebrokenprovable
provableZ∗n(p=256, s=16, r=5)
2136
1360
1040
1376
328
1280
448

ECC
(p=32, s=16, r=5)
11761
4001
8481
4161
2321
1602
224

Table 1. Comparison between the lengths of different cryptographic packet formats in bytes. RSA schemes
superscripted with (1 ) have been converted to use elliptic curve Elgamal (hence p = 2p), while schemes
superscripted with (2 ) were modified to use a simple Diffie-Hellman over EC. The parameter p denotes thelength of asymmetric elements, s is the length of symmetric elements, while r is the maximum path length.

OAEP) and AES in CBC mode. Instead of appending
the RSA ciphertexts to each other, Mixminion compresses the headers by including parts of the next
RSA ciphertext in the plaintext of the previous one.
This means that the 2048 bytes of each sub-header
can encode information for more than 8 hops. Given
that the OAEP overhead is about 2s and that a hashand a key is contained in each layer of the header(again 2s) the cost of both headers of Mixminion is2[p + (2s + 2s)(r − 1)] + s bytes. There exist no known
attacks against this format, but at the same time it only
comes with heuristic security arguments.
Minx [9] was the first attempt to achieve a very
compact mix packet format. It uses raw RSA, and
AES in IGE and bi-IGE modes, without any additional
overhead for integrity checking. Instead it relies on thefragility and error propagation characteristics of bi-IGE
to ensure no information is recoverable from tagging
attacks. Like Mixminion, it encapsulates parts of RSA
ciphertexts into previous plaintexts, making the headersquite small. Its abstract length is p + (s + 1)(r − 1)bytes (assuming only a single byte of routing data).
The security argument underlying Minx is heuristic,
however, and recent work [21] shows that there isindeed a polynomial-time attack against it, taking
advantage of the naive use of raw RSA encryption.
Shimshock et al. [21] proposed a fix for Minx, which
we denote SSH08. The SSH08 format encodes only
keys in separate RSA headers destined to each mix,
and for technical reasons does not use the compression
technique employed by Mixminion and Minx. This
leads to a cost of pr bytes. It is also worth notingthat the encoding of a message relies on making one
byte of the hash of the RSA plaintext collide with theone byte destination of the packet. That is, there is no
way of telling hop i which node should be hop i + 1
short of constructing a message whose hash happens

to contain the (8-bit) identifier of the desired hop i + 1.
This requires, on average, about 256 RSA encryptions
per hop to construct the message. This design choicemakes the packet format quite compact, and easily
portable to elliptic curves, at the cost of flexibility.
The sender can only communicate a very small amountof information to each mix, since it would have tofind—using brute force—an element that decodes tothe desired information.
Table 1 summarises the overhead lengths and otherproperties of each cryptographic packet format andcompares them to Sphinx. Concrete lengths are illustrated through the choice of two sets of parameters, ineach case for a message that is capable of travellingon paths up to length r = 5. First the length of theheader is calculated for cryptosystems based on thehardness of the discrete logarithm and RSA problems
over number fields. To achieve 128-bit security werequire p = 256 byte (2048-bit) asymmetric elements,and s = 16 byte symmetric elements. We can see thatin this context Sphinx outperforms all other secure proposals (note that Minx is not considered secure [21]).
A second comparison is made between Sphinx
and other schemes when they are implemented using
asymmetric primitives based on elliptic curves. In that
context we substitute RSA encryption, used by mostother schemes, with an EC-based version of Elgamal.
This requires two asymmetric elements of total lengthp = 2p. Sphinx and SSH08 on the other hand do
not encrypt anything, and the asymmetric part of theheader is only required to perform key derivation.
As such they only use a single element of lengthp = 32 bytes, the size necessary to achieve 128-bit
security. The SSH08 scheme is more compact thanMinx only because it is capable of transmitting very
little information from the sender to the intermediatemixes (about 8 bits of information, at the cost ofabout 28 public key operations per mix). Sphinx can
carry much more information to intermediate mixes,
supporting more complex mixing strategies, and at amuch lower computational cost to the sender.
Finally, we note that Sphinx messages are computationally cheap to process: they require a single
public key operation (an exponentiation in Z∗n or
multiplication in ECC) to derive a key, followed by
fast symmetric-key operations.

6. Conclusions
Sphinx is a compact and provably secure mix packet
format, designed as a drop-in replacement for existingremailers.
Sphinx is flexible in two important ways: first, it allows the system designer to chose their preferred family of cryptographic primitives. With Diffie-Hellman
over prime fields, Sphinx is the most compact format,
with an overhead of 448 bytes to route through 5
mixes. The use of ECC makes it even more compact,with a header length of only 224 bytes. The compactness of the format allows novel applications ofanonymity to flourish: short messages can be cheaply
routed, supporting privacy for services like microblogging with a low cryptographic overhead.
Second, Sphinx can be trivially extended to act asa general-purpose secure transport between sendersof messages and the intermediate mixes on a path.
This means that system designers are free to choose
any mix strategies, including those that rely on thesender providing detailed information to mixes about
the processing of messages. Such strategies are crucial for blending high-and-low latency traffic [11], or
preventing flooding attacks [13].
The security guarantees associated with Sphinx arevery strong, and backed by reduction proofs to wellstudied cryptographic primitives. Hence, we can say
with high confidence that the short length of thepackets does not lead to any reduction in security.
The line of research up to this state-of-the-art Sphinx
design demonstrates that the cryptographic aspects ofanonymous communications are now well understoodand mature. Off-the-shelf packet formats are now
available to route messages through any system, allowing designers of anonymity systems to concentrateon preventing traffic analysis and sorting out denialof-service problems, as well as implementing robust
business models around anonymous communications.
Sphinx can act as a transport layer for any of theseapplications, ensuring that the cryptography of theanonymous transport is no longer a security worry.

Acknowledgements
The design of Sphinx has greatly benefitted fromdiscussions with Anna Lysyanskaya, at the 2005 Daghstul school on anonymous communications. Steven
Murdoch, Greg Zaverucha and Emilia Käsper provided
very useful early feedback on the ideas as well as adraft of the paper. We would like to thank the Natural
Sciences and Engineering Research Council of Canada
and the Mathematics of Information Technology andComplex Systems Network of Centres of Excellence
for supporting this work. We would also like to thankthe anonymous reviewers for making suggestions toimprove this paper.

References[1] Ross J. Anderson and Eli Biham. Two Practical andProvably Secure Block Ciphers: BEARS and LION. In
Dieter Gollmann, editor, FSE, volume 1039 of Lecture
Notes in Computer Science, pages 113–120. Springer,
1996.
[2] Elaine Barker, William Barker, William Burr, William
Polk, and Miles Smid. Recommendation for Key
Management—Part 1: General (Revised). National Institute of Standards and Technology Special Publication
800-57, May 2006.
[3] Daniel J. Bernstein. Curve25519: New Diffie-Hellman
Speed Records. In Public Key Cryptography 2006,
pages 207–228, 2006.
[4] Oliver Berthold, Andreas Pfitzmann, and Ronny
Standtke. The disadvantages of free MIX routes andhow to overcome them. In H. Federrath, editor, Proceedings of Designing Privacy Enhancing Technologies: Workshop on Design Issues in Anonymity andUnobservability, pages 30–45. Springer-Verlag, LNCS
2009, July 2000.
[5] Jan Camenisch and Anna Lysyanskaya. A formal
treatment of onion routing. In Victor Shoup, editor, Proceedings of CRYPTO 2005, pages 169–187.
Springer-Verlag, LNCS 3621, August 2005.
[6] Ran Canetti. Universally composable security: A newparadigm for cryptographic protocols. In FOCS, pages
136–145, 2001.
[7] David Chaum. Untraceable electronic mail, return
addresses, and digital pseudonyms. Communicationsof the ACM, 4(2), February 1981.
[8] George Danezis, Roger Dingledine, and Nick Mathewson. Mixminion: Design of a Type III Anonymous
Remailer Protocol. In Proceedings of the 2003 IEEE
Symposium on Security and Privacy, pages 2–15, May2003.

[9] George Danezis and Ben Laurie. Minx: A simple andefficient anonymous packet format. In Proceedingsof the Workshop on Privacy in the Electronic Society(WPES 2004), Washington, DC, USA, October 2004.
[10] Whitfield Diffie and Martin E. Hellman. New directions
in cryptography. IEEE Transactions on Information
Theory, IT-22(6):644–654, 1976.
[11] Roger Dingledine, Andrei Serjantov, and Paul Syverson. Blending different latency traffic with alphamixing. In George Danezis and Philippe Golle, editors, Proceedings of the Sixth Workshop on Privacy
Enhancing Technologies (PET 2006), pages 245–257,
Cambridge, UK, June 2006. Springer.
[12] Ceki Gülcü and Gene Tsudik. Mixing E-mail with
Babel. In Proceedings of the Network and Distributed
Security Symposium - NDSS ’96, pages 2–16. IEEE,
1996.
[13] Dogan Kesdogan, Jan Egner, and Roland Büschkes.
Stop-and-go MIXes: Providing probabilistic anonymity
in an open system. In Proceedings of Information
Hiding Workshop (IH 1998). Springer-Verlag, LNCS
1525, 1998.
[14] David Mazières and M. Frans Kaashoek. The Design,
Implementation and Operation of an Email PseudonymServer. In Proceedings of the 5th ACM Conference on
Computer and Communications Security (CCS 1998).
ACM Press, 1998.
[15] Bodo Möller. Provably secure public-key encryption
for length-preserving chaumian mixes. In Proceedingsof CT-RSA 2003. Springer-Verlag, LNCS 2612, 2003.
[16] Ulf Möller, Lance Cottrell, Peter Palfrader, and Len
Sassaman. Mixmaster Protocol — Version 2. IETF
Internet Draft, 2003.
[17] Mridul Nandi and Douglas R. Stinson. Multicollision Attacks on Some Generalized Sequential Hash
Functions. IEEE Transactions on Information Theory,53(2):759–767, February 2007.
[18] Birgit Pfitzmann and Andreas Pfitzmann. How tobreak the direct RSA-implementation of MIXes. In
Proceedings of EUROCRYPT 1989. Springer-Verlag,
LNCS 434, 1990.
[19] Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures andpublic-key cryptosystems. Commun. ACM, 21(2):120–
126, 1978.
[20] Andrei Serjantov, Roger Dingledine, and Paul Syverson. From a trickle to a flood: Active attacks on several
mix types. In Fabien Petitcolas, editor, Proceedingsof Information Hiding Workshop (IH 2002). SpringerVerlag, LNCS 2578, October 2002.

[21] Eric Shimshock, Matt Staats, and Nick Hopper. Breaking and Provably Fixing Minx. In Nikita Borisov and
Ian Goldberg, editors, Proceedings of the Eighth International Symposium on Privacy Enhancing Technologies (PETS 2008), pages 99–114, Leuven, Belgium,
July 2008. Springer.