Nmedia - Fotolia

News Stay informed about the latest enterprise technology news and product updates.

David Chaum's cMix: New tool for anonymity on the Internet

David Chaum presents Internet anonymity tool PrivaTegrity, using the cMix mix network for reliable, high-performance Internet anonymity and protection against attacks or unauthorized backdoors.

Cryptographer David Chaum presented a project for protecting privacy on the Internet using cMix, a new type of anonymity or pseudonymity mixing network, at the Real World Cryptography Conference 2016 in Stanford, Calif., earlier this month. The announcement spurred criticism, which Chaum claimed to be unfounded.

Chaum and a team of academics proposed PrivaTegrity, based on a new type of mix network, called cMix, as a way to offer both improved efficiency and the potential to be more resistant to attacks, as well as a potentially better anonymity service than Tor. But the immediate reaction was mostly criticism over the reported inclusion of a backdoor in PrivaTegrity -- anathema to any privacy service for social media or the Internet in general.

Chaum, speaking to Wired magazine, allowed use of the term backdoor to describe the system -- a decision that Chaum walked back in a subsequent interview with Fortune. Further speculation about how PrivaTegrity and cMix would work -- and why anyone would be willing to use them in light of the apparent decision to incorporate a backdoor -- was dispelled with a close reading of the cMix paper, as well as a short conversation with Chaum, himself.

As proposed, PrivaTegrity operates over a cMix mixnet, with nine mix nodes and one network handler server, which organizes message transmission to and from the mixnet. The so-called backdoor refers to the possibility that messages can be traced only if all mix nodes have been compromised, or if all of them are colluding to break user anonymity.

Part of the beauty of cMix is that it works to protect anonymity as long as there is a single uncompromised mix node. In order to be successful, an attack would have to compromise every mix node.

"It's an extraordinary level to say that you have 10 entities that would all have to be compromised and collude at the same time in order to spy forward," Chaum told SearchSecurity. "That would mean, then, that at least it's very likely that it would become known; at least one of them would leak out the fact that this was happening, and then the whole effort would be useless, because there's no old data in there."

Chaum said that in the event that all servers were compromised, it would still not permit the attackers to trace old messages, because the system has "perfect forward secrecy." This means that even if all mix nodes in the network were compromised -- or were to collude -- it would not be possible to reveal any information about past communications; it would only permit the attackers or colluders to deanonymize communications after the compromise. Chaum added that old messages would not be accessible from a PrivaTegrity user's phone, either. "You have [perfect forward secrecy] both on the server side and the phone side," he said.

There is no intention to have decloaking in PrivaTegrity. Let's be clear about that.
David Chaumcryptographer

As for breaking anonymity, Chaum was adamant that "there is no intention to have decloaking in PrivaTegrity. Let's be clear about that." What is intentional in PrivaTegrity is an attempt to provide a trustworthy privacy network, as well as a privacy tool that can operate efficiently in lower-power devices, such as mobile phones or tablets.

One of the key features of cMix, as described in the cMix paper, is that it is able to "reduce the computation overhead by replacing real-time public-key operations with symmetric-key operations." By letting the mix nodes precompute values to be used in communication by users' systems, the higher computational cost of doing public key cryptography is bypassed. And while some may view the use of only nine trusted mix nodes as a drawback -- especially when compared to the Tor network's thousands of relays -- cMix is designed to prevent the kind of attacks that are possible with Tor when a nation state or APT attacker adds systems they control as gateways into the anonymity network.

Chaum explained the design decision to incorporate multiple mix nodes as a way of distributing trust.

"It is always better to, instead of trusting a single person, to trust some number of people to not collude," Chaum said. "In general, in society, we rely on only two parties -- almost always. It's two guys in the submarine who can blow up the world if they want to; they don't have to receive any messages from anyone."

In the cMix paper, possible applications were noted, including "private message delivery without use of public key, and including confidential authentication of the sender to the recipient." The paper's authors also wrote that "a number of additional applications are being developed using cMix as a primitive, including payments, photo sharing, anonymous feed following and general credential mechanisms. Other possible applications include voting and anonymous surveys."

Reception to the PrivaTegrity proposal was broadly debated online. Ryan Lackey, a security expert who emphasized he was speaking for himself and not for his employer, CloudFlare, told SearchSecurity he doesn't think the focus here was to create a usable product for a given market, but rather to create a new technology and describe it with an illustrative use case.

"I would not say that David Chaum's reputation is being a market- or product-driven visionary; it's more that he creates amazing technology, but it's mostly for its own sake -- not so much for a practical purpose," Lackey said. "I saw the presentation, I read the cMix paper, and then I read part of the PrivaTegrity [presentation slides]. This seems to me a very interesting academic project. Some of it [cMix] looks pretty good."

