---
abstract: '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.'
author:
- Sebastian Berndt
- Maciej Liśkiewicz
title: |
    Algorithm Substitution Attacks from a\
    Steganographic Perspective
---

Introduction
============

The publication of secret internal documents of the NSA by Edward Snowden (see [e.g.]{}[@ball2013revealed; @greenwald2014no; @perlroth2013nsa]) allowed the cryptographic community a unique insight into some well-kept secrets of one of the world’s largest security agency. Two conclusions may be drawn from these reveals:

-   On the one hand, even a large organization such as the NSA seems not to be able to break well established implementations of cryptographic primitives such as RSA or AES.

-   On the other hand, the documents clearly show that the NSA develops methods and techniques to *circumvent* the well established security notions by [e.g.]{}manipulating standardization processes ([e.g.]{}issues surrounding the number generator `Dual_EC_DRBG` [@checkoway2014dual; @schneier2007did; @shumow2007back]) or reason about metadata.

This confirms that the security guarantees provided by the cryptographic community are sound, but also indicates that some security definitions are too narrow to evade all possible attacks, including (non-)intentional improper handling of theoretically sound cryptographic protocols. A very realistic attack which goes beyond the common framework is a modification of an appropriate implementation of a secure protocol. The modified implementation should remain indistinguishable from a truthful one and its aim is to allow leakage of secret information during subsequent runs of the subverted protocol. Attacks of this kind are known in the literature [@young1997kleptography; @young1996dark; @bellare2015asa; @bellare2014asa; @ateniese2015sig; @russell2016cliptography] and an overview on this topic is given in the current survey [@schneier2015survey] by @schneier2015survey

A powerful class of such attacks that we will focus on – coined *secretly embedded trapdoor with universal protection (SETUP) attacks* – was presented over twenty years ago by Young and Yung in the *kleptographic* model framework [@young1996dark; @young1997kleptography]. The model is meant to capture a situation where an adversary (or “big brother” as we shall occasionally say) has the opportunity to implement (and, indeed, “mis-implement” or subvert) a basic cryptographic tool. The difficulty in detecting such an attack is based on the hardness of program verification. By using *closed source* software, the user must trust the developers that their implementation of cryptographic primitives is truthful and does not contain any backdoors. This is especially true for hardware-based cryptography [@bellare2014asa]. But it is difficult to verify this property. Even if the software is *open source* – the source code is publicly available – the sheer complexity of cryptographic implementations allows only very specialized experts to be able to judge these implementations. Two of the most prominent bugs of the widely spread cryptographic library `OpenSSL`[^1] – the *Heartbleed bug* and Debian’s faulty implementation of the pseudorandom number generator – remained undiscovered for more than two years [@schneier2015survey].

Inspired by Snowden’s reveals, the recent developments reignited the interest in these kind of attacks. @bellare2014asa named them *algorithm substitution attacks (ASA)* and showed several attacks on certain symmetric encryption schemes [@bellare2014asa]. Note that they defined a very weak model, where the only goal of the attacker was to distinguish between two ciphertexts, but mostly used a stronger scenario with the aim to recover the encryption key. @degabriele2015asa criticized the model of [@bellare2014asa] by pointing out the results crucially rely on the fact that a subverted encryption algorithm always needs to produce valid ciphertexts (the *decryptability assumption*) and proposed a refined security notion [@degabriele2015asa]. The model of algorithm substitution attacks introduced in [@bellare2014asa] was extended to signature schemes by @ateniese2015sig in [@ateniese2015sig]. Simultaneously, @bellare2015asa [@bellare2015asa] strengthened the result of [@bellare2014asa] by enforcing that the attack needs to be stateless.

In this paper we thoroughly analyze (general) ASAs from the *steganographic* point of view. The principle goal of steganography is to hide information in unsuspicious communication such that no observer can distinguish between normal documents and documents that carry additional information. Modern steganography was first made popular due to the prisoners’ problem by Simmons [@simmons1984prisoners] but, interestingly, the model was inspired by detecting the risk of ASAs during development of the SALT2 treaty between the Soviet Union and the United States in the late seventies [@simmons1998history]. This sheds some light on the inherent relationship between these two frameworks which is well known in the literature (see [e.g.]{}[@young1996dark; @young1997kleptography; @russell2016destroying]). A related result showing that so called *decoy password vaults* are very closely related to stegosystems on a certain kind of channels was presented by @pasquini2017decoy in [@pasquini2017decoy].

Our main achievement is providing a strict relationship between secure algorithm substitution attacks and the common computational model for secret-key steganography. Particularly, we 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” results of [@bellare2014asa; @bellare2015asa; @ateniese2015sig] concerning ASAs.

The computational model for steganography used in this paper was first presented by Hopper, Langford, and von Ahn [@hopper2002provably; @hopper2009provably] and independently proposed by Katzenbeisser and Petitcolas [@katzenbeisser2002defining]. A *stegosystem* consists of an encoder and a decoder sharing a key. The encoder’s goal is to *embed* a secret message into a sequence of documents which are send via a public *communication channel* ${\mathcal{C}}$ monitored by an adversary (often called the *warden* due to the prisoners problem of Simmons [@simmons1984prisoners]). The warden wants to distinguish documents that carry no secret information from those sent by the encoder. If all polynomial-time (in the security parameter $\kappa$) wardens fail to distinguish these cases, we say that the stegosystem is *secure*. If the decoder is able to reconstruct the secret message from the sequence send by the encoder, the system is called *reliable*.

Our Results {#our-results .unnumbered}
-----------

We first investigate algorithm substitution attacks against symmetric encryption schemes in the framework by @bellare2015asa [@bellare2015asa]. We model encryption schemes as steganographic channels in appropriate way which allows to relate algorithm substitution attacks with steganographic systems and vice versa. This leads to the following result.

\[thm:stego:asa:iff:on:ses\] Assume that $\operatorname{\mathsf{SES}}$ is a symmetric encryption scheme. Then there exists an indistinguishable and reliable algorithm substitution attack against $\operatorname{\mathsf{SES}}$ if and only if there exists a secure and reliable stegosystem on the channel determined by $\operatorname{\mathsf{SES}}$.

The proof of the theorem is constructive in the sense that we give an explicit construction of an algorithm substitution attack against $\operatorname{\mathsf{SES}}$ from a stegosystem and vice versa. As conclusion we provide a generic ASA against *every* symmetric encryption scheme $\operatorname{\mathsf{SES}}$ whose insecurity is negligible if, roughly speaking, $\operatorname{\mathsf{SES}}$ has sufficiently large min-entropy. Our algorithm against $\operatorname{\mathsf{SES}}$ achieves almost the same performance as the construction of @bellare2015asa (see Theorem 4.1 and Theorem 4.2 in [@bellare2015asa] and also our discussion in Section \[Sec:ASA:against:encrypted:as:stego\]).

Next, we generalize our construction and show a generic algorithm substitution attack $\operatorname{\mathsf{ASA}}$ against any (polynomial-time) randomized algorithm $\operatorname{\mathsf{R}}$ which, with hardwired secret $s$, takes inputs $x$ and generates outputs $y$. Algorithm $\operatorname{\mathsf{ASA}}$, using a hidden hardwired random key ${\textit{ak}}$, returns upon the secret $s$ the sequence $\tilde{y}_1,\tilde{y}_2,\ldots$ such that the output is indistinguishable from $\operatorname{\mathsf{R}}(s,x_1), \operatorname{\mathsf{R}}(s,x_2),\ldots$ and $\tilde{y}_1,\tilde{y}_2,\ldots$ embeds the secret $s$. From this result we conclude:

\[thm:generic-attack\] There exists a generic algorithm substitution attack $\operatorname{\mathsf{ASA}}$ that allows an undetectable subversion of any cryptographic primitive of sufficiently large min-entropy.

\[thm:min-entropy\] Let $\Pi$ be a cryptographic primitive consisting with algorithms $(\Pi.A_{1},\Pi.A_{2},\ldots,$ $ \Pi.A_{r})$ such that $\{A_{i}\mid i\in
  I\}$ for some $I\subseteq \{1,\ldots,r\}$ are deterministic. Then there is no ASA on $\Pi$ which subverts only algorithms $\{A_{i}\mid i\in I\}$.

As a corollary we obtain the result of @ateniese2015sig (Theorem 1 in [@ateniese2015sig]) that for every *coin-injective* signature scheme, there is a successful algorithm substitution attack of negligible insecurity. Moreover we get (Theorem 2 in [@ateniese2015sig]) that for every *coin-extractable* signature scheme, there is a successful and secure ASA. We can conclude also (Theorem 3 in [@ateniese2015sig]) that *unique signature schemes* are resistant to ASAs fulfilling the *verifiability condition*. Roughly speaking the last property means that each message has exactly one signature and the ASA can only produce valid signatures.

We furthermore introduce the concept of *universal ASAs* that can be used without a detailed description of the implementation of the underlying cryptographic primitive and note that almost all known ASAs belong to this class. Based upon this definition, we prove the following upper bound on the information that can be embedded into a single ciphertext:

\[thm:universal:bound\] No universal ASA is able to embed more than $\mathcal{O}(1)\cdot \log(\kappa)$ bits of information into a single ciphertext.

The paper is organized as follows. Section \[sec:prelim\] contains the basic preliminaries and notations that we use throughout this work, Section \[sec:asa\] presents the formal definitions of algorithm substitution attacks, and Section \[sec:stego\] gives the necessary background on steganography. In order to relate ASAs and steganography, we make use of an appropriate channel for symmetric encryption schemes defined in Section \[sec:channel\]. The proof of Theorem \[thm:stego:asa:iff:on:ses\] is given in Section \[Sec:ASA:against:encrypted:as:stego\], where one direction is contained in Theorem \[thm:asa:on:ses:impl:stego\] and the other direction is given as Theorem \[thm:ses:on:ses:impl:stego\]. We generalize our results to arbitrary randomized algorithms in Section \[sec:general\]. Combining the positive results of Theorem \[thm:generic-attack:against:R\] with the generic stegosystem provided by Theorem \[thm:rejsam:secure\] allows us to conclude Theorem \[thm:generic-attack\]. The negative results of Theorem \[thm:no-attack:against:R\] directly give Theorem \[thm:min-entropy\]. Finally, Section \[sec:bound\] defines universal ASAs and contains the upper bound on the transmission rate of these ASAs via a sequence of lemmata that results in Corollary \[cor:bound\] implying Theorem \[thm:universal:bound\].

Basic Preliminaries and Notations {#sec:prelim}
=================================

We use the following standard notations. A function $f\colon {\mathbb{N}}\to {\mathbb{N}}$ is *negligible*, if for all $c\in {\mathbb{N}}$, there is an $n_{0}\in {\mathbb{N}}$ such that $f(n) < n^{-c}$ for all $n\geq n_{0}$. The set of all strings of length $n$ on an alphabet $\Sigma$ is denoted by $\Sigma^{n}$ and the set of all strings of length at most $n$ is denoted by $\Sigma^{\leq
  n}:=\cup_{i=0}^{n}\Sigma^{i}$. If $S$ is a set, $x\gets S$ denotes the uniform random assignment of an element of $S$ to $x$. If $\mathsf{A}$ is a randomized algorithm, $x\gets \mathsf{A}$ denotes the random assignment (with regard to the internal randomness of $\mathsf{A}$) of the output of $\mathsf{A}$ to $x$. The *min-entropy* measures the amount of randomness of a probability distribution $D$ and is defined as ${H_{\infty}}(D)=\inf_{x\in \operatorname{supp}(D)}\{-\log \Pr_{D}(x)\}$, where $\operatorname{supp}(D)$ is the support of $D$. Moreover, PPTM stands for probabilistic polynomial-time Turing machine.

A *symmetric encryption scheme* $\operatorname{\mathsf{SES}}$ is a triple of probabilistic polynomial-time algorithms $({\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Gen}}},{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}},{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Dec}}})$ with parameters ${\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)$ describing the length of the encrypted message and ${\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{cl}}}(\kappa)$ describing the length of a generated cipher message. The algorithms have the following properties:

-   The *key generator* ${\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Gen}}}$ produces upon input $1^{\kappa}$ a key $k$ with $|k|=\kappa$.

-   The *encryption algorithm* ${\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}}$ takes as input the key $k$ and a message $m\in \{0,1\}^{{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$ of length ${\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)$ and produces a *ciphertext* $c\in \{0,1\}^{{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{cl}}}(\kappa)}$ of length ${\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{cl}}}(\kappa)$.

