Onion routing and mix networks
are fundamental concepts to
provide users
with anonymous access
to the Internet.

Various corresponding solutions
rely on the efficient
Sphinx packet format.
flaws in Sphinx's
underlying proof strategy
were found recently.
It is thus currently unclear
which guarantees Sphinx
actually provides,
even worse,
there is no
suitable proof strategy

In this paper,
we restore the security foundation
for all these works
by building a theoretical framework
for Sphinx.
We discover that
the previously-used DDH assumption
is insufficient for a security proof
and show that
the Gap Diffie-Hellman (GDH) assumption
is required instead.
We apply it
to prove that a
slightly adapted version
of the Sphinx packet format
is secure
under the GDH assumption.
Ours is the first work
to provide a detailed,
in-depth security proof
for Sphinx in this manner.

Our adaptations to Sphinx are necessary,
as we demonstrate
with an attack
on sender privacy
that would be possible otherwise.

§ INTRODUCTION

The majority of today's Internet traffic
fails to protect
the privacy of its users
since the exposed IP addresses serve as identifying information.
Onion routing (OR)
and mix networks
are techniques
that address this issue
by hiding the users' IP addresses.
OR and mix networks
are similar
in the sense that
both use relays
together with
multiple layers of encryption
to hide the link
between the sender
and the message
and receiver.
The sender
wraps the message
in multiple encryption layers,
thus creating an onion packet.
The layers
are peeled off
one by one
while traversing
the relays
on the onion's path.
As a critical distinction,
mix networks
protect against
a global adversary by changing the order of packets
at each relay (hence mixing
the communications). This comes
at the cost of
introducing additional delays. OR networks avoid these delays, but become vulnerable to global passive adversaries.
Proposed works for both
OR and mix networks
exist in two network models:
In the integrated-system model,
the receiver acts
as the last relay.
On the contrary,
in the service model,
the receiver is
unaware of the OR or mix network.
The last relay,
which is called
the exit relay,
retrieves and forwards
the message
to the receiver
as in the underlying protocol.

To hide the link
from senders
to messages and receivers,
protocol designers
aim to make
all incoming
and outgoing packets
at honest relays
unlinkable for the adversary.
This requires special care
when designing the packet formats,
as any part
of the packet
could include
linkable information.
Tor <cit.> is being broadly applied against local adversaries but mix networks against global adversaries are increasingly developed.
The most efficient
and commonly used
mix network packet format
is Sphinx
In fact,
Sphinx is not only used
as a foundation
for mix networks
but also for OR protocols
and even inspired
a recent improvement
of Tor <cit.>.

Sphinx <cit.> works
in the service model
and assumes
an additional party,
the nymserver
While the name
is the same,
this server has
nothing to do
with the anonymization network
Senders send onions
with reply information
to the nymserver.
Exit relays send
anonymous reply messages
via the nymserver,
which uses the reply information
to build
a reply packet.
Sphinx packets
consist of a header
and a payload.
The header contains
encrypted routing information
and keys.
The payload contains
the encrypted message.
Using only group exponentiations
and well-known
symmetric cryptography,
Sphinx is highly efficient

Sphinx's privacy has been
proven previously
using a proof strategy
In order to comply
with  <cit.>
and to honor
Sphinx's applicability
for OR protocols,
we (ab-)use the onion terminology
in the rest of this paper,
while always meaning
OR and mix networks
and considering
a global adversary.
Camenisch and Lysyanskaya's proof strategy
first proposes
an idealized version
of OR
in the form of
an ideal functionality
in the Universal Composability framework <cit.>.
This ideal functionality
is effectively an abstract version
of an OR protocol,
from which privacy guarantees
can be derived
more readily.
As proving that
a protocol securely realizes
this functionality directly
is cumbersome,
they also create
a set of
game-based properties
which they claim
imply realization
of the ideal functionality
As it turns out,
those properties,
which were used
in Sphinx's privacy proof,
are insufficent
to realize the ideal functionality

propose new properties
that indeed imply the ideal functionality
Sphinx is not able
to achieve them
for two reasons.
Sphinx, along with
many real-world applications,
works in the service model,
while the new proof strategy
is in the integrated-system model.
Sphinx does not protect
the integrity of the payload
at each hop
and thus allows
for a malleability attack
on the payload:
If the adversary tags
flips bits of the payload)
an onion
leaving its sender,
the exit relay processing the Sphinx packet
will notice that
the payload has been modified
and drop the message.
If Sphinx is used
in the integrated-system model,
this attack allows
an adversarial receiver
colluding with the first relay
to learn which user
was contacting it.
As this violates
the desired privacy goal,
it follows
that Sphinx
does not achieve
the integrated-system properties
of the related work
In the service model,
this attack only allows
an adversary to
link the sender
to the exit relay
and completely destroys
the message
in the process.
there is hope that the highly efficient
Sphinx packet format is still secure to use
as long as it is
in its intended
service model.
this question is highly relevant
since all known protocols
that prevent this attack
while supporting
anonymous replies
incur extremely high overhead
due to heavy,
relatively new
cryptographic primitives

In addition
to the problems
noted above,
we discover that
the Decisional Diffie-Hellman (DDH) assumption
used by Danezis and Goldberg
to prove
that Sphinx satisfies
Camenisch and Lysyanskaya's game-based properties
is insufficient
for Sphinx's security proof.

In this paper,
we hence set out to
perform a thorough analysis
and provide
the missing privacy proofs
for Sphinx.
We first
provide the
necessary framework
for the service model:
A reusable game-based proof strategy
which is of independent interest
for future work
on packet formats
as well as
as ideal functionality
in the UC framework
for use
in analyzing the privacy guarantees
of service-model OR protocols.
We first define
this new ideal functionality,
which incorporates both the
relaxed privacy accounting for
payload malleability
as well as
the changes required
for the service model.
We then construct
our game-based onion properties
and prove that
a protocol satisfying them
implies that that protocol
also realizes the ideal functionality.
During the work
on this proof,
we also discover and fix mistakes and details
in the proof
for the related work
in the integrated-system model <cit.>.

we turn to
an analysis of Sphinx
and realize that
an adaptation
must be made
to the packet format
and its operation
in order to achieve
provable security.
As originally defined,
Sphinx uses a nymserver
to enable its reply functionality.
the use of such third parties
allows for
an additional tagging attack
based on
payload malleability.
For secure operation
of Sphinx,
we hence propose
an adaptation
of the Sphinx protocol
that works without a nymserver,
but still supports
anonymous replies.
This works by
simply embedding the reply information
in the packet's payload
instead of sending it separately.
we discuss the effect
of our privacy relaxation
and detail criteria
for the secure usage
of Sphinx.

In summary,
our main contributions are:

* the definition of
repliable service OR schemes,

* the construction of
an ideal functionality
tailored to Sphinx
as well as
corresponding game-based properties,

* minor fixes
in the proof
for the related integrated-system model work,

* the discovery that
the GDH assumption
is required to prove Sphinx secure
instead of the DDH assumption,

* the first detailed security proof
for (a slightly adapted version of) Sphinx
under the GDH assumption,

* a discussion of criteria
for secure usage
of Sphinx.

<ref> introduces
the required background
on onion routing.
<ref> constructs
the formal foundations
for repliable OR in the service model,
<ref> uses
to analyze
and adapt Sphinx.
discusses the privacy
achieved by
our adapted Sphinx
as well as
relevant criteria
under which
the adapted Sphinx
is considered secure.
concludes this paper.

§ BACKGROUND AND RELATED WORK

We first introduce
our privacy requirements,
onion routing and mix networks
and the general network model
before providing background
on the formal analysis
in this work
and the Sphinx packet format

§.§ Onion Routing and Mix Network Packet Formats

Onion routing
and mix networks
aim to hide the sender
of a packet
in a set of users
called the anonymity set.
They thereby
prevent linking the sender
both to the sent message
and the receiver.
The networks
employ multiple relays
between the sender
and receiver
that process packets
and forward them
to the next relay
or the receiver.
As the message
in the packet
is typically wrapped
into multiple layers
of encryption,
it is also called
an onion
and every processing result
on an onion's relay path
is an onion layer

Relay services
are typically run
by volunteers
that want to
help the sender
increase its privacy
against adversarial receivers,
but also internet providers
and possibly even
nation-state adversaries.
Due to this
open nature
of the network,
it is assumed that
a fraction of the relays
is controlled by
the adversary
as well
Mix networks
aim to protect against
a global adversary
and therefore
not only
change the representation
of the onion packet,
but also reorder
incoming packets
before forwarding them.
Onion routing networks,
traditionally protect only
against local adversaries
and prioritize
offering low-latency service
over stronger protection
In terms of
the packet format,
the networks are similar —
they share
the underlying idea
of layered encryption.
For the sake of
compatibility with related work,
we use OR as a representative for both
OR and mix network packet formats.
We stress that
we nonetheless target
a global adversary.

§.§ Network Models and Functionalities

We distinguish between
two network models
for OR protocols:
The integrated-system model
assumes that
the receiver is aware of
and runs
the OR protocol,
while the service model
assumes that
the receiver can be
unaware of
the OR protocol.
The last relay
before the receiver,
the exit relay,
translates the packets accordingly.

We also distinguish
two different functionalities:
Non-repliable OR
only sends messages
from senders to receivers
in one direction and
repliable OR acts as
two-way communication.
Repliable OR schemes involve
sending requests
as forward messages
and receiving responses
as reply messages.

