Algorithm Substitution Attacks from a Steganographic Perspective


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.

Original languageEnglish
Title of host publicationCCS '17 Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security
Number of pages12
Publication date30.10.2017
ISBN (Print)978-1-4503-4946-8
Publication statusPublished - 30.10.2017
EventComputer and Communications Security - Dallas, United States
Duration: 30.10.201703.11.2017


Dive into the research topics of 'Algorithm Substitution Attacks from a Steganographic Perspective'. Together they form a unique fingerprint.

Cite this