Document Open Access Logo

How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts

Authors Thibaut Horel, Sunoo Park, Silas Richelson, Vinod Vaikuntanathan

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.42.pdf
  • Filesize: 0.59 MB
  • 20 pages

Document Identifiers

Author Details

Thibaut Horel
  • Harvard University, Cambridge, MA, USA
Sunoo Park
  • MIT, Cambridge, MA, USA
Silas Richelson
  • University of California, Riverside, CA, USA
Vinod Vaikuntanathan
  • MIT, Cambridge, MA, USA

Funding

  • Horel, Thibaut: Supported, in part, by the National Science Foundation under grants CAREER IIS-1149662, and CNS-1237235, by the Office of Naval Research under grants YIP N00014-14-1-0485 and N00014-17-1-2131, and by a Google Research Award.
  • Park, Sunoo: Supported by the Center for Science of Information STC (CSoI), an NSF Science and Technology Center (grant agreement CCF-0939370), MACS project NSF grant CNS-1413920, and a Simons Investigator Award Agreement dated 2012-06-05.
  • Vaikuntanathan, Vinod: Supported in part by NSF Grants CNS-1350619, CNS-1414119 and CNS-1718161, Alfred P. Sloan Research Fellowship, Microsoft Faculty Fellowship and a Steven and Renee Finn Career Development Chair from MIT.

Cite As Get BibTex

Thibaut Horel, Sunoo Park, Silas Richelson, and Vinod Vaikuntanathan. How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.42

Abstract