By design,
the anonymity of
the sender
is required to hold
even against
a malicious replying receiver.
the receiver must not know
to whom it sends its reply.
To achieve this,
the sender can
prepare an anonymized
return envelope
and include it in its onion.
Some repliable OR protocols
(including Sphinx) additionally
require forward
and reply packets
to be indistinguishable
from each other
while they are
moving through
the network
in order to
increase the anonymity set
of each packet

§.§ Formally Analyzing Mix Network Packet Formats

The state of the art
uses the
Universal Composability (UC) framework <cit.>
to formalize OR security
for packet formats.
In UC,
the desired security
is defined by
an ideal functionality ,
which is
an optimal, abstract version
of the protocol.
performs all computations
on a trusted third party
and clearly specifies how
the environment
(which controls the honest parties)
and the adversary
are allowed to interact
with that third party.
The goal is then
to show that a real protocol
is as secure
as and thus
securely realizes .
This means
all attacks
against the real protocol
must also work in (which is secure
by definition).
In this model,
the environment controls
all of the honest parties
and the adversary controls
the corrupted parties.
To show that
a protocol securely realizes ,
one constructs a simulator
that translates the actions
of the real-world adversary
into the ideal-world 's
adversarial entity's behavior
and the ideal world's
honest parties' actions
into real-world
protocol messages.
The environment
and the adversary
are allowed to collaborate
and the environment's view
after the protocol ends
is given to
a distinguisher.
Only if
the view of the environment
when it is interacting with
the simulator and  is indistinguishable from
the view created from
an interaction
of the environment with
the real-world adversary
and the real protocol
does the protocol
securely realize

§.§.§ Overview of Analysis Works

The first approach
to consider OR
in the UC framework
was proposed by
Camenisch and Lysyanskaya.
They create an ideal functionality
and (as they claim)
corresponding game-based
security properties
for the integrated-system model
without replies
The reason for
the creation of
the game-based properties
is that
proving that
a protocol securely realizes
an ideal functionality
is complex
and involves multiple steps:
One must construct
a simulator for every adversary
and then prove that
the simulator simulates
the adversary indistinguishably.
Since many OR protocols
operate in a similar way,
Camenisch and Lysyanskaya
reduce this overhead
by defining their game-based properties.
Their secure realization proof
works for any OR protocol
in their model
that satisfies the game-based properties,
taking advantage of
the similarities
between protocols.
For authors of packet formats,
this means that
they only need to prove
that their format
satisfies the game-based properties
in order to
securely realize
the ideal functionality

A series of protocols
have based
their security proofs
on Camenisch and Lysyanskaya's
game-based properties
Kuhn et al.
find flaws
in the proposed properties
as well as
in the corresponding protocols
They fix
the proof strategy
by proposing
new OR properties
that imply the ideal functionality
as originally proposed by
Camenisch and Lysyanskaya.

extend the ideal functionality
and OR properties
to include replies
in the integrated-system model
and propose
a new OR scheme
for this model.

improve on
's work
by improving the privacy in the schemes,
ideal functionality,
and the onion properties
for repliable integrated-system-model OR.

§.§.§ Summary of Integrated-System Framework

In the following,
we present
a high-level summary
of the integrated-system framework
which we will adapt
for our repliable service-model

The ideal functionality [R]
for repliable OR in
the integrated-system model
offers an interface
to the environment and adversary
that allows relays
to send and forward onions.
The honest and corrupted parties
send messages
to the trusted third party
to trigger these actions.
[R] then provides
the appropriate outputs
to the parties —
these correspond to
the ideal outputs
one would expect from
a secure OR protocol.
For example,
the adversary is notified
when an onion is forwarded
by an honest relay
and receives a temporary onion identifier
that it can send back to [R]
when it decides
to deliver that onion
to the next honest relay.
never constructs
or outputs any real onions.
the parties only receive
information about the onions
associated with
the aforementioned
temporary onion identifiers,
These identifiers include
no information about
the sender,
the receiver,
the path,
or the message
of the respective onion.
The identifiers are also
replaced with
a new random temporary identifier
at each honest relay.
This is done because
any honest relay
in an OR network
breaks the link
between the onion layers
before and after itself.

Proving secure UC-realization
for each OR protocol individually
involves a lot of redundant work.
In line with earlier work,

thus define onion properties
that are sufficient to prove
that an
integrated-system packet format
securely realizes [R].
These are
Forwards Layer Unlinkability (),
Backwards Layer Unlinkability (),
and Repliable Tail Indistinguishability ()

Correctness requires that
onions follow their set paths
and decrypt correctly
if they are honestly processed.

In the Forwards Layer Unlinkability
() game,
onion layers
between honest relays
on the forward path
of the onion
are replaced with
random onion layers
taking the same path.
The adversary is required
to distinguish the replacement
from the original.
If the adversary
cannot do so,
the packet format ensures that
onion layers
on the forward path
of an onion
cannot be linked
across an honest relay.

In the Backwards Layer Unlinkability
() game,
onion layers
on the reply path
(instead of
the forward path)
are replaced
with random onion layers.
it replaces them with
random forward onion layers.
the adversary must distinguish
the replacement
from the original.
If it cannot do so,
the packet format ensures
unlinkability of reply onion layers.
This property
also implies indistinguishability of
forward and reply onions.

In the Repliable Tail Indistinguishability
() game,
onion layers
going to a corrupted receiver relay
are replaced with
random onion layers
with the same path
and message contents.
The adversary must
once again tell the difference
between the two.
If it cannot,
the packet format guarantees
that different onions
with the same message
going to a corrupted receiver
are indistinguishable.

Note that,
if all four properties
are satisfied,
every layer of an onion
can be replaced
with a random layer
such that only
the respective subpaths
between honest relays
stay the same
(and the message,
if the layer goes
to a corrupted receiver).
this means that
an adversary learns
no more from
any given sequence of onion layers
than it would
if given a temporary onion identifier
and the corresponding subpath
like in [R].

These onion properties are used
to enable the
secure realization proof:
When constructing the simulator
that simulates the adversary,
but interacts only with [R],
the simulator
does not learn
the full path or message
of onions
from honest senders,
but only the subpaths
between two honest relays.
This is by construction
of [R].
In order to translate
the ideal-world onion
into a real-world onion,
it must thus replace
the real onion layers
that the adversary and environment
would expect to see
with random (forward) onion layers
that only match
the original onion
in their subpath
(and their message
if an adversarial receiver
gets the onion).
The properties ensure
that the replacement
cannot be detected,
allowing the proof
to be completed
in this manner.

§.§ Sphinx

Sphinx <cit.> is a
compact repliable mix packet format
in the service model
following the adversary model
and privacy goals
described above.

§.§.§ The Sphinx Packet

A Sphinx packet
consists of a header $\eta$
and a payload $\delta$.
The header of the packet
contains all of
the routing information
for the packet
while the payload
contains the message
and the receiver address.
The sender of the packet
builds both components
layer by layer,
starting at the final
innermost layer
and adding one additional layer
of encryption
for each relay
on the packet's path
as chosen by
the sender.
If the path
is shorter
than the configured
maximum path length,
padding is added
to the final layer
of the header.
The relays each remove
one layer of that encryption
when they process
the packet.
The final relay
removes the last layer of encryption
from the packet
and discovers
the message and receiver address.
It then delivers
the message
to the receiver
The packet format
is described
in more detail
in <ref>.

The separation
of the header and payload
allows for Sphinx's replies:
A sender forms
a repliable packet by
creating a header
for the reply
as well as
a key for the reply payload
before sending
the forward packet.
The reply header and the key
are sent to a third-party
using another forward packet
and stored under a pseudonym there.
After receiving a reply
from the receiver,
the exit relay of the packet
sends the nymserver
the reply message
and the pseudonym
it learned
from the forward packet.
The nymserver
the reply payload
using the key
and attaches it
to the reply header
before sending it

§.§.§ Sphinx Security

Sphinx (as defined in  <cit.>)
has two known flaws.
The first
is due to the padding
in the final layer
of the header.
In the original Sphinx definition,
this padding
consists of only 0 bits and
depends on the chosen path length
As this pattern is recognizable,
a corrupted exit relay
learns information about the path length.
The Sphinx implementation <cit.>
fixes this issue
by using
random bits instead.
In the following,
we consider
the version of Sphinx
that includes this fix.

Payload Tagging
Sphinx's second flaw
concerns the integrity
of the payload.
Due to how Sphinx handles replies,
it cannot use
a standard integrity check
of the payload $\delta$
at each relay
Note that there are
repliable OR schemes
that solve this issue,
but they are highly inefficient as they require
significantly more complex
cryptographic primitives
Adversarial modifications
of the payload thus
go unnoticed
until the packet
reaches its exit relay,
which notices
(and drops)
the modified packet
during the integrity check
on the payload.
this allows the adversary
to link the packet
it tagged
(by, e.g.,
flipping bits
in its payload)
to the packet
that was dropped
by the exit relay.
The payload
is completely destroyed
in the process.
If Sphinx is used
in the integrated-system model,
(as, e.g., in <cit.>),
this attack
links sender and receivers
and thereby completely breaks
the scheme's security.
if Sphinx is used
in its intended service model,
the attack only links
the sender
to its corresponding
exit relay.
This can be
an acceptable leak
in some settings,
as we discuss later
Note that
tagging the Sphinx header
in this manner
is not possible:
The header's integrity
is protected by a MAC
that is checked
at every relay
for both forward
and reply onions.
The reason for
this being easier to achieve
than payload integrity
is that
the reply header
can be built by the sender
ahead of time,
while the reply payload
cannot (as the sender
does not know
the reply message).

