International Association
for Cryptologic Research

To provide users with anonymous access to the Internet, onion routing and mix networks were developed. Assuming a stronger adversary than Tor, Sphinx is a popular packet format choice for such networks due to its efficiency and strong protection. However, it was recently shown that Sphinx is susceptible to a tagging attack on the payload in some settings. The only known packet formats which prevent this attack rely on advanced cryptographic primitives and are highly inefficient, both in terms of packet sizes and computation overhead.

In this paper, we provide the first packet format that protects against the tagging attack with an acceptable overhead. At the cost of doubling the payload size, we are able to build a provably private solution from basic cryptographic primitives. Our implementation demonstrates that our solution is as computationally efficient as Sphinx, beating previous schemes by a large margin. For our security proof, we first strengthen the state-of-the-art proof strategy, before applying it to our solution to demonstrate that not only the tagging attack is prevented, but our scheme is provably private.