In this work, we examine the feasibility of secure and undetectable point-to-point communication when an adversary (e.g., a government) can read all encrypted communications of surveillance targets. We consider a model where the only permitted method of communication is via a government-mandated encryption scheme, instantiated with government-mandated keys. Parties cannot simply encrypt ciphertexts of some other encryption scheme, because citizens caught trying to communicate outside the government's knowledge (e.g., by encrypting strings which do not appear to be natural language plaintexts) will be arrested. The one guarantee we suppose is that the government mandates an encryption scheme which is semantically secure against outsiders: a perhaps reasonable supposition when a government might consider it advantageous to secure its people's communication against foreign entities. But then, what good is semantic security against an adversary that holds all the keys and has the power to decrypt?
We show that even in the pessimistic scenario described, citizens can communicate securely and undetectably. In our terminology, this translates to a positive statement: all semantically secure encryption schemes support subliminal communication. Informally, this means that there is a two-party protocol between Alice and Bob where the parties exchange ciphertexts of what appears to be a normal conversation even to someone who knows the secret keys and thus can read the corresponding plaintexts. And yet, at the end of the protocol, Alice will have transmitted her secret message to Bob. Our security definition requires that the adversary not be able to tell whether Alice and Bob are just having a normal conversation using the mandated encryption scheme, or they are using the mandated encryption scheme for subliminal communication.
Our topics may be thought to fall broadly within the realm of steganography. However, we deal with the non-standard setting of an adversarially chosen distribution of cover objects (i.e., a stronger-than-usual adversary), and we take advantage of the fact that our cover objects are ciphertexts of a semantically secure encryption scheme to bypass impossibility results which we show for broader classes of steganographic schemes. We give several constructions of subliminal communication schemes under the assumption that key exchange protocols with pseudorandom messages exist (such as Diffie-Hellman, which in fact has truly random messages).

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic protocols
Keywords
  • Backdoored Encryption
  • Steganography

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, and Karn Seth. On the Impossibility of Cryptography with Tamperable Randomness. In CRYPTO 2014, Proceedings, Part I, volume 8616 of Lecture Notes in Computer Science, pages 462-479. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44371-2_26.
  2. Michael Backes and Christian Cachin. Public-Key Steganography with Active Attacks. In TCC 2005, Proceedings, volume 3378 of Lecture Notes in Computer Science, pages 210-226. Springer, 2005. URL: http://dx.doi.org/10.1007/978-3-540-30576-7_12.
  3. Boaz Barak, Russell Impagliazzo, and Avi Wigderson. Extracting Randomness Using Few Independent Sources. In 45th Symposium on Foundations of Computer Science (FOCS 2004), Proceedings, pages 384-393, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.29.
  4. Mihir Bellare, Joseph Jaeger, and Daniel Kane. Mass-surveillance without the State: Strongly Undetectable Algorithm-Substitution Attacks. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (CCS) 2015, pages 1431-1440. ACM, 2015. URL: http://dx.doi.org/10.1145/2810103.2813681.
  5. Mihir Bellare, Kenneth G. Paterson, and Phillip Rogaway. Security of Symmetric Encryption against Mass Surveillance. In CRYPTO 2014, Proceedings, Part I, volume 8616 of Lecture Notes in Computer Science, pages 1-19. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44371-2_1.
  6. Sebastian Berndt and Maciej Liśkiewicz. Algorithm Substitution Attacks from a Steganographic Perspective. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017, pages 1649-1660. ACM, 2017. URL: http://dx.doi.org/10.1145/3133956.3133981.
  7. Christian Cachin. An Information-Theoretic Model for Steganography. In David Aucsmith, editor, Information Hiding, Second International Workshop, Portland, Oregon, USA, April 14-17, 1998, Proceedings, volume 1525 of Lecture Notes in Computer Science, pages 306-318. Springer, 1998. URL: http://dx.doi.org/10.1007/3-540-49380-8_21.
  8. Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 670-683, 2016. Google Scholar
  9. Benny Chor and Oded Goldreich. Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity. SIAM J. Comput., 17(2):230-261, 1988. URL: http://dx.doi.org/10.1137/0217015.
  10. Aloni Cohen and Saleet Klein. The GGM Function Family Is a Weakly One-Way Family of Functions. In Theory of Cryptography - 14th International Conference, TCC 2016-B, Part I, volume 9985 of Lecture Notes in Computer Science, pages 84-107, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53641-4_4.
  11. Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Trans. Information Theory, 22(6):644-654, 1976. URL: http://dx.doi.org/10.1109/TIT.1976.1055638.
  12. Yevgeniy Dodis, Ariel Elbaz, Roberto Oliveira, and Ran Raz. Improved Randomness Extraction from Two Independent Sources. In 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, Proceedings, pages 334-344, 2004. Google Scholar
  13. Yevgeniy Dodis, Chaya Ganesh, Alexander Golovnev, Ari Juels, and Thomas Ristenpart. A Formal Treatment of Backdoored Pseudorandom Generators. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Proceedings, Part I, volume 9056 of Lecture Notes in Computer Science, pages 101-126. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-46800-5_5.
  14. Oded Goldreich. The ggm construction does not yield correlation intractable function ensembles. In Oded Goldreich, editor, Studies in Complexity and Cryptography, pages 98-108. Springer-Verlag, Berlin, Heidelberg, 2011. URL: http://dl.acm.org/citation.cfm?id=2028116.2028129.
  15. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. J. ACM, 33(4):792-807, 1986. URL: http://dx.doi.org/10.1145/6490.6503.
  16. Nicholas J. Hopper, John Langford, and Luis von Ahn. Provably Secure Steganography. In CRYPTO 2002, Santa Barbara, California, USA, Proceedings, volume 2442 of Lecture Notes in Computer Science, pages 77-92. Springer, 2002. URL: http://dx.doi.org/10.1007/3-540-45708-9_6.
  17. Thibaut Horel, Sunoo Park, Silas Richelson, and Vinod Vaikuntanathan. How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts. Cryptology ePrint Archive, Report 2018/212, 2018. URL: https://eprint.iacr.org/2018/212.
  18. Silvio Micali. ALGORAND: the efficient and democratic ledger. CoRR, abs/1607.01341, 2016. URL: http://arxiv.org/abs/1607.01341.
  19. Thomas Mittelholzer. An Information-Theoretic Approach to Steganography and Watermarking. In Information Hiding, Third International Workshop, IH'99, Proceedings, volume 1768 of Lecture Notes in Computer Science, pages 1-16. Springer, 1999. URL: http://dx.doi.org/10.1007/10719724_1.
  20. Gustavus J. Simmons. The Prisoners' Problem and the Subliminal Channel. In CRYPTO 1983., pages 51-67. Plenum Press, New York, 1983. Google Scholar
  21. Luca Trevisan and Salil P. Vadhan. Extracting Randomness from Samplable Distributions. In FOCS 2000, Redondo Beach, California, USA, pages 32-42, 2000. Google Scholar
  22. Emanuele Viola. Extractors for Circuit Sources. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pages 220-229. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.20.
  23. Luis von Ahn and Nicholas J. Hopper. Public-Key Steganography. In EUROCRYPT 2004, Proceedings, volume 3027 of Lecture Notes in Computer Science, pages 323-341. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-24676-3_20.
  24. Adam L. Young and Moti Yung. Cryptovirology: Extortion-Based Security Threats and Countermeasures. In 1996 IEEE Symposium on Security and Privacy, May 6-8, 1996, Oakland, CA, USA, pages 129-140. IEEE Computer Society, 1996. URL: http://dx.doi.org/10.1109/SECPRI.1996.502676.
  25. Adam L. Young and Moti Yung. The Dark Side of "Black-Box" Cryptography, or: Should We Trust Capstone? In CRYPTO 1996, Proceedings, volume 1109 of Lecture Notes in Computer Science, pages 89-103. Springer, 1996. URL: http://dx.doi.org/10.1007/3-540-68697-5_8.
  26. Adam L. Young and Moti Yung. Kleptography: Using Cryptography Against Cryptography. In EUROCRYPT '97, Proceedings, volume 1233 of Lecture Notes in Computer Science, pages 62-74. Springer, 1997. URL: http://dx.doi.org/10.1007/3-540-69053-0_6.
  27. Jan Zöllner, Hannes Federrath, Herbert Klimant, Andreas Pfitzmann, Rudi Piotraschke, Andreas Westfeld, Guntram Wicke, and Gritta Wolf. Modeling the Security of Steganographic Systems. In David Aucsmith, editor, Information Hiding, Second International Workshop, Portland, Oregon, USA, April 14-17, 1998, Proceedings, volume 1525 of Lecture Notes in Computer Science, pages 344-354. Springer, 1998. URL: http://dx.doi.org/10.1007/3-540-49380-8_24.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact