Protecting Sensitive Metadata So It Cannot Be Used for Surveillance

“That was like a punch to the cryptography and security communities,” Kwon says. “That meant encryption wasn’t really doing anything to stop spying in that regard.”

Kwon spent most of his PhD program focusing on metadata privacy. With XRD, Kwon says he “put a new spin” on a traditional E2EE metadata-protecting scheme, called “mix nets,” which was invented decades ago but suffers from scalability issues.

Mix nets use chains of servers, known as mixes, and public-private key encryption. The first server receives encrypted messages from many users and decrypts a single layer of encryption from each message. Then, it shuffles the messages in random order and transmits them to the next server, which does the same thing, and so on down the chain. The last server decrypts the final encryption layer and sends the message to the target receiver.

Servers only know the identities of the immediate source (the previous server) and immediate destination (the next server). Basically, the shuffling and limited identity information breaks the link between source and destination users, making it very difficult for eavesdroppers to get that information. As long as one server in the chain is “honest”— meaning it follows protocol — metadata is almost always safe.

However, “active attacks” can occur, in which a malicious server in a mix net tampers with the messages to reveal user sources and destinations. In short, the malicious server can drop messages or modify sending times to create communications patterns that reveal direct links between users.

Some methods add cryptographic proofs between servers to ensure there’s been no tampering. These rely on public key cryptography, which is secure, but it’s also slow and limits scaling. For XRD, the researchers invented a far more efficient version of the cryptographic proofs, called “aggregate hybrid shuffle,” that guarantees servers are receiving and shuffling message correctly, to detect any malicious server activity.

Each server has a secret private key and two shared public keys. Each server must know all the keys to decrypt and shuffle messages. Users encrypt messages in layers, using each server’s secret private key in its respective layer. When a server receives messages, it decrypts and shuffles them using one of the public keys combined with its own private key. Then, it uses the second public key to generate a proof confirming that it had, indeed, shuffled every message without dropping or manipulating any. All other servers in the chain use their secret private keys and the other servers’ public keys in a way that verifies this proof. If, at any point in the chain, a server doesn’t produce the proof or provides an incorrect proof, it’s immediately identified as malicious.

This relies on a clever combination of the popular public key scheme with one called “authenticated encryption,” which uses only private keys but is very quick at generating and verifying the proofs. In this way, XRD achieves tight security from public key encryption while running quickly and efficiently.   

To further boost efficiency, they split the servers into multiple chains and divide their use among users. (This is another traditional technique they improved upon.) Using some statistical techniques, they estimate how many servers in each chain could be malicious, based on IP addresses and other information. From that, they calculate how many servers need to be in each chain to guarantee there’s at least one honest server.  Then, they divide the users into groups that send duplicate messages to multiple, random chains, which further protects their privacy while speeding things up.

Getting to Real-Time
In computer simulations of activity from 2 million users sending messages on a network of 100 servers, XRD was able to get everyone’s messages through in about four minutes. Traditional systems using the same server and user numbers, and providing the same cryptographic security, took one to two hours.

“This seems slow in terms of absolute speed in today’s communication world,” Kwon says. “But it’s important to keep in mind that the fastest systems right now [for metadata protection] take hours, whereas ours takes minutes.”

Next, the researchers hope to make the network more robust to few users and in instances where servers go offline in the midst of operations, and to speed things up. “Four minutes is acceptable for sensitive messages and emails where two parties’ lives are in danger, but it’s not as natural as today’s internet,” Kwon says. “We want to get to the point where we’re sending metadata-protected messages in near real-time.”

Rob Matheson is writer and web producer at MIT News. Reprinted with permission of MIT News