Paper 2015/748

A More Cautious Approach to Security Against Mass Surveillance

Jean Paul Degabriele, Pooya Farshim, and Bertram Poettering


At CRYPTO 2014 Bellare, Paterson, and Rogaway (BPR) presented a formal treatment of symmetric encryption in the light of algorithm substitution attacks (ASAs), which may be employed by `big brother' entities for the scope of mass surveillance. Roughly speaking, in ASAs big brother may bias ciphertexts to establish a covert channel to leak vital cryptographic information. In this work, we identify a seemingly benign assumption implicit in BPR's treatment and argue that it artificially (and severely) limits big brother's capabilities. We then demonstrate the critical role that this assumption plays by showing that even a slight weakening of it renders the security notion completely unsatisfiable by any, possibly deterministic and/or stateful, symmetric encryption scheme. We propose a refined security model to address this shortcoming, and use it to restore the positive result of BPR, but caution that this defense does not stop most other forms of covert-channel attacks.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in FSE 2015
mass surveillancealgorithm substitution attacksymmetric encryptioncovert channel.
Contact author(s)
jpdega @ gmail com
pooya farshim @ gmail com
bertram poettering @ rhul ac uk
2015-08-07: last of 2 revisions
2015-07-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jean Paul Degabriele and Pooya Farshim and Bertram Poettering},
      title = {A More Cautious Approach to Security Against Mass Surveillance},
      howpublished = {Cryptology ePrint Archive, Paper 2015/748},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.