§ REPLIABLE SERVICE ONION ROUTING

We formalize repliable OR
in the service model,
hereafter referred to
as repliable service OR
and construct
an ideal functionality
and corresponding onion properties
that allow for
the payload malleability attack
on Sphinx.
We base
our formalization
on 's work

§.§ Defining Repliable Service Onion Routing

§.§.§ Notation

In general,
we follow the notation
of the corresponding related work
as much as possible.
We represent
messages with $m$,
headers with $\eta$,
and payloads,
which include $m$
along with other metadata,
with $\delta$.
A packet is the combination of  $\eta$ and $\delta$.
We also refer to packets
as onion layers
and shorten the term onion layer
to onion where appropriate.
Onion paths $\mathcal{P}=(P_1,\dots, P_n)$
consist of
a sequence of relays
with $P_i$ being
the $i$-th relay's name
and $P_n$ being
the exit relay.
the receiver,
is not part of
the onion's path.
$PK_i$ and $SK_i$
are the public and secret key
of relay $P_i$.
$O_i$ is the $i$-th onion layer,
the processing result
that $P_{i-1}$ produces
and sends to $P_i$.
For reply information,
we use the same notation
with an additional
superscript arrow:
$x\ba$ indicates
the reply counterpart
to the forward component $x$.

§.§.§ Assumptions

In this work,
we make use of
the following standard assumptions
regarding the OR protocol,
which we inherit
from related work
Note that none of them
require additional trust,
but just limit
the packet schemes
our model applies to.
To the best of our knowledge,
every previously-proposed
OR scheme and protocol
adheres to
these assumptions.

A maximum path length (number of relays on the path)
of $N$  is used (inclusive upper bound).

Honest senders choose
acyclic paths
(to increase the chance
of picking
at least one
honest relay).

Replay protection at honest relays
drops onions
whose headers
are bit-for-bit identical
to ones
that have already been seen
at that relay.
Detecting these duplicates
only fails with a
negligible probability.

A sender always knows
the public keys $PK_i$
of any relays $P_i$
it uses
for its onion's paths.

An onion $O$
consists of
a header $\eta$
and a payload $\delta$
such that
$O = (\eta, \delta)$.

Honest relays
inside the OR network
communicate with each other
via secure channels
This assumption
was implicitly introduced
in the UC proof
Relays and receivers
do not communicate
via secure channels.

Assumption <ref>
expands the secure-channel assumption
for honest relays
from <cit.>
by explicitly denying
relay-receiver pairs
from using secure channels
to communicate
since we do not know
the state
of the external network.

we introduce new assumptions
related to the service model.

Receivers drop
any onions
sent to them.
relays drop
any onions
they get
from links
to receivers.

Since we assume
that receivers
are unaware
of the OR network,
they cannot process onions.
Traffic between receivers
is not part
of our OR model.

An onion
in an RSOR packet format
never has
an empty forward path.
If it is repliable,
it does not have
an empty backward path.

An onion
with an empty forward path
is effectively
not an onion at all
since the sender
is also
the exit relay.
The packet format
should thus not allow
a valid onion
to have an empty path.
We use
an empty backward path
as a sentinel value
for a non-repliable onion.

An honest relay
will always drop
an unsolicited reply
a reply
with a header
the relay
does not recognize
as belonging to
the final reply layer
of an onion it sent).

This is not
a surprising limitation.
Honest relays
will only process replies
that they expect.
we add one cryptographic assumption
that we require
for our game-based properties
and UC realization proof:

Onion payloads
are encrypted with
a pseudorandom permutation (PRP).

With this assumption,
any modification
of a payload
(i.e., a tagging attack)
will completely randomize
and thus destroy
the payload contents,
which we require
for security against
these attacks.

§.§.§ Formal RSOR Schemes

