Sphinx: The anonymous data format behind Lightning and Nym

---

Sphinx is an anonymous cryptographic packet format without precedent, and it powers both the Lightning Network and Nym. This is how it works its magic.

On 12 January 2009, Satoshi Nakamoto sent famed cypherpunk Hal Finney 10 BTC in the world’s first bitcoin transaction. Eleven years later, the Nym mixnet made its first anonymous transaction, shipping Sphinx packets between mix-nodes run by volunteers from Chaos Computer Club, Blockstream, Electric Coin Company, and elsewhere.

In memoriam to Hal Finney (1956–2014)

A functional mixnet that can provide stronger network-level privacy than Tor has long been the dream of privacy advocates, researchers and cypherpunks. Mixnets pre-date Tor, and their most effective deployment so far has been Mixminion, a ‘type-3’ remailer used to anonymously send email. Since mixnet development stalled — with two of Mixminion’s primary developers, Nick Mathewson and Roger Dingledine, moving on to build Tor — there has been little open-source work since 2003, and no commits since 2011.

Thanks to an effort that began with PANORAMIX and continues with Nym, mixnets are back.

As detailed in our previous post, Nym’s mixnet is composed of mix-nodes that pass packets to each other. The nodes add timing delays to obfuscate the timing metadata of transactions, and produce dummy traffic when there’s not enough real traffic. So the Nym mixnet provides superior privacy for message-based traffic than Tor or VPNs (including dVPNs).

The real secret sauce of mixnets is the Sphinx packet format used by both Nym and the Lightning Network. Sphinx is tricky to understand and not used by the Lightning Network in a way that guarantees anonymity. So let’s do a deep-dive into Sphinx and answer its riddles!

What is Sphinx?

Sphinx¹ anonymously routes a message from sender to receiver. It provides several properties needed for sender anonymity in multi-hop systems:

1. Bitwise unlinkability: Any packet coming into a mix cannot be correlated to any outgoing packet based on its binary representation by an adversary observing the network. In other words, the packets are anonymous.
2. Integrity: Resistance to active attacks like tagging and replay attacks, where the adversary modifies and re-injects messages to extract information about their destinations or content.
3. Hiding routing information: No mix-node can tell the number of hops a packet has travelled so far, or the length of the path of a message. Only predecessor and successor mix-nodes are known to a given mix-node.

With Sphinx, anonymous reply packets can offer receiver anonymity with Single-Use Reply Blocks (SURBs) that are indistinguishable from the Sphinx messages sent forward in the network.

Sphinx in a Nutshell

A Sphinx packet is composed of two independent parts:

1. A header encapsulating all information needed to route the message from source to destination; and
2. A payload within which the actual message content is hidden.

Consider a world where Nakamoto wants to anonymously send a message to Hal Finney via a mix-network, where the nodes are represented by their IP addresses and public keys. Nakamoto needs to distribute keys so that each mix-node in the route can decode the necessary routing information to forward an encrypted packet and still keep the rest of the route hidden.

The structure of Sphinx

First, Nakamoto chooses a route, looking up the public key of each mix-node and computing a shared key for each. The ‘key’ component of the Sphinx header is a single group element ɑ which, when combined with the nodes’ public keys, allows computing a shared key for each via Diffie-Hellman key exchange, and so the first node in the user-chosen route can forward the packet to the next, and only that mix-node can decrypt it.

This ephemeral shared key s allows a node to process the packet by deriving the keys needed to ensure the packet header was not modified by checking the integrity tag ɣ in the header, and decrypt the encrypted routing information β, which carries a set of instructions from the sender to the designated mix-node about what the mix-node should forward, and where.

The group element ɑ is cryptographically blinded at each mixing step in order to prevent packet correlation per user. The blinding factor b is extracted from the shared key s, and thus both the sender and a respective mix can perform all operations necessary to forward packets. The payload δ in the Sphinx packet is computed using a wide-block cipher to ensure that, if an adversary modifies the payload at any point, the message content is irrecoverably lost. The integrity tag ɣ encoded in the header allows checks only on whether the packet header was not also modified. All packets need to be padded to the same length at each hop.

Ensuring the header preserves constant length is more complicated. Sphinx uses a sophisticated padding technique to ensure constant packet size introduces a minimal overhead.

Creating a Sphinx Packet

To route the message m via a selected path of mixes M₀, M₁, M₂, Nakamoto generates a fresh secret value x and pre-computes all group elements ɑ, shared keys s and blinding factors b using x and the mix-nodes’ public keys. He starts the header encoding by layer-encapsulating routing information like the IP address with the header integrity tag for each mix-node in the route, from last to first.

