Cliptography: Post-Snowden Cryptography

ABSTRACT

This tutorial will present a systematic overview of {\em kleptography}: stealing information subliminally from black-box cryptographic implementations; and {\em cliptography}: defending mechanisms that clip the power of kleptographic attacks via specification re-designs (without altering the underlying algorithms). Despite the laudatory history of development of modern cryptography, applying cryptographic tools to reliably provide security and privacy in practice is notoriously difficult. One fundamental practical challenge, guaranteeing security and privacy without explicit trust in the algorithms and implementations that underlie basic security infrastructure, remains. While the dangers of entertaining adversarial implementation of cryptographic primitives seem obvious, the ramifications of such attacks are surprisingly dire: it turns out that -- in wide generality -- adversarial implementations of cryptographic (both deterministic and randomized) algorithms may leak private information while producing output that is statistically indistinguishable from that of a faithful implementation. Such attacks were formally studied in Kleptography. Snowden revelations has shown us how security and privacy can be lost at a very large scale even when traditional cryptography seems to be used to protect Internet communication, when Kleptography was not taken into consideration. We will first explain how the above-mentioned Kleptographic attacks can be carried out in various settings. We will then introduce several simple but rigorous immunizing strategies that were inspired by folklore practical wisdoms to protect different algorithms from implementation subversion. Those strategies can be applied to ensure security of most of the fundamental cryptographic primitives such as PRG, digital signatures, public key encryptions against kleptographic attacks when they are implemented accordingly. Our new design principles may suggest new standardization methods that help reducing the threats of subverted implementation. We also hope our tutorial to stimulate a community-wise efforts to further tackle the fundamental challenge mentioned at the beginning.

References

1. Mihir Bellare, Joseph Jaeger, and Daniel Kane. 2015. Mass-surveillance without the State: Strongly Undetectable Algorithm-Substitution Attacks ACM CCS 15, bibfieldeditorIndrajit Ray, Ninghui Li, and Christopher Kruegel: (Eds.). ACM Press, 1431--1440.
2. Mihir Bellare, Kenneth G. Paterson, and Phillip Rogaway. 2014. Security of Symmetric Encryption against Mass Surveillance CRYPTO 2014, Part I (LNCS), bibfieldeditorJuan A. Garay and Rosario Gennaro (Eds.), Vol. Vol. 8616. Springer, Heidelberg, 1--19. https://doi.org/10.1007/978--3--662--44371--2_1
3. Stephen Checkoway, Shaanan Cohney, Christina Garman, Matthew Green, Nadia Heninger, Jacob Maskiewicz, Eric Rescorla, Hovav Shacham, and Ralf-Philipp Weinmann 2016. A Systematic Analysis of the Juniper Dual EC Incident Proceedings of ACM CCS 2016. shownoteFull version available at http://eprint.iacr.org/2016/376.
4. Stephen Checkoway, Ruben Niederhagen, Adam Everspaugh, Matthew Green, Tanja Lange, Thomas Ristenpart, Daniel J. Bernstein, Jake Maskiewicz, Hovav Shacham, and Matthew Fredrikson. 2014. On the Practical Exploitability of Dual EC in TLS Implementations Proceedings of the 23rd USENIX Security Symposium, San Diego, CA, USA, August 20--22, 2014. 319--335.
5. Jean Paul Degabriele, Kenneth G. Paterson, Jacob C. N. Schuldt, and Joanne Woodage 2016. Backdoors in Pseudorandom Number Generators: Possibility and Impossibility Results CRYPTO 2016, Part I (LNCS), bibfieldeditorMatthew Robshaw and Jonathan Katz (Eds.), Vol. Vol. 9814. Springer, Heidelberg, 403--432. https://doi.org/10.1007/978--3--662--53018--4_15
6. Yevgeniy Dodis, Ilya Mironov, and Noah Stephens-Davidowitz. 2016. Message Transmission with Reverse Firewalls--Secure Communication on Corrupted Machines. In CRYPTO 2016, Part I (LNCS), bibfieldeditorMatthew Robshaw and Jonathan Katz (Eds.), Vol. Vol. 9814. Springer, Heidelberg, 341--372. https://doi.org/10.1007/978--3--662--53018--4_13
7. Nicholas J. Hopper, John Langford, and Luis von Ahn. 2002. Provably Secure Steganography. In CRYPTO 2002 (LNCS), bibfieldeditorMoti Yung (Ed.), Vol. Vol. 2442. Springer, Heidelberg, 77--92.
8. Jeff Larson, Nicole Perlroth, and Scott Shane. 2013. Revealed: The NSA's secret campaign to crack, undermine internet security. Pro-Publica. (2013). shownotehttp://www.propublica.org/article/the-nsas-secret-campaign-to-crack-undermine-internet-encryption.
9. Ilya Mironov and Noah Stephens-Davidowitz 2015. Cryptographic Reverse Firewalls. In EUROCRYPT 2015, Part II (LNCS), bibfieldeditorElisabeth Oswald and Marc Fischlin (Eds.), Vol. Vol. 9057. Springer, Heidelberg, 657--686. https://doi.org/10.1007/978--3--662--46803--6_22
10. Nicole Perlroth, Jeff Larson, and Scott Shane. 2013. N.S.A. able to foil basic safeguards of privacy on web. The New York Times. (2013). shownotehttp://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html.
11. Alexander Russell, Qiang Tang, Moti Yung, and Hong-Sheng Zhou. 2016. Cliptography: Clipping the Power of Kleptographic Attacks ASIACRYPT 2016, Part II (LNCS), bibfieldeditorJung Hee Cheon and Tsuyoshi Takagi (Eds.), Vol. Vol. 10032. Springer, Heidelberg, 34--64. https://doi.org/10.1007/978--3--662--53890--6_2
12. Alexander Russell, Qiang Tang, Moti Yung, and Hong-Sheng Zhou. 2017. Generic Semantic Security against a Kleptographic Adversary Proceedings of the 24nd ACM SIGSAC Conference on Computer and Communications Security, Dallas, TX, USA, October 30-November 4, 2017.
13. Adam Young and Moti Yung 1996. The Dark Side of "Black-Box" Cryptography, or: Should We Trust Capstone? CRYPTO'96 (LNCS), bibfieldeditorNeal Koblitz (Ed.), Vol. Vol. 1109. Springer, Heidelberg, 89--103.
14. Adam Young and Moti Yung 1997. Kleptography: Using Cryptography Against Cryptography EUROCRYPT'97 (LNCS), bibfieldeditorWalter Fumy (Ed.), Vol. Vol. 1233. Springer, Heidelberg, 62--74.
15. Kim Zetter. 2015. Secret Code Found in Juniper's Firewalls Shows Risk of Government Backdoors. (December 2015). endthebibliography

Index Terms

• Security and privacy

  • Cryptography