International Association
for Cryptologic Research

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.