-   The *decryption algorithm* ${\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Dec}}}$ takes as input the key $k$ and a ciphertext $c\in \{0,1\}^{{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{cl}}}(\kappa)}$ and produces a message $m'\in
      \{0,1\}^{{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$.

If the context is clear, we also write $\operatorname{\mathsf{Gen}}$, $\operatorname{\mathsf{Enc}}$, $\operatorname{\mathsf{Dec}}$, $\operatorname{\mathsf{ml}}$ and $\operatorname{\mathsf{cl}}$ without the prefix $\operatorname{\mathsf{SES}}$. We say that $(\operatorname{\mathsf{Gen}},\operatorname{\mathsf{Enc}},\operatorname{\mathsf{Dec}})$ is *reliable*, if $\operatorname{\mathsf{Dec}}(k,\operatorname{\mathsf{Enc}}(k,m))=m$ for all $k$ and all $m$.

An *cpa-attacker* $\operatorname{\mathsf{A}}$ against a symmetric encryption scheme is a PPTM that mounts *chosen-plaintext-attacks (cpa)*: It is given a challenging oracle $\operatorname{CH}$ that either equals $\operatorname{\mathsf{Enc}}_{k}$ for a randomly generated key $k$ or produces random bitstrings of length $\operatorname{\mathsf{cl}}(\kappa)$. For an integer $\lambda$, let $\operatorname{RAND}(\lambda)$ be an algorithm that returns uniformly distributed bitstrings of length $\lambda$. The goal of $\operatorname{\mathsf{A}}$ is to distinguish between those settings. Formally, this is defined via the following experiment named $\operatorname{\mathsf{CPA-Dist}}$:

attacker $\operatorname{\mathsf{A}}$, symmetric encryption scheme $\operatorname{\mathsf{SES}}=(\operatorname{\mathsf{Gen}},\operatorname{\mathsf{Enc}},\operatorname{\mathsf{Dec}})$

$k\gets \operatorname{\mathsf{Gen}}(1^{\kappa})$; $b\gets \{0,1\}$ $b' \gets \operatorname{\mathsf{A}}^{\operatorname{CH}}(1^{\kappa})$

$b=0$ [**then**]{} [ **return** $\operatorname{\mathsf{Enc}}(k,m)$]{}

A symmetric encryption scheme $\operatorname{\mathsf{SES}}$ is *cpa-secure* if for every attacker $\operatorname{\mathsf{A}}$ there is a negligible function $\operatorname{\mathsf{negl}}$ such that $$\begin{aligned}
  &\operatorname{\mathbf{Adv}}^{\operatorname{cpa}}_{\operatorname{\mathsf{SES}}}(\kappa) :=
  |\Pr[\operatorname{\mathsf{CPA-Dist}}_{\operatorname{\mathsf{A}},\operatorname{\mathsf{SES}}}(\kappa)=\textsf{true}] - 1/2|\leq
  \operatorname{\mathsf{negl}}(\kappa).\end{aligned}$$ The maximal advantage of any attacker against $\operatorname{\mathsf{SES}}$ is called the *insecurity* of $\operatorname{\mathsf{SES}}$ and is defined as $$\begin{aligned}
  \operatorname{\mathbf{InSec}}^{\operatorname{cpa}}_{\operatorname{\mathsf{SES}}}(\kappa) := \max_{\operatorname{\mathsf{A}}}\{\operatorname{\mathbf{Adv}}_{\operatorname{\mathsf{A}},\operatorname{\mathsf{SES}}}^{\operatorname{cpa}}(\kappa)\}.\end{aligned}$$

For a $\operatorname{\mathsf{SES}}=(\operatorname{\mathsf{Gen}},\operatorname{\mathsf{Enc}},\operatorname{\mathsf{Dec}})$ we will assume that it has nontrivial randomization measured by the min-entropy ${H_{\infty}}(\operatorname{\mathsf{SES}})$ of ciphertexts that is defined via $$2^{-{H_{\infty}}(\operatorname{\mathsf{SES}})} = \max_{k,m,c} \Pr[{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}}(k,m)=c].$$

For two numbers $\ell,\ell'\in {\mathbb{N}}$, denote the *set of all function* from $\{0,1\}^{\ell}$ to $\{0,1\}^{\ell'}$ by $\operatorname{\mathsf{Fun}}(\ell,\ell')$. Clearly, in order to specify a random element of $\operatorname{\mathsf{Fun}}(\ell,\ell')$, one needs $2^{\ell}\times \ell'$ bits and we can thus not use completely random functions in an efficient setting. Therefore we will use efficient functions that are indistinguishable from completely random functions. A *pseudorandom function* is a pair of PPTMs $\operatorname{\mathsf{F}}=({\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{Eval}}},{\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{Gen}}})$ such that ${\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{Gen}}}$ upon input $1^{\kappa}$ produces a key $k\in \{0,1\}^{\kappa}$. The keyed function ${\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{Eval}}}$ takes the key $k\gets {\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa})$ and a bitstring $x$ of length ${\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{in}}}(\kappa)$ and produces a string ${\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{Eval}}}_{k}(x)$ of length ${\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{out}}}(\kappa)$. An attacker, called *distinguisher* $\operatorname{\mathsf{Dist}}$, is a PPTM that upon input $1^{\kappa}$ gets oracle access to a function that either equals ${\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{Eval}}}_{k}$ for a randomly chosen key $k$ or is a completely random function $f$. The goal of $\operatorname{\mathsf{Dist}}$ is to distinguish between those cases. A pseudorandom function $\operatorname{\mathsf{F}}$ is secure if for every distinguisher $\operatorname{\mathsf{Dist}}$ there is a negligible function $\operatorname{\mathsf{negl}}$ such that $$\begin{aligned}
  &\operatorname{\mathbf{Adv}}_{\operatorname{\mathsf{Dist}},\operatorname{\mathsf{F}}}^{\operatorname{prf}}(\kappa) \ := \\ 
  & \quad \quad \left| \Pr[\operatorname{\mathsf{Dist}}^{{\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{Eval}}}_{k}}(1^{\kappa})=1] -
  \Pr[\operatorname{\mathsf{Dist}}^{f}(1^{\kappa})=1]\right| \leq \operatorname{\mathsf{negl}}(\kappa),\end{aligned}$$ where $k\gets {\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa})$ and $f\gets
\operatorname{\mathsf{Fun}}({\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{in}}}(\kappa),{\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{out}}}(\kappa))$. If $\operatorname{\mathsf{Dist}}$ outputs $1$, this means that the distinguisher $\operatorname{\mathsf{Dist}}$ believes that he deals with a truly random function.

As usual, the maximal advantage of any distinguisher against $\operatorname{\mathsf{F}}$ is called the *prf-insecurity* $\operatorname{\mathbf{InSec}}_{\operatorname{\mathsf{F}}}^{\operatorname{prf}}(\kappa)$ and defined as $$\begin{aligned}
  \operatorname{\mathbf{InSec}}_{\operatorname{\mathsf{F}}}^{\operatorname{prf}}(\kappa) := \max_{\operatorname{\mathsf{Dist}}}\{\operatorname{\mathbf{Adv}}^{\operatorname{prf}}_{\operatorname{\mathsf{Dist}},\operatorname{\mathsf{F}}}(\kappa)\}.\end{aligned}$$

Algorithm Substitution Attacks against Encryption Schemes {#sec:asa}
=========================================================

While it is certainly very useful for an attacker to be able to reconstruct the key, one can also consider situations, where the extractor should be able to extract different information from the ciphertexts or signatures. We will thus generalize the algorithm substitution attacks described in the literature to the setting, where the substituted algorithm also takes a message ${\textit{am}}$ as argument and the goal of the extractor is to derive this message from the produced ciphertext. By always setting ${\textit{am}}:= k$, this is the setting described by @bellare2015asa in [@bellare2015asa]. We thus strengthen the model of [@bellare2014asa] and [@bellare2015asa] in this sense.

Below we give in detail our definitions based upon the model proposed by Bellare et al. in [@bellare2015asa]. If the substitution attack is *stateful*, we allow the distinguisher that tries to identify the attack to also choose this state and observe the internal state of the attack. Every algorithm substitution attack thus needs to be *stateless*, as in the model of Bellare et al. in [@bellare2015asa]. Note that this is a stronger requirement than in [@bellare2014asa] and [@ateniese2015sig], as those works also allowed stateful attacks.

In our setting an *algorithm substitution attack* against a symmetric encryption scheme $\operatorname{\mathsf{SES}}=({\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Gen}}},{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}},{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Dec}}})$ is a triple of PPTMs $$\begin{array}{rcl}
  \operatorname{\mathsf{ASA}}&=&({\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Gen}}},{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}},{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Ext}}}) \\
 \end{array}$$ with parameter ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)$ for the *message length* – the length of the attacker message – and the following functionality.

-   The *key generator* ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Gen}}}$ produces upon input $1^{\kappa}$ an attacker key ${\textit{ak}}$ of length $\kappa$.

-   The *encryption algorithm* ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}$ takes an attacker key ${\textit{ak}}\in \operatorname{supp}({\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa}))$, attacker message ${\textit{am}}$ such that ${\textit{am}}\in \{0,1\}^{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$, an encryption key $k\in \operatorname{supp}({\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Gen}}}$ $(1^{\kappa}))$, an encryption message $m\in \{0,1\}^{{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$, and a state $\sigma\in \{0,1\}^{*}$ and produces a ciphertext $c$ of length ${\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{cl}}}(\kappa)$ and a new state $\sigma'$.

-   The *extraction algorithm* ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Ext}}}$ takes as input an attacker key ${\textit{ak}}\in \operatorname{supp}({\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa}))$ and $\ell =
                                    {\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)$ a ciphertext $c_{1},\ldots,c_{\ell}$ with $c_{i}\in
     \{0,1\}^{{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{cl}}}(\kappa)}$ and produces an attacker message ${\textit{am}}'$.

An algorithm substitution attack needs (a) to be indistinguishable from the symmetric encryption scheme and (b) should be able to reliably extract the message ${\textit{am}}$ of length ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)$ from the ciphertexts. Due to information-theoretic reasons, it might be impossible to embed the attacker message ${\textit{am}}$ into a single ciphertext: If ${\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}}$ uses $10$ bits of randomness, at most $10$ bits from ${\textit{am}}$ can be reliably embedded into a ciphertext. Hence, the algorithm substitution attack needs to produce more than one ciphertext in this case. For message $m_{1},\ldots,m_{\ell}$, the complete output, denoted as ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}^{\ell}({\textit{ak}},{\textit{am}},k,m_{1},\ldots,m_{\ell})$ is defined as follows:

1.  $\sigma = \varnothing$

2.  [**for**]{} $j=1$ to $\ell$ [**do**]{} $(c_{j},\sigma)\gets {\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}({\textit{ak}},{\textit{am}},k,m_{j},\sigma)$

3.  [**return**]{} $c_{1},\ldots,c_{\ell}$

To formally define the probability that the extractor is able to reliably extract ${\textit{am}}$ from the given ciphertexts $c_{1},\ldots,c_{\ell}$, we define its *reliability*[^2] as $1-\operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)$, where the *unreliability* $\operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}$ is given as $$\begin{aligned}
  &\max                                     \{
\Pr[{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Ext}}}({\textit{ak}},{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}^{\ell}({\textit{ak}},{\textit{am}},k,m_{1},\ldots,m_{\ell}))\neq
  {\textit{am}}]\},\end{aligned}$$ with the maximum taken over all ${\textit{ak}}\in \operatorname{supp}({\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa})), 
 {\textit{am}}\in\{0,1\}^{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$, and $m_{i}\in\{0,1\}^{{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$. The algorithm is *successful*, if there is negligible function $\operatorname{\mathsf{negl}}$ with $\operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa) \leq \operatorname{\mathsf{negl}}(\kappa).$

The indistinguishability of an ASA is defined as follows. Call a *watchdog* $\operatorname{\mathsf{Watch}}$ a PPTM that tries to distinguish the output of the attacker encryption algorithm ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}$ from the original encryption algorithm $\operatorname{\mathsf{Enc}}$. The indistinguishability is defined via the game named $\operatorname{\mathsf{ASA-Dist}}$:

watchdog $\operatorname{\mathsf{Watch}}$, algorithm substitution attack $\operatorname{\mathsf{ASA}}=({\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Gen}}}, {\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}},$ $ {\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Ext}}})$, and encryption scheme $\operatorname{\mathsf{SES}}=({\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Gen}}},{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}},{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Dec}}})$

${\textit{ak}}\gets {\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa})$; $b\gets \{0,1\}$ $b' \gets \operatorname{\mathsf{Watch}}^{\operatorname{CH}}(1^{\kappa})$ $b=0$ [**then**]{} $c\gets {\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}}(k,m)$ $(c,\sigma) \gets {\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}({\textit{ak}},{\textit{am}},k,m,\sigma)$

An algorithm substitution attack $\operatorname{\mathsf{ASA}}$ is called *indistinguishable* from the symmetric encryption scheme $\operatorname{\mathsf{SES}}$, if for every watchdog $\operatorname{\mathsf{Watch}}$, there is a negligible function $\operatorname{\mathsf{negl}}$ such that $$\begin{aligned}
  &\operatorname{\mathbf{Adv}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{Watch}}, \operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa) \
   :=\\ &\quad \quad |\Pr[\operatorname{\mathsf{ASA-Dist}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)=\textsf{true}] -1/2| 
    \leq \ \operatorname{\mathsf{negl}}(\kappa).\end{aligned}$$

The maximal advantage of any watchdog distinguishing $\operatorname{\mathsf{ASA}}$ from $\operatorname{\mathsf{SES}}$ is called the *indistinguishability* or *insecurity* of $\operatorname{\mathsf{ASA}}$ and is defined as $$\begin{aligned}
  \operatorname{\mathbf{InSec}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa) := \max_{\operatorname{\mathsf{Watch}}}\{\operatorname{\mathbf{Adv}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}^{\operatorname{enc-watch}}(\kappa)\}.\end{aligned}$$

