There are challenging tensions between users encrypting network traffic and operators enforcing policies about the way their network is used. An ongoing debate that exemplifies this is the deployment of encrypted DNS, which met (and is meeting) resistance from many network operators because it prevents enforcing DNS-based policies like malware scanning or domain filtering.
At the upcoming USENIX Security 2022 conference, my coauthors (Arasu Arun, Ye Zhang, Joseph Bonneau, and Michael Walfish) and I will present a paper that demonstrates a new way to resolve these tensions. Our paper introduces zero-knowledge middleboxes (ZKMBs), which allow operators to enforce arbitrary policies on the underlying traffic of an encrypted connection without decrypting it.
ZKMBs work without having to modify widely-used protocols like TLS 1.3, and do not require trusted hardware. Instead, they leverage recent advances in efficient zero-knowledge proofs, and specifically zk-SNARKs. In this blog post, I’ll explain the basic architecture of a ZKMB, describe a case study of DNS filtering, and briefly touch on performance and our ongoing work.
- Encrypting traffic breaks existing approaches to policy enforcement in networks.
- Zero-knowledge middleboxes (ZKMBs) let users encrypt their traffic while still enabling operators to enforce policies.
- Operators can use ZKMBs to enforce a DNS filtering policy without having to see user DNS queries.
- ZKMBs are not yet fully practical, but we’re optimistic that they will be soon.
What are zero-knowledge middleboxes
To understand how ZKMBs work, I’ll first explain exactly why the tension between encryption and policy seemed so fundamental.
In the early days of the Internet, almost no network traffic was encrypted. Thus, when the first generation of network architects was faced with the challenge of enforcing usage policies in their networks — one example policy we’ll come back to is content filtering, or preventing users from visiting certain websites — they accomplished this with network middleware (middleboxes) that looked at all the traffic traversing the network to make sure it abided by the policy. If the middlebox detected a policy violation, it just dropped the traffic.
Because the middlebox saw exactly what everyone was sending and receiving, it could enforce policies perfectly, at least in theory. This is why encryption caused, and is causing, such huge problems — by design, encryption prevents exactly the kind of scanning that middleboxes rely on to enforce policies.
The key idea of a ZKMB is that clients can ‘scan’ their own traffic before they encrypt it, and then cryptographically convince the middlebox of two things:
- The client scanned the traffic exactly how the middlebox would have.
- The scanned traffic is compliant with the policy.
Crucially, using a zero-knowledge proof (ZKP), the client can convince the middlebox that these two things are true only if they are actually true, but without revealing the traffic to the middlebox.
It isn’t really necessary to understand all of the details about how ZKPs work, just that they are a cryptographic protocol between two parties — a prover and a verifier. In the protocol, the prover generates and sends a proof to a verifier, who runs a verification algorithm on the proof that outputs either ‘true’ (meaning the prover’s claimed statement is true) or ‘false’ (meaning the claimed statement is not true).
Let’s use Figure 1 to break down the ZKMB protocol:
Step 1 — The network creates a description of the policy that is ‘compatible’ with the ZKP machinery.
Step 2 — When the client joins the network, the middlebox gives the client a description of the policy it needs to abide by.
Step 3 — The client sets up a connection and sends some encrypted traffic through the network.
Step 4 — This initial encrypted traffic includes a proof of the truth of the two facts above.
Step 5 — Finally, the middlebox verifies the proof.
If the verification algorithm outputs ‘false’, the middlebox can block the traffic.
There are a lot of details I’m omitting — see the paper if you’re curious — but the punchline is that zero-knowledge proof machinery is flexible enough to allow ZKMBs for highly complex protocols like TLS 1.3, and nontrivial policies like DNS filtering.
Applying ZKMBs for DNS filtering
To make this discussion a little more concrete, I’ll explain one of the case studies from our paper, namely building a ZKMB for encrypted DNS filtering.
The network wants to prevent users from visiting websites on a blocklist. If the network itself resolved all of the user’s DNS queries, it could filter them by (say) refusing to resolve any domain on the blocklist. (Indeed, this is exactly how a lot of in-network filtering software works today.) The ZKMB we designed allows operators to achieve the same filtering functionality, without acting as the resolver or even seeing DNS queries at all!
The ZKMB protocol begins with the network setting up the blocklist and giving it to newly-joining clients. Then, when the client sends encrypted traffic containing a DNS query, it also sends alongside it a ZKP of the truth of the statement, “This encrypted traffic contains a DNS query for a domain not on the blocklist”. Finally, the middlebox tries to verify the proof; if verification succeeds, it forwards the packet to the DNS resolver.
Extensions and evaluation
In our paper, we describe a couple of other interesting ZKMB case studies. One lets clients prove that their traffic is HTTP; another is a ZKMB for proving that Oblivious DNS-over-HTTPS (ODoH) traffic is destined for a filtered DNS resolver. We also explain how, with some reduction in performance, the description of the policy itself can be kept secret from the client in some cases.
Read: Improving the privacy of DNS and DoH with oblivion
If you’ve read this far, hopefully you’re super excited about ZKMBs and are wondering if the performance overheads of all this fancy cryptography are low enough for ZKMBs to be practical. Our paper’s evaluation found that ZKMBs are not yet fully practical, but they are surprisingly close.
For the encrypted DNS case study above, our proof is actually split up into two parts:
- A more expensive one-time ‘setup’ when the TLS session is opened.
- A cheaper per-packet proof for each DNS query sent.
In our implementation, the once-per-TLS-session cost for the client is about fifteen seconds, and the per-DNS-query cost is about three seconds. In both cases, the proof is small — about the same size as the encrypted DNS packet itself — and the cost to the middlebox of verifying it is only about five milliseconds.
Now, as I said, ZKMBs aren’t exactly blazingly fast yet, but we’re very optimistic for two main reasons:
- There is still huge potential for optimizing ZKMBs using existing techniques.
- Creating new ZKPs for the ZKMB setting will quite likely reduce overheads much further.
In ongoing (not yet published) work, we’re pursuing both of these ideas and have seen very promising initial results. To learn more read our paper.
Paul Grubbs is an assistant professor at the University of Michigan. His research is in applied cryptography.
The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.