We build an RSOR scheme
using the following algorithms (following

* Key generation algorithm $G$ for $P \in \Nn$:

\[(PK, SK) \gets G(1^\lambda, p, P)\]

* Onion sending algorithm $(n, n\ba \leq N)$:

\begin{gather*}
O_i\! \gets\! \FormO(i, \bm{\Rrs}, m, \bm{R}, \Pp, \Pp\ba\!\!, PK_{\Pp}, PK_{\Pp\ba\!\!}), \\
\Pp^{(\leftarrow)} = (P^{(\leftarrow)}_1, \ldots, P^{(\leftarrow)}_{n^{(\leftarrow)}}) \in \Nn^{n^{(\leftarrow)}}, \\
PK_{\Pp^{(\leftarrow)}} = (PK^{(\leftarrow)}_1, \ldots, PK^{(\leftarrow)}_{n^{(\leftarrow)}}).
\end{gather*}

If $i > n$,
$R$ is ignored
and the onion $O_i$
is formed like a reply
with the message $m$.
$\Pp\ba$ may be empty
if no reply is desired.
$\Pp\ba$ contains
the reply receiver
(which is the sender )
as its final relay.

* Onion processing algorithm at $P$:

\[(O', P') \gets \Proc(SK, O, P).\]

$P$  processing $O$
with its secret key $SK$
results in an onion $O'$
to send to
the next relay $P'$.
In case of an error,
$(O', P') = (\bot, \bot)$.

$(m, R) = \Proc(SK_E, O_n, E)$
if $E$ is the exit relay of the onion.
$m$ is the message for receiver $R$.

$(m\ba, \bot) = \Proc(SK_s, O_{n+n\ba}, \Ps)$
if sender (with private key $SK_s$)
received the reply onion $O_{n+n\ba}$
containing reply message

* Reply sending algorithm :

\[(O\ba, P\ba) \gets \Reply(m\ba, O, E, SK).\]

The reply onion $O\ba$
to be sent to $P\ba$ is created
from the reply message $m\ba$
and the original onion $O$
as processed by
$O$'s exit relay $E$
with the secret key $SK$.
If an error occurs,
$(O\ba, P\ba) = (\bot, \bot)$.

An RSOR scheme
is a tuple of polynomial-time algorithms
($G$, , , ).

Using an RSOR scheme,
we can construct
a corresponding protocol
as follows:

* A sender
selects the parameters
for its onion,
builds it
using $\FormO$,
and sends $O_1$
to $P_1$.

* Each relay $P_i$
processes the onion
in turn
using $\Proc$
and sends $O_i$
to $P_i$.

* The onion's exit relay $P_n$
$(m, R)$ $\gets$ $\Proc($$SK_n$, $O_n$, $P_n)$.
It generates
a random reply ID $rid$,
remembers $O_n$ in a map
as $(rid, O_n)$,
and sends $(m, rid)$
to $R$.

* $R$ receives $(m, rid)$
and decides
to reply to the message.
It sends its reply $(m\ba, rid)$
back to $P_n$.

* $P_n$ gets the reply message
and finds ($rid$, $O_n$)
in its map.
It calculates
$(O\ba, P\ba) \gets \Reply(m\ba, O_n, P_n, SK_n)$
and sends $O\ba$
to $P\ba$.

* The reply onion
follows its reply path
like in step four
until the sender receives
and processes it
to receive $(m\ba, \bot)$.

We introduce the concept
of reply IDs ($rid$s)
in the protocol description.
These IDs are
intended to be abstractions
of the connections
established by real-world
network connection protocols
like TCP —
To avoid the complexity
actual connections
would bring
into our definitions,
we represent them
as a simple device
that allows a receiver
to send a reply
directly to the relay
it received the $rid$ from.
Our protocols
do not protect $rid$s,
so they can be
manipulated by adversaries
(preventing this
would require
the establishment
of secure channels
between receivers and relays,
which contradicts

In addition
to the algorithms defined above,
we also require
the algorithm
$\textsc{RecognizeOnion}($$i$, $O$, $\Rr$, $m$, $R$, $\Pp$, $\Pp\ba$, $PK_{\Pp}$, $PK_{\Pp\ba})$
to be defined
for RSOR
to its original definition
by or_replies:
The algorithm compares
the header of $O$
to the $i$-th layer
of the onion
originally created
from the given inputs.
For our RSOR schemes,
this means that
the message
is not checked
since it is
in the payload.

§.§ RSOR Ideal Functionalities

In this section,
we provide an overview
of our ideal functionality for RSOR,
focusing on the core ideas
and issues
in its construction.
We base it on
[R] <cit.>.
We also explain
the differences between
and [R].
is given in pseudocode
in Appendix

§.§.§ Ideal Functionality

Recall from
in an UC ideal functionality ,
all processing happens
on a trusted party
with a set of interfaces
and procedures
that the environment and the adversary interact with
and receive information from.

Fundamental concept
Following the related work,
onion layers are abstracted
into a series of
random temporary identifiers,
the temp IDs ($tid$s).
When an onion
is forwarded through
an honest relay,
it receives a new $tid$,
thus rendering
the layers before the relay
and after the relay unlinkable.
Corrupted relays
do not cause
the $tid$
to be replaced.
As an onion
is forwarded
between honest relays,
the $tid$s
for the layers
along with information
on the layers' paths.
This corresponds
to the intuition that
the adversary learns nothing
about the content
of the onion
and cannot link
the layers
before and after
an honest relay
to each other.
all of the interactions
between relays
and between relays and receivers
in the network
including all possible
adversarial capabilities
in our adversary model.
This includes corner cases
and unusual adversary behavior.

Detailed Interaction
To send a new onion
in ,
(for honest parties) or (for adversarial parties)
notify with the desired receiver,
and forward
and reply paths.
The resulting temp ID $tid$
is given to ,
which controls the links
and may choose to deliver
the $tid$
(i.e., the onion)
to the next honest relay.
If the onion
was sent by a corrupted sender,
all of the information
on the onion
for every path segment
This matches the behavior
of real packet formats like Sphinx,
where the sender
calculates every layer itself
and can thus recognize them.
can decide
when honest relays
are done processing
an onion and forward it
to the next relay.

While the onion
is being forwarded
through the network,
can also choose
to tag it.
This feature
behaves like the tagging
of a Sphinx packet
(which is explained
in <ref>).
When the onion
is forwarded
by its last honest relay,
it is either discarded
(if it was tagged)
or the message and receiver
are leaked
to .

Reply handling
comes in two variants:
If the last honest relay
is the exit relay
of the onion,
a reply ID $rid$
(an abstraction
of a connection
that could be established
by a protocol
like TCP)
and gives it to .
can use
the $rid$
to provide the exit relay
with a message
for the reply onion.
On the other hand,
if the exit relay
of the onion
is corrupted,
a $tid$
it can use
to send the reply onion
with a reply message
from any corrupted relay
A packet format
cannot prevent
the adversary
from sending messages
using any of the relays
under its control.
Since the channels
between the relays
and receivers
are not secure,
we have to assume that
has complete control
over message and reply delivery.
Honest receivers
can also initiate
sending a reply
to a message
with an $rid$.

§.§.§ Comparison with Repliable Integrated-System OR

While we are able to
reuse large parts
of 's [R]
to build ,
switching to the service model
requires several additions
to the existing [R].

the new tagging feature
marks onions
to be discarded when
they reach their
last honest relay
Since the ideal functionality itself
does not model
adversarial processing,
this is the case
even when
the last honest relay
is not the exit relay.
In that case,
is provided with
the remainder
of the onion's path.
tagging behaves asymmetrically:
when a forward onion
is tagged,
the last honest relay
discards it.
On the reply path,
a tagged onion
is noticed
by the reply receiver.
If the reply receiver is honest,
is not informed
about the tag.

Second, adds handling of
message and reply delivery
on the final link.
Since these links
are not secure,
a real-life adversary
is capable of
manipulating the traffic
on them in many ways.
These include
delivering messages
and $rid$s to the wrong receivers
or exit relays,
swapping $rid$ and message pairs,
exit relays to receivers
and vice versa,
and sending reply onions
from other corrupted relays
if the exit relay
is corrupted.
accounts for
all of these
adversarial behaviors
in its interface
to .

§.§ RSOR Onion Properties

Our properties are based on
the onion properties
originally defined
by or_replies
with appropriate adjustments
for the new algorithms
and functionality.
We detail one property
and sketch
the others here.
For a formal definition
of the other properties
see Appendix <ref>.

§.§.§ RSOR-Correctness

This property requires that
the scheme works as intended
if no adversarial actions
take place.
this means that,
as the onion
is processed using ,
each relay
decrypts the correct
address of the next relay
and the next onion layer
and the final layer
decrypts to the message
chosen by the sender.
The same applies
to the corresponding
reply onion.

§.§.§ Tagging-Forward Layer Unlinkability

the RSOR equivalent
of .
It replaces onion layers
between the honest sender
and the first honest relay
of an onion
with random layers
using that path segment.
The introduction
of tagging
requires us to adjust
this property.
The original definition
of provides the adversary
with the challenge onion $O_1$
or its replacement onion $\bar{O}_1$
as produced
by the sender
and recognizes
the processed layer $O_j$
or $\bar{O}_j$
when the adversary
submits it
to the processing oracle
of the first honest relay.
This recognition
is based on
the onion's header,
so a tagged onion
is still recognized.
In the $b = 0$ case,
the tagged $O_j$
is processed normally
and a tagged $O_{j+1}$
is output to
the adversary.
in the $b = 1$ case,
the tagged $\bar{O}_j$
is recognized
by the oracle
and the original
$O_{j+1}$ is output
without being tagged.
The adversary
can simply finish
the onion's processing
to tell the difference.

To alleviate this issue,
's oracle
recognizes when
the payload
of the challenge onion
has been tagged
and forwards
the tag
by tagging $O_{j+1}$
before sending it.
If the honest relay
is the exit relay,
the oracle outputs nothing
in this case.
Since we assume that
the payload is encrypted
using a PRP,
tagging the onion
simply involves
replacing the payload
with randomness.

[draw, red, minimum height=2cm] (P1) $P_1$;
[draw, left=of P1, minimum height=2cm] (Pr0) ;
[anchor=north] (P0) at (P1.north) ;
[anchor=south] (Pbkm1) at (P1.south) ;

[font=, left=1.7 of Pbkm1] (b) (b);
[font=] (a) at (b.center |- P0.center) (a);

[draw, red, right=0.5 of P1, minimum height=2cm] (Pjm1) $P_{j-1}$;
[draw, right=0.7 of Pjm1, minimum height=2cm] (Pj) $P_j$;

[draw, red, right=0.9 of Pj] (Pjp1) $P_{j+1}$;
[draw, red, right=0.6 of Pjp1] (Pnp1) $P_{n+1}$;
[draw, red, right=0.6 of Pnp1] (Pback) $P\ba_{n\ba\!\!\!-1}$;
[draw, right=0.6 of Pback] (P02) ;

[below=0.2 of Pnp1] (m) $(m, R)$;
[below=0.2 of P02] (mback) $m\ba$;

[->] (Pr0.east |- P0.center) – node[auto] $O_1$ (P1.west |- P0.center);
[->] (Pr0.east |- Pbkm1.center) – node[auto] $\bar{O}_1$ (P1.west |- Pbkm1.center);

[->, dashed] (P1.east |- P0.center) – (Pjm1.west |- P0.center);
[->, dashed] (P1.east |- Pbkm1.center) – (Pjm1.west |- Pbkm1.center);

[->] (Pjm1.east |- P0.center) – node[auto] $O_j$ (Pj.west |- P0.center);
[->] (Pjm1.east |- Pbkm1.center) – node[auto] $\bar{O}_{j}$ (Pj.west |- Pbkm1.center);

[->] (Pj) – node[auto] $O_{j+1}$ (Pjp1);

[->, dashed] (Pjp1) – (Pnp1);
[->, dashed] (Pnp1) – (Pback);
[->] (Pback) – (P02);

[->] (Pnp1) – (m);
[->] (P02) – (mback);

[The Forwards Layer Unlinkability onion property]

The onion property.
The adversary is given
either its chosen onion $O_1$ (a)
or the random onion $\bar{O}_1$ (b)
and must distinguish
the two cases.
Relays marked in
this style
are adversarial,
while those
in the normal style
are honest.
Omitted adversary-chosen paths
are shown with dashed lines.
The secondary output $O_{j+1}$
after $P_j$
is the same
in both cases.

The following full definition
of is derived from
the original version
by or_replies.
Our modifications
are given in
this style.
We also abbreviate
as for the sake of formatting.

Tagging-Forward Layer Unlinkability
is defined as:

* The adversary receives
the router names $P_H$, and challenge public keys $PK_S$, $PK_H$,
chosen by the challenger
by letting $(PK_H, SK_H) \gets G(1^\lambda, p, P_H)$
and $(PK_S, SK_S) \gets G(1^\lambda, p, \Ps)$.

* Oracle access:
The adversary may submit
any number of Proc
and Reply requests
for $P_H$ or to the challenger.
For any $\textbf{Proc}(P_H, O)$,
the challenger checks
whether $\eta$ is
on the $\eta_H$-list.
If it is not on the list,
it sends the output of
$\Proc(SK_H, O, P_H)$,
stores $\eta$
on the $\eta_H$-list
and $O$ on the $O_H$-list.
For any $\textbf{Reply}(P_H, O, m)$,
the challenger checks
if $O$ is on the $O_H$-list
and if so,
the challenger sends ${\ch \Reply}(m, O, P_H, SK_H)$
to the adversary.
(Similar for requests
on with the $\eta_S$-list).

* The adversary submits
a message $m$,
a receiver $R$,
a position $j$ with $1 \leq j \leq {\ch n}$,
a path ${\ch\Pp} = (P_1, \ldots, P_j, \ldots, P_{\ch n})$
with $P_j = P_H$,
a path $\Pp\ba = (P_1\ba, \ldots, P\ba_{\ch n\ba} = \Ps)$
and public keys
for all relays $PK_i$
($1 \leq i \leq {\ch n}$
for the relays on the path
and ${\ch n} < i$
for the other relays).

* The challenger checks
that the chosen paths are acyclic,
the router names
and public keys are valid
and that the same key is chosen
if the router names are equal,
and if so,
sets $PK_j = PK_H$
and $PK\ba_{\ch n\ba} = PK_S$
and picks $b \in {0, 1}$
at random.

* The challenger creates
the onion $O_1$ with
the adversary's input choice
and honestly chosen randomness :

\[{\ch \FormO(1, \Rr, m, R, \Pp, \Pp\ba, PK_{\Pp}, PK_{\Pp\ba})}\]

and a replacement onion $\bar{O}_1$
with the first part
of the forward path ${\ch \bar{\Pp}} = (P_1, \ldots, P_j)$,
a random message $\bar{m} \in M$,
another honestly chosen randomness $\bar{\Rr}$,
an honestly chosen random receiver $\bar{R}$,
and an empty backward path $\bar{\Pp}\ba = ()$:

\[{\ch \FormO(1, \bar{\Rr}, \bar{m}, \bar{R}, \bar{\Pp}, \bar{\Pp}\ba, PK_{\bar{\Pp}}, PK_{\bar{\Pp}\ba})}\]

* If $b = 0$,
the challenger gives
$O_1$ to the adversary.

the challenger gives
$\bar{O}_1$ to the adversary.

* Oracle access:
If $b = 0$
the challenger processes
all oracle requests
as in step 2).

the challenger processes
all requests
as in step 2)
except for:

