Algorithm Substitution Attacks from a Steganographic Perspective
This work provides a rigorous theoretical foundation for understanding ASAs, which are critical for security in cryptographic implementations, though it is incremental as it builds on prior models and results.
The paper tackles the problem of algorithm substitution attacks (ASAs) in cryptography by analyzing them from a steganographic perspective, establishing a formal equivalence between successful ASAs and secure stegosystems on specific channels.
The goal of an algorithm substitution attack (ASA), also called a subversion attack (SA), is to replace an honest implementation of a cryptographic tool by a subverted one which allows to leak private information while generating output indistinguishable from the honest output. Bellare, Paterson, and Rogaway provided at CRYPTO'14 a formal security model to capture this kind of attacks and constructed practically implementable ASAs against a large class of symmetric encryption schemes. At CCS'15, Ateniese, Magri, and Venturi extended this model to allow the attackers to work in a fully-adaptive and continuous fashion and proposed subversion attacks against digital signature schemes. Both papers also showed the impossibility of ASAs in cases where the cryptographic tools are deterministic. Also at CCS'15, Bellare, Jaeger, and Kane strengthened the original model and proposed a universal ASA against sufficiently random encryption schemes. In this paper we analyze ASAs from the perspective of steganography - the well known concept of hiding the presence of secret messages in legal communications. While a close connection between ASAs and steganography is known, this lacks a rigorous treatment. We consider the common computational model for secret-key steganography and prove that successful ASAs correspond to secure stegosystems on certain channels and vice versa. This formal proof allows us to conclude that ASAs are stegosystems and to "rediscover" several results concerning ASAs known in the steganographic literature.