Cryptology ePrint Archive: Report 2014/438

Security of Symmetric Encryption against Mass Surveillance

Mihir Bellare and Kenneth Paterson and Phillip Rogaway

Abstract: 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.

Category / Keywords: secret-key cryptography / Algorithm-substitution attacks, big brother, kleptography, mass surveillance, symmetric encryption

Original Publication (with major differences): IACR-CRYPTO-2014

Date: received 7 Jun 2014, last revised 24 Aug 2015

Contact author: mihir at eng ucsd edu

Available format(s): PDF | BibTeX Citation

Version: 20150824:221250 (All versions of this report)

Short URL: ia.cr/2014/438

Discussion forum: Show discussion | Start new discussion