* If $j < {\ch n}$:

* $\textbf{Proc}(P_H, O)$ with

\[{\ch \RO(j, O, \bar{\Rr}, \bar{m}, \bar{R}, \bar{\Pp}, \bar{\Pp}\ba, PK_{\bar{\Pp}}, PK_{\bar{\Pp}\ba}),}\]

and the expected payload $\delta_j$,
$\eta$ is not
on the $\eta_H$-list
\[\Proc(SK_H, O, P_H) \neq {\ch (\bot, \bot)}\mathpunct{:}\]

The challenger outputs $(P_{j+1}, O_c)$ with

\begin{align*}
O_c \gets {\ch \FormO(}{\ch j + 1, \Rr, m, R,}{\ch \Pp, \Pp\ba, PK_{\Pp}, PK_{\Pp\ba})}
\end{align*}

and adds $\eta$
to the $\eta_H$-list
and $O$
to the $O_H$-list.

* $\textbf{Proc}(P_H, O)$ with

\[{\ch \RO(j, O, \bar{\Rr}, \bar{m}, \bar{R}, \bar{\Pp}, \bar{\Pp}\ba, PK_{\bar{\Pp}}, PK_{\bar{\Pp}\ba})}\]

but the incorrect payload $\delta'$,
$\eta$ is not
on the $\eta_H$-list
\[\Proc(SK_H, O, P_H) \neq {\ch (\bot, \bot)}\mathpunct{:}\]

The challenger outputs $(P_{j+1}, \ch{\tilde{O}_c})$

\begin{align*}
O_c \gets {\ch \FormO(}{\ch j + 1, \Rr, m, R,}{\ch \Pp, \Pp\ba, PK_{\Pp}, PK_{\Pp\ba})}
\end{align*}

and $\tilde{O}_c$
being $O_c$ with a tagged payload
and adds $\eta$
to the $\eta_H$-list
and $O$
to the $O_H$-list.

* If $j = {\ch n}$:

* $\textbf{Proc}(P_H, O)$
\[{\ch \RO(j, O, \bar{\Rr}, \bar{m}, \bar{R}, \bar{\Pp}, \bar{\Pp}\ba\!, PK_{\bar{\Pp}}, PK_{\bar{\Pp}\ba})},\]

$\eta$ is not in the $\eta_H$-list
\[\Proc(SK_H, O, P_H) \neq {\ch (\bot, \bot)}\mathpunct{:}\]

The challenger outputs $(m, {\ch R})$
and adds $\eta$
to the $\eta_H$-list
and $O$
to the $O_H$-list.

* $\textbf{Reply}(P_H, O, m\ba)$
\[{\ch \RO(j, O, \bar{\Rr}, \bar{m}, \bar{R}, \bar{\Pp}, \bar{\Pp}\ba\!, PK_{\bar{\Pp}}, PK_{\bar{\Pp}\ba})}\]

$O$ is on the $O_H$-list
and has not
been replied before
\[{\ch \Reply}(m\ba, O, P_H, SK_H) \neq {\ch (\bot, \bot)}\mathpunct{:}\]

The challenger outputs ${\ch (O_c, P_1\ba)}$

\begin{align*}
O_c \gets {\ch \FormO(}{\ch j + 1, \Rr, m\ba, R,}{\ch \Pp, \Pp\ba, PK_{\Pp}, PK_{\Pp\ba}).}
\end{align*}

* The adversary produces
guess $b'$.

${\ch \TFLU}$ is achieved
if any PPT adversary cannot guess $b' = b$
with a probability
non-negligibly better than $\frac{1}{2}$.

§.§.§ REOR-Backwards Layer Unlinkability

The definition of
the property
is analogous to
the property,
but replaces the challenge onion
on a path segment
of the reply path.
the replacement onion
is a forward onion,
not a reply onion.
This ensures that
a scheme satisfying will have
forward and reply onions
in the OR network.
We do not need to
adapt to account for
the tagging attack
since the reply receiver
processing oracle
never produces output
for onions
with the challenge headers,
so it cannot
produce a wrong
(untagged) output.

[draw, red, minimum height=2cm] (P1) $P\ba_{j\ba\!\!\!+1}$;
[draw, left=of P1, minimum height=2cm] (Pr0) $P\ba_{j\ba}$;
[anchor=north] (P0) at (P1.north) ;
[anchor=south] (Pbkm1) at (P1.south) ;

[font=, left=2.2 of Pbkm1] (b) (b);
[font=] (a) at (b.center |- P0.center) (a);

[draw, red, right=0.4 of P1, minimum height=2cm] (Pjm1) $P\ba_{n\ba\!\!\!-1}$;
[draw, right=1.2 of Pjm1, minimum height=2cm] (Pj) ;

[draw, red, left=0.8 of Pr0] (Pjp1) $P\ba_{j\ba\!\!\!-1}$;
[draw, red, left=0.4 of Pjp1] (Pnp1) $P_{n+1}$;
[draw, red, left=0.4 of Pnp1] (Pback) $P_1$;
[draw, left=0.5 of Pback] (P02) ;

[below=0.2 of Pnp1] (m) $(m, R)$;

[->] (Pr0.east |- P0.center) – node[auto] $O\ba_{j\ba\!\!\!+1}$ (P1.west |- P0.center);
[->] (Pr0.east |- Pbkm1.center) – node[auto] $\bar{O}_1$ (P1.west |- Pbkm1.center);

[->, dashed] (P1.east |- P0.center) – (Pjm1.west |- P0.center);
[->, dashed] (P1.east |- Pbkm1.center) – (Pjm1.west |- Pbkm1.center);

[->] (Pjm1.east |- P0.center) – node[auto] $O\ba_{n\ba}$ (Pj.west |- P0.center);
[->] (Pjm1.east |- Pbkm1.center) – node[auto] $\bar{O}_{n\ba\!\!\!-j\ba}$ (Pj.west |- Pbkm1.center);

[->] (Pjp1) – node[auto] $O\ba_{j\ba}$ (Pr0);

[->] (P02) – node[auto] $O_1$ (Pback);
[->, dashed] (Pback) – (Pnp1);
[->, dashed] (Pnp1) – (Pjp1);

[->] (Pnp1) – (m);

[The RSOR-Backwards Layer Unlinkability onion property]

The onion property.
The adversary is initially given
its chosen onion $O_1$.
The oracle at the relay $P\ba_{j\ba}$
will then return
either its chosen onion $O\ba_{j\ba+1}$ (a)
or the random onion $\bar{O}_1$ (b)
and must distinguish
the two scenarios.
Relays marked in
this style
are adversarial,
while those
in the normal style
are honest.
Omitted adversary-chosen paths
are shown with dashed lines.

§.§.§ REOR-Tail Indistinguishability

The property
is RSOR's counterpart
for the property
in the integrated-system model.
It replaces the challenge onion
with a random onion
using the same path segment
between an honest relay
on the forward path
and a second honest relay
on the reply path.
In ,
we do not allow
the exit relay
to be
the honest relay
since that situation
is already covered
by .

[draw, minimum height=2cm] (Pj) $P_j$;
[anchor=north] (Pjm1) at (Pj.north) ;
[anchor=south] (Pbkm1) at (Pj.south) ;

[font=, left=0.2 of Pbkm1] (b) (b);
[font=] (a) at (b.center |- Pjm1.center) (a);

[draw, red, right=1 of Pj, minimum height=2cm] (Pjp1) $P_{j+1}$;
[draw, red, right=0.7 of Pjp1, minimum height=2cm] (Pnp1) $P_{n+1}$;
[draw, red, right=0.7 of Pnp1, minimum height=2cm] (Pback) $P_{j\ba\!\!\!-1}$;
[draw, right=1 of Pback, minimum height=2cm] (Pjback) $P_{j\ba}$;

[below=0.2 of Pnp1] (m) $(m, R)$;

[->] (Pj.east |- P0.center) – node[auto] $O_{j+1}$ (Pjp1.west |- P0.center);
[->] (Pj.east |- Pbkm1.center) – node[auto] $\bar{O}_{1}$ (Pjp1.west |- Pbkm1.center);

[->, dashed] (Pjp1.east |- P0.center) – (Pnp1.west |- P0.center);
[->, dashed] (Pjp1.east |- Pbkm1.center) – (Pnp1.west |- Pbkm1.center);
[->, dashed] (Pnp1.east |- P0.center) – (Pback.west |- P0.center);
[->, dashed] (Pnp1.east |- Pbkm1.center) – (Pback.west |- Pbkm1.center);
[->, dashed] (Pnp1.east |- P0.center) – (Pback.west |- P0.center);
[->, dashed] (Pnp1.east |- Pbkm1.center) – (Pback.west |- Pbkm1.center);
[->] (Pback.east |- P0.center) – node[auto] $O\ba_{j\ba}$ (Pjback.west |- P0.center);
[->] (Pback.east |- Pbkm1.center) – node[auto] $\bar{O}_{j\ba}$ (Pjback.west |- Pbkm1.center);

