Cryptographic Reverse Firewalls

Ilya Mironov


Between recent revelations regarding scope and sophistication of surveillance programs, integrity of cryptographic standards (e.g., Dual_EC_DRBG), security of common implementations (e.g., Heartbleed), the boundaries separating the adversary and trusted code or hardware are crumbling. Facing the disturbing, and quite real, possibility of a compromise that reaches inside one’s communication platform, we address the following, seemingly paradoxical question: Can we design cryptographic protocols that achieve meaningful security when the adversary may arbitrarily tamper with the victim’s computer?

Inverting the metaphor from network security, we propose and investigate the power of a (cryptographic) reverse firewall - an entity whose role is to protect cryptographic schemes and protocols from insider attacks. Similarly to a regular firewall, we require the reverse firewall be transparent to legitimate traffic, be stackable (one can deploy multiple reverse firewalls that are oblivious to one another), and only improve security (security is always better off with a reverse firewall than without). Importantly, we do not model the firewall as a trusted party. It does not share any secrets with the user, and the protocol should be both secure and functional without the firewall (when it is implemented correctly). In contrast to the standard firewall, the focus of a reverse firewalls is on the inside of the perimeter. In particular, one important goal of reverse firewall is prevention of exfiltration attacks.

Our security definition for reverse firewalls depends on the security notion(s) of the underlying protocol. As such, our model generalizes much prior work and provides a general framework for building cryptographic schemes that remain secure when run on compromised machine. It is also a modern take on a line of work that received considerable attention in the 80s and 90s.

We show that our definition is achievable by constructing a private function evaluation protocol with a secure reverse firewall for each party. Along the way, we design an oblivious transfer protocol that also has a secure RF for each party, and a rerandomizable garbled circuit that is both more efficient and more secure than previous constructions. Finally, we show how to convert any protocol into a protocol with an exfiltration-resistant reverse firewall for all parties. (In other words, we provide a generic way to prevent a tampered machine from leaking information to an eavesdropper via any protocol.)

Joint work with Noah Stephens-Davidowitz (NYU). E-print version is here:

Time and Place

Tuesday, October 28, 4:15pm
Gates 498