Paper 2015/548

Message Transmission with Reverse Firewalls---Secure Communication on Corrupted Machines

Yevgeniy Dodis, Ilya Mironov, and Noah Stephens-Davidowitz

Abstract

Suppose Alice wishes to send a message to Bob privately over an untrusted channel. Cryptographers have developed a whole suite of tools to accomplish this task, with a wide variety of notions of security, setup assumptions, and running times. However, almost all prior work on this topic made a seemingly innocent assumption: that Alice has access to a trusted computer with a proper implementation of the protocol. The Snowden revelations show us that, in fact, powerful adversaries can and will corrupt users' machines in order to compromise their security. And, (presumably) accidental vulnerabilities are regularly found in popular cryptographic software, showing that users cannot even trust implementations that were created honestly. This leads to the following (seemingly absurd) question: ``Can Alice securely send a message to Bob even if she cannot trust her own computer?!'' Bellare, Paterson, and Rogaway recently studied this question. They show a strong lower bound that in particular rules out even semantically secure public-key encryption in their model. However, Mironov and Stephens-Davidowitz recently introduced a new framework for solving such problems: reverse firewalls. A secure reverse firewall is a third party that ``sits between Alice and the outside world'' and modifies her sent and received messages so that even if the her machine has been corrupted, Alice's security is still guaranteed. We show how to use reverse firewalls to sidestep the impossibility result of Bellare et al., and we achieve strong security guarantees in this extreme setting. Indeed, we find a rich structure of solutions that vary in efficiency, security, and setup assumptions, in close analogy with message transmission in the classical setting. Our strongest and most important result shows a protocol that achieves interactive, concurrent CCA-secure message transmission with a reverse firewall---i.e., CCA-secure message transmission on a possibly compromised machine! Surprisingly, this protocol is quite efficient and simple, requiring only four rounds and a small constant number of public-key operations for each party. It could easily be used in practice. Behind this result is a technical composition theorem that shows how key agreement with a sufficiently secure reverse firewall can be used to construct a message-transmission protocol with its own secure reverse firewall.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
reverse firewallsexfiltrationsecure message transmission
Contact author(s)
noahsd @ gmail com
History
2016-02-16: last of 2 revisions
2015-06-08: received
See all versions
Short URL
https://ia.cr/2015/548
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/548,
      author = {Yevgeniy Dodis and Ilya Mironov and Noah Stephens-Davidowitz},
      title = {Message Transmission with Reverse Firewalls---Secure Communication on Corrupted Machines},
      howpublished = {Cryptology ePrint Archive, Paper 2015/548},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/548}},
      url = {https://eprint.iacr.org/2015/548}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.