Anonymous publishing with Riffle

Preserving anonymity online is an understandably hot topic these days. But it can be confused with related concepts like privacy and secure communication. A new protocol called Riffle was recently published [PDF] by researchers at MIT; it offers a different take on anonymity than that implemented by other projects. A Riffle network could be used to implement an anonymous but verifiable blogging or publishing platform: one in which the messages are visible to everyone, but the identity of all users remains hidden.

For comparison, the most well-known anonymity project is, no doubt, Tor, which enables users to access Internet services without revealing their physical location on the network. It is possible to use Tor to access publishing services like Twitter and, thus, to broadcast content to the Internet at large without revealing one's identity. But Tor is just as useful at solving other problems, such as accessing remote servers that are blocked by a firewall. While important, that usage of Tor does not necessarily involve anonymity; one could, for instance, use it to log in to Facebook, and Tor alone does not prevent the use of web trackers by sites.

Furthermore, Tor is the focus of near-constant attacks (against the network itself and against the algorithms that keep it working), and it may be vulnerable to large-scale traffic analysis—such as a national ISP could perform. One of the stated goals of Riffle is to prevent such traffic analysis, which has led to popular reports and online discussions referring to Riffle as a Tor competitor.

But Riffle, in fact, tackles a narrower problem set. In a Riffle network, every message sent or file uploaded is eventually published in plaintext form where everyone can see it. The Riffle protocol offers strong guarantees that the identity of the message's uploader cannot be discovered—even in cases where multiple servers in the network have been compromised.

Background

The system builds on two existing ideas: verifiable shuffles [PDF] and dining cryptographer networks (DC-nets). Verifiable shuffles enable a server to reorder a set of incoming messages before sending them back out in a seemingly random sequence, while allowing the participants to verify that all of the output messages correspond to the inputs. In particular, participants can verify that all of their messages were delivered and that no phony messages were inserted.

Such shuffle algorithms generate a reordered sequence of messages as well as a proof that can be used to verify the validity of the shuffling step, but that cannot be used to reverse-engineer the permutation used. They can also be employed by pools of servers in so-called "mixnets." That makes network traffic difficult to analyze in the hopes of discovering who sent any particular message (thus guarding against Tor's weakness), but it comes at an inconveniently high computational cost.

DC-nets provide strong anonymity by having each node in the network transmit a message that is cryptographically mixed with the message of a neighbor node, which is then mixed with the message of that node's neighbor, and so forth. The pairwise mixing of messages also makes it impossible for cheaters to crack the encryption unless they control every node. But DC-nets require every node to send traffic in every round, and they do not scale well because the message channel is broadcast-only: all messages are passed around to all participants, making poor use of the available bandwidth. With more than a few dozen participants, throughput slows to a crawl.

The Dissent system was able to overcome some of traditional DC-nets' limitations by splitting the nodes into server and client classes. The servers (presumably higher-end hardware) can take care of the verifiable shuffle without imposing that computational burden on the clients. Dissent also altered the trust model versus traditional DC-nets (in which every node participated in the message-passing step), letting the servers shoulder much of that burden as well. The authors demonstrated that, as long as at least one server remains uncompromised, clients could trust the entire Dissent server pool. Nevertheless, the authors of the Riffle paper said, Dissent still slows down proportionally as more users join the network.

Riffle

Riffle is, in many respects, an iteration on Dissent designed to overcome that system's bandwidth-sharing problem. Like Dissent, Riffle has servers and clients. But clients each consume only bandwidth proportional to their own message size. Furthermore, the computational load on the servers is reduced, with the intensive verifiable-shuffle calculations only performed on periodic occasions (such as when the set of available servers changes).

The bandwidth reduction is accomplished by using different upload and download mechanisms. When a client sends a message, it is placed into the network's verifiable-shuffle system. When a client downloads messages, it uses a separate private information retrieval (PIR) protocol.

In the setup phase, each server first generates a public key pair and publishes the public key to all of the clients. The servers in the server pool also generate a set of permutations they will use for the verifiable shuffle and exchange proofs with the other servers. Once setup is complete, however, the servers continue to use this fixed shuffle, alleviating the need to compute a new shuffle for every round of messages, as was done in traditional verifiable-shuffle mixnets.

In the communication phase, each client onion-encrypts its outgoing message—meaning that the message is encrypted, in turn, with the public key of each server. But each client opens a channel to just one server and sends it the onion-encrypted message, breaking it into fixed-size chunks to better obscure message size.

Next, each server decrypts the message chunks it has received using its private key, then shuffles the chunks and relays them to the next server. ElGamal keys are used for the onion-encryption stage because they are commutative; the servers in the pool can each decrypt the message they see using their own key, and the order of the original encryption does not affect the output. Once the messages reach the last server in the pool, they have been decrypted by every private key and are now plaintext.

Finally, the clients download the messages they want using PIR. In this scheme, the server pool publishes an index of the chunks available at each server, and the clients request a random set of indexes that includes the messages it is interested in. That way, each client can only use as much bandwidth as it desires; if some other client has uploaded a large document, other clients are not obligated to download it. The authors of the paper note, however, that the PIR step is not critical to the rest of the system; if a shared message channel is preferable, users could simply run Riffle in a broadcast manner instead.

The computational savings occur because Riffle does the setup phase only once per "epoch," which entails the verifiable-shuffle computations by the servers, and uses less expensive TLS channels to exchange all other content. What constitutes an epoch is not strictly defined; whenever a new server leaves or joins the pool, the server will have to re-do the verifiable-shuffle setup, but the network could be configured to periodically start a new epoch for added security.

The paper goes on to demonstrate that Riffle is resistant to the same attacks that verifiable-shuffle mixnets and older DC-nets protect against. The real question is whether or not the new system results in a scheme that can scale better to large networks. The authors cite tests showing that Riffle can achieve an average bandwidth of 100KBps for a network of 200 clients when tuned for file-sharing usage. Tuning for speed instead, as one might do for a Twitter-style microblogging network, the authors claim to support a network of 10,000 clients with a message latency of less than one second.

The Riffle paper's main author, Albert Kwon, has released a prototype implementation on GitHub, which he called "performance accurate (but probably not security accurate)". The repository includes client and server code, both written in Go, but it, regrettably, does not have any license attached.

There are clearly plenty of interesting ideas to be found in Riffle, although at this point it is hard to say whether or not the paper or its concepts will have a practical impact on projects like Tor. One subscriber did post links to the Riffle paper to the tor-talk mailing list, but it has elicited no discussion so far.

It is easy to speculate that some of Riffle's components (such as verifiable shuffles) could potentially be added to Tor, and might even be beneficial. But perhaps Riffle will prove most interesting to developers tackling different problems altogether. There might be uses for a Twitter-like microblogging service that has strong anonymity baked in from the start, or for an anonymous file-sharing network. Either of those use cases could prove to be a valuable tool for end users, without requiring use of the more general-purpose Tor network.