A VMware Research team has unveiled a new anonymous communications network that can obscure or “blind” the network to the senders’ identities. According to VMware Postdoctoral Researcher Avishay Yanai, the new system, Blinder, hides important metadata that could be acquired by a third-party entity, such as a system operator or Internet provider. While well-known encrypted message networks, such as Signal, Telegram, and Proton Mail, are private from end to end, the communication is not provably anonymous.
Metadata includes information about the identities of the senders and receivers, as well as when and how much they are communicating. An anonymous communication system must hide this metadata, not just the conversation content, according to the research team, which includes VMware Senior Researcher Ittai Abraham and Benny Pinkas, a computer science professor at Bar Ilan University in Tel Aviv.
The importance of anonymity
Anonymous communication is considered a social necessity. A UN report from 2015 stated that “encryption and anonymity enable people to exercise their rights to freedom of opinion and expression and the right to privacy in the digital age,” and urged countries to make sure people are free to use such tools.
In addition to the human-rights issues, anonymous communication is important to whistleblowers, protecting their identities as they work to fight corruption and defend the public interest. This is reflected in the Whistleblower Directive entered into force in 2019 by the European Union. It is also a necessary layer for cryptocurrencies, such as Monero and Zcash (which support anonymity in the application layer but not in the network layer).
Properties of anonymous communication
An anonymous communication system must allow its users to communicate over a public network in a way that does not reveal their identities to potential adversaries. From this high-level requirement, it is clear that the message passing over the network originates with a user, who is actually connected in some way to that network. The set of users who are connected to the network is called the “Anonymity Set.” In general, the larger this set, the better it is for users’ anonymity because it increases the uncertainty in relating a message to its potential sender.
In this context, “adversary” refers to a single entity who may control a subset of the network operators, a subset of users, or a combination of both. In addition, we usually distinguish between a global adversary (who may tap all communication channels) from a local adversary, who may tap only a subset of the communication channels. Indeed, when properly securing the channels, the adversary could not learn the content of the communication, yet it could infer that a communication took place, as well as its volume. This data alone can leak a lot of information about the communicating parties. “We kill people based on metadata” is a famous quote by General Michael Hayden, former director of the NSA and the CIA.
The subsets of network operators, users, and communication channels the adversary may control are called the “threat model.” These threat models differ from one system to another. Blinder follows a very strict threat model, in which the adversary is global. It may control any number of clients and a fraction of the servers, but it is unable to leak information about the senders of messages.
How Blinder works
Blinder is a sophisticated modification of the Dining Cryptographers network (DC-net in short) introduced by computer scientist and cryptographer David Chaum in 1985, in which a few servers mediate the messages of many clients, instead of having all clients communicate directly over a full graph network. In its simplest form, users send their messages to a server, which collects many messages, shuffles them, and outputs them. If the server is honest, it is difficult to identify the messages’ sender.
To avoid reliance on the honesty of a single server, Blinder builds on a cryptographic technique called “threshold secret sharing,” which was invented in 1979 by Adi Shamir, one of the co-developers of the RSA encryption algorithm, and cryptographer George Blakley. This technique enables us to abstract out this server split to multiple entities. Below is a high-level version of how Blinder works.
First, we assign n as the number of servers and N as the number of clients (“senders” in other communication systems). The servers maintain a big table with at least N entries in a way that a single server (or a small group of servers) cannot see what values reside in the entries because it shares each entry’s content cryptographically.
The servers will be able to inspect the value within an entry only if a sufficiently large group of them agrees to do so. The goal is for each client to write its message to a single, random entry in the table, so the servers cannot detect the location to which they are writing. This property is called “obliviousness” and it can be achieved through a cryptographic technique called “Private Information Write” (PIW).
Revealing only necessary information
After all clients have placed their messages in the table, the servers agree to open all of the entries and reveal the messages inside. At this point, it is not possible to identify which client put a message in a given entry, because the content of the entries has been obscured from the servers (again, each client has written its message to a table entry at a random location that only it knows).
The above description serves as a solution template, which is followed by other solutions in the literature. In that template, there are two technical placeholders: secret sharing and PIW. Before we delve into the descriptions of these two, it is important to understand that each client picks its entry at random and without any coordination with other clients. For this reason, it is inevitable to have collisions. In other words, when two or more clients pick the same entry, they will interfere with each other. To solve this, we first note that when a client picks an entry and places its message, we do not want it to override that entry. Instead, we want it to add its message to whatever was there previously. For example, if one client places msg1 in an entry and another client places msg2 in the same entry, then the content of that entry becomes msg1+msg2.
To this end, we treat messages as elements in a finite field (so the addition of messages makes sense) and initialize the table entries with zero. Working with a table of size exactly N, for each entry, the probability of containing a single message is approximately 1/Ne, meaning that only about 1/e of the messages will not collide. The rest of the messages will collide and result in entries with undecodable messages. A simple way to increase the number of non-colliding messages would be to work with a table with much more than N entries. If we want that number to be, say 95N, then the size of the table should be approximately 20N. A previous work on anonymous broadcast called Riposte found a more compact way to do that, using two tables with a total size of only 5.4N.
As mentioned earlier, due to secret sharing, the entries of the table remain secret to the servers until the very end (after all clients have placed their message). Blinder uses a threshold version of secret sharing, with the threshold t=n/4. Each server holds a piece of an entry’s content so that one piece on its own carries no information about the content. Furthermore, even when gathering less than t pieces, their combined information is unrelated to the value of that entry. In contrast, possessing t or more pieces completely determines the value. The client of a message is responsible for breaking its message into n pieces with that threshold property. These are collectively called “sharing.”
In the next step, it sends each server a single piece of the message. If we believe that the adversary could corrupt only less than t servers, the client’s message remains secret.
The Private Information Write
You may be wondering — how can a client put its message in an entry without revealing which entry it was? This leads us to the second placeholder, the Private Information Write (PIW). Instead of writing a message to only a single entry, a client will write something to every entry. Since writing is done via secret sharing, the servers cannot tell which message is written to which entry. If a client picks the k-th entry, it will write its message, m, to the k-th entry, and the value O to every other entry. As explained above, messages in an entry are being added to each other (rather than overriding each other). For this reason, the client changes the value that resides in the k-th entry only, since the value O is added to all others. Note that thanks to the privacy properties of secret sharing, the servers cannot tell whether a client writes its message or the value O to an entry. The servers know nothing about the entry chosen by the client: the write procedure is oblivious.
An oblivious write comes at a cost because the bandwidth required from a client is now O(N) rather than O(1). So, if there are many clients, the solution becomes impractical. To this end, for the Blinder protocol, we devised a more efficient way to obliviously write into the table, incurring only a bandwidth of O(√N). Moreover, Blinder’s oblivious write scheme is amenable to a GPU acceleration, which dramatically reduces the system’s latency and makes this design highly attractive.
Avishay Yanai will present Blinder at the ACM Conference on Computer and Communications Security (CCS), which will take place on November 9-13, 2020. Download the paper here.