In [@bellare2014asa], Bellare et al. proposed a (stateless) construction $\operatorname{\mathsf{ASA}}$ against all symmetric encryption schemes $\operatorname{\mathsf{SES}}$. They prove in Theorem 3 that if $\operatorname{\mathsf{SES}}$ is a randomized, stateless, coin-injective symmetric encryption scheme with randomness-length $r$ and if the ASA uses a PRF $\operatorname{\mathsf{F}}$ then for a watchdog $\operatorname{\mathsf{Watch}}$ that makes $q$ queries to its $\operatorname{CH}$ oracle we can construct an adversary $\operatorname{\mathsf{A}}$ such that $ \operatorname{\mathbf{Adv}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{Watch}}, \operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa) \le q/2^{2^r} +
\operatorname{\mathbf{Adv}}^{\operatorname{prf}}_{\operatorname{\mathsf{A}},\operatorname{\mathsf{F}}}(\kappa)$, where $\operatorname{\mathsf{A}}$ makes $q$ oracle queries and its running time is that of $\operatorname{\mathsf{Watch}}$.

Bellare et al. conclude that as long as their scheme uses a non-trivial amount of randomness, for example $r \ge 7$ bits resulting $2^r \ge 128$, Theorem 3 implies that the subversion is undetectable.

Backgrounds of Steganography {#sec:stego}
============================

The definitions of the basic steganography concepts presented in this section are essentially those of [@hopper2009provably] and [@dedic2009upper].

In order to define undetectable hidden communication, we need to introduce a notion of *unsuspicious* communication. We do this via the notion of a *channel* ${\mathcal{C}}$. A channel ${\mathcal{C}}$ on the alphabet $\Sigma$ with maximal document length ${{{\mathcal{C}}\,\!.\!\,n}}$ is a function that maps a string of previously send elements $h\in (\Sigma^{\leq {{{\mathcal{C}}\,\!.\!\,n}}})^{*}$ – the *history* – to a probability distribution upon $\Sigma^{\leq {{{\mathcal{C}}\,\!.\!\,n}}}$. We denote this probability distribution by ${\mathcal{C}}_{h}$. The elements of $\Sigma^{\leq {{{\mathcal{C}}\,\!.\!\,n}}}$ are called *documents*. As usually, we will assume that the sequences of documents are efficiently prefix-free recognizable.

A *stegosystem* $\operatorname{\mathsf{S}}$ on a family of channels $\bm{{\mathcal{C}}}=\{{\mathcal{C}}^{\kappa}\}_{\kappa\in {\mathbb{N}}}$ is a triple of probabilistic polynomial-time (according to the security parameter $\kappa$) algorithms: $$\begin{array}{rcl}
  \operatorname{\mathsf{S}}&=&({\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Gen}}},{\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Enc}}},{\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Dec}}}) 
\end{array}$$ with parameters ${\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)$ describing the *message length* of the subliminal (hidden, or attacker) message and ${\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)$ describing the length of a generated sequence of stego documents to embed the whole hidden message. The algorithms have the following functionality:

-   The *key generator* ${\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Gen}}}$ takes the unary presentation of an integer $\kappa$ – the *security parameter* – and outputs a key (we will call it an attacker key) ${\textit{ak}}\in \{0,1\}^{\kappa}$ of length $\kappa$.

-   The *stegoencoder* ${\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Enc}}}$ takes as input the key ${\textit{ak}}$, the attacker (or hidden) message ${\textit{am}}\in
    \{0,1\}^{{\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$, a history $h$, and a state $\sigma$ and outputs a document $d$ from ${\mathcal{C}}^{\kappa}$ such that ${\textit{am}}$ is (partially) embedded in this document and a new state. In order to produce the document, ${\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Enc}}}$ also has sampling access to ${\mathcal{C}}^{\kappa}_{h}$. We denote this by writing ${\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Enc}}}^{{\mathcal{C}}}({\textit{ak}},{\textit{am}},h,\sigma)$.

-   The *(history-ignorant) stegodecoder* ${\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Dec}}}$ takes as input the key ${\textit{ak}}$ and $\ell={\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)$ documents $d_{1},\ldots,d_{\ell}$ and outputs a message ${\textit{am}}'$. A history-ignorant stegodecoder thus has no knowledge of previously sent documents. The stegodecoders of nearly all known systems are history-ignorant.

To improve readability, if the stegosystem is clear from the context, we will omit the prefix $\operatorname{\mathsf{S}}$. If $\bm{{\mathcal{C}}}=\{{\mathcal{C}}^{\kappa}\}_{\kappa\in \mathbb{N}}$ is a family of channels, the *min-entropy* of ${H_{\infty}}(\bm{{\mathcal{C}}},\kappa)$ is defined as ${H_{\infty}}(\bm{{\mathcal{C}}},\kappa) = \min_{h\in
  \Sigma^{*}}\{{H_{\infty}}({\mathcal{C}}^{\kappa}_{h})\}$. In order to be useful, the stegodecoder should *reliably* decode the embedded message from the sequence of documents. As in the setting of algorithm substitution attack, the complete output of $\ell$ documents of the stegosystem for the history $h$ on the subliminal message ${\textit{am}}$ of length ${\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)$ is denoted as ${\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Enc}}}^{\ell,{\mathcal{C}}}({\textit{ak}},{\textit{am}},h)$ and is defined as follows.

1.  $\sigma = \varnothing$

2.  [**for**]{} $j=1$ to $\ell$ [**do**]{}

3.  $(d_{j},\sigma)\gets{\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Enc}}}^{{\mathcal{C}}}({\textit{ak}},{\textit{am}},h,\sigma)$; $h = h \mid\mid d_{j}$

4.  [**return**]{} $d_{1},\ldots,d_{\ell}$

The *unreliability* $\operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)$ of the stegosystem $\operatorname{\mathsf{S}}$ on the channel family $\{{\mathcal{C}}^{\kappa}\}_{\kappa\in {\mathbb{N}}}$ with security parameter $\kappa$ is defined as $$\begin{aligned}
 & \operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa) := \\
 &  \max_{{\textit{ak}}, {\textit{am}}} \max_{h}
 \{\Pr[{\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Dec}}}({\textit{ak}},{\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Enc}}^{\ell,{\mathcal{C}}}}({\textit{ak}},{\textit{am}},h))\neq {\textit{am}}]\},\end{aligned}$$ where the maximum is taken over all ${\textit{ak}}\in \operatorname{supp}({\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa})), 
 {\textit{am}}\in \{0,1\}^{{\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$, and $h\in(\Sigma^{n(\kappa)})^{*}$. If there is a negligible function $\operatorname{\mathsf{negl}}$ such that $\operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)\leq \operatorname{\mathsf{negl}}(\kappa)$, we say that $\operatorname{\mathsf{S}}$ is *reliable* on ${\mathcal{C}}$. Furthermore, the *reboot-reliability* of the stegosystem $\operatorname{\mathsf{S}}$ is defined as $$\begin{aligned}
& \operatorname{\mathbf{UnRel}}^{\star}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa) := \\
&\max_{{\textit{ak}}, {\textit{am}}} \max_{\tau}\max_{ h_1,\ldots,h_{\tau}}\max_{\ell_1,\ldots,\ell_{\tau}} \{
  \Pr[{\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Dec}}}({\textit{ak}},
d_1,d_2,\ldots,d_{\ell}
  )\neq {\textit{am}}]\}  \end{aligned}$$ where the maxima are taken over all ${\textit{ak}}\in \operatorname{supp}({\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa}))$, ${\textit{am}}\in \{0,1\}^{{\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$, all positive integers $\tau\le \ell$, all histories $h_{1},\ldots,h_{\tau}$, and all positive integers $\ell_1,\ldots,\ell_{\tau}$ such that $\ell_1 + \ldots + \ell_{\tau}=\ell$. The documents $d_{1},\ldots, d_{\ell}$ are the concatenated output of the runs $$\begin{aligned}
 {\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Enc}}^{\ell_1,{\mathcal{C}}}}({\textit{ak}},{\textit{am}},h_1)\mid\mid
    \ldots \mid\mid
  {\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Enc}}^{\ell_\tau,{\mathcal{C}}}}({\textit{ak}},{\textit{am}},h_\tau).  \end{aligned}$$ We say that the stegosystem $\operatorname{\mathsf{S}}$ is *reboot-reliable* if $\operatorname{\mathbf{UnRel}}^{\star}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)$ is bounded from above by a negligible function. This corresponds to a situation where the stegoencoder is restarted $\tau$ times, each time with the history $h_i$, and is allowed to generate $\ell_i$ documents. Note that reboot-reliability is a strictly stronger requirement than reliability and we can thus conclude $$\begin{aligned}
  \operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)\leq \operatorname{\mathbf{UnRel}}^{\star}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa).\end{aligned}$$

To define the security of a stegosystem, we first specify the abilities of an attacker: A *warden* $\operatorname{\mathsf{Ward}}$ is a probabilistic polynomial-time algorithm that will have access to a *challenge oracle* $\operatorname{CH}$. This challenge oracle can be called with a message ${\textit{am}}$ and a history $h$ and is either equal to ${\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Enc}}}^{{\mathcal{C}}}({\textit{ak}},{\textit{am}},h,\sigma)$ for a key ${\textit{ak}}\gets {\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa})$ or equal to random documents of the *channel*.

The goal of the warden is to distinguish between those oracles. It also has access to samples of the channel ${\mathcal{C}}^{\kappa}_{h}$ for a freely chosen history $h$. Formally, the *chosen-hiddentext-attack-advantage* is defined via the following game $\operatorname{\mathsf{SS-CHA-Dist}}$:

warden $\operatorname{\mathsf{Ward}}$, stegosystem $\operatorname{\mathsf{S}}$, channel ${\mathcal{C}}$

${\textit{ak}}\gets {\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa})$ $b\gets \{0,1\}$ $b' \gets \operatorname{\mathsf{Ward}}^{\operatorname{CH},{\mathcal{C}}}(1^{\kappa})$ $b=0$ [**then**]{} $d \gets {\mathcal{C}}^{\kappa}_{h}$ $(d,\sigma)\gets {\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{Enc}}}({\textit{ak}},{\textit{am}},h,\sigma)$

A stegosystem $\operatorname{\mathsf{S}}$ is called *secure against chosen-hiddentext attacks* if for every warden $\operatorname{\mathsf{Ward}}$, there is a negligible function $\operatorname{\mathsf{negl}}$ such that $$\begin{aligned}
  \operatorname{\mathbf{Adv}}^{\operatorname{cha}}_{\operatorname{\mathsf{Ward}}, \operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa) 
   &:= |\Pr[\operatorname{\mathsf{SS-CHA-Dist}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)=\textsf{true}] -1/2| \\
  & \leq \ \operatorname{\mathsf{negl}}(\kappa).\end{aligned}$$

The maximal advantage of any warden against $\operatorname{\mathsf{S}}$ is the *insecurity* $\operatorname{\mathbf{InSec}}^{\operatorname{cha}}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)$ and defined as $\max_{\operatorname{\mathsf{Ward}}}\{\operatorname{\mathbf{Adv}}^{\operatorname{cha}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)\}$.

A very common technique in the design of secure stegosystems called *rejection sampling* goes back to an idea of Anderson, presented in [@anderson1996limits]. The basic concept is that the stegoencoder samples from the channel until he finds a document that already encodes the hiddentext. This was first used by Cachin in [@Cachin2004] to construct a secure stegosystem in the information-theoretic sense.

In the following, let $\operatorname{\mathsf{F}}$ be pseudorandom function that maps input strings of length ${\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{in}}}(\kappa)$ (documents) to strings of length ${\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{out}}}(\kappa)=\log(\operatorname{\mathsf{ml}}(\kappa))+1$ (message parts). To simplify notation, we treat the output of ${\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{Eval}}}_{k}$ as a pair $(b,j)$ with $|b|=1$ and $|j|=\log(\operatorname{\mathsf{ml}}(\kappa))$. The encoder of the *rejection sampling stegosystem*, which we denote as $\operatorname{\mathsf{RejSam}}^{\operatorname{\mathsf{F}}}$, is defined as follows:

key ${\textit{ak}}$, message ${\textit{am}}$, history $h$, state $\sigma$

$i := 0$; $d \gets {\mathcal{C}}_{h}$ $i := i+1$ $(b,j) := {\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{Eval}}}_{{\textit{ak}}}(d)$

The key generator ${\operatorname{\mathsf{RejSam}}^{\operatorname{\mathsf{F}}}\!.\!\operatorname{\mathsf{Gen}}}$ is equal to ${\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{Gen}}}$ and the decoder derives ${\textit{am}}$, as long as its input documents contain every bit ${\textit{am}}[j]$, by applying ${\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{Eval}}}_{{\textit{ak}}}$ to these documents. Below we present the description of the decoder. Note that the stegosystem is stateless.

key ${\textit{ak}}$, documents $d_{1},\ldots,d_{{\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)}$

let ${\textit{am}}_{j} := \bot$ $(b,j) := {\operatorname{\mathsf{F}}\!.\!\operatorname{\mathsf{Eval}}}_{k}(d_{i})$ let ${\textit{am}}_{j} := b$