[->] (Pnp1) – (m);

[The RSOR-Tail Indistinguishability onion property]

The onion property.
The adversary is given
either its chosen onion $O_{j+1}$ (a)
or the random onion $\bar{O}_{1}$ (b)
and must distinguish
the two cases.
Relays marked in
this style
are adversarial,
while those
in the normal style
are honest.
Omitted adversary-chosen paths
are shown with dashed lines.

§.§.§ Comparison with Integrated-System Properties

Besides the adaptions necessary
for the different representation
of the receiver
and path,
the main difference
between the integrated-system properties
and RSOR properties
is the introduction
of tagging for .
The other two properties
do not require provisions
for tagging mitigation:
remains unaffected
because of
the previously-described
asymmetry of the tagging attack
on the reply path,
while never outputs
a challenge onion
from its oracles.

§.§ Properties imply FRSOR

With the properties defined above,
we can now define
secure RSOR schemes and protocols
as those
that satisfy the properties
and behave
in the way described
in <ref>.

An RSOR scheme
($G$, , , )
that satisfies the four
onion properties
and is a secure RSOR scheme.

A secure RSOR protocol
is based on
a secure RSOR scheme
and behaves as defined
in <ref>.
A full definition
of the protocol behavior
is given in

Appendix <ref>.

A secure RSOR protocol
securely realizes .

The proof of this theorem
is analogous to
's original proof
for integrated-system protocols
and [R]
We provide a brief sketch
of the proof
and the required changes here.
The full proof
is given in

Appendix <ref>.

we construct a simulator that interacts
with the adversary and ,
the adversary's real-world actions
in and vice versa.
After that,
we use
a hybrid proof
to show that
any RSOR protocol
that satisfies
the RSOR properties
is indistinguishable from
our simulator
interacting with .

When interacting
with and ,
must correctly translate
the onions and messages
sent by honest relays
in into
the real world
without complete information
on the contents
or paths
of the onions.
The RSOR properties
ensure that
the simulator can create
replacement onions
with randomized contents
and truncated paths
whenever it needs
to do so
without or noticing the replacement.

§.§.§ Differences to FR

Introducing tagging
requires additional logic
in the simulator.
When the adversary tags
an onion
from an honest sender,
the simulator can tell
that the payload
has been manipulated
and tag the onion
in .
If the onion
is from a corrupted sender,
notices the manipulation
when it processes the onion
at its honest exit relay
and can tag it
in at that point.
This behavior
allows the simulator
to handle tagging attacks

In addition,
now also
needs to handle
communication with
external receivers
involving messages
and reply IDs.
Translating these
between and the real world
involves forwarding
the appropriate communications
while potentially
impersonating exit relays
or receivers.

In performing our
hybrid machine construction,
we fix an error
in 's proof:
They apply the (and ) properties
to path segments
that do not start
at the honest sender
(or end at
the honest reply receiver)
the properties
do not apply
to these situations.
We fix this problem
by applying the property
in these situations
to truncate the paths
of the corresponding onions.
we can apply
the or properties
as before.
The same change
(using )
can be used to
repair the proof
in <cit.>.

§ ANALYZING SPHINX'S SECURITY

We now aim to show that the Sphinx securely realizes
we use our RSOR properties
and show that
Sphinx satisfies each of them.
to be able to do so,
we have to make
two further adjustments
to the Sphinx protocol:
we remove the nymserver,
as it allows
for attacks
(in <ref>).
we rely on
a slightly stronger
cryptographic assumption
for the proof
(in <ref>).

§.§ The Sphinx Packet

A Sphinx packet
consists of
a header
$\eta = (\alpha, \beta, \gamma)$
and a payload $\delta$
(see <ref>
for an overview).
$\alpha$ contains
the shared secret keys
encrypted for each relay,
$\beta$ holds
the routing information
padded by the sender,
and $\gamma$ is a MAC
for $\beta$.

Each relay $P_i$ has
an asymmetric key pair
of the form
$(x_i, y_i := g^{x_i})$
with $x_i \in \mathbb{Z}_q^*$
and $g$ as a generator
of a cyclic group $\mathcal{G}$
with the prime order $q$.
$q$ should be approximately
where $\kappa$ is
the security parameter
The public keys
are used along with
random oracles
in order to encapsulate
the shared secret keys used
for the symmetric cryptographic primitives
in each layer
of the Sphinx packet.
We refer to
this part
of the packet format
as Sphinx's
random oracle-key encapsulation mechanism (RO-KEM).

The RO-KEM's ciphertext
is $\alpha$,
the first component
of the Sphinx packet header
$\alpha$ is formed
using the public keys
of the relays
on the sender's chosen path.
the sender chooses
a secret $x \in \mathbb{Z}_q^*$.
$x$ is the only source
of randomness
in the Sphinx packet.
Using $x$,
the sender generates
the $\alpha$-key encapsulation
for the first onion layer
(which is layer 0):
$\alpha_0 = g^x$.
The sender
then derives
the shared secret
for the first relay:
$s_0 = y_0^x$,
where $y_0$ is the public key
of the first relay
Note that
our indices $i$
for relay names
are relative to
a single packet's path
for clarity.
When the first layer
of the onion reaches
the first relay,
it can derive $s_0$
using its secret key:
$s_0 = \alpha_0^{x_0}$.
The keys and random values
used in the
cryptographic primitives
in the Sphinx packet
are all derived from $s_0$
using the random oracles
and $h_\pi$

In particular,
the random oracle $h_b$
is used to build
the key encapsulations
for the following onion layers:
To calculate $\alpha_1$,
the sender lets
$b_0 = h_b(\alpha_0, s_0)$
and $\alpha_1 = g^{xb_0}$.
The corresponding shared secret
is similarly calculated
as $s_1 = y_1^{xb_0}$,
using the public key
of the second relay
on the onion's path.
The $b_i$ are referred to
as blinding factors.
When the first relay
processes the first onion layer,
it can calculate
$\alpha_1 = \alpha_0^{b_0}$
with the blinding factor
$b_0$ that it gets from
the same random oracle $h_b$.
With this,
the second relay
can derive its shared secret
using its private key.
This process is repeated
for each onion layer.
Note that
only $\alpha_0$
is included in
the final first onion layer —
the later $\alpha_i$
are calculated
by the relays themselves
and replace
the respective $\alpha_{i-1}$
in the packet
during processing

Since we focus
on Sphinx's RO-KEM
in the following sections,
we only give
a short overview
of the remaining
packet structure here.
For a more detailed
and technical description,
see Appendix <ref>.

The other two components
of the Sphinx header
are $\beta$ and $\gamma$.
In each onion layer $i$,
$\gamma_i$ is simply
a MAC $\mu$ of $\beta_i$
keyed with $h_\mu(s_i)$.
$h_\mu$ is
one of the random oracles
keyed with
that layer's shared secret.
$\beta_i$ contains
the address of
the next relay $P_{i+1}$,
the next MAC $\gamma_{i+1}$,
and a prefix
of the next $\beta_{i+1}$
in that order.
This information
is XORed with the output
of a PRG $\rho$
keyed with $h_\rho(s_i)$.
When processing
an onion layer,
the relay $P_i$
creates $\beta_{i+1}$
from $\beta_i$
by appending a string
of zero bits
to $\beta_i$,
XORing the PRG output
onto the result,
and cutting off
the relay address
and MAC
at the start
of the end result.
The construction
of Sphinx's padding scheme
means that
the XORing the zero-bit extension
with the PRG output
results in
exactly the missing suffix
of $\beta_{i+1}$.

the Sphinx packet payload $\delta$
is simply constructed
thorugh multiple layers
of encryption
with a pseudorandom permutation (PRP) $\pi$,
which is keyed with
in the $i$-th layer.
The payload
is constructed by the sender
in reverse order,
layering encryption
from the final onion layer
to the first.
The innermost layer
a zero padding
of length equal
to the security parameter,
the receiver address,
and the message
in that order.
When a relay
processes an onion,
it simply removes
one layer of encryption
from the payload.
The final relay
performs an integrity check
by checking that
the zero padding
at the beginning of the payload
is intact.

§.§ Nymserver

The original Sphinx definition
by sphinx
uses a nymserver
to hold the reply headers
for the onions
in the network.
To create a repliable onion,
the sender first sends
a non-repliable onion
containing the reply header
and a symmetric key
for the payload
to the nymserver
under a pseudonym.
The sender is responsible
for embedding that pseudonym
in the forward onion
for the exit relay
to find.
If the receiver
decides to reply,
it sends its reply message
back to the exit relay.
The exit relay
sends the reply message
and the pseudonym
to the nymserver.
The nymserver
finds the reply header
associated with
the pseudonym
in its database,
encrypts the payload,
attaches it
to the reply header,
and sends the reply onion