The innermost layer is constructed as a concatenation of Finney’s address ∆, an identifier I used for SURBs, and sequence of padding, which ensures the path length is not accidentally revealed. These are then encrypted by XORing with the output of a pseudo-random number generator seeded with shared key _s_₂. The result is finally merged with a filler string ɸ, the addition of which ensures the header packets remain constant in size as layers of encryption are added or removed. Once the final encrypted routing information β₂ is ready, Nakamoto computes its HMAC as the integrity tag ɣ₂ = HMAC(_s_₂, β₂) and encrypts this routing information β concatenated with integrity check ɣ. The process starts again with β₁, then to the next β recursively, as shown below:

Constructing a Sphinx packet: The darker the grey, the more encryption!

Nakamoto then reuses the computed shared keys to layer-encrypt the payload. Just as in the header, the payload encapsulation is performed in reverse order of the route through the mix-nodes. The initial δ_₂_ is created using the wide block cipher, using key s₂, of the concatenation of the message m, Finney’s address ∆, and a sequence of zero-byte padding, which allows verification that the body was not modified in transit — if a single bit is modified by an attacker, the wide-block cipher will decrypt the payload to random bits.

Finney still needs to be able to distinguish whether it is a valid message or a random cipher text using the additional known-sequence zero-byte padding. Once δ_₂_ is ready, Nakamoto again encrypts it using s₁ and s₀, one by one.

Processing a Sphinx Packet

1. Upon receiving a packet, the mix-node extracts the group element ɑ from the header and combines it with its own secret key in order to derive the shared key s.
2. Using s, the mix computes the keyed-hash of the encrypted routing information as HMAC(s, β) and compares with the integrity tag ɣ attached in the packet header. If the integrity check fails because the header has been tampered with, the packet is dropped. Otherwise, the mix-node proceeds to step 3.
3. The mix-node is now ready to decrypt the attached β. In order to extract the routing instructions, the mix-node first appends a zero-byte padding at the end of β and decrypts the padded block of routing information B by XORing it with a pseudo-random stream of bytes generated using s. The amount of zero-byte padding appended to β is equal to the length of the routing instructions the mix-node needs to extract in order to preserve length-invariance. Note that since the padding is hashed within integrity tag ɣ, it must be identical to the padding pre-generated by Nakamoto.
4. The mix-node parses the routing instructions from B in order to obtain the address of the next mix-node (or in the case of the final hop, destination address ∆ and identifier I), as well the new integrity tag ɣ’ and β’, which should be forwarded to the next hop.
5. The mix-node also performs wide-block cipher decryption of δ resulting in δ’, which will be forwarded to the next hop.
6. The mix-node blinds the received ɑ using a blinding factor derived from the shared key s to obtain a fresh group element ɑ’.

Once both header and payload are encrypted, and the group element is blinded, the mix-node can assemble a new packet as ((ɑ’, β’, ɣ’), δ’) and forward it to the next address.

Original illustration of the Sphinx packet format, from Danezis and Goldberg (2014)

How Nym defeats attacks on Sphinx

One of Sphinx’s best aspects is that it’s provably secure — the original paper offers a security proof of the properties it assumes. In general, we want security proofs, which cryptographers typically do by hand to show a design actually has a set of properties that can be logically proven from a set of mathematical assumptions. It’s much harder to prove privacy properties, which typically involve simulation.

When cryptographers make security proofs by hand, they can make mistakes or simply overlook aspects of what they want to prove. The work by Kuhn et al.,² shows that since the formal properties defined for onion-routing based systems by Camenisch and Lysyanskaya³ are insufficient, a significant flaw in the Sphinx packet’s original design was not detected in the security proof presented by Danezis and Goldberg. If this flaw is not corrected, it might significantly harm the privacy of the users in systems using Sphinx.

The original Sphinx design proposed using a zero-byte padding, but with only a sequence of zeros, as the padding allows the last mix-node in the path to infer information about the length of the path, hence breaking one of the security properties promised by Sphinx, and possibly inferring significant information about the route or even a final destination.

As described earlier, the last mix-node in the route receives the innermost layer of encrypted routing information β, generated as the encryption of the receiver address (∆), an identifier (I), and a zero-byte padding, and combined with the filler string ɸ.

Following the notation used in the Sphinx paper, the innermost β is created as

where |ɸ| = 2(v-1)κ, and κ, r are respectively a security parameter and maximum path length, while v is the length of the path traversed by the packet. The processing of received β by the mix-node is performed as

So, how does the last mix-node infer any information about the path length from this magical math?