In [@hopper2009provably], Hopper et al. were the first to prove the security of this stegosystem in the complexity-theoretic model. Their argument was simplified by Dedi[ć]{} et al. in [@dedic2009upper] and by Backes and Cachin in [@backes2005public]. The version given here is based upon the stateless construction of Dedi[ć]{} et al. and also uses the idea of Bellare et al. in [@bellare2015asa] to apply the *coupon collector’s problem* to completely get rid of the state by randomly choosing an index to embed.

The analysis of the coupon collector’s problem shows that by sending $\operatorname{\mathsf{ml}}(\kappa)\cdot (\ln \operatorname{\mathsf{ml}}(\kappa)+\beta)$ documents – for an appropriate value $\beta$ – one only introduces a term $\exp(-\beta)$ into the unreliability (see [e.g.]{}[@mitzenmacher2005probability] for a proof of this fact), which can be made negligible by setting $\beta\geq \operatorname{\mathsf{ml}}(\kappa)-\ln(\operatorname{\mathsf{ml}}(\kappa))$. The output length on messages of length $\operatorname{\mathsf{ml}}(\kappa)$ will thus be bounded by $\operatorname{\mathsf{ml}}(\kappa)^{2}$.

The security of this system directly follows from the analysis of Dedi[ć]{} et al. in [@dedic2009upper]:

\[thm:rejsam:secure\] For every polynomial $\operatorname{\mathsf{ml}}(\kappa)$, there exists a universal history-ignorant stegosystem $\operatorname{\mathsf{S}}=\operatorname{\mathsf{RejSam}}^{\operatorname{\mathsf{F}}}$ with security parameter $\kappa$ and $s\ge 1$ such that for every channel ${\mathcal{C}}^{\kappa}$ we have

-   ${\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)=\operatorname{\mathsf{ml}}(\kappa)$,

-   $\operatorname{\mathbf{InSec}}^{\operatorname{cha}}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa) \leq
        \mathcal{O}(\operatorname{\mathsf{ml}}(\kappa)^{4}\cdot
        2^{-{H_{\infty}}({\mathcal{C}}^{\kappa})}+\operatorname{\mathsf{ml}}(\kappa)^{2}\cdot
        \exp(-s))+\operatorname{\mathbf{InSec}}^{\operatorname{prf}}_{\operatorname{\mathsf{F}},{\mathcal{C}}}(\kappa)$, and

-   $\operatorname{\mathbf{UnRel}}^{\star}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa) \leq
        \operatorname{\mathsf{ml}}(\kappa)^{2}(2\cdot
        \exp(-2^{{H_{\infty}}({\mathcal{C}}^{\kappa})-3}) +
        \exp(-2^{-2} s))+
        \operatorname{\mathbf{InSec}}^{\operatorname{prf}}_{\operatorname{\mathsf{F}},{\mathcal{C}}}(\kappa)$.

The notation $\operatorname{\mathbf{InSec}}^{\operatorname{prf}}_{\operatorname{\mathsf{F}},{\mathcal{C}}}(\kappa)$ indicates the insecurity of the pseudorandom function $\operatorname{\mathsf{F}}$ *relative to the channel ${\mathcal{C}}$*. Informally, this means that the attacker against $\operatorname{\mathsf{F}}$ also has sampling access to ${\mathcal{C}}$ (for a formal definition, see [@dedic2009upper]). For an *efficiently sampleable* channel ${\mathcal{C}}$ ([i.e.]{}one that can be simulated by a PPTM), it clearly holds that $\operatorname{\mathbf{InSec}}^{\operatorname{prf}}_{\operatorname{\mathsf{F}},{\mathcal{C}}}(\kappa)=\operatorname{\mathbf{InSec}}^{\operatorname{prf}}_{\operatorname{\mathsf{F}}}(\kappa)$. All channels used in this work are efficiently sampleable and we will thus omit the index ${\mathcal{C}}$ from the term $\operatorname{\mathbf{InSec}}$.

Encryption Schemes as Steganographic Channels {#sec:channel}
=============================================

Let $\operatorname{\mathsf{SES}}=(\operatorname{\mathsf{Gen}},\operatorname{\mathsf{Enc}},\operatorname{\mathsf{Dec}})$ be a symmetric encryption scheme that encodes messages of length $\operatorname{\mathsf{ml}}(\kappa)$ into ciphertexts of length $\operatorname{\mathsf{cl}}(\kappa) \geq \operatorname{\mathsf{ml}}(\kappa)$ and let $\ell$ be a polynomial of $\kappa$. For $\operatorname{\mathsf{SES}}$ we define a channel family, named ${\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{SES}}}(\ell)$, indexed with parameter $\kappa\in {\mathbb{N}}$, where the documents will correspond to the input of generalized algorithm substitution attack against encryption schemes. The essential idea behind the definition of the channel ${\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{SES}}}(\ell)$ is that for all $k\in \operatorname{supp}(\operatorname{\mathsf{Gen}}(1^{\kappa}))$ and every sequence of messages $m_{1},m_{2},\ldots, m_{\ell(\kappa)}$, with $m_{i}\in\{0,1\}^{\operatorname{\mathsf{ml}}(\kappa)}$, for the history $$h= k \mid\mid m_{1} \mid\mid m_{2} \mid\mid \ldots \mid\mid m_{\ell(\kappa)}$$ the distribution of the sequences of documents $$\begin{aligned}
     c_{1} \mid\mid c_{2} \mid\mid \ldots \mid\mid c_{\ell(\kappa)}
  \end{aligned}$$ generated by the channel is exactly the same as the distribution for $$\begin{aligned}
     \operatorname{\mathsf{Enc}}(k,m_{1}) \mid\mid \operatorname{\mathsf{Enc}}(k,m_{2}) \mid\mid \ldots \mid\mid \operatorname{\mathsf{Enc}}(k,m_{\ell(\kappa)}).
  \end{aligned}$$ To give a formal definition of $\{{\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{SES}}}(\ell)\}_{\kappa\in {\mathbb{N}}}$ we need to specify the probability distributions for any history $h$. Thus, we define the family, on the alphabet $\{0,1\}$, as follows.

For the empty history $h=\varnothing$, define $$\begin{aligned}
{\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{SES}}}(\ell)_{\varnothing}  \end{aligned}$$ as the distribution of all keys generated by $\operatorname{\mathsf{Gen}}(1^{\kappa})$. For a key $k\in \operatorname{supp}(\operatorname{\mathsf{Gen}}(1^{\kappa}))$ and a (possibly empty) sequence of messages $m_{1},m_{2},\ldots, m_{r}$, with $m_{i}\in \{0,1\}^{\operatorname{\mathsf{ml}}(\kappa)}$ and $0\leq r\leq \ell(\kappa)-1$, the distribution $$\begin{aligned}
    {\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{SES}}}(\ell)_{k\mid\mid m_{1}\mid\mid
    m_{2}\mid\mid \ldots \mid\mid m_{r}}
  \end{aligned}$$ is the uniform distribution on all messages $m_{r+1}\in
  \{0,1\}^{\operatorname{\mathsf{ml}}(\kappa)}$. For $k\in \operatorname{supp}(\operatorname{\mathsf{Gen}}(1^{\kappa}))$, a sequence of messages $m_{1},m_{2},\ldots,$ $ m_{\ell(\kappa)}$ with $m_{i}\in
  \{0,1\}^{\operatorname{\mathsf{ml}}(\kappa)}$, and a (possibly empty) sequence of ciphertexts $c_{1},\ldots,c_{r}$, with $c_{i}\in \operatorname{supp}(\operatorname{\mathsf{Enc}}(k,m_{((i-1)\bmod
    \ell(\kappa))+1})),$ the distribution $$\begin{aligned}
    {\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{SES}}}(\ell)_{k\mid\mid m_{1}\mid\mid
    m_{2}\mid\mid \ldots \mid\mid m_{\ell(\kappa)}\mid\mid
    c_{1}\mid\mid c_{2}\mid\mid \ldots \mid\mid
    \ldots  \mid\mid c_{r}}
  \end{aligned}$$ is the distribution of $\operatorname{\mathsf{Enc}}(k,m_{(r \bmod \ell(\kappa))+1})$.

ASAs against Encryption in the Steganographic Model {#Sec:ASA:against:encrypted:as:stego}
===================================================

The main message of our paper is that algorithm substitution attacks against a primitive $\Pi$ are equivalent to the use of steganography on a corresponding channel ${\mathcal{C}}_{\Pi}$ determined by the protocol $\Pi$. Focusing on symmetric encryption schemes as a common cryptographic primitive, we will show in this section exemplary proofs for the general relations between ASAs and steganography.

In the previous section we showed a formal specification of the family of communication channels ${\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{SES}}}(\ell)$ determined by a symmetric encryption scheme $\operatorname{\mathsf{SES}}$. We will now prove that a secure and reliable stegosystem on ${\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{SES}}}(\ell)$ implies the existence of an indistinguishable and successful algorithm substitution attack on $\operatorname{\mathsf{SES}}$. On the other hand, we will also show that the existence of an indistinguishable and successful algorithm substitution attack on $\operatorname{\mathsf{SES}}$ implies a secure and reliable stegosystem on ${\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{SES}}}(\ell)$.

As a consequence we get a construction of an ASA against any encryption scheme using a generic stegosystem like [e.g.]{}this proposed by Dedi[ć]{} et al. [@dedic2009upper]. Thus, we can conclude Theorem 1 and Theorem 3 proposed by Bellare et al. in [@bellare2014asa] that there exist indistinguishable and successful ASAs against encryption schemes. Moreover we obtain Theorem 4 in [@bellare2014asa] which says that an ASA is impossible for unique ciphertext symmetric encryption schemes.

Steganography implies ASAs
--------------------------

\[thm:asa:on:ses:impl:stego\] Assume $\operatorname{\mathsf{SES}}$ is a symmetric encryption scheme and let $\operatorname{\mathsf{S}}$ be a stegosystem on the channel ${\mathcal{C}}:={\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{SES}}}({\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ol}}}(\kappa))$ determined by $\operatorname{\mathsf{SES}}$. Then there exists an algorithm substitution attack $\operatorname{\mathsf{ASA}}$ against $\operatorname{\mathsf{SES}}$ of indistinguishability, resp. reliability such that: $$\begin{array}{rcl}
   \operatorname{\mathbf{InSec}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa) &\le&  \operatorname{\mathbf{InSec}}^{\operatorname{cha}}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)
   \quad \text{and} \\
   \operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa) &=&  \operatorname{\mathbf{UnRel}}^{\star}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa).
\end{array}$$

Let $\operatorname{\mathsf{SES}}=(\operatorname{\mathsf{Gen}},\operatorname{\mathsf{Enc}},\operatorname{\mathsf{Dec}})$ be a symmetric encryption scheme and $\operatorname{\mathsf{S}}=(\operatorname{\mathsf{SGen}},\operatorname{\mathsf{SEnc}},\operatorname{\mathsf{SDec}})$ be a stegosystem on the channel ${\mathcal{C}}$. To simplify notation, let $\ell=\ell(\kappa):={\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)$. We will construct the algorithm substitution attack $\operatorname{\mathsf{ASA}}=(\operatorname{\mathsf{AGen}},\operatorname{\mathsf{AEnc}},$ $\operatorname{\mathsf{AExt}})$ on $\operatorname{\mathsf{SES}}$ from the stegosystem $\operatorname{\mathsf{S}}$ and show the indistinguishability and success of $\operatorname{\mathsf{ASA}}$ depending on security and reliability of $\operatorname{\mathsf{S}}$. The components of the $\operatorname{\mathsf{ASA}}$ are defined as follows.