This nymserver construction
is insecure in the presence
of an attacker that can
tag or drop onions
and controls the nymserver
or observes its traffic:
A sender that wants to
send a repliable onion
actually sends two onions,
one going to the nymserver.
The attacker tags (or drops)
one of these onions,
hoping that it picked
the nymserver onion.
If it is successful,
the reply header
is not stored
in the nymserver.
When the exit relay
(on behalf of the receiver,
which is trivally linkable
to the exit relay)
sends the message
and pseudonym
to the nymserver,
the attacker can observe
that no onion
is produced
by the nymserver
If the attacker
controls the nymserver itself,
it can simply see
that the requested pseudonym
does not exist.
thus learning the connection
between the sender
and the receiver.

To fix this problem
and create a version of Sphinx
that can be proven secure,
we adapt Sphinx
to include the reply header
and payload symmetric key
in the forward onion payload
Note that
there are other feasible mitigations
for this attack,
sending multiple reply headers
ahead of time
to make
linking the missing reply header
to the original sender
more difficult
for an attacker.
our adaptation
both completely prevents the attack
and simplifies
the Sphinx protocol
while being very simple itself.
We thus consider it
the most appropriate fix
for the problem.
In the original definition
of Sphinx,
a forward payload
has the contents
and a reply payload
has the contents
Messages are always padded
to the full length
of the PRP's message space.
In our adaptation,
forward payloads
are formed as
with $R$
as the receiver address,
$\eta_0$ as the reply header,
and $\tilde{k}$
as the symmetric key.
Non-repliable forward payloads
and reply payloads
zero paddings
and $\text{pad}\ba_{\kappa,N}$
of the appropriate lengths
instead of
and $R\|\eta_0\|\tilde{\kappa}$
This means
a non-repliable forward payload
and a reply payload
This change fixes
the issue
while removing a third party
from the protocol
and simplifying Sphinx.
With this change,
the exit relay
is now responsible for
taking the reply message
from the receiver,
embedding it
in the reply payload,
and sending
the completed reply onion.

§.§ Sphinx Key Encapsulation Mechanism (KEM)

Before we move on
to the RSOR properties,
we discuss the security
of Sphinx's random oracle (RO-)KEM,
which is used
to form the $\alpha$
in each header.
To simplify its analysis
in isolation,
we define the KEM
separately from
the rest of the packet format
and prove that
it satisfies
a modified version
of the IND-CCA property
for KEMs ()
as defined by
The property
we use here
is defined
in Section 7.1.2.
where the challenger
outputs additional information
that we require
in our later onion property proofs.
In those proofs,
we will make use
of our property
in order to
randomize the blinding factors
and symmetric keys
used in the challenge onion.
In this section,
we abbreviate the concatenation
of the three random oracles
and $h_\pi$
as $h_*$
for legibility
since they operate identically
with regards to the KEM.

The is a three-tuple of polynomial-time algorithms
(KeyGen, Encap, Decap)

* Key generation:

\[\textsc{KeyGen}(1^\kappa) := (PK = g^x, SK = x)\]

with $x \gets^R \mathbb{Z}^*_q$
and $g$ as the public generator
of the group $\mathcal{G}$.

* Encapsulation:

