[Cryptography] attacking algorithms with substitution

[ianG]

h/t to cryptogram: http://eprint.iacr.org/2014/438

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

...