The key generator $\operatorname{\mathsf{AGen}}$ just simulates $\operatorname{\mathsf{SGen}}$ – the key generator of the stegosystem. It will output the attack key ${\textit{ak}}$. The encoding algorithm $\operatorname{\mathsf{AEnc}}$ on input ${\textit{ak}}\in
    \operatorname{supp}(\operatorname{\mathsf{AGen}}(1^{\kappa}))$, ${\textit{am}}\in
    \{0,1\}^{{\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$, $k\in
    \operatorname{supp}(\operatorname{\mathsf{Gen}}(1^{\kappa}))$, and $m\in
    \{0,1\}^{{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$ simulates $\operatorname{\mathsf{SEnc}}$ on channel ${\mathcal{C}}$ with input key ${\textit{ak}}$, the message ${\textit{am}}$ and the history $h=k\mid\mid m^{\ell}$, where $m^{\ell}$ is the string of length $\ell\cdot |m|$ containing $\ell$ copies of $m$. Whenever $\operatorname{\mathsf{SEnc}}$ makes a query to its channel oracle, algorithm $\operatorname{\mathsf{AEnc}}$ uses $\operatorname{\mathsf{Enc}}$ on input $k$ and $m$ to produce a corresponding ciphertext and sends it to $\operatorname{\mathsf{SEnc}}$. The encoder $\operatorname{\mathsf{AEnc}}$ then outputs the document $d$ generated by $\operatorname{\mathsf{SEnc}}$. Finally, the extraction algorithm $\operatorname{\mathsf{AExt}}$ on input ${\textit{ak}}\in \operatorname{supp}(\operatorname{\mathsf{AGen}}(1^{\kappa}))$ and documents $d_{1},\ldots,d_{\ell}$ just simulates $\operatorname{\mathsf{SDec}}$ on the same inputs.

As one can see from the definitions, $\operatorname{\mathsf{ASA}}$ is a generalized algorithm substitution attack against $\operatorname{\mathsf{SES}}$. We will now prove that it is indistinguishable from $\operatorname{\mathsf{SES}}$ and that it is successful.

We prove first indistinguishability of the system. Let $\operatorname{\mathsf{Watch}}$ be a watchdog against the above $\operatorname{\mathsf{ASA}}$ with maximal advantage, i.e. $$\begin{aligned}
     \operatorname{\mathbf{Adv}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}^{\operatorname{enc-watch}}(\kappa) = \operatorname{\mathbf{InSec}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa),
    \end{aligned}$$ where $\operatorname{\mathbf{Adv}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{Watch}}, \operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)$ is equal to the success probability that $\operatorname{\mathsf{ASA-Dist}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)=\textsf{true}$. We will now construct a warden $\operatorname{\mathsf{Ward}}$ from $\operatorname{\mathsf{Watch}}$ such that $$\begin{aligned}
\operatorname{\mathbf{Adv}}^{\operatorname{cha}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)
=
\operatorname{\mathbf{Adv}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}^{\operatorname{enc-watch}}(\kappa).  \end{aligned}$$ Thus, we will get that $$\label{ineq:insecasa:insecstego}
  \operatorname{\mathbf{InSec}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)
  \le 
  \operatorname{\mathbf{InSec}}^{\operatorname{cha}}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa).$$ The warden $\operatorname{\mathsf{Ward}}$ on input $1^{\kappa}$ just simulates the watchdog $\operatorname{\mathsf{Watch}}$ and gives the same output as $\operatorname{\mathsf{Watch}}$ at the end of the simulation. Whenever the watchdog makes a query on input ${\textit{am}}$, $k$, and $m$ to its challenging oracle (that is either equal to $\operatorname{\mathsf{SES}}$’s encryption algorithm $\operatorname{\mathsf{Enc}}(k,m)$ or to $\operatorname{\mathsf{ASA}}$’s encryption $\operatorname{\mathsf{AEnc}}({\textit{ak}},{\textit{am}},k,m,\sigma)$ for ${\textit{ak}}\gets \operatorname{\mathsf{AGen}}(1^{\kappa})$), the warden $\operatorname{\mathsf{Ward}}$ queries its own challenging oracle with message ${\textit{am}}$, state $\sigma$ and history $h=k\mid\mid m^{\ell}$. Note that the challenging oracle of $\operatorname{\mathsf{Ward}}$ is either equal to the channel ${\mathcal{C}}$ or to $\operatorname{\mathsf{SEnc}}({\textit{ak}},{\textit{am}},h,\sigma)$ for ${\textit{ak}}\gets \operatorname{\mathsf{SGen}}(1^{\kappa})$.

If the challenging oracle of $\operatorname{\mathsf{Ward}}$ is equal to the steganographic encoding $\operatorname{\mathsf{SEnc}}({\textit{ak}},{\textit{am}},h,\sigma)$ ([i.e.]{}the bit $b$ in $\operatorname{\mathsf{SS-CHA-Dist}}$ equals $1$, denoted by $\operatorname{\mathsf{SS-CHA-Dist}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)\langle b=1\rangle$), the answer of $\operatorname{\mathsf{Ward}}$ is the same as the output of the $\operatorname{\mathsf{Watch}}$ in case it queries the ASA’s encoding algorithm $\operatorname{\mathsf{AEnc}}({\textit{ak}},{\textit{am}},k,m)$ by construction. Thus, $$\begin{aligned}
  &\Pr[\operatorname{\mathsf{SS-CHA-Dist}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)\langle b=1\rangle=\textsf{true}]\\  
  &= \ \Pr[\operatorname{\mathsf{ASA-Dist}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)\langle b=1\rangle=\textsf{true}].\end{aligned}$$

If the challenging oracle of $\operatorname{\mathsf{Ward}}$ is equal to the channel (the bit $b$ in $\operatorname{\mathsf{SS-CHA-Dist}}$ equals $0$), by the definition of the channel ${\mathcal{C}}$ for the symmetric encryption scheme $\operatorname{\mathsf{SES}}$, the answer of the challenging oracle is equal to the output of $\operatorname{\mathsf{Enc}}(k,m)$. Hence, $$\begin{aligned}
  &\Pr[\operatorname{\mathsf{SS-CHA-Dist}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)\langle b=0\rangle=\textsf{true}]\\
  & = \
  \Pr[\operatorname{\mathsf{ASA-Dist}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)\langle b=0\rangle=\textsf{true}].\end{aligned}$$ We thus have $$\begin{array}{rcl}
  \operatorname{\mathbf{Adv}}^{\operatorname{cha}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)
    & = &
  |\Pr[\operatorname{\mathsf{SS-CHA-Dist}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)=\textsf{true}] - 1/2| \\
  & = & |\Pr[\operatorname{\mathsf{ASA-Dist}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)=\textsf{true} -1/2| \\ 
  & = &
  \operatorname{\mathbf{Adv}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{Watch}}, \operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)
\end{array}$$ which completes the proof of .

We still need to prove that $\operatorname{\mathsf{AExt}}$ is reliably able to extract the attacker message ${\textit{am}}$ from the ciphertext. But, as $\operatorname{\mathsf{AExt}}=\operatorname{\mathsf{SDec}}$, the reboot-reliability of $\operatorname{\mathsf{SDec}}$ directly implies that $\operatorname{\mathsf{AExt}}$ is successful with probability of $1-\operatorname{\mathsf{negl}}(\kappa)$.

By combining Theorem \[thm:asa:on:ses:impl:stego\] and Theorem \[thm:rejsam:secure\], we can conclude the following corollary.

\[coroll:thm:ipl:bellare\] For every symmetric encryption scheme $\operatorname{\mathsf{SES}}$, there exists an algorithm subsection attack $\operatorname{\mathsf{ASA}}$ with message length $\operatorname{\mathsf{ml}}(\kappa)$ and parameter $s\ge 1$ such that $$\begin{array}{rcl}
     \operatorname{\mathbf{InSec}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)&\leq&
       \mathcal{O}(\operatorname{\mathsf{ml}}(\kappa)^{4}\cdot 2^{-{H_{\infty}}({\mathcal{C}}^{\kappa})})+\\
&&\mathcal{O}(\operatorname{\mathsf{ml}}(\kappa)^{2}\cdot
    \exp(-s))+
     \operatorname{\mathbf{InSec}}^{\operatorname{prf}}_{\operatorname{\mathsf{F}}}(\kappa),\\[2mm]
\operatorname{\mathbf{UnRel}}^{\star}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa) &\leq&
    2 \operatorname{\mathsf{ml}}(\kappa)^{2}\cdot
    \exp(-2^{{H_{\infty}}({\mathcal{C}}^{\kappa})-3}) +\\
&&  \operatorname{\mathsf{ml}}(\kappa)^{2}\cdot  \exp(-2^{-2} s)+
    \operatorname{\mathbf{InSec}}^{\operatorname{prf}}_{\operatorname{\mathsf{F}}}(\kappa)
    \end{array}$$ where ${\mathcal{C}}:={\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{SES}}}({\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ol}}}(\kappa))$

One can compare this corollary to the construction used in the proof of Theorem 4.1 and Theorem 4.2 in [@bellare2015asa]. We can see that our generic algorithm substitution attack gets almost the same bounds for insecurity and for unreliability.

Note that the protocols in [@bellare2015asa; @ateniese2015sig] and our generic protocol of Corollary \[coroll:thm:ipl:bellare\] have a very bad rate: $
    \frac{\operatorname{\mathsf{ml}}}{\operatorname{\mathsf{ml}}\cdot (\ln \operatorname{\mathsf{ml}}+\beta)} = 1/(\ln \operatorname{\mathsf{ml}}+\beta)
$ for an appropriate value $\beta$. One can easily modify the above constructions such that instead of one bit $b$ of a message ${\textit{am}}$ we embed a block of $\log(\operatorname{\mathsf{ml}})$ bits per ciphertext. This improves the rate to $
     \frac{\log \operatorname{\mathsf{ml}}}{\ln(\operatorname{\mathsf{ml}}) - \ln\log(\operatorname{\mathsf{ml}}) +\beta} = \Theta(1).
$

ASAs imply Steganography
------------------------

\[thm:ses:on:ses:impl:stego\] Assume $\operatorname{\mathsf{SES}}$ is a symmetric encryption scheme and let $\operatorname{\mathsf{ASA}}$ be an algorithm substitution attack against $\operatorname{\mathsf{SES}}$ of output length ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)$. Then there exists a stegosystem $\operatorname{\mathsf{S}}$ with the output length ${\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)=2\cdot  {\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)+1$ on the channel ${\mathcal{C}}:={\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{SES}}}({\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ol}}}(\kappa))$ determined by $\operatorname{\mathsf{SES}}$ such that $\operatorname{\mathsf{S}}$’s insecurity, resp. its reliability satisfy $$\begin{array}{rcl}
   \operatorname{\mathbf{InSec}}^{\operatorname{cha}}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa) &\le& \operatorname{\mathbf{InSec}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)
   \quad \text{and} \\
   \operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa) &=& \operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa) . 
\end{array}$$

Let $\operatorname{\mathsf{SES}}=(\operatorname{\mathsf{Gen}},\operatorname{\mathsf{Enc}},\operatorname{\mathsf{Dec}})$ be a symmetric encryption scheme and $\operatorname{\mathsf{ASA}}=(\operatorname{\mathsf{AGen}},\operatorname{\mathsf{AEnc}},\operatorname{\mathsf{AExt}})$ be an algorithm substitution attack against $\operatorname{\mathsf{SES}}$. To simplify notation, let $\ell={\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)$. We construct the stegosystem $\operatorname{\mathsf{S}}=(\operatorname{\mathsf{SGen}},\operatorname{\mathsf{SEnc}},\operatorname{\mathsf{SDec}})$ on ${\mathcal{C}}$ out of the $\operatorname{\mathsf{ASA}}$.

The key generation algorithm $\operatorname{\mathsf{SGen}}$ simply simulates $\operatorname{\mathsf{AGen}}$. It will output the key ${\textit{ak}}$. To encode a message ${\textit{am}}$ using the key ${\textit{ak}}$, the stegoencoding algorithm $\operatorname{\mathsf{SEnc}}$ generates for any history $h$ a sequence of ${\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)=2\ell+1$ documents such that the last $\ell$ documents embed the message ${\textit{am}}$. To describe the algorithm we need to distinguish between different given histories $h$.

In this case, $\operatorname{\mathsf{SEnc}}$ chooses a random key $k\gets {\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa})$ using the generation algorithm of $\operatorname{\mathsf{SES}}$ and outputs $k$.

Encoder $\operatorname{\mathsf{SEnc}}$ samples a random message $m_{r+1}$ and outputs it.

The stego-encoder $\operatorname{\mathsf{SEnc}}$ simulates $\operatorname{\mathsf{AEnc}}({\textit{ak}},{\textit{am}},k,m_{(r+1) \bmod \ell +1})$ and outputs the generated ciphertext.

Note that by construction, in any case the last $\ell$ documents generated by $\operatorname{\mathsf{SEnc}}^{2\ell+1}$ embed the message ${\textit{am}}$ in the same way as done by $\operatorname{\mathsf{ASA}}^{\ell}$.

If the decoder $\operatorname{\mathsf{SDec}}$ is given documents $d_{1},\ldots,d_{2\ell+1}$, we output $\operatorname{\mathsf{AExt}}({\textit{ak}},d_{\ell+2},\ldots,d_{2\ell+1})$.

As one can see from the definitions, the decoding algorithm of $\operatorname{\mathsf{S}}$ is history-ignorant. We will prove that on the channel ${\mathcal{C}}={\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{SES}}}(2\ell+1)$ the security and reliability of the stegosystem $\operatorname{\mathsf{S}}$ satisfy the stated conditions.

We first analyze the security of the system. Let $\operatorname{\mathsf{Ward}}$ be a warden against $\operatorname{\mathsf{S}}$ on ${\mathcal{C}}$ with maximal advantage, i.e. $$\begin{aligned}
     \operatorname{\mathbf{Adv}}^{\operatorname{cha}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)
      =
      \operatorname{\mathbf{InSec}}^{\operatorname{cha}}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa),
    \end{aligned}$$ where $       \operatorname{\mathbf{Adv}}^{\operatorname{cha}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)
        = \Pr[\operatorname{\mathsf{SS-CHA-Dist}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)=\textsf{true}].
    $ We will construct a watchdog $\operatorname{\mathsf{Watch}}$ against the algorithm substitution attack $\operatorname{\mathsf{ASA}}$ with the same advantage as $\operatorname{\mathsf{Ward}}$: $$\begin{aligned}
      \operatorname{\mathbf{Adv}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}^{\operatorname{enc-watch}}(\kappa) =
      \operatorname{\mathbf{Adv}}^{\operatorname{cha}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa).
    \end{aligned}$$ This will prove that $$\label{ineq:insecstego:insecasa}
    \operatorname{\mathbf{InSec}}^{\operatorname{cha}}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)
    \le
      \operatorname{\mathbf{InSec}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa).$$