\begin{equation*}
\textsc{Encap}(1^\kappa, PK=g^x) := ((h_*(PK^{x'}), h_b(g^{x'}, PK^{x'})), g^{x'})
\end{equation*}

for a random $x' \in \mathbb{Z}^*_q$,
with $h_*$ and $h_b$
being the random oracles
used to key the components
of the Sphinx header.

* Decapsulation:

\begin{equation*}
\textsc{Decap}(1^\kappa, SK=x, \alpha=g^{x'}) := (h_*(\alpha^{SK}), h_b(\alpha, \alpha^{SK})),
\end{equation*}

where $\alpha$ is an encapsulation
produced by Encap

The basic game
as defined by
is unfortunately insufficient
for our later proofs,
where we require information
on the RO outputs used in
other (non-challenge) layers.
We thus define
a modified that outputs all of the information
required to build
a Sphinx packet
while embedding the KEM challenge
at an adversary-chosen index.

* First, the challenger chooses
$(PK, SK) \gets \textsc{KeyGen}(1^\kappa)$
and sends $PK$
to the adversary.

* Oracle access:
The adversary can submit requests
to the decapsulation oracle and the random oracles
$h_*$ and $h_b$.

* The adversary submits

* $n - 1$ public keys
$y_0, \ldots, y_{j-1}, y_{j+1}, \ldots, y_{n-1}$
with $n < N$.
These are the public keys
for the non-honest relays
on the KEM's path,

* and a position $j$ with $0 \leq j < n$.

* The challenger checks
that the $y_i$ are all distinct
and valid public keys.

* The challenger creates
the KEM challenge
for the adversary
by choosing a random
$x' \in \mathbb{Z}^*_q$
and generating
the first $j$ encapsulations
$\alpha_0$ through $\alpha_{j-1}$
and secrets $s_i$
like for a Sphinx header:
$\alpha_i \gets g^{x'b_0\cdots b_{i-1}}$,
$s_i \gets y_i^{x'b_0\cdots b_{i-1}}$,
$b_i \gets h_b(\alpha_i, s_i)$.

* The challenger sends
the adversary its auxiliary information
Note that this is
all of the information
required to build any layer
of the Sphinx packet
preceding the
challenge layer $j$.

* The first encapulation $\alpha_0$,

* the $h_*$ outputs
$h_*(s_0)$, …, $h_*(s_{j-1})$,

* and the blinding factors
$b_0$, …, $b_{j-1}$.

* The challenger provides
the adversary with
the KEM challenge:
It picks $b \in \{0,1\}$
at random.
If $b = 0$,
the challenger lets
$b_j = h_b(\alpha_j, s_j)$
and gives the adversary
$(\alpha_j, h_*(s_j), b_j)$.
the adversary gets
$(\alpha_j, r_1, b_j)$
for $r_1 \gets^R \{0,1\}^{3\kappa}$
and $b_j \gets^R \mathbb{Z}^*_q$.
the challenger generates
the rest of the KEM layers
$\alpha_{j+1}$, …, $\alpha_n$
with $s_{j+1}$, …, $s_n$
and $b_{j+1}$, …, $b_n$
the same way as the previous layers
(using the corresponding $b_j$)
and gives the adversary
$h_*(s_{j+1})$, …, $h_*(s_n)$
and $b_{j+1}$, …, $b_n$.

* Oracle access:
The adversary gets access
to the same ,
$h_*$, and $h_b$ oracles.

* The adversary submits
its guess $b'$
to the challenger.

is achieved
if any PPT adversary cannot guess $b' = b$
with a probability
non-negligibly better
than $\frac{1}{2}$.

§.§.§ Security

In order to show
that the satisfies our security property,
we can perform
a reduction proof
to a Diffie-Hellman assumption.
The original Sphinx definition
uses the DDH assumption
for the in order to show
that the blinding factors
and symmetric keys
are indistinguishable
from randomness
for the adversary
a more detailed analysis
reveals that
the DDH assumption
is insufficient
to prove the secure:
In a reduction
from to the DDH assumption,
the DDH attacker must
simulate both
the decapsulation oracle as well as the random oracles
$h_*$ and $h_b$
for the attacker.
Doing so correctly
for adversary-chosen inputs
involves identifying
which encapsulations $\alpha$
and secrets $s$
belong together.
Since being able
to do so efficiently
would already break DDH,
the redution
is not possible
in this form.
We use
the Gap Diffie-Hellman assumption instead.
It states that
the CDH problem is hard
even given an oracle
that solves the DDH problem.
It is generally assumed
that the GDH assumption
holds in the standard elliptic curve groups,
which Sphinx already uses
For our reduction,
this means
that we are reducing
to the CDH problem,
but our CDH attacker
additionally receives
a DDH oracle [G].
Using [G],
the CDH attacker
can correctly identify
matching secrets
and encapsulations.
It follows that:

The satisfies under the GDH assumption.

We use a attacker on the to construct
a GDH attacker $\Bb^{\Oo[G]}$
with the DDH oracle
uses its CDH challenge
$(g, g^{x_1}, g^{x_2})$
as a public key $PK = g^{x_1}$
and a challenge $\alpha = g^{x_2}$.
After getting
the challenge index $j$
and the other public keys
from ,
$\alpha_j = \alpha$
and constructs
the rest of the KEM's path
by choosing
random blinding factors $b_i$
and $h_*$ outputs
for every layer,
programming its choices
into the ROs.
also randomly chooses
a bit $b \in \{0,1\}$
to determine which scenario
it simulates.
The only difference
between the two
is whether
the random oracle outputs
on layer $j$
are programmed
into the ROs.
then simulates
the oracles,
keeping the outputs consistent
using its DDH oracle [G].
In order for to tell the scenarios apart,
it must request
$h_*$ or $h_b$
with $g^{x_1x_2}$,
allowing to win the GDH game.
For the full proof see Appendix <ref>.

§.§ Sphinx Security Analysis

In order to prove
that Sphinx
securely realizes ,
we show
that it satisfies
our new properties.
For the sake of brevity,
we only sketch
the proof for here
along with short proof outlines
for and .

Extended explanations
of the proofs
are given in
Appendix <ref>
and Appendix <ref>.
The full proofs for and can be found in

The full proofs for
all three properties
can be found in
Appendix <ref>,
Appendix <ref>
and Appendix <ref>.

RSOR-Correctness follows
from inspection
of the Sphinx scheme.

Sphinx satisfies under the GDH assumption.

To show that Sphinx
satisfies ,
we prove that an adversary
cannot distinguish
the $b = 0$ scenario
of the game
from the $b = 1$ scenario
through a hybrid argument
starting at $b=0$
and ending at $b=1$.
We gradually move
from the $b=0$ scenario
to the $b=1$ scenario
by constructing one hybrid
after another.
The first hybrid game
is simply the $b=0$ scenario.
Each hybrid changes
the challenge onion
or the challenger's behavior
in an indistinguishable way
until the final hybrid
is identical to
the $b=1$ scenario.
We summarize
the hybrids' construction here,
see Appendix <ref>
for details.
For clarity,
we also separate the proof
into two cases:
One where $j = n$
and the other
where $j < n$.
In the game,
$j$ determines
the index of the honest relay
on the challenge onion's path.

Case 1 $(j = n)$:
In this case,
the honest relay
on the forward path
is also
the exit relay
of the onion
and thus also
the sender of the reply onion.
This case demands
that the entire forward onion
is replaced with an onion
using the same forward path,
but containing
a random message
and receiver
as well as
having an empty reply path.

To perform this replacement,
we take advantage
of the innermost layer
of the PRP protecting
the payload's contents:
Since the adversary
cannot tell
what the contents
of the payload are,
we can replace
the message,
and reply header
with a random message,
a random receiver,
and padding (i.e., an empty reply path)

The original reply header
is still used
to form the actual reply onion
at the honest exit relay.
We use the PRP's security
and the implicit integrity check
in the forward payload
(via the zero padding)
to show that
the adversary
does not notice this change
and cannot manipulate
the payload
in order to
to affect the reply header.
With this,
the forward onion
given to the adversary
is completely independent
of the challenge onion
and contains
a random message,
a random receiver,
and an empty reply path.
The reply header of
the challenge onion
is still used
on the reply path.
This is identical
to the $b=1$ scenario.

Case 2 $(j < n)$:
we consider the case
where the honest relay
on the forward path
is not the exit relay.
This case
is more complex
since the forward path
of our replacement onion
is not the same
as the forward path
of the challenge onion.
Our hybrids thus need to
truncate the forward path
of the challenge onion
at the honest relay
in order to move
to the $b=1$ scenario.
In addition,
our hybrids must also handle
a potential tagging attack
by the adversary correctly.
Proceed as follows:

* First,
we need to handle
tagging attacks.
If the adversary tags
the challenge onion
in the $b=0$ scenario,
the payload will be mangled
by the PRP decryption step
in the honest relay's processing.
The key aspect
of this mangling
is that the PRP's output
in that case
is indistinguishable from
a random bitstring
of the same length.
We take advantage
of this fact
in the first hybrids:
Instead of processing
the challenge payload normally
at the honest relay,
the hybrid checks
whether the payload has been modified.
If not,
the next layer
of the challenge onion
with the correct
next payload layer
is output.
If the payload
has been modified (i.e., tagged),
then the payload output
is replaced with
a random bitstring.
This change reduces to
the PRP's security
at the honest relay
and the reply receiver.

With the new payload handling,
we have effectively decoupled
the onion layers
before and after
the honest relay:
Any adversary modification
to the layers
before the honest relay
either results
in a failure in processing
(due to the MAC
if the header is modified)
or in the payload
being replaced
with randomness
(if the payload is modified).
We can thus change
the contents
of both the header and payload layers
before the honest relay
and replace the changed onion
with the original challenge onion
at the honest relay oracle
without the adversary
being able to
sneak information
through the honest relay.
The contents
of the payload layers
before the honest relay
are replaced with
a random message,
a random receiver,
and an empty reply path
like in the $j = n$ case.

* Next,
we detach
the layers of the challenge onion's header
before the honest relay
(which we will refer to as $A$)
from the layers
after it
(referred to as $B$).

As a first step,
the final layer of $A$
is no longer processed
at the honest relay.
The first layer of $B$
is always output
as the next layer's header
We detach
$A$ from $B$
in multiple steps:
replace the innermost contents
of $A$'s header layers
with the contents
of a final Sphinx header layer
such that
the $A$ layers
are now formed
as if the onion's path
ended at the honest relay.
We can do so
since the PRG
protects that header information
until the honest relay.
the KEM keys
used to build $B$
are replaced with
a new instance
of the KEM
that starts at
the honest relay.
We use the randomness
of the blinding factor
multiplied onto the exponent
at the honest relay
to secure this step.
the padding in $B$,
which still contains
$A$'s padding,
is changed:
The bits corresponding to
$A$'s padding
are replaced with random bits
in the last header layer
of $B$.
This is possible
due to Sphinx's padding construction
and the PRG's security.
After these steps,
the $A$ header layers
are completely independent
of the $B$ header layers.

* In a last step,
we adjust $B$'s padding
and KEM construction
so that the $B$ layers
are built like part
of the complete challenge onion again.
$A$ is an independent forward onion
with a truncated path,
an empty reply path,
and a random message
and receiver,
while $B$
is built like
the original challenge onion.
This corresponds to
the $b=1$ scenario
of .

The proof works
similarly to the proof.
the part
of the challenge reply onion
after the honest relay
is detached
from the first part.
the second part's header and payload contents
are adapted into
those of a forward onion.

For the proof,
we have to truncate
the forward and reply paths
of the challenge onion
to move from one scenario
to the other.
Truncating the forward path
is like performing
hybrid [_9]
from the proof
and adjusting the padding accordingly.
Truncating the reply path
is analogous to hybrid [_7].

Given that Sphinx
each of the RSOR properties,
it follows that

Nymserverless Sphinx securely realizes under the GDH assumption.

§ DISCUSSION

In this section we argue
that the relaxation
used in our
ideal functionality
is acceptable in practice
under certain conditions. We further give
detailed advice on
when we consider
the usage of Sphinx

§.§ Relaxed Security Requirements of FRSOR

We stress that
still prevents
all tagging attacks
except for the malleability attack
on the payload.
if an adversary
is able to
link layers
of an honest sender's onion
that do not involve the exit relay,
both and our properties
are not achieved.

However, we
also emphasize that
the reduction in security
due to allowing
the malleability attack
can be critical
and RSOR protocols
should only be used
under the following conditions:

the exit relay choice
must not leak critical information.
the exit relay
cannot depend on
the receiver
This might be considered
in order to
have an exit relay
that is
topologically close
to the receiver.
or the included message.
However, if
(as in many protocols)
the exit relays are chosen
uniformly at random
or randomly according to
their capacities,
linking the sender
to the exit relay
does not provide the adversary
with useful new information.

Second, senders must not
react to receiving
tagged payloads
in a way
that an adversary
can distinguish
from the reception
of a well-formed,
correct payload.
the payload tagging attack
becomes a threat
once again:
A corrupted exit relay
could tag
a reply payload
and observe
that one sender
reacts differently
to receiving
a reply onion
and link a sender-receiver pair.
In particular,
if a packet format is used
as part of
a larger protocol,
an honest sender
receiving a reply message
must not trigger
any output
to the adversary.

one must not use
sessions visible to
the exit relay.
This includes techniques
that allow the linking
of multiple onions
for the same sender-receiver pair
to each other.
one packet from the sender
can be tagged
while the other packets
are not.
This allows for
conclusions about
the receiver
and content
of the tagged onion
via the onions
which are linked
to the tagged one
because of the session.

§.§ Using Sphinx in a Network

We want to give
practical advice
on the cases in which
we consider
the usage of Sphinx
in its intended RSOR model
a secure choice.
First of all,
Sphinx should only be used
with the changes
we apply
in this paper.
one must include
the fix for path padding
(random bits instead of zero bits)
and the Sphinx reply header
has to be included
in the forward payload
to avoid attacks
based on the nymserver.

it is important
to ensure that
all of the conditions
mentioned for security
in <ref>
are met.
This means that the exit relay
is chosen randomly,
independently of the communication parties
and contents,
senders' reactions
to well-formed replies
and tagged replies
are indistinguishable,
and multiple onions
between the same communication parties
cannot be linked
to each other
at the relays.

§ CONCLUSION

With this paper,
we provide
the privacy formalization
for repliable service-model OR protocols
with our ideal functionality and the four new onion properties
Tagging-Forward Layer Unlinkability,
RSOR-Backwards Layer Unlinkability,
and RSOR-Tail Indistinguishability.
We prove that
these properties
imply together.
Our formalization
pays close attention
to consider all
the new edge cases
of the service model
and to relax
the security
in an acceptable way
to allow for
payload malleability.

For Sphinx,
we correct
the cryptographic group assumption
for the Sphinx scheme
from DDH to GDH.
we realize that
a security proof
is not possible
in the presence of
the nymserver.
We propose to
include the reply header
in the forward payload instead.
With our formal groundwork,
we are then able to
prove this adapted version
of Sphinx
secure according to .
To our knowledge,
we are the first
to provide a security proof
for Sphinx
at our level of detail.
We thereby ensure
that the OR and mix networks
that base their protocols
on the Sphinx packet format
can rely on
a thoroughly-analyzed
foundation again.

Of course,
there is still progress
in OR,
mix networks,
and packet formats
to be expected
in future works.
Authors of new OR
and mix network protocols
benefit from our investigation
of the criteria
for using Sphinx
in a secure way
to decide whether or not
to base their protocols
on Sphinx.
In addition,
future works
on OR and mix network packet formats
profit from
our formalization
in the service model,
especially by using
our new onion properties
to build their algorithms
and prove their privacy.

We thank Dennis Hofheinz
for pointing us
towards the GDH assumption.

get arXiv to do 4 passes: Label(s) may have changed. Rerun