There are other implementation obstacles that must be overcome, such as gaining a large user base, since mix networks rely on having a large "crowd" of users in which individual users can get lost.

"An anonymity system can be, at best, as good as the size of its user base," Aggelos Kiayias, head of the cryptography-security group, and associate professor of cryptography and security at the University of Athens, told SearchSecurity by email. "From a technical point of view, the system is novel, as it can be an order of magnitude faster in terms of real-time processing (the mixing process itself) than previous systems. Whether this will translate to a large user base, it remains to be seen when the system becomes available."

Chaum is confident that there will be sufficient demand for a service like that offered by PrivaTegrity, and that the project had already generated commercial interest.

"If you look at the consumer surveys, you'll see it's a very important issue for people -- privacy in social media," Chaum said. "And I think that means that it can be a very successful social media offering."

Mixnets explained

David Chaum was the first to describe a mix network in 1981, which enabled use of pseudonyms and incorporated a mechanism by which an anonymous sender could receive messages back from a correspondent, without compromising their own anonymity by exposing a return address. The mixnet itself is composed of mix nodes, which take messages submitted from multiple users and then break them into smaller units, mixing them up and then forwarding them to other mix nodes, which repeat the process. The messages are forwarded to their destinations once it has become sufficiently difficult to trace the messages back to their original senders.

An onion-routed network, such as Tor, is sometimes considered a special type of mixnet in that both types of networks provide anonymity by encrypting communications into chunks such that an intermediate routing node -- called a "mix" in mix networks -- can unwrap one layer at a time and forward to the next hop. One key difference between the two is that in mix networks, each mix collects messages from multiple senders and shuffles them before forwarding them.

Mix networks of all types are most effective when there are many concurrent users, giving a larger "crowd" in which users can "hide" to preserve their anonymity. In onion-routed networks like Tor, relay systems forward traffic from a sender to a recipient, even if there is no other traffic with which to mix it. Mix networks use successive rounds of encryption -- like onion routing networks -- to transmit data to each mix system, but they also aggregate traffic from multiple sources so that anonymity can be preserved, even if an attacker is able to determine the routes that the mix traffic is being sent over.

"Mix networks get their security from the mixing done by their component mixes, and may or may not use route unpredictability to enhance security. Onion routing networks primarily get their security from choosing routes that are difficult for the adversary to observe, which, for designs deployed to date, has meant choosing unpredictable routes through a network. And onion routers typically employ no mixing at all," Paul Syverson, inventor of onion routing and one of the original designers of Tor, wrote in 2013. "Mixes are also usually intended to resist an adversary that can observe all traffic everywhere, and, in some threat models, to actively change traffic. Onion routing assumes that an adversary who observes both ends of a communication path will completely break the anonymity of its traffic. Thus, onion-routing networks are designed to resist a local adversary, one that can only see a subset of the network and the traffic on it."

Another hurdle is putting together the mixnet software on all the mix nodes. Chaum told SearchSecurity that the goal would be, eventually, to have different code written to the specification for each mix node.

Lackey said there would be no way to deploy this in a reasonable way with a single codebase.

"You'd have to build a reference design, let individual server operators audit and implement their own versions of this," Lackey said. "Because if your security model is that you need to hack nine servers at the same time to do it, you want them to be as diverse as possible. If they have the same codebase, you just find a flaw that works in all nine of them at the same time."

As for adoption of an anonymity system with a backdoor, Kaiyias said this could only happen if everyone is convinced that the backdoor could not be abused, and that would be activated only via due process.

"This is a really tall order. I haven't seen anything concrete or convincing in this direction by PrivaTegrity or any other system," Kiayias said. "Also, the real question here is not whether people will be willing to use a system with a backdoor, but whether criminals will use a system with a backdoor. And the answer is that, most likely, they won't, because they will find alternatives and workarounds, or build and use systems without backdoors."

As for how PrivaTegrity would satisfy governments clamoring for access to anonymized communications of suspected terrorists or other criminals, Kiayias said it is hard to imagine how it will work.

"The suggestion is that the mix servers will be in different legal jurisdictions, and thus, it will require coordination between these jurisdictions for the backdoor to be applied," said Kiayias. "This is not just an engineering problem; it is a complex legal problem as well, and I don't see it being solved easily."

"If the system becomes popular, it will definitely be very attractive as a target. Furthermore, if the backdoor functionality comes with an interface, this would be a single point of failure for the privacy of the whole system," Kiayias said. "The real problem is how to manage backdoors -- and there are no good solutions for this so far."

Next Steps

Find out more about the increasing demand for Internet anonymity.

Do politicians understand the issues of deploying encryption backdoors?

Learn why technical experts warn against law enforcement backdoors for encrypted material.

Dig Deeper on Data privacy issues and compliance