The watchdog $\operatorname{\mathsf{Watch}}$ on input $1^{\kappa}$ simply simulates the warden $\operatorname{\mathsf{Ward}}$. Whenever the warden $\operatorname{\mathsf{Ward}}$ makes a query to its channel oracle ${\mathcal{C}}$ with a history $h$, the watchdog $\operatorname{\mathsf{Watch}}$ simulates the oracle response as follows:

-   If $h=\varnothing$, the watchdog uses $\operatorname{\mathsf{Gen}}(1^{\kappa})$ to construct a key $k$ and returns $k$ to the warden.

-   If $h=k\mid\mid m_{1}\mid\mid \ldots \mid\mid
          m_{r}$ with $r < \ell$, the watchdog uniformly chooses a message $m_{r+1}$ from $\{0,1\}^{{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$ and outputs $m_{r+1}$.

-   If $h=k\mid\mid m_{1}\mid\mid \ldots\mid\mid 
          m_{\ell}\mid\mid c_{1}\mid\mid \ldots\mid\mid c_{r}$ with $r\geq 0$, the watchdog computes $c_{r+1}\gets \operatorname{\mathsf{Enc}}(k,m_{((r+1)\bmod \ell)+1})$ and outputs $c_{r+1}$.

Clearly, this simulates the channel distribution ${\mathcal{C}}$ perfectly. If the warden queries its challenge oracle ${\operatorname{\mathsf{Ward}}\!.\!\operatorname{CH}}$ with chosen message ${\textit{am}}$, state $\sigma$, and history $h$ (that is either equivalent to sampling from ${\mathcal{C}}_{h}$ or to calling $\operatorname{\mathsf{SEnc}}({\textit{ak}},{\textit{am}},h,\sigma)$), the watchdog simulates the response of the oracle ${\operatorname{\mathsf{Ward}}\!.\!\operatorname{CH}}$ as follows:

-   If $h=\varnothing$ then $\operatorname{\mathsf{Watch}}$ chooses a random key $k\gets \operatorname{\mathsf{Gen}}(1^{\kappa})$ and outputs it.

-   If $h=k\mid\mid m_1\mid\mid m_2\mid\mid \ldots \mid\mid
          m_r$ for $0\leq r\leq \ell-1$ then $\operatorname{\mathsf{Watch}}$ samples a random message $m$ and outputs it.

-   If $h=k\mid\mid m_{1}\mid\mid m{_2}\mid\mid \ldots
          \mid\mid m_{\ell}\mid\mid c_{1}\mid\mid \ldots \mid\mid
          c_{r}$ with $r\geq 0$ then $\operatorname{\mathsf{Watch}}$ queries its own oracle on $k$ and $m_{((r+1)\bmod \ell)+1}$.

If ${\operatorname{\mathsf{Watch}}\!.\!\operatorname{CH}}$ is equal to $\operatorname{\mathsf{Enc}}$ of $\operatorname{\mathsf{SES}}$ (the bit $b$ in $\operatorname{\mathsf{ASA-Dist}}$ is set to $0$) the corresponding answer is identically distributed to a sample of the channel ${\mathcal{C}}$. Hence, $$\begin{aligned}
      &\Pr[\operatorname{\mathsf{ASA-Dist}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)\langle
      b=0\rangle=\textsf{true}]=\\
      &\Pr[\operatorname{\mathsf{SS-CHA-Dist}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)\langle b=0\rangle=\textsf{true}].
    \end{aligned}$$ On the other hand, if ${\operatorname{\mathsf{Watch}}\!.\!\operatorname{CH}}$ is equal to $\operatorname{\mathsf{AEnc}}$ (the bit $b$ in $\operatorname{\mathsf{ASA-Dist}}$ is set to $1$), the corresponding answer is identically distributed to $\operatorname{\mathsf{SEnc}}({\textit{ak}},{\textit{am}},h,\sigma)$ and thus $$\begin{aligned}
       & \Pr[\operatorname{\mathsf{ASA-Dist}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)\langle b=1\rangle=\textsf{true}]=\\
      &\Pr[\operatorname{\mathsf{SS-CHA-Dist}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)\langle b=1\rangle=\textsf{true}].
    \end{aligned}$$ We thus have $$\begin{array}{ll}
         & \operatorname{\mathbf{Adv}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)
          \ =\\
         &\quad\quad |\Pr[\operatorname{\mathsf{ASA-Dist}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)=\textsf{true}] - 1/2|  \ =\\
         &\quad\quad |\Pr[\operatorname{\mathsf{SS-CHA-Dist}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)=\textsf{true}] - 1/2|  \ =\\
         &\quad\quad \operatorname{\mathbf{Adv}}^{\operatorname{cha}}_{\operatorname{\mathsf{Ward}},\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa)
      \end{array}$$ which proves .

The reliability of $\operatorname{\mathsf{S}}$ is the same as the success probability of $\operatorname{\mathsf{ASA}}$ since $\operatorname{\mathsf{SDec}}$ simply simulates $\operatorname{\mathsf{AExt}}$.

By using the fact that channels with min-entropy $0$ can not be used for steganography (see [e.g.]{}Theorem 6 in [@hopper2009provably]) and observing that channels corresponding to deterministic encryption schemes have min-entropy $0$, we can conclude the following corollary:

For all deterministic encryption schemes $\operatorname{\mathsf{SES}}$ and all algorithm substitution attacks $\operatorname{\mathsf{ASA}}$ against $\operatorname{\mathsf{SES}}$: $$\begin{aligned}
    \operatorname{\mathbf{InSec}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)\geq 1.\end{aligned}$$

Note that this exactly Theorem 4 in [@bellare2014asa].

General Results {#sec:general}
===============

Let $\operatorname{\mathsf{R}}$ be a polynomial-time randomized algorithm with hardwired secret $s$ which takes inputs $x$ and generates outputs $y$. The general task of an algorithm substitution attack against $\operatorname{\mathsf{R}}$ is to construct a subverted algorithm $\operatorname{\mathsf{AR}}_{{\textit{ak}}}$ which using a hidden hardwired random key ${\textit{ak}}$ outputs on the secret $s$ in the sequence of calls $\operatorname{\mathsf{AR}}_{\textit{ak}}(s,x_1), \operatorname{\mathsf{AR}}_{\textit{ak}}(s,x_2),\ldots$ a sequence such that

the output $\operatorname{\mathsf{AR}}_{\textit{ak}}(s,x_1), \operatorname{\mathsf{AR}}_{\textit{ak}}(s,x_2),\ldots$ is indistinguishable from $\operatorname{\mathsf{R}}(s,x_1), \operatorname{\mathsf{R}}(s,x_2),\ldots$ and

$\operatorname{\mathsf{AR}}_{\textit{ak}}(s,x_1), \operatorname{\mathsf{AR}}_{\textit{ak}}(s,x_2),\ldots$ embeds the secret $s$.

In our setting we model the attack on $\operatorname{\mathsf{R}}$ as a stegosystem on a channel determined by $\operatorname{\mathsf{R}}$ and define such a channel.

ASA against a Randomized Algorithm
----------------------------------

In this section we give formal definitions for algorithm substitution attack $\operatorname{\mathsf{AR}}$, its advantage $\operatorname{\mathbf{Adv}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{AR}},\operatorname{\mathsf{R}}}$, etc. Formally, an *algorithm substitution attack against $\operatorname{\mathsf{R}}$* is a triple of efficient algorithms $\operatorname{\mathsf{ASA}}=(\operatorname{\mathsf{Gen}},\operatorname{\mathsf{AR}},\operatorname{\mathsf{Ext}})$, where $\operatorname{\mathsf{Gen}}$ generates the key ${\textit{ak}}$, the algorithm $\operatorname{\mathsf{AR}}$ takes the key ${\textit{ak}}$, a secret $s$ and all inputs $x_{1},x_{2},\ldots$ to $\operatorname{\mathsf{R}}$ and the extractor $\operatorname{\mathsf{Ext}}$ tries to extract $s$ from the outputs of $\operatorname{\mathsf{AR}}$ with the help of ${\textit{ak}}$ (but without knowing $x_{1},x_{2},\ldots$). Similarly to the setting for encryption schemes, $\operatorname{\mathsf{ASA}}$ is called *indistinguishable*, if every PPTM $\operatorname{\mathsf{Watch}}$ – the *watchdog* – is not able to distinguish between $\operatorname{\mathsf{AR}}_{{\textit{ak}}}(s,x_{1}),\operatorname{\mathsf{AR}}_{{\textit{ak}}}(s,x_{2}),\ldots$ and $\operatorname{\mathsf{R}}(x_{1}),\operatorname{\mathsf{R}}(x_{2}),\ldots$ even if he is allowed to choose $s$ and all $x_{i}$. This is defined via the game $\operatorname{\mathsf{RASA-Dist}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{R}}}$ defined analogously to $\operatorname{\mathsf{ASA-Dist}}$. The maximal advantage of any watchdog distinguishing $\operatorname{\mathsf{ASA}}$ from $\operatorname{\mathsf{R}}$ is called the *insecurity* or indistinguishability of $\operatorname{\mathsf{ASA}}$ and is formally defined as $$\begin{aligned}
\operatorname{\mathbf{InSec}}^{\operatorname{asa}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{R}}}(\kappa) := \max_{\operatorname{\mathsf{Watch}}}\{\operatorname{\mathbf{Adv}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{R}}}^{\operatorname{asa}}(\kappa)\},\end{aligned}$$ where $$\begin{aligned}
    &\operatorname{\mathbf{Adv}}^{\operatorname{asa}}_{\operatorname{\mathsf{Watch}}, \operatorname{\mathsf{ASA}},\operatorname{\mathsf{R}}}(\kappa) 
   := \\ 
   &\quad\quad |\Pr[\operatorname{\mathsf{RASA-Dist}}_{\operatorname{\mathsf{Watch}},\operatorname{\mathsf{ASA}},\operatorname{\mathsf{R}}}(\kappa)=\textsf{true}] - 1/2|.\end{aligned}$$

The *unreliability* of $\operatorname{\mathsf{ASA}}$ is also defined like before: $$\begin{aligned}
  &\operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{R}}}(\kappa) \ :=\\ &\max
  \{
  \Pr[{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{AExt}}}({\textit{ak}},{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{AR}}}({\textit{ak}},{\textit{am}},x_{1},\ldots,x_{\ell}))\neq
  {\textit{am}}]\},\end{aligned}$$ where the maximum is taken over all ${\textit{ak}}\in \operatorname{supp}({\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa})), \allowbreak
 {\textit{am}}\in\{0,1\}^{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$, and $x_{1},\ldots,x_{\ell}$ being inputs to $\operatorname{\mathsf{R}}$.

Known examples which fit into this setting include [e.g.]{}the subversion-resilient signature schemes presented in the work of Ateniese et al. [@ateniese2015sig].

Channel determined by a Randomized Algorithm
--------------------------------------------

Let $\operatorname{\mathsf{R}}$ be a polynomial-time randomized algorithm with parameter $\kappa$. We assume that the secret $s$ is generated by $\operatorname{\mathsf{Gen}}$ and the inputs $x$ to $\operatorname{\mathsf{R}}$ are generated by the randomized polynomial-time algorithm $\operatorname{\mathsf{GenInput}}$, associated with $\operatorname{\mathsf{R}}$ (which may be chosen adversarially as shown in the definition above). Let $\ell$ be a polynomial of $\kappa$. For $\operatorname{\mathsf{R}}$ we define a channel family, named ${\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{R}}}(\ell)$, indexed with parameter $\kappa\in {\mathbb{N}}$, with documents which correspond to the input of $\operatorname{\mathsf{AR}}$. The essential idea behind the definition of the channel ${\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{R}}}(\ell)$ is that for all $s\in \operatorname{supp}(\operatorname{\mathsf{Gen}}(1^{\kappa}))$ and every sequence of inputs $x_{1},x_{2},\ldots, x_{\ell(\kappa)}$, with $x_{i}\in\operatorname{supp}(\operatorname{\mathsf{GenInput}}(1^{\kappa}))$, for the history $$h= s \mid\mid x_{1} \mid\mid x_{2} \mid\mid \ldots \mid\mid x_{\ell(\kappa)}$$ the distribution of the sequences of documents $$\begin{aligned}
     y_{1} \mid\mid y_{2} \mid\mid \ldots \mid\mid y_{\ell(\kappa)}
  \end{aligned}$$ generated by the channel is exactly the same as the distribution for $$\begin{aligned}
     \operatorname{\mathsf{R}}(s,x_{1}) \mid\mid \operatorname{\mathsf{R}}(s,x_{2}) \mid\mid \ldots \mid\mid \operatorname{\mathsf{R}}(s,x_{\ell(\kappa)}).
  \end{aligned}$$ To give a formal definition of $\{{\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{R}}}(\ell)\}_{\kappa\in {\mathbb{N}}}$ we need to specify the probability distributions for any history $h$. Thus, we define the family, on the alphabet $\{0,1\}$, as follows: For empty history $h=\varnothing$, we define ${\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{R}}}(\ell)_{\varnothing}$ as the distribution on all possible keys generated by $\operatorname{\mathsf{Gen}}(1^{\kappa})$. For $s\in \operatorname{supp}(\operatorname{\mathsf{Gen}}(1^{\kappa}))$ and a (possibly empty) sequence inputs $x_{1},x_{2},\ldots, x_{r}$ with $x_{i}\in \operatorname{supp}(\operatorname{\mathsf{GenInput}}(1^{\kappa}))$ and $0\leq r\leq \ell(\kappa)-1$, the distribution ${\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{R}}}(\ell)_{s\mid\mid x_{1}\mid\mid
    x_{2}\mid\mid \ldots \mid\mid x_{r}}$ is the distribution on inputs $x_{r+1}\gets \operatorname{\mathsf{GenInput}}(1^{\kappa})$. For $s\in \operatorname{supp}(\operatorname{\mathsf{Gen}}(1^{\kappa}))$, a sequence of inputs $x_{1},x_{2},\ldots, x_{\ell(\kappa)}$ with $x_{i}\in\operatorname{supp}(\operatorname{\mathsf{GenInput}}(1^{\kappa}))$, and a (possibly empty) sequence of $\operatorname{\mathsf{R}}$’s outputs $y_{1},\ldots,y_{r}$ with $y_{i}\in \operatorname{supp}(\operatorname{\mathsf{R}}(s,x_{((i-1)\bmod
    \ell(\kappa))+1}))$, the probability distribution of ${\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{R}}}(\ell)_{s\mid\mid x_{1}\mid\mid
    x_{2}\mid\mid \ldots \mid\mid x_{\ell(\kappa)}\mid\mid
    y_{1}\mid\mid y_{2}\mid\mid \ldots \mid\mid
    \ldots  \mid\mid y_{r}}$ is the probability distribution of $\operatorname{\mathsf{R}}(s,x_{(r \bmod \ell(\kappa))+1})$.

