Zero-Knowledge Middleboxes

Paul Grubbs - NYU/UMich

Arasu Arun - NYU

Ye Zhang - NYU

Joseph Bonneau - NYU/Melbourne

Mike Walfish - NYU

USENIX Security 2022

​

eprint.iacr.org/2021/1022.pdf

Zero-Knowledge Middleboxes

enforce

network

policies�

allow

encrypted

traffic

�

(using zero-knowledge proofs)

DNS Filtering

Client

MiddleBox

example.com

Is example.com allowed?

DNS Resolver

example.com

Local Network

DNS Filtering is a fact of life

In-flight

Schools

Cafes

Parental controls

legally required in USA

The rise of encrypted DNS: standards

The rise of encrypted DNS: resolvers

1.1.1.1

8.8.8.8

9.9.9.9

The rise of encrypted DNS: browsers

Encrypted DNS breaks filtering

Dilemma:

Client’s Privacy

vs.

Network Policy

MiddleBox

Is Enc(Query) allowed?

???

Enc(Query)

Client

Mozilla’s “solution”: network-level kill switch

Past academic solutions

• Approach #1: modify TLS to use functional encryption
• Blindbox [Sherry et al. 2015], Embark [Lan et al. 2016]
• Requires server-side changes
• Weakens TLS security guarantees

​

• Approach #2: enforce network policies using trusted hardware
• SGX-Box [Han et al. 2017], Endbox [Goltzsche et al. 2018]
• Requires clients have trusted hardware
• Vulnerable to TEE side-channel attacks

Can we achieve privacy & policy enforcement?

• Compatibility: work with TLS 1.3, no server-side changes
• Privacy: middlebox learns nothing additional beyond policy compliance
• Flexibility: support arbitrary network policies
• Efficiency: “reasonable” client overhead, very low middlebox overhead

This is a job for zero-knowledge proofs

Zero-Knowledge �Sudoku Proof

Proof

Puzzle

Accept/Reject

Solution

Sudoku

Testing Algorithm

Prover knows �solution �to

Puzzle

Puzzle

, Proof

Prover

Verifier

ZK 101

• Possible for any NP statement
• Continual efficiency improvement since 1980s
• Practical deployment during 2010s
• Compilers produce prover/verifier from higher-level description

proof π

public input

(statement)

private input

(witness)

Proving

Algorithm

Verification Algorithm

public input

(statement)

Accept/Reject

Blockchains have brought $$$ to ZKPs

• Privacy-benefits: prove a transactions is valid without publishing details

​

​

​

​

​

​

• Efficiency benefits: prove many transactions are valid in a short proof

​

New Application: ZKMBs

MiddleBox

Client

DNS Resolver

Enc(Query) + Proof

Verification Algorithm��Enc(Query) + Proof

Query is not in the Blocklist

Enc(Query)

Many evasion strategies exist for motivated clients

• Application-layer encryption

​

• Alternate routing protocols (e.g. TELEX)
• Tor hidden services
• Steganography
• Out-of-band communication

Assumption: client, server use standard protocols only

Filtering vs. Censorship

Censorship

Filtering

Polite request

Designing ZKMBS

Designing efficient ZK proofs remains challenging

Long-term expectations:

• Generic zk-SNARK constructions exist for all NP statements
• Compilers exist from human-level languages to circuit representation
• Programmers can choose from multiple “backends” with different tradeoffs

Today’s reality:

• Generic zk-SNARK can be very expensive
• Compiled circuits often impractically slow
• Practicality requires problem-specific optimization
• As much art as science

TLS is complex (even TLS 1.3)

ZKMBs proofs decompose into several tasks

Channel opening

Parse & extract

Policy

check

​

Ciphertext

Plaintext

Policy-relevant text

Accept/

reject

Channel opening statement proves plaintext matches transcript

Plaintext

Proof

Decryption (AES)

TLS Key Schedule (SHA-256)

key

Handshake

Transcript

TLS secrets

Simply supplying a valid AES key + decryption is insufficient

Problem:

• AES-GCM (as used in TLS 1.3) is not committing
• Multiple keys can decrypt the same plaintext to different ciphertexts

​

Observation: TLS transcripts do commit to an exact AES key

Simple solution:

• Provide client Diffie-Hellman secret as a witness
• Prove that the AES key was derived from the DH exchange

Fast solution:

• Provide only AES key as a witness
• Prove the key is derived from an intermediate value in the handshake

Parse & extract circuit (DNS example)

Optional hints

Proof

Plaintext

​

Queried domain

Policy check: Merkle-tree non-membership

Proof

Merkle �Non-Membership Proof

Domain

Blocklist

commitment

• Leaves are domains in sorted order
• “Circuit-friendly” hash used (Poseidon)

Implementation #1 (MB-optimized)

• ZKPs were constructed using xJsnark
• Proofs generated using libsnark - Groth16 algorithm

xJsnark: https://github.com/akosba/xjsnark

libsnark: https://github.com/scipr-lab/libsnark

Proving Time is the Bottleneck

Channel-opening

Parsing, policy check (DNS filtering)

Proving Time is the Bottleneck

MiddleBox

Client

Enc(Query) + Proof

5 ms

20 seconds

300 bytes

Verification time

Proof size

Proving time

75% of the runtime is due to SHA256!

Amortization

Opening Proof

Reuse Proof throughout session

Client

MiddleBox

20 seconds

6

seconds

* Middlebox needs to store some state

TLS 1.3 Session

Pre-computation

Opening Proof

Reuse Proof throughout session

TLS 1.3 Session

Doesn’t affect

DNS latency

Client

MiddleBox

20 seconds

6

seconds

Implementation #2 (balanced?)

• ZK proofs were constructed using Spartan

​

Spartan: https://github.com/microsoft/Spartan

Spartan is much more client-friendly

Channel-opening

Parsing, policy check (DNS filtering)

Future Work

​

• Support other encrypted protocols
• Tor, VPNs

​

• Support private blocklists�
• Support other policies: Data Loss Prevention

Conclusion: ZKMBs close to practical!

​

“Zero-Knowledge Middleboxes” paper: eprint.iacr.org/2021/1022.pdf

Implementation: github.com/pag-crypto/zkmbs

This work supported by the DARPA SIEVE Project

Operations Involved

Blocklist with ~1 M entries