To explain how this attack works, we present a simple example. First, recall that given value x = a⊕b, both x, and a and b have the same length, and if we further XOR x with b we receive x⊕b = a⊕b⊕b = a. For our example, let’s assume that the output of PRNG with the shared key of node v-1 as input is 10101010101010101010….

Let’s now consider the following value of β received by last mix

Now, following (2), we perform the same operations as the exit mixnode would perform to decrypt and parse β

By design, the last mix-node in the path knows the total length of the expected β (in our example it was 9 bits), and that the concatenation of destination address (∆) and the identifier (I) is followed respectively by the zero-padding, and the pseudo-random bits of filler string. Given the knowledge about the exact lengths ∆ and I, the honest-but-curious last mix-node looks where the first bit 1 is after the identifier, since it knows that the filler string starts there or earlier. The observation where the first 1 bit after the identifier is allows the last mix to determine a lower bound on the length of the filler string. Since the total length of ɸ is defined by design as twice the route length multiplied by security parameter κ , the lower bound on the length of the filler string leaks the information about a lower bound on the length of the path used.

Why knowing the length of the path is harmful

As research has shown,⁴ in networks which use restricted or sparse topologies (Lightning, for example), knowledge of the path length decreases the anonymity set under which a sender can hide. The example in the figure below shows how the knowledge of the lower bound of the path length can decrease sender anonymity. If D acts as an exit mix-node and forwards a packet to Timmy, without knowing the length of the path any of the nodes A, B, C, E, G, F can be the sender. However, if D can infer that the path length is at least 3, then by looking at the network graph we infer that only either A or B can be the sender, hence the set of potential senders is significantly decreased.

It is quite simple to prevent this attack. In (1) when we create β instead of using zero-padding, we just need to use random-bits padding. Actually, the Python implementation by George Danezis already recognizes this flaw.

Fig. 1

But this attack does not impact Nym

1. Nym uses a stratified topology in order to maximize anonymity, so all paths are equal length and each mix-node knows its position in the path. This is not the case with Lightning. It uses variable length paths so its original implementation of Sphinx was vulnerable to this attack, although it has now been fixed.
2. The last layer of Sphinx encoding is removed by the application itself, not the exit mix (like in Tor). However, Nym’s Sphinx implementation in Rust is resistant to this attack (it uses randomized padding) and so can be safely reused by any Sphinx-based design.

What’s next for Nym?

Nym’s first anonymous Sphinx packet won’t be our last. The Nym network will gradually evolve into a stable, general-purpose mixnet for any internet application. Our testnet is already up and running and should be in production by the end of 2020.

But who needs network-level privacy anyway? Almost everyone, as it turns out.

The Lightning Network already uses Sphinx packets, just in a manner that violates its ability to give transactions privacy, as Claudia Diaz demonstrated at the Lightning Conference in November 2019. With some changes, Lightning could be made privacy-enhanced, as it already shares lots of infrastructure such as Sphinx with Nym. The combination of Nym and Lightning might be the most viable path for making Bitcoin private.

(iframe src="https://www.youtube.com/embed/g55kMhggIBY?feature=oembed" width="700" height="393")(/iframe)

Claudia Diaz presenting on why Sphinx isn’t help Lightning’s privacy — and how it can be fixed

Privacy-enhanced cryptocurrencies and side-chains of any cryptocurrency should also use network-level anonymity, or attacks can use timing data to deanonymize packets and even lead to attacks on on-chain privacy techniques like zkSNARKS. We’re doing outreach to a number of communities, and we’ll have more to say soon.

And let’s not forget the interest in decentralized VPNs by Brave and others. How fast can Sphinx packets go? Sphinx uses a lot of asymmetric cryptography and exotic wide-block ciphers to achieve unlinkability, but it could perhaps also be redesigned to achieve the speeds that will make these kinds of use-cases a reality.

Sphinx gives ordinary internet packets the power of anonymity — but with great power comes great responsibility. We look forward to seeing what new kinds of services and applications take hold of this responsibility and build on top of Nym!

---

References

¹ George Danezis and Ian Goldberg. Sphinx: A compact and provably secure mix format. In IEEE Symposium on Security and Privacy, pp 269–282. IEEE, 2009.

² Christiane Kuhn, Martin Beck, and Thorsten Strufe. Breaking and (partially) fixing provably secure onion routing. arXiv preprint arXiv:1910.13772, 2019.

³ Jan Camenisch and Anna Lysyanskaya. A formal treatment of onion routing. In Annual International Cryptology Conference, pp 169–187. Springer, 2005.

⁴ George Danezis. Mix-networks with restricted routes. In International Workshop on Privacy Enhancing Technologies, pp 1–17. Springer, 2003.