Results
-------

The theorems proved in the previous section can simply be generalized by using our general construction of the channel ${\mathcal{C}}^{k}_{\operatorname{\mathsf{R}}}(\ell)$ for the randomized algorithm $\operatorname{\mathsf{R}}$ and the generic stegosystem $\operatorname{\mathsf{RejSam}}^{\operatorname{\mathsf{F}}}$ provided by Theorem \[thm:rejsam:secure\].

\[thm:generic-attack:against:R\] For every randomized algorithm $\operatorname{\mathsf{R}}$, there exists a generic algorithm substitution attack $\operatorname{\mathsf{ASA}}$ against $\operatorname{\mathsf{R}}$ such that $$\begin{array}{rcl}
      \operatorname{\mathbf{InSec}}^{\operatorname{\operatorname{\mathsf{ASA}}}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{R}}}(\kappa)&\leq&
 \mathcal{O}(\operatorname{\mathsf{ml}}(\kappa)^{4}\cdot 2^{-{H_{\infty}}({\mathcal{C}}^{\kappa})})+\\
&&\mathcal{O}(\operatorname{\mathsf{ml}}(\kappa)^{2}\cdot
    \exp(-s))+
     \operatorname{\mathbf{InSec}}^{\operatorname{prf}}_{\operatorname{\mathsf{F}}}(\kappa),\\[2mm]
      \operatorname{\mathbf{UnRel}}^{\star}_{\operatorname{\mathsf{S}},{\mathcal{C}}}(\kappa) &\leq&
    2 \operatorname{\mathsf{ml}}(\kappa)^{2}\cdot
    \exp(-2^{{H_{\infty}}({\mathcal{C}}^{\kappa})-3}) +\\
&&  \operatorname{\mathsf{ml}}(\kappa)^{2}\cdot  \exp(-2^{-2} s)+
    \operatorname{\mathbf{InSec}}^{\operatorname{prf}}_{\operatorname{\mathsf{F}}}(\kappa)                
  \end{array}$$ where ${\mathcal{C}}:={\mathcal{C}}^{\kappa}_{\operatorname{\mathsf{R}}}({\operatorname{\mathsf{S}}\!.\!\operatorname{\mathsf{ol}}}(\kappa))$.

\[thm:no-attack:against:R\] For all deterministic algorithms $\operatorname{\mathsf{R}}$ and all algorithm substitution attacks $\operatorname{\mathsf{ASA}}$ against $\operatorname{\mathsf{R}}$: $$\begin{aligned}
    \operatorname{\mathbf{InSec}}^{\operatorname{asa}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{R}}}(\kappa) = 1.\end{aligned}$$

Theorem \[thm:generic-attack\] is thus just a consequence of Theorem \[thm:generic-attack:against:R\] and Theorem \[thm:min-entropy\] is just a consequence of Theorem \[thm:no-attack:against:R\].

These general results also imply several other results from the literature, for example on signature schemes. Ateniese et al. [@ateniese2015sig] study algorithm substitution attacks[^3] on *signature schemes* $\operatorname{\mathsf{SIG}}=(\operatorname{\mathsf{Gen}},\operatorname{\mathsf{Sign}},\operatorname{\mathsf{Vrfy}})$, where

-   The *key generator* ${\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Gen}}}$ produces upon input $1^{\kappa}$ a pair $({\textit{pk}},{\textit{sk}})$ of keys with $|{\textit{pk}}|=|{\textit{sk}}|=\kappa$. We call ${\textit{pk}}$ the *public key* and ${\textit{sk}}$ the *secret key*.

-   The *signing algorithm* ${\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Sign}}}$ takes as input the secret key ${\textit{sk}}$ and a message $m\in \{0,1\}^{{\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{ml}}}}$ of length ${\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)$ and produces a signature $\sigma\in \{0,1\}^{{\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{sl}}}(\kappa)}$ of length ${\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{sl}}}(\kappa)$.

-   The *verifying algorithm* ${\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Vrfy}}}$ takes as input the public key ${\textit{pk}}$, the message $m$ and a signature $\sigma$ and outputs a bit $b$.

On the positive side (from the view of an algorithm substitution attack) they show that all randomized *coin-injective* schemes and all *coin-extractable* schemes have ASA. A randomized algorithm $A$ is *coin-injective*, if the function $f_{A}(x,\rho)=A(x;\rho)$ (where $\rho$ denotes the random coins used by $A$) is injective and *coin-extractable* if there is another randomized algorithm $B$ such that $\Pr[B(A(x;\rho))=\rho] \geq 1-\operatorname{\mathsf{negl}}$ for a negligible function $\operatorname{\mathsf{negl}}$. They prove the following theorems:

For every coin-injective signature scheme $\operatorname{\mathsf{SIG}}$, there is a successful algorithm substitution attack $\operatorname{\mathsf{ASA}}$ and a negligible function $\operatorname{\mathsf{negl}}$ such that $$\begin{aligned}
      \operatorname{\mathbf{InSec}}^{\operatorname{asa}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SIG}}}(\kappa)\leq \operatorname{\mathbf{InSec}}^{\operatorname{prf}}_{\mathsf{F}}(\kappa)+\operatorname{\mathsf{negl}}(\kappa)
    \end{aligned}$$ for a pseudorandom function $\mathsf{F}$.

For every coin-extractable signature scheme $\operatorname{\mathsf{SIG}}$, there is a successful algorithm substitution attack $\operatorname{\mathsf{ASA}}$ and a negligible function $\operatorname{\mathsf{negl}}$ such that $$\begin{aligned}
            \operatorname{\mathbf{InSec}}^{\operatorname{asa}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SIG}}}(\kappa)\leq \operatorname{\mathsf{negl}}(\kappa).
    \end{aligned}$$

Both of these results are easily implied by Theorem \[thm:generic-attack:against:R\].

On the negative side (from the view of an algorithm substitution attack), they show that *unique signature schemes* are resistant to ASAs fulfilling the *verifiability condition*. Informally this means that (a) each message has exactly on signature (for a fixed key-pair) and (b) each signature produced by the ASA must be valid.

For all unique signature schemes $\operatorname{\mathsf{SIG}}$ and all algorithm substitution attacks $\operatorname{\mathsf{ASA}}$ against them that fulfill the verifiability condition, there is a negligible function $\operatorname{\mathsf{negl}}$ such that $$\begin{aligned}
            \operatorname{\mathbf{InSec}}^{\operatorname{asa}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SIG}}}(\kappa)\geq 1-\operatorname{\mathsf{negl}}(\kappa).
    \end{aligned}$$

As unique signature schemes do not provide enough min-entropy for a stegosystem, this results follows from Theorem \[thm:min-entropy\].

A Lower Bound for Universal ASA {#sec:bound}
===============================

A setting similar to steganography, where *universal* stegosystems exist, that can be used for *any* channel of sufficiently large min-entropy, would be quite useful for attackers that plan to launch algorithm substitution attacks. Such a system would allow them to attack any symmetric encryption scheme *without* knowing the internal specification of the encryption algorithm. A closer look at the results in [@bellare2014asa; @bellare2015asa; @ateniese2015sig] reveals that their attacks do indeed go without internal knowledge of the used encryption algorithm. They only manipulate the random coins used in the encryption process. Note that ${\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}}(k,m;r)$ (where $r$ denotes the random coins used by $\operatorname{\mathsf{Enc}}$) is a deterministic function, as ${\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}}$ is a PPTM.

We thus define a *universal algorithm substitution attack* as a triple of PPTMs such that for every symmetric encryption scheme $\operatorname{\mathsf{SES}}$, the triple $$\begin{aligned}
\operatorname{\mathsf{ASA}}^{\operatorname{\mathsf{SES}}}=({\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Gen}}},{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}^{{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}}(\cdot,\cdot; \cdot)},{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Ext}}})  \end{aligned}$$ is an ASA against $\operatorname{\mathsf{SES}}$. Hence, ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}$ has only oracle access to the encryption algorithm ${\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}}$ of the encryption scheme: It may thus choose arbitrary values $k$, $m$, and $r$ and receives a ciphertext $$\begin{aligned}
c\gets {\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}}(k,m; r)  \end{aligned}$$ without having a complete description of the encryption schemes.

As noted above, all attacks in [@bellare2014asa; @bellare2015asa; @ateniese2015sig] are universal and @bellare2015asa explicitly state in their work [@bellare2015asa] that their ASA works against any encryption scheme of sufficiently large min-entropy. We also remark that the rejection sampling ASA presented earlier is universal.

For a universal algorithm substitution attack $\operatorname{\mathsf{ASA}}$ and a symmetric encryption scheme $\operatorname{\mathsf{SES}}$, let ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{query}}}(\operatorname{\mathsf{SES}},\kappa,{\textit{ak}},{\textit{am}},k,m_j,\sigma)$ be the expected number of oracle calls that a single call of the substitution encoder ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}^{{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}}(\cdot,\cdot;\cdot)}({\textit{ak}},{\textit{am}},k,m_j,\sigma)$ makes to its encryption oracle ${\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}}$. We then define $$\begin{aligned}
  &{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{query}}}(\operatorname{\mathsf{SES}},\kappa)=\\
  &\max_{\substack{{\textit{ak}}\in\operatorname{supp}({\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa})),\\ {\textit{am}}\in \{0,1\}^{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)},\\ k\in \operatorname{supp}({\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa})),\\ m\in \{0,1\}^{{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)},\\ \sigma\in \{0,1\}^{*}}} \{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{query}}}(\operatorname{\mathsf{SES}},\kappa,{\textit{ak}},{\textit{am}},k,m_j,\sigma)\}.\end{aligned}$$ For a family $\mathcal{F}$ of encryption schemes, let ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{query}}}(\mathcal{F},\kappa)$ be the maximal value of ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{query}}}(\operatorname{\mathsf{SES}},\kappa)$ for $\operatorname{\mathsf{SES}}\in \mathcal{F}$.

In the steganographic setting, @dedic2009upper showed in [@dedic2009upper] that (under the cryptographic assumption that one-way functions exist) no universal stegosystem can embed more than $\mathcal{O}(1)\cdot \log(\kappa)$ bits per document and thus proved that the rejection sampling based systems have optimal rate. The needed ingredients of this proof are summarized by two key lemmas based on Lemma 12 and Lemma 13 in [@Berndt2016].

\[lem:secure\_asa\] Let $\operatorname{\mathsf{ASA}}$ be a algorithm substitution attack for the symmetric encryption scheme $\operatorname{\mathsf{SES}}$ such that $\operatorname{\mathsf{ASA}}$ is secure against $\operatorname{\mathsf{SES}}$. Then for all integers $\kappa\in {\mathbb{N}}$, messages $m\in \{0,1\}^{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$, ciphertexts $c_{1},c_{2},\ldots,c_{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)}\gets
{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}({\textit{ak}},{\textit{am}},k,m,\sigma)$ and all positions $i\in
\{1,\ldots,{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)\}$: $$\begin{aligned}
\Pr_{{\textit{ak}}\gets {\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa})}[c_{i}\not\in \operatorname{supp}({\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}}(k,m))]
   \leq \operatorname{\mathbf{InSec}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa).\end{aligned}$$

\[lem:reliable\_asa\] Let $\operatorname{\mathsf{ASA}}$ be a universal and reliable algorithm substitution attack against the symmetric encryption scheme $\operatorname{\mathsf{SES}}$. Then for every $\kappa$, the probability that the encoder ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}$ produces a ciphertext, which was not provided by the encryption oracle, is at least $$\begin{aligned}
 1-\operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}}(\kappa)-\frac{({\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)\cdot {\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{query}}}(\operatorname{\mathsf{SES}},\kappa))^{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)}}{2^{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}}.
  \end{aligned}$$

