More secure networks with the power of zero knowledge

There’s a fundamental tension baked into computer networks: how do administrators identify unsafe activities without interfering with user privacy? In settings like K-12 schools, for instance, it’s expected that networks will filter out obscene content, while classified settings need protection against things like data loss, intrusions, or compromised sensitive information.

Paul Grubbs, assistant professor of Computer Science and Engineering at the University of Michigan, is grappling with this tension between privacy and network policies using a technique called zero-knowledge proofs. A relatively new technique in cryptographic applications, zero-knowledge proofs enable a secret message to be tested against some requirement without needing to divulge the secret itself. Grubbs’ work is among the first applications of the zero-knowledge paradigm to network security and privacy.

This paradigm, Grubbs argues, is one opportunity to defuse this tension by ultimately enabling policy enforcement without sharing all the details of user activities.

“My goal is to establish a safe default tradeoff between network policies and user privacy,” he says.

Enforcing network policies requires users to pass their request for content, like a website, through a network device that inspects the destination, with varying degrees of elegance. In the most basic example, the so-called middlebox will vet the user’s request message as plain text, with all of their browsing activity fully visible.

“Everywhere you go on the web corresponds to a Domain Name System (DNS) query that your computer sends,” Grubbs explains. “So knowing your list of DNS queries reveals the domains you’re browsing on the web.”

The move toward privacy-protected network protocols using encryption made this straightforward enforcement technique more difficult to implement without breaking user trust. Unlike the early internet, much of the world’s network activities today are encrypted to some extent, and many services offer full end-to-end protection of user data.

“By design,” Grubbs wrote in a blogpost for APNIC, “encryption prevents exactly the kind of scanning that middleboxes rely on to enforce policies.”

This is where the zero-knowledge paradigm can provide a middle ground. A new type of enforcement technology, termed by Grubbs a “zero-knowledge middlebox,” would enable users to scan their own traffic before they encrypt it and pass along a verification that their activity doesn’t violate a network policy. This user-supplied verification would need to convince the new middlebox that their activity was scanned properly and turned up no violations.

In order to convince the middlebox, the user would provide a zero-knowledge proof alongside their standard, encrypted network requests. This proof states that the request contains policy compliant traffic, and the middlebox would simply need to verify that the proof was created correctly. No data demonstrating why the traffic is compliant – in essence, no data about the user’s traffic at all – is shared with the middlebox.

In proposing a design for this system, Grubbs identified five requirements it had to meet: don’t weaken encryption, only reveal whether traffic is policy compliant; enable networks to continue enforcing policies as they did before; don’t introduce new trust assumptions; and don’t make changes to web servers.

This last requirement is part of Grubbs’ ambition to design a system that’s readily adoptable.

“The goal is to make these zero-knowledge techniques fit as easily as possible into existing network flows,” he says. “It’d be so easy to write a paper that proposes a whole new internet that has a nice privacy feature, but it’s not a very useful exercise because nobody’s going to bother.”

In early implementations of this technology, Grubbs demonstrated that a zero-knowledge middlebox could be made fully compatible with existing encrypted network protocols like TLS 1.3 without the need for these customizations or particular trusted hardware. He also described some early extensions to the technology, including proving that certain traffic contains HTTP and proving that Oblivious DNS-over-HTTPS (ODoH) traffic is destined for a filtered DNS resolver – both with zero knowledge.

Additionally, Grubbs notes, the final design of systems making use of zero-knowledge middleboxes should be such that it can’t be used for censorship, and can still be circumvented when the need arises.

A key early challenge to building usable systems out of this framework is added computing time overhead, Grubbs says. After several early optimizations, Grubbs’ first implementation of a zero-knowledge middlebox to filtering Domain Name System (DNS) queries resulted in an added 3 second wait for every query.

“This isn’t practical by any means yet,” says Grubbs. “Waiting 3 seconds to do a DNS query is of course prohibitive. But I think these are very exciting early results for this ongoing work. There are a lot of tools in our toolbox to get this cost down.”

This work was first covered in “Zero-Knowledge Middleboxes,” co-authored by Paul Grubbs and collaborators Arasu Arun, Ye Zhang, Joseph Bonneau, and Michael Walfish from New York University. The paper was presented at USENIX Security, 2022.