Paper 2014/438

Security of Symmetric Encryption against Mass Surveillance

Mihir Bellare, Kenneth Paterson, and Phillip Rogaway


Motivated by revelations concerning population-wide surveillance of encrypted communications, we formalize and investigate the resistance of symmetric encryption schemes to mass surveillance. The focus is on algorithm-substitution attacks (ASAs), where a subverted encryption algorithm replaces the real one. We assume that the goal of ``big~brother'' is undetectable subversion, meaning that ciphertexts produced by the subverted encryption algorithm should reveal plaintexts to big~brother yet be indistinguishable to users from those produced by the real encryption scheme. We formalize security notions to capture this goal and then offer both attacks and defenses. In the first category we show that successful (from the point of view of big brother) ASAs may be mounted on a large class of common symmetric encryption schemes. In the second category we show how to design symmetric encryption schemes that avoid such attacks and meet our notion of security. The lesson that emerges is the danger of choice: randomized, stateless schemes are subject to attack while deterministic, stateful ones are not.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2014
Algorithm-substitution attacksbig brotherkleptographymass surveillancesymmetric encryption
Contact author(s)
mihir @ eng ucsd edu
2015-08-24: last of 3 revisions
2014-06-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Kenneth Paterson and Phillip Rogaway},
      title = {Security of Symmetric Encryption against Mass Surveillance},
      howpublished = {Cryptology ePrint Archive, Paper 2014/438},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.