We will now show how one can modify an existing symmetric encryption scheme $\operatorname{\mathsf{SES}}$ with the help of a signature scheme $\operatorname{\mathsf{SIG}}$ into a family of encryption schemes such that no universal ASA can achieve a super-logarithmic rate on all of these encryption schemes. The construction is very similar to the construction used in [@Berndt2016].

A *signature scheme* $\operatorname{\mathsf{SIG}}=({\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Gen}}},{\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Sign}}},{\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Vrfy}}})$ is a triple of probabilistic polynomial-time algorithms with the following properties:

-   The *key generator* ${\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Gen}}}$ produces upon input $1^{\kappa}$ a pair $({\textit{pk}},{\textit{sk}})$ of keys with $|{\textit{pk}}|=|{\textit{sk}}|=\kappa$. We call ${\textit{pk}}$ the *public key* and ${\textit{sk}}$ the *secret key*.

-   The *signing algorithm* ${\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Sign}}}$ takes as input the secret key ${\textit{sk}}$ and a message $m\in \{0,1\}^{{\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{ml}}}}$ of length ${\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)$ and produces a signature $\sigma\in \{0,1\}^{{\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{sl}}}(\kappa)}$ of length ${\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{sl}}}(\kappa)$.

-   The *verifying algorithm* ${\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Vrfy}}}$ takes as input the public key ${\textit{pk}}$, the message $m$ and a signature $\sigma$ and outputs a bit $b$.

We say that $(\operatorname{\mathsf{Gen}},\operatorname{\mathsf{Sign}},\operatorname{\mathsf{Vrfy}})$ is *reliable*, if $\operatorname{\mathsf{Vrfy}}({\textit{pk}},m,\operatorname{\mathsf{Sign}}({\textit{sk}},m))=1$ for all ${\textit{pk}}$, ${\textit{sk}}$ and $m$.

A *forger* $\operatorname{\mathsf{Fo}}$ is a probabilistic polynomial time algorithm that upon input ${\textit{pk}}$ and oracle access to $\operatorname{\mathsf{Sign}}_{{\textit{sk}}}$ tries to produce a pair $(m,\sigma)$ such that $\operatorname{\mathsf{Vrfy}}_{{\textit{pk}}}(m,\sigma)=1$. Formally, this is defined via the following experiment $\operatorname{\mathsf{Sig-Forge}}$:

Forger $\operatorname{\mathsf{Fo}}$, Signature Scheme $\operatorname{\mathsf{SIG}}=(\operatorname{\mathsf{Gen}},\operatorname{\mathsf{Sign}},\operatorname{\mathsf{Vrfy}})$ length $\kappa$

$({\textit{pk}},{\textit{sk}}) \gets \operatorname{\mathsf{Gen}}(1^{\kappa})$ $(m,\sigma) \gets \operatorname{\mathsf{Fo}}^{\operatorname{\mathsf{Sign}}_{{\textit{sk}}}}({\textit{pk}})$ Let $Q$ be the set of messages given to $\operatorname{\mathsf{Sign}}_{{\textit{sk}}}$ by $\operatorname{\mathsf{Fo}}$

A signature scheme $\operatorname{\mathsf{SIG}}$ is called *existentially unforgeable*, if for every forger $\operatorname{\mathsf{Fo}}$, there is a negligible function $\operatorname{\mathsf{negl}}$ such that $$\begin{aligned}
  \operatorname{\mathbf{Adv}}^{\operatorname{sig}}_{\operatorname{\mathsf{Fo}},\operatorname{\mathsf{SIG}}}(\kappa) :=
  \Pr[\operatorname{\mathsf{Sig-Forge}}_{\operatorname{\mathsf{Fo}},\operatorname{\mathsf{SIG}}}(\kappa)=1]\leq \operatorname{\mathsf{negl}}(\kappa).\end{aligned}$$

The maximal advantage of any forger against $\operatorname{\mathsf{SIG}}$ is called the *insecurity* of $\operatorname{\mathsf{SIG}}$ and is defined as $$\begin{aligned}
  \operatorname{\mathbf{InSec}}_{\operatorname{\mathsf{SIG}}}^{\operatorname{sig}}(\kappa) := \max_{\operatorname{\mathsf{Fo}}}\{\operatorname{\mathbf{Adv}}^{\operatorname{sig}}_{\operatorname{\mathsf{Fo}},\operatorname{\mathsf{SIG}}}(\kappa)\}.\end{aligned}$$

For $({\textit{pk}},{\textit{sk}})\in
\operatorname{supp}({\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa}))$, let $\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}$ be the encryption scheme with

-   ${\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}\!.\!\operatorname{\mathsf{Gen}}}={\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Gen}}}$, [i.e.]{}the key generation algorithm remains the same.

-   The encryption algorithm ${\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}\!.\!\operatorname{\mathsf{Enc}}}$ is given as:

    key $k$, message $m$

    $c \gets {\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}}(k,m)$ $\gets {\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Sign}}}({\textit{sk}},c)$

-   Similarly, the decryption algorithm ${\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}\!.\!\operatorname{\mathsf{Dec}}}$ is given as:

    key $k$, ciphertext $(c,\sigma)$

By using this family $$\begin{aligned}
\mathcal{F}(\operatorname{\mathsf{SES}},\operatorname{\mathsf{SIG}})=\{\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}\}_{({\textit{pk}},{\textit{sk}})\in     \operatorname{supp}({\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa}))},\end{aligned}$$

we can derive the following upper bound on the rate of each universal ASA:

Let $\operatorname{\mathsf{SES}}$ be a symmetric encryption scheme, $\operatorname{\mathsf{SIG}}$ be a signature scheme and $\mathcal{F}=\mathcal{F}(\operatorname{\mathsf{SES}},\operatorname{\mathsf{SIG}})$ be defined as above. For every universal algorithm substitution attack $\operatorname{\mathsf{ASA}}$ against $\operatorname{\mathsf{SES}}$, there exist a forger $\operatorname{\mathsf{Fo}}$ on $\operatorname{\mathsf{SIG}}$ with advantage at least $$\begin{aligned}
1-\operatorname{\mathbf{InSec}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{ASA}},\mathcal{F}}(\kappa)-\operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{ASA}},\mathcal{F}}(\kappa)-\varphi(\operatorname{\mathsf{ASA}},\kappa)
  \end{aligned}$$ for every $\kappa$, where $$\begin{aligned}
    \varphi(\operatorname{\mathsf{ASA}},\kappa)=\frac{({\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)\cdot {\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{query}}}(\mathcal{F},\kappa))^{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)}}{2^{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}}.
  \end{aligned}$$

The proof is analogue to the proof of [@Berndt2016 Theorem 13].

Fix $\kappa\in {\mathbb{N}}$ and $({\textit{pk}},{\textit{sk}})\in \operatorname{supp}({\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa}))$. We will now construct an forger on $\operatorname{\mathsf{SIG}}$ with the help of the algorithm substitution attacker $\operatorname{\mathsf{ASA}}$. Choose a random attacker message ${\textit{am}}^{*}\gets
  \{0,1\}^{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$, a random attacker key ${\textit{ak}}^{*}\gets {\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa})$, a random message $m^{*}\gets  \{0,1\}^{{\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}$ and a random key $k^{*}\gets {\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Gen}}}(1^{\kappa})$.

The forger now simulates the run of the algorithm substitution attack ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}^{{\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}\!.\!\operatorname{\mathsf{Enc}}}(\cdot,\cdot;\cdot)}({\textit{ak}}^{*},{\textit{am}}^{*},k^{*},m^{*})$ against the symmetric encryption scheme $\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}$. Whenever ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}$ makes an access $(k,m;r)$ to its encryption oracle, the forger computes $c={\operatorname{\mathsf{SES}}\!.\!\operatorname{\mathsf{Enc}}}(k,m;r)$ and uses its signing oracle ${\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Sign}}}_{{\textit{sk}}}$ upon $c$. This returns a valid signature $\sigma$ for $c$ and the forger returns $(c,\sigma)$ to ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}$. This simulation hence yields the same result as ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}^{{\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}\!.\!\operatorname{\mathsf{Enc}}}(\cdot,\cdot;\cdot)}({\textit{ak}}^{*},{\textit{am}}^{*},k^{*},m^{*})$. Denote the first document produced by the run of the algorithm substitution attack ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}^{{\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}\!.\!\operatorname{\mathsf{Enc}}}(\cdot,\cdot;\cdot)}({\textit{ak}}^{*},{\textit{am}}^{*},k^{*},m^{*})$ as $(\widehat{c},\widehat{\sigma})$. By , the probability that the pair $(\widehat{c},\widehat{\sigma})$ does not belong to to the support $\operatorname{supp}({\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}\!.\!\operatorname{\mathsf{Enc}}}(k,m))$ ([i.e.]{}it is no valid ciphertext-signature pair) is bounded by $\operatorname{\mathbf{InSec}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}}(\kappa)$. Furthermore, implies that the probability that $(\widehat{c},\widehat{\sigma})$ is equal to any $(c,\sigma)$ which was given to the ASA is at most $\operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}}(\kappa)+\varphi(\operatorname{\mathsf{ASA}},\kappa)$. We can thus conclude that with probability $$\begin{aligned}
    1-&\operatorname{\mathbf{InSec}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}}(\kappa)-\operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}}(\kappa)-\\
      &\frac{({\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)\cdot {\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{query}}}(\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}},\kappa))^{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)}}{2^{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}},
  \end{aligned}$$ the ciphertext-signature pair $(\widehat{c},\widehat{\sigma})$ is a valid ciphertext-signature pair and was not produced by the oracle ${\operatorname{\mathsf{SIG}}\!.\!\operatorname{\mathsf{Sign}}}_{{\textit{sk}}}$ The advantage of the forger against the signature scheme $\operatorname{\mathsf{SIG}}$ is thus at least $$\begin{aligned}
    1-&\operatorname{\mathbf{InSec}}^{\operatorname{enc-watch}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}}(\kappa)-\operatorname{\mathbf{UnRel}}_{\operatorname{\mathsf{ASA}},\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}}}(\kappa)-\\
    &\frac{({\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)\cdot {\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{query}}}(\operatorname{\mathsf{SES}}_{{\textit{pk}},{\textit{sk}}},\kappa))^{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ol}}}(\kappa)}}{2^{{\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{ml}}}(\kappa)}},
  \end{aligned}$$ The running time of the forger is polynomial in $\kappa$ due to the polynomial running time of ${\operatorname{\mathsf{ASA}}\!.\!\operatorname{\mathsf{Enc}}}$.

This allows us to conclude the following corollary bounding the number of bits embeddable into a single ciphertext by a universal algorithm substitution attack.

\[cor:bound\] There is no universal algorithm substitution attack that embeds more than $\mathcal{O}(1)\cdot \log(\kappa)$ bits per ciphertext (unless one-way functions do not exist).

Conclusions
===========

In this work, we proved that ASAs in the strong undetectability model of Bellare, Jaeger and Kane [@bellare2015asa] are a special case of stegosystems on a certain kind of channels described by symmetric encryption schemes. This gives a rigorous proof of the well-known connection between steganography and algorithm substitution attacks. We make use of this relationship to show that a wide range of results on ASAs are already present in the steganographic literature. Inspired by this connection, we define *universal ASAs* that work with no knowledge on the internal implementation of the symmetric encryption schemes and thus work for *all* such encryption schemes with sufficiently large min-entropy. As almost all known ASAs are universal, we investigate their rate – the number of embedded bits per ciphertext – and prove a logarithmic upper bound of this rate.

[00]{}

\#1 \#1[[DOI:]{}0[\#1]{} ]{} \#1 \#1 \#1 \#1 \#1[\#1]{} \#1[\#1]{} \#1[\#1]{}

[anderson1996limits]{} . . In , Vol. . , .

[ateniese2015sig]{} . . In . ACM, .

[backes2005public]{} . . In , Vol. . , .

[ball2013revealed]{} . . ().

[bellare1997concrete]{} . . In . , .

[bellare2015asa]{} . . In . ACM, .

[bellare2014asa]{} . . In , Vol. . .

[bellare1993randomoracle]{} . . In . , .

[Berndt2016]{} . . In , Vol. . , .

[Cachin2004]{} . . , (), .

[checkoway2014dual]{} . . In . , .

[dedic2009upper]{} . . , (), .

[degabriele2015asa]{} . . In , Vol. . , .

[greenwald2014no]{} . . .

[hopper2002provably]{} . . In . , Vol. . , .

[hopper2009provably]{} . . , (), .

[lindell2007introduction]{} . . .

[katzenbeisser2002defining]{} . . In . SPIE, .

[mitzenmacher2005probability]{} . . .

[pasquini2017decoy]{} . . In , Vol. . Springer, .

[perlroth2013nsa]{} . . ().

[russell2016cliptography]{} . . In , Vol. . Springer, .

[russell2016destroying]{} . (), .

[schneier2007did]{} . . ().

[schneier2015survey]{} . . (), .

[shumow2007back]{} . . . ().

[simmons1984prisoners]{} . . In . Springer, .

[simmons1998history]{} . . , (), .

[young1996dark]{} . . In , Vol. . Springer, .

[young1997kleptography]{} . . In , Vol. . Springer, .

[^1]: <https://www.openssl.org/>

[^2]: In [@bellare2015asa], this is called the *key recovery security*.

[^3]: To be more precise, their attacks only replace the signing algorithm $\operatorname{\mathsf{Sign}}$.
