Paper 2015/808

Mass-surveillance without the State: Strongly Undetectable Algorithm-Substitution Attacks

Mihir Bellare, Joseph Jaeger, and Daniel Kane

Abstract

We present new algorithm-substitution attacks (ASAs) on symmetric encryption that improve over prior ones in two ways. First, while prior attacks only broke a sub-class of randomized schemes having a property called coin injectivity, our attacks break ALL randomized schemes. Second, while prior attacks are stateful, ours are stateless, achieving a notion of strong undetectability that we formalize. Together this shows that ASAs are an even more dangerous and powerful mass surveillance method than previously thought. Our work serves to increase awareness about what is possible with ASAs and to spur the search for deterrents and counter-measures.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. MAJOR revision.22nd ACM Conference on Computer and Communications Security (CCS), 2015
DOI
10.1145/2810103.2813681
Keywords
mass surveillancealgorithm substitution attackskleptographysymmetric encryption
Contact author(s)
mihir @ eng ucsd edu
History
2017-05-02: last of 3 revisions
2015-08-14: received
See all versions
Short URL
https://ia.cr/2015/808
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/808,
      author = {Mihir Bellare and Joseph Jaeger and Daniel Kane},
      title = {Mass-surveillance without the State: Strongly Undetectable Algorithm-Substitution Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2015/808},
      year = {2015},
      doi = {10.1145/2810103.2813681},
      note = {\url{https://eprint.iacr.org/2015/808}},
      url = {https://eprint.iacr.org/2015/808}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.