Subverting Decryption in AEAD

Abstract

This work introduces a new class of Algorithm Substitution Attack (ASA) on Symmetric Encryption Schemes. ASAs were introduced by Bellare, Paterson and Rogaway in light of revelations concerning mass surveillance. An ASA replaces an encryption scheme with a subverted version that aims to reveal information to an adversary engaged in mass surveillance, while remaining undetected by users. Previous work posited that a particular class of AEAD scheme (satisfying certain correctness and uniqueness properties) is resilient against subversion. Many if not all real-world constructions – such as GCM, CCM and OCB – are members of this class. Our results stand in opposition to those prior results. We present a potent ASA that generically applies to any AEAD scheme, is undetectable in all previous frameworks and which achieves successful exfiltration of user keys. We give even more efficient non-generic attacks against a selection of AEAD implementations that are most used in practice. In contrast to prior work, our new class of attack targets the decryption algorithm rather than encryption. We argue that this attack represents an attractive opportunity for a mass surveillance adversary. Our work serves to refine the ASA model and contributes to a series of papers that raises awareness and understanding about what is possible with ASAs.

The research of Armour was supported by the EPSRC and the UK government as part of the Centre for Doctoral Training in Cyber Security at Royal Holloway, University of London (EP/P009301/1). The research of Poettering was supported by the European Union’s Horizon 2020 project FutureTPM (779391). The full version of this article is available at https://eprint.iacr.org/2019/987 [3].

1 Introduction

The Snowden revelations in 2013 exposed that mass surveillance is a reality. They also showed that even sophisticated adversaries with large resources have been unable to break well established cryptographic primitives and hardness assumptions, shifting their focus to circumventing cryptography. Together, these two facts suggest that the study of subverted implementations of cryptographic primitives and protocols is a fruitful area of research; Rogaway has gone so far as to call it a moral imperative [23]. The reader is referred to the survey by Schneier et al. [28], which provides a broad overview of subversion of cryptography, with some useful case studies. The idea that an adversary may embed a backdoor or otherwise tamper with the implementation or specification of a cryptographic scheme or primitive predates the Snowden revelations, and was initiated in a line of work by Young and Yung that they named kleptography [30, 31]. This area of study can be traced back to Simmons’ work on subliminal channels, e.g. [29], undertaken in the context of nuclear non-proliferation during the Cold War. In the original conception, kleptography considered a saboteur who designs a cryptographic algorithm whose outputs are computationally indistinguishable from the outputs of an unmodified trusted algorithm. The saboteur’s algorithm should leak private key data through the output of the system, which was achieved using the same principles as Simmons’ earlier subliminal channels.

Preceding Work. Post-Snowden, work in this area was reignited by Bellare, Paterson and Rogaway (BPR) [8], who formalised study of so-called algorithm substitution attacks (ASAs) through the specific example of symmetric encryption schemes. In abstract terms, the adversary’s goal in an ASA is to create a subverted implementation of a scheme that breaks some aspect of security (such as IND-CPA) while remaining undetected by the user. There is a tension for ‘Big Brother’ between mounting a successful attack and being detected; clearly an attack that simply replaces the encryption algorithm with one that outputs the messages in plaintext would be devastating yet trivially detectable. BPR stipulate that subverted schemes should at the very least decrypt correctly (according to the unmodified specification) in order to have some measure of resistance to detection, going on to define the success probability of a mass surveillance adversary in carrying out a successful attack, as well as the advantage of a user in detecting that an attack is taking place. BPR [8] demonstrate an attack against randomized schemes that relies on influencing the randomness generated in the course of encryption. Their attack applies to a sub-class of randomized schemes satisfying a property they call ‘coin-injectivity’. Lastly, BPR also establish a positive result that shows that under certain assumptions, it is possible for authenticated encryption schemes to provide resistance against subversion attacks.

Degabriele, Farshim and Poettering (DFP) [12] critiqued the definitions and underlying assumptions of BPR. Their main insight is that perfect decryptability—as mandated by BPR—is a very strong requirement and artificially limits the adversary’s set of available strategies. In practice, a subversion with negligible failure probability should be considered effectively correct.¹ As DFP note, decryption failures may happen for reasons other than subverted encryption, and if they occur sporadically may easily go unnoticed. DFP demonstrate how this can be achieved with an input-triggered subversion, where the trigger is some input (message, associated data, nonce, or a combination thereof) that is difficult to guess, making detection practically impossible.

Bellare, Jaeger and Kane (BJK) [6] improved on the attack of BPR, giving an attack which is effective against all randomized schemes. Whereas the attack of BPR is stateful and so vulnerable to detection through state reset, the BJK attack is stateless. BJK furthermore formalised that the desired outcome of an ASA from the point of view of a mass surveillance adversary is successful key recovery.

In concurrent work, we study the effects of subverting the receiver in the setting of message authentication codes [1, 2]. Using similar techniques as in the current report, we provide ASAs that result in successful key exfiltration and thus universal forgeries.

Contributions. Our work continues a line of investigation that serves to raise awareness of what is possible with ASAs, and highlights the importance of work countering subverted implementations. We consider ASAs from a new perspective that leads to results of practical importance. Recall that BPR established a covert channel through ciphertexts by manipulating the randomness generation; their model stipulated perfect decryptability, which resulted in their definitions being fragile. DFP identified this and proposed tolerating a (minimal) compromise of correctness, allowing trigger messages. We note that attacks employing trigger messages appear trivial to plant in formal security abstractions like IND-CPA where the adversary has full control over encrypted messages, associated data, and nonces. In practice, however, it is certainly questionable that adversaries have enough influence on any of the three to conduct DFP style attacks, as messages are chosen in special formats mandated by applications, nonces are implemented via counters, etc. We remove these dependencies, complementing the DFP approach, by attacking from a different angle: leaving perfect correctness intact, we (minimally) limit ciphertext integrity and establish a covert channel through decryption error events. Concretely, we manipulate the decryption algorithm to accept certain bogus ciphertexts. This requires the surveillance adversary to be able to observe whether a decryption implementation outputs a message or rejects the ciphertext. In many practical scenarios this is a mild assumption, for example if a decryption error results in a packet being dropped and automatically retransmitted. Furthermore, a subverted decryption algorithm could go beyond this by e.g. influencing timing information in future messages sent to the network. We conclude that this attack represents an attractive and easy to implement opportunity for a mass surveillance adversary.

Our results stand in opposition to previous work [6, 8, 12] which proposed subversion resilience of a large class of AEAD schemes to which many if not all real-world constructions such as GCM, CCM and OCB belong, as long as their nonces are generated deterministically via a shared state maintained by both encryptor and decryptor.² The key observation to resolve this apparent contradiction is that previous work has assumed, besides explicitly spelled out requirements like uniqueness of ciphertexts and perfect decryptability, implicit notions such as integrity of ciphertexts. In the ASA setting for AEAD where undermining the confidentiality of a scheme is the key goal of an adversary, it seems just as natural to assume that the adversary is also willing to compromise the integrity guarantees as well.

Related Work. We outlined the key publications on ASAs against symmetric encryption schemes above. Other works, briefly described here, consider subversion on different primitives and in different contexts. Berndt and Liskiewicz [9] reunite the fields of cryptography and steganography. Ateniese, Magri and Venturi [4] study ASAs on signature schemes. In a series of work, Russell, Tang, Yung and Zhou [24,25,26,27] consider ASAs on one-way functions, trapdoor one-way functions and key generation as well as defending randomized algorithms against ASAs. Goh, Boneh, Pinkas and Golle [18] show how to add key recovery to the SSL/TLS and SSH protocols. Dodis, Ganesh, Golovnev, Juels and Ristenpart [13] provide a formal treatment of backdooring PRGs, another form of subversion. Armour and Poettering [1, 2] study subversion options for message authentication schemes (MAC). Cryptographic reverse firewalls [14, 20, 21] represent an architecture to counter ASAs via trusted code in network perimeter filters. Fischlin and Mazaheri show how to construct ASA-resistant encryption and signature algorithms given initial access to a trusted base scheme [17]. Fischlin, Janson and Mazaheri [16] show how to immunize (keyed and unkeyed) hash functions against subversion. Bellare, Kane and Rogaway [7] explore using large keys to prevent key exfiltration in the symmetric encryption setting. Bellare and Hoang [5] give public key encryption schemes that defend against the subversion of random number generators.

Camenisch, Drijvers and Lehmann [11] consider Direct Anonymous Attestation (DAA) in the presence of a subverted Trusted Platform Module (TPM). We note that subversion attacks on cryptographic primitives (on DAA, but just as well on message authentication as considered in the present article) manifest a major attack vector in particular against embedded cryptographic hardware modules like TPMs. This is because the main goal of such modules is to serve as a root of trust in exposed devices for which losing system integrity could be fatal. Subverting a TPM can thus have severe implications. As TPMs are widely available today, including for being embedded into virtually every modern PC, subverting them seems to be a promising option to conduct mass surveillance.

Structure. We first recall (Sect. 2) standard definitions for symmetric encryption schemes and their security. We next give definitions (Sect. 3) that provide a general framework in which to study ASAs. These have been refined and extended from prior work, crucially including the decryption oracle which had been ignored by previous work. Section 4 details our new type of attack, together with formal theorems quantifying the ability of an adversary to exfiltrate keys and the ability of the subversion to go undetected. We give two versions of our ASA: one for a passive adversary (the adversarial model considered by previous work), which we extend to a second ASA requiring an active trigger: a modified ciphertext provided to the decryption algorithm. We discuss the results of a proof-of-concept implementation in Sect. 5. Lastly, Sect. 6 explains how our attacks can be leveraged to compromise the security of popular practical schemes even more effectively, demonstrating how powerful ASAs become when conducted outside the clearly demarcated boundaries of a formal model. Concretely, we give evidence that ASAs against standardized AEAD constructions like GCM or OCB3 can be even more damaging than our attacks from Sect. 4.

2 Notation and Definitions

Notation. For a natural number $k \in \mathbb {N}$, we let $[k] = \{0, 1, \ldots , k - 1\}$. We refer to an element $x \in {\{0,1\}}^*$ as a string, and denote its length by |x|. By $\varepsilon$ we denote the empty string. The set of strings of length $\ell$ is denoted ${\{0,1\}}^\ell$. In addition we denote by $\bot \notin {\{0,1\}}^*$ a reserved special symbol. For $x\in {\{0,1\}}^*$, we let x[i] denote the i-th bit of x, with the convention that we count from 0, i.e., we have $x=x[0]\ldots x[|x|-1]$. For two strings $x, x'$ we denote by $x \mathrel {\Vert }x'$ their concatenation. If S is a finite set, then $s \leftarrow _{\scriptscriptstyle \$}S$ denotes choosing s uniformly at random from S. If $\mathcal {A}$ is a randomized algorithm, we write $y \leftarrow _{\scriptscriptstyle \$}\mathcal {A}(x)$ to indicate that it is invoked on input x (and fresh random coins), and the result is assigned to variable y. In security games we write $\mathcal {A}^{\mathcal {O}_1, \ldots , \mathcal {O}_c} \Longrightarrow 1$ to denote the event that the adversary outputs 1 after being given access to the c oracles.

In Appendix A, we recall standard definitions for (length-preserving) pseudo-random functions and permutations.

2.1 Symmetric Encryption

We focus on the likely most widespread and practically useful encryption primitive: Authenticated Encryption with Associated Data (AEAD). We recall standard definitions of (deterministic) nonce-based AEAD, as per [22].

AEAD. A symmetric encryption scheme ${\mathrm {\Pi }}$ providing authenticated encryption with associated data is a triple of algorithms $({\mathrm {\Pi }}.\mathsf {Gen}, {\mathrm {\Pi }}.\mathsf {Enc}, {\mathrm {\Pi }}.\mathsf {Dec})$. Associated to ${\mathrm {\Pi }}$ are two parameters, ${\mathrm {\Pi }}.\mathsf {kl}$ and ${\mathrm {\Pi }}.\mathsf {nl}$, representing the key length and the nonce length. The key generation algorithm ${\mathrm {\Pi }}.\mathsf {Gen}$ is a probabilistic algorithm that takes as input the key length ${\mathrm {\Pi }}.\mathsf {kl}$ and returns a key $k \in {\{0,1\}}^{{\mathrm {\Pi }}.\mathsf {kl}}$. Often ${\mathrm {\Pi }}.\mathsf {Gen}$ is taken as the algorithm choosing k uniformly at random from ${\{0,1\}}^{{\mathrm {\Pi }}.\mathsf {kl}}$. The encryption algorithm ${\mathrm {\Pi }}.\mathsf {Enc}$ is deterministic and takes key k, message m, associated data d and nonce $n \in {\{0,1\}}^{{\mathrm {\Pi }}.\mathsf {nl}}$ to deterministically obtain ciphertext $c \leftarrow {\mathrm {\Pi }}.\mathsf {Enc}(k, m, d; n)$. Decryption algorithm ${\mathrm {\Pi }}.\mathsf {Dec}$ is deterministic and ${\mathrm {\Pi }}.\mathsf {Dec}(k, c , d; n)$ returns either a message m or the special symbol $\bot$. For simplicity, we assume that $|{\mathrm {\Pi }}.\mathsf {Enc}(k, m, d; n)|$ is an affine function of the form $|m|+\tau$ where $\tau$ is some constant associated to the encryption scheme (all practical encryption schemes are of this type). We call $\tau$ the stretch of the encryption scheme. Lastly, where the context is clear, we drop the prefix ${\mathrm {\Pi }}$.

Definition 1

A symmetric encryption scheme ${\mathrm {\Pi }}$ is said to be $\delta$-correct if for all tuples (m, d; n) it holds that:

$$\begin{aligned} \Pr \left[ m \ne m' \mid k \leftarrow _{\scriptscriptstyle \$}\mathsf {Gen}(\mathsf {kl}), c \leftarrow \mathsf {Enc}(k, m, d; n), m' \leftarrow \mathsf {Dec}(k, c, d; n) \right] \le \delta . \end{aligned}$$

If $\delta = 0$ the scheme is referred to as being perfectly correct.

The classic privacy notion used for AEAD is indistinguishability from random bits under an adaptive chosen-plaintext-and-nonce attack, utilising standard game-based definitions. For the authenticity notion, we consider adversaries that aim to create (strong) forgeries. Security notions are as in [22]. Intuitively, the scheme provides confidentiality if the privacy advantage of any realistic adversary is negligible and authenticity if the forging advantage of any realistic adversary is negligible.

Definition 2

The privacy advantage of an adversary $\mathcal {A}$ is given by

where the $\$$ oracle returns $c \leftarrow _{\scriptscriptstyle \$}{\{0,1\}}^{|m| + \tau }$ for any query $\$(m, d; n)$. We assume that $\mathcal {A}$ is nonce-respecting; that is, $\mathcal {A}$ does not make two queries with the same nonce.

Definition 3

The authenticity advantage of an adversary $\mathcal {A}$ is given by

where we say that $\mathcal {A}$ forges if it receives any $m' \ne \bot$ from $\mathsf {Dec}$ where we require that (c, d; n) is not the result of an encryption query (m, d; n). We assume that $\mathcal {A}$ is nonce-respecting; that is, $\mathcal {A}$ does not make two encryption queries with the same nonce.

3 ASAs on Symmetric Encryption Schemes

We now outline the framework which will allow us to describe our concrete ASAs in Sect. 4. The aim of an ASA is to replace a given (symmetric encryption) scheme with a compromised version; if the original scheme is denoted ${\mathrm {\Pi }}$, we write $\widetilde{\mathrm {\Pi }}$ for its subversion. The attacker may choose to replace one component of the scheme, or multiple. We model the subverted scheme as having an embedded attacker key which is shared with an external (mass surveillance) adversary. This approach was first used by BPR [8]. From the attacker’s perspective, the ASA should be undetectable by the user and result in effective surveillance. We formalise these notions as detectability and key recovery. Our definitions are inherited from prior work [6, 8, 12]. Whereas previous work assumed that only the encryption algorithm might be subverted, we have generalised the definitions to reflect the possibility that any component (one or multiple) of the symmetric encryption scheme could be subverted, and adapted to explicitly consider AEAD schemes. We broadly follow the notational choices of BJK [6].

ASA Syntax. An algorithm substitution attack $\mathsf {A}$ on a scheme ${\mathrm {\Pi }}$ consists of a triple $(\mathsf {A}.\mathsf {Gen},\mathsf {A}.\mathsf {Ext}, \widetilde{\mathrm {\Pi }})$, where:

• 1. The attacker key generation algorithm $\mathsf {A}.\mathsf {Gen}$ returns an attacker key $k_\mathsf {A}\in {\{0,1\}}^{\mathsf {A}.\mathsf {kl}}$ for some constant $\mathsf {A}.\mathsf {kl}$.

• 2. $\widetilde{\mathrm {\Pi }}= (\widetilde{\mathrm {\Pi }}.\mathsf {Gen}, \widetilde{\mathrm {\Pi }}.\mathsf {Enc}, \widetilde{\mathrm {\Pi }}.\mathsf {Dec})$ is a subverted symmetric encryption scheme.

  • (a) The subverted key generation algorithm $\widetilde{\mathrm {\Pi }}.\mathsf {Gen}$ is a probabilistic algorithm that takes as input the key length $\widetilde{\mathrm {\Pi }}.\mathsf {kl}$ and the attacker key $k_\mathsf {A}$, returning a key $k \in {\{0,1\}}^{\widetilde{\mathrm {\Pi }}.\mathsf {kl}}$.

  • (b) The subverted encryption algorithm $\widetilde{\mathrm {\Pi }}.\mathsf {Enc}$ takes the attacker key $k_\mathsf {A}$, user key k, message m, associated data d and nonce $n \in {\{0,1\}}^{\widetilde{\mathrm {\Pi }}.\mathsf {nl}}$, outputting ciphertext $c\leftarrow \widetilde{\mathrm {\Pi }}.\mathsf {Enc}(k_\mathsf {A},k,m,d;n)$.

  • (c) The subverted decryption algorithm $\widetilde{\mathrm {\Pi }}.\mathsf {Dec}(k_\mathsf {A},k,c,d;n)$ returns either a message m or the special symbol $\bot$.

• 3. The key extraction algorithm $\mathsf {A}.\mathsf {Ext}$ takes as input $k_\mathsf {A}$ and has oracle access to both encryption and decryption oracles in the case of an active adversary, or to a transcript of ciphertexts in the case of a passive adversary. These notions are formalised in the key recovery game in Fig. 2. The output of this algorithm is a key $k \in {\{0,1\}}^{\widetilde{\mathrm {\Pi }}.\mathsf {kl}}$.

We require that $\widetilde{\mathrm {\Pi }}.\mathsf {kl}= {\mathrm {\Pi }}.\mathsf {kl}$ and $\widetilde{\mathrm {\Pi }}.\mathsf {nl}= {\mathrm {\Pi }}.\mathsf {nl}$, as the subverted algorithm would otherwise be trivially detected. As in previous work, we assume throughout that the key generation is unsubverted, but we retain a syntax that allows for the more general case.

Fig. 1.

Game to define the detectability advantage of $\mathcal {D}$ with respect to $\widetilde{\mathrm {\Pi }},{\mathrm {\Pi }}$.

Detectability. In the formal notion of detectability, we allow a distinguisher $\mathcal {D}$ to interact with subverted encryption, subverted decryption and (for generality) subverted key generation. We assume that the distinguisher has access to its own reference copy of the unsubverted algorithms. It wins if it can distinguish between the base scheme and the subverted scheme in the game defined in Fig. 1. The detectability advantage of $\mathcal {D}$ with respect to ${\mathrm {\Pi }}$, $\widetilde{\mathrm {\Pi }}$ is given by

This definition is adapted from strong undetectability of [6]. Notice that (informally) a ‘hard-to-detect’ subversion of a perfectly correct base scheme necessarily satisfies some correctness condition. To see this, suppose that the subversion does not satisfy $\delta$-correctness: it is detectable with probability at least $\delta$.

Key Recovery. Following [6], recovering the user’s secret key is a strong property for an attacker. We give two flavours of the key recovery game, one for passive adversaries $\mathsf {PassiveKR}$ and one for active adversaries $\mathsf {ActiveKR}$, as given in Fig. 2. In the passive case, we allow the adversary to observe ciphertexts and whether they are rejected. This is formalised through the transcript oracle $\mathcal {O}_\mathsf {Trans}$. For the active case, we allow the attacker to generate valid ciphertexts via $\mathcal {O}_\mathsf {Enc}$ and interact with a decryption oracle $\mathcal {O}_\mathsf {Dec}$ that reveals whether a submitted ciphertext is rejected. Both games are parametrised by a message sampler algorithm $\mathcal {M}$. Given its current state $\sigma$, $\mathcal {M}$ returns the next message with associated data (m, d) to be encrypted, together with a nonce $n \in {\{0,1\}}^{{\mathrm {\Pi }}.\mathsf {nl}}$ and an updated state. It represents the choice of messages made by the sender. For simplicity, we model $\mathcal {M}$ as non-adaptive and nonce-respecting. It could be argued that a more realistic model might take into account that the adversary could influence the user’s choice of messages to be encrypted. However, in constructing attacks we assume the weakest properties of the attacker.

Adversary $\mathsf {A}$ wins if $\mathsf {A}.\mathsf {Ext}$ recovers the user’s key k after interacting with the subverted encryption scheme. The key recovery advantage of $\mathsf {A}$ with respect to $\widetilde{\mathrm {\Pi }}$ and $\mathcal {M}$ is given by

where $\mathsf {{}KR}_{\widetilde{\mathrm {\Pi }}, \mathcal {M}}(\mathsf {A})$ refers to the appropriate key recovery game according to whether the adversary is passive or active.

Fig. 2.

Game to define the key recovery advantage of $\mathsf {A}$ with respect to $\widetilde{\mathrm {\Pi }}$ and $\mathcal {M}$.

4 Mounting Attacks via Decryption Subversion

We now detail our ASAs, first for a passive surveillance adversary and then in the active case. It is easy to see that the attacks are undetectable according to the models in the literature [6, 8, 12], as the encryption algorithm is not subverted.

Imagine that Alice communicates with Bob. A passive adversary can observe ciphertexts from Alice to Bob. In addition, an active adversary can replace ciphertexts in transmission and submit its own (forged) ciphertexts to Bob. In the passive attack, the decryption algorithm is subverted so that it rejects a fraction of valid ciphertexts, bounded by an attacker controlled parameter. In the active attack, the decryption algorithm is subverted so that it accepts a (similarly bounded) fraction of invalid ciphertexts. The active attack requires the adversary to send Bob bogus ciphertexts (derived from genuine ciphertexts) that reveal Bob’s secret key using decryption errors. Normally, these bogus ciphertexts are unlikely to decrypt correctly, i.e., they would be rejected. In both cases, if the decryptor is subverted then either real ciphertexts (in the passive case) or bogus ciphertexts (in the active case) can either be accepted or rejected, creating via the acceptance/rejection pattern a covert channel that will allow the key to be exfiltrated.

From the point of view of a mass surveillance adversary this is an attractive prospect: having passively collected all communications, triggered by some suspicion they can now target Alice and Bob’s communication. By recovering Bob’s key they may now decrypt all of the stored communication between Alice and Bob (and indeed from Bob to Alice as well).

We note that both of our attacks are stateless, which not only allows for much easier backdoor implementation from a technical perspective but also should decrease the likelihood that an implemented attack is detected through code review or observing memory usage.

4.1 Attack 1: Passive

Consider the following subversion of a given symmetric encryption scheme $({\mathrm {\Pi }}.\mathsf {Gen}, {\mathrm {\Pi }}.\mathsf {Enc}, {\mathrm {\Pi }}.\mathsf {Dec})$. Let $\widetilde{\mathrm {\Pi }}.\mathsf {Gen}= {\mathrm {\Pi }}.\mathsf {Gen}$ and $\widetilde{\mathrm {\Pi }}.\mathsf {Enc}= {\mathrm {\Pi }}.\mathsf {Enc}$. Let $\mathsf {A}.\mathsf {Gen}$ choose a key $k_\mathsf {A}$ by $k_\mathsf {A}\leftarrow _{\scriptscriptstyle \$}{\{0,1\}}^{\mathsf {A}.\mathsf {kl}}$. Algorithms $\widetilde{\mathrm {\Pi }}.\mathsf {Dec}$ and $\mathsf {A}.\mathsf {Ext}$ are then specified in Fig. 3. The subverted decryptor $\widetilde{\mathrm {\Pi }}.\mathsf {Dec}$ takes the same input as ${\mathrm {\Pi }}.\mathsf {Dec}$ together with the attacker key, and utilises a pseudo-random function³ F with $F :{\{0,1\}}^{\mathsf {A}.\mathsf {kl}} \times {\{0,1\}}^*\rightarrow [{\mathrm {\Pi }}.\mathsf {kl}] \times {\{0,1\}}$. In $\mathsf {A}.\mathsf {Ext}$, we use the symbol $\star$ as a ternary symbol (neither 0 nor 1) to keep track of which key bits have been collected. In line 2 of the algorithm for $\widetilde{\mathrm {\Pi }}.\mathsf {Dec}$, we write $B(\delta )$ to denote a Bernoulli trial which returns 1 with probability $\delta$. Key extractor $\mathsf {A}.\mathsf {Ext}$ takes as input the attacker key and the transcript, consisting of triples (c, d, n, v) where v is a bit representing whether or not the ciphertext decrypts to $\bot$.

Fig. 3.

Passive ASA against AEAD

Theorem 1

Let ${\mathrm {\Pi }}$ be a perfectly-correct symmetric encryption scheme and let $\ell = {\mathrm {\Pi }}.\mathsf {kl}$. Let $\widetilde{\mathrm {\Pi }}.\mathsf {Dec}$ and $\mathsf {A}.\mathsf {Ext}$ be defined as in Fig. 3. Let $\mathcal {M}$ be a message sampling algorithm, and $F :{\{0,1\}}^{\mathsf {A}.\mathsf {kl}} \times {\{0,1\}}^*\rightarrow [\ell ] \times {\{0,1\}}$ be a PRF with $\mathsf {Adv}^{\mathrm {prf}}_F{(\mathcal {F})}< \epsilon$ for all efficient adversaries $\mathcal {F}$. Then

• (1) $\mathsf {Adv}^{\mathrm {kr}}_{\widetilde{\mathrm {\Pi }}, \mathcal {M}}(\mathsf {A}){} \ge 1 - \ell e^{-\frac{q\delta }{2\ell }}$, where q is the number of queries that $\mathsf {A}.\mathsf {Ext}$ makes to the transcript oracle.

• (2) For all distinguishers $\mathcal {D}$, $\mathsf {Adv}^{\mathrm {det}}_{{\mathrm {\Pi }}, \widetilde{\mathrm {\Pi }}}{(\mathcal {D})}{} \le {\frac{\delta q}{2}(1 + \epsilon )}$ where $\mathcal {D}$ makes q queries to its decryption oracle.

Proof of (1). We use a combinatorial argument. Notice that this is essentially a coupon collection problem. We are looking for the probability that every key bit has been exfiltrated. If we fix i key bits that are not exfiltrated, there are $\left( {\begin{array}{c}\ell \\ i\end{array}}\right)$ ways to choose those fixed key bits. The probability that (at least) i of the key bits have not been exfiltrated is given by $\left( {\begin{array}{c}\ell \\ i\end{array}}\right) (1 - \frac{i\delta }{2\ell } )^q$. Using the principle of inclusion exclusion, the probability that no key bit has not been exfiltrated is given by

   $\square$

Proof of (2). Clearly, the only way to distinguish between ${\mathrm {\Pi }}$ and $\widetilde{\mathrm {\Pi }}$ is to observe $\widetilde{\mathrm {\Pi }}.\mathsf {Dec}$ output $\bot$. Thus in order to distinguish, $\mathcal {D}$ must find (m, d; n) such that $\bot = \mathcal {O}_\mathsf {Dec}(k, {c}, d; n)$ for $c \leftarrow {\mathrm {\Pi }}.\mathsf {Enc}(k, m, d; n)$. This reduces to $\mathcal {D}$ finding some $c \mathrel {\Vert }d$ such that $F(k_\mathsf {A}, c\mathrel {\Vert }d) = i \mathrel {\Vert }k[i]$ for some index i. Call this event W. Notice that for any F it holds that for all $k_\mathsf {A}, c, d$ we have $F(k_\mathsf {A}, c \mathrel {\Vert }d) = i \mathrel {\Vert }b$ for some index i and bit b.

We note that $\Pr \left[ W \right] \le \Pr \left[ \mathsf {PRF}_{F}(\mathcal {F}) \right]$ for all PRF adversaries $\mathcal {F}$. If not, it would be possible for $\mathcal {F}$ to act as a challenger to $\mathcal {D}$ and win its prf game whenever W occurs. Thus,

   $\square$

Remark. Whereas (un)detectability does depend on the security of the PRF, the PRF can be quite weak without much impacting the adversary’s key recovery advantage. If the base scheme ${\mathrm {\Pi }}$’s ciphertexts are indistinguishable from random (IND$), then the PRF could simply choose the first $\lceil \log (\ell ) \rceil + 1$ many bits of the ciphertext. This seems paradoxical, as strong privacy security is usually a desirable property but here it allows a simpler ASA to be successful.

We note that in practice, the subverted decryption algorithm $\widetilde{\mathrm {\Pi }}.\mathsf {Dec}$ can be made more effective in a number of ways. Indeed, the model is very conservative and in practice it may be possible for $\mathsf {A}.\mathsf {Ext}$ to observe a number of distinguishable error messages following [10].

Fig. 4.

Active ASA against AEAD

4.2 Attack 2: Active

Consider algorithms $\widetilde{\mathrm {\Pi }}.\mathsf {Dec}$ and $\mathsf {A}.\mathsf {Ext}$ as specified in Fig. 4. The adversary $\mathsf {A}.\mathsf {Ext}$ crafts special messages using a length-preserving pseudo-random permutation E under the attacker key⁴. We let $E: {\{0,1\}}^{\mathsf {A}.\mathsf {kl}} \times {\{0,1\}}^*\rightarrow {\{0,1\}}^*$. The security of E will determine how easily the distinguisher $\mathcal {D}$ will be able to recreate a special message to trigger $\widetilde{\mathrm {\Pi }}$. Furthermore, as in the passive attack, $\widetilde{\mathrm {\Pi }}.\mathsf {Dec}$ makes use of a PRF F to determine whether or not to reject submitted ciphertexts. We let $F :{\{0,1\}}^{\mathsf {A}.\mathsf {kl}} \times {\{0,1\}}^*\rightarrow [{\mathrm {\Pi }}.\mathsf {kl}] \times {\{0,1\}}$. Although the notation implies keys are the same, we assume independent behaviour of F, E.⁵ We analyse this construction in the formal model defined by game $\mathsf {{Active}KR}_{\widetilde{\mathrm {\Pi }}, \mathcal {M}}$ in Fig. 2.

Theorem 2

Let ${\mathrm {\Pi }}$ be a perfectly-correct symmetric encryption scheme and let $\ell = {\mathrm {\Pi }}.\mathsf {kl}$. Let $\widetilde{\mathrm {\Pi }}.\mathsf {Dec}$ and $\mathsf {A}.\mathsf {Ext}$ be defined as in Fig. 4. Let $\mathcal {M}$ be a message sampling algorithm. Let $\ell = {\mathrm {\Pi }}.\mathsf {kl}$ and $\mathsf {Adv}^{\mathrm {auth}}_{{\mathrm {\Pi }}}{} < \epsilon$. Let $F :{\{0,1\}}^{\mathsf {A}.\mathsf {kl}} \times {\{0,1\}}^*\rightarrow [\ell ] \times {\{0,1\}}$ be a PRF with $\mathsf {Adv}^{\mathrm {prf}}_F{(\mathcal {F})} < 1$ for all efficient adversaries $\mathcal {F}$. Let E be a lp-PRP with $E: {\{0,1\}}^{\mathsf {A}.\mathsf {kl}} \times {\{0,1\}}^*\rightarrow \{0, 1\}^*$ and $\mathsf {Adv}^{\mathrm {prp}}_{E}(\mathcal {F}') < \epsilon '$ for all efficient PRP adversaries $\mathcal {F}'$. Then

• (1) $\mathsf {Adv}^{\mathrm {kr}}_{\widetilde{\mathrm {\Pi }}, \mathcal {M}}(\mathsf {A}){} \ge 1 - \ell e^{-\frac{q}{\ell }(1 - \epsilon )}$, where $\mathsf {A}.\mathsf {Ext}$ makes exactly ${\mathrm {\Pi }}.\mathsf {kl}$ calls to the decryption oracle and q calls to the encryption oracle.

• (2) For every distinguisher $\mathcal {D}$, $\mathsf {Adv}^{\mathrm {det}}_{{\mathrm {\Pi }}, \widetilde{\mathrm {\Pi }}}{(\mathcal {D})}{} \le \frac{q}{2^{\tau }} + \epsilon '$, where $\mathcal {D}$ makes q queries to its decryption oracle.

Proof of (1). We use the same combinatorial argument as in Theorem 1. This time, the probability that (at least) i of the key bits have not been correctly exfiltrated is given by $\left( {\begin{array}{c}\ell \\ i\end{array}}\right) \left[ (1 - \frac{i}{\ell }) + \frac{\alpha i}{2\ell } \right] ^q$. Here $\alpha$ is the probability that ${\mathrm {\Pi }}.\mathsf {Dec}(k, \widetilde{c}, d; n) \ne \bot$ given that $F^{-1}(k_\mathsf {A}, \widetilde{c}) = j \mathrel {\Vert }k[j]$ for j in the set of indices being counted. We note that $\mathsf {Adv}^{\mathrm {auth}}_{{\mathrm {\Pi }}}{} \ge \alpha$.

   $\square$

Proof of (2). As in Theorem 1, the only way to distinguish between ${\mathrm {\Pi }}$ and $\widetilde{\mathrm {\Pi }}$ is by observing $\widetilde{\mathrm {\Pi }}.\mathsf {Dec}$ accepting a forged ciphertext. To do this, the distinguisher $\mathcal {D}$ must find some ciphertext c with associated data d such that ${F(k_\mathsf {A},\widetilde{c}\parallel d)=i\parallel k[i]}$ for some $i \in [\ell ]$ and where $\widetilde{c} = E^{-1}(k_\mathsf {A}, c)$. Noting that $\mathsf {Adv}^{\mathrm {prf}}_F{(\mathcal {F})}< 1$, we thus obtain

Consider the following game, which we will refer to as the pre-image game. For $b \in \{0, 1\}$ we define experiment b as follows:

• 1. The challenger initially sets $C\leftarrow \emptyset$ and responds to query $c_i$ in the following way:

  • if $(b = 0)$ then set $c'_i\leftarrow _{\scriptscriptstyle \$}{\{0,1\}}^{|c_i|}\setminus C$, update and return $c'_i$

  • if $(b = 1)$ then return $c'_i\leftarrow E^{-1}(k_\mathsf {A}, c_i)$.

• 2. The adversary $\mathcal {D}$ submits a sequence of queries $c_1, c_2, \ldots , c_q$ to the challenger and receives $c'_i$ for $i \in [q]$.

For $b \in {\{0,1\}}$, let $W_b$ be the event that $\mathcal {D}$ outputs 1 in experiment b; $\mathcal {D}$ outputs 1 if for some d, n, ${{\mathrm {\Pi }}.\mathsf {Dec}(k, c'_i, d; n) \ne \bot }$. The advantage of $\mathcal {D}$ in the pre-image game is clearly less than its advantage in distinguishing a lp-PRP from a random length preserving permutation. To see this, given $\mathcal {D}$ with some advantage playing the pre-image game we can construct an adversary $\mathcal {B}$ acting as a challenger to $\mathcal {D}$ such that $\mathcal {B}$ outputs 1 in the distinguishing game $\mathsf {PRP}_{E}(\mathcal {B})$ whenever $\mathcal {D}$ does in the pre-image game. Thus,

Noting that $\Pr \left[ W_1 \right] = \frac{q}{2^{\tau }}$, where $\tau$ is the stretch of the encryption scheme, we conclude that

   $\square$

5 Implementation

We implemented our attacks in proof-of-concept Python code to verify their functionality and effectiveness.⁶ The particular AEAD scheme we attack is AES-GCM [15], using black-box access to the implementation provided by [32]. We simulated both active and passive attacks 10,000 times, and recorded the number of queries for successful extraction of a 128-bit key (thus, $\ell = 128$). Messages, nonces and associated data were generated using the random.getrandbits method from the Crypto.Random library. The plots below (Figs. 5 and 6) show the distribution (in blue) of the recorded number of queries q, and (in red) the cumulative success probability as a function of q. Our results confirm the theoretical estimates from Theorems 1 and 2; in particular, the exponential success rate. While the attacks have different application and success profiles, both reliably recover keys.

Passive. The expected number of calls to the transcript oracle for successful exfiltration is given by $\frac{2\ell }{\delta } \sum ^{\ell }_{i = 1} \frac{1}{i}$ (see proof of Theorem 1). We set $\delta = 0.1$ for illustration. This gives us an expected value of $q = 13910$ compared to the recorded mean of 13920.59. Alternatively, the result from Theorem 1 gives a key recovery advantage of ${\approx }1/2$ with $q = 14000$, compared to the recorded median of 13380. The discrepancy is due to the exponential approximation in the proof.

Fig. 5.

Results of running an implementation of the passive attack 10,000 times. Key length $\ell = 128$, and parameter $\delta = 0.1$. Left axis: The blue histogram shows the distribution of the number of queries required for successful key exfiltration. The data has been sorted into 50 bins. Right axis: The red curve shows the cumulative probability of successful key exfiltration against q. (Colour figure online)

Active. We assume that for AES-GCM, $\mathsf {Adv}^{\mathrm {auth}}_{{\mathrm {\Pi }}}\approx 0$ and set $\epsilon = 0$. The expected number of encryption calls for successful exfiltration is then $\ell \sum ^{\ell }_{i = 1} \frac{1}{i}$ (see proof of Theorem 2). This gives an expected value of $q = 696$ compared to the recorded mean of 695.05. Alternatively, the result from Theorem 2 gives a key recovery advantage of $\approx 1/2$ with $q = 710$ compared to the recorded median of 670. Again, the difference is due to exponential approximation.

Fig. 6.

Results of running an implementation of the active attack 10,000 times with key length $\ell = 128$. Left axis: The blue histogram shows the distribution of the number of queries required for successful key exfiltration. The data has been sorted into 50 bins. Right axis: The red curve shows the cumulative probability of successful key exfiltration against q. (Colour figure online)

6 Breaking Security Without Extracting the Full Key

The attacks presented in Sect. 4 are generic in that they are independent of the targeted AEAD scheme. Our approach, in common with previous work, was to extract the full key with which the AEAD instance is operated. Message recovery follows immediately by the definition of correctness. From this it is tempting to conclude that choosing longer keys, e.g. 256 bits instead of 128 in the case of AES-based encryption, gives better security against ASAs. (This approach is generally explored in big key cryptography [7].). In this section we show that this intuition is not necessarily correct. As we detail, many current AEAD schemes have inner building blocks that maintain their own secret values, and scaling up key sizes does not automatically also increase the sizes of these internal values. Note that ASAs in the style proposed in the previous section could easily be adapted to leak this internal information instead of the key. As the recovery of such values might not always directly lead to full message recovery, the assessment of whether the resulting overall attack is more or less effective than our generic attacks has to be made on a per scheme basis. We exemplify this on the basis of two of the currently best-performing AES-based AEAD schemes: GCM [15] and OCB3 [19]. In both cases, the size of the crucial internal value and the block size of the cipher have to coincide and the latter value is fixed to 128 bits for AES (independently of key size).

AES-GCM. We consider the following abstraction of GCM. The AEAD key k is used directly to create an instance E of the AES blockcipher. To encrypt a message m with respect to associated data d and nonce n, E is operated in counter mode, giving a pad $E(n+1) \mathrel {\Vert }E(n+2) \mathrel {\Vert }\ldots ,$ where a specific nonce encoding ensures there are no collisions between counter values of different encryption operations. The first part $c_1$ of the ciphertext $c=c_1c_2$ is obtained by XORing the pad into the message, and finally the authentication tag $c_2$ is derived by computing $c_2\leftarrow E(n)+H_h(d, c_1)$. Here $H_h$ is an instance of a universal hash function H indexed (that is, keyed) with the 128-bit value $h=E(0^{128})$. Concretely, $H_h(d, c_1)= \sum _{i=1}^l v_i h^{l-i+1},$ where coefficients $v_1, \ldots , v_l$ are such that a prefix $v_1\ldots v_j$ is a length-padded copy of the associated data d, the middle part $v_{j+1}\ldots v_{l-1}$ is a length-padded copy of ciphertext component $c_1$, and the last item $v_l$ is an encoding of the lengths of d and $c_1$. The addition and multiplication operations deployed in this computation are those of a specific representation of the Galois field $\mathrm {GF}(2^{128})$.

In executing a practical algorithm substitution attack against AES-GCM, it might suffice to leak the value h (which has length 128 independently of the AES key length, and furthermore stays invariant across encryption operations). The insight is that if the key of a universal hash function is known, then it becomes trivial to compute collisions. Concretely, assume the adversary is provided with the AES-GCM encryption $c=c_1c_2=\mathsf {Enc}(k,m,d;n)$ for unknown k, m but chosen d, n. Then by the above we have $c_2=R+\sum _{i=1}^ jv_i h^{l-i+1}$ where the coefficients $v_1\ldots v_j$ are an encoding of d and R is some residue. If, having been successfully leaked by the ASA, the internal value h is known, by solving a linear equation it is easy to find an associated data string $d'\ne d$, $|d'|=|d|$, such that for its encoding $v'_1\ldots v'_j$ we have $\sum _{i=1}^j v'_i h^{l-i+1}=\sum _{i=1}^j v_i h^{l-i+1}$. Overall this means that we have found $d'\ne d$ such that $\mathsf {Enc}(k,m,d';n)=c=\mathsf {Enc}(k,m,d;n)$. In a CCA attack the adversary can thus query for the decryption of c with associated data $d'$ and nonce n, and thus fully recover the target message m. We finally note that this attack can be directly generalized to one where also the $c_1$ and $c_2$ components are modified, resulting in the decryption of a message $m'\ne m$ for which the XOR difference between $m=m'$ is controlled by the adversary.

OCB3. Multiple quite different versions of the OCB encryption scheme exist, but a common property is that the associated data input is incorporated via ‘ciphertext translation’ [22]. To encrypt a message m under key k with associated data d and nonce n, in a first step the message m is encrypted with a pure AE scheme (no AD!) to an intermediate ciphertext $c^*\leftarrow \mathsf {Enc}^*(k,m;n)$. Then to obtain the final ciphertext c, a pseudo-random function value $F_k(d)$ of the associated data string is XORed into the trailing bits of $c^*$. Concretely, in OCB3 we have $F_k(d)=\sum _{i=1}^lE(v_i+C_i)$ where all addition operations are XOR combinations of 128 bit values, $E(\cdot )$ stands for AES enciphering with key k, values $v_1,\ldots ,v_l$ represent a length-padded copy of associated data d, and coefficients $C_1,\ldots ,C_l$ are (secret) constants deterministically derived from the value $L=E(0^{128})$.

In the context of an ASA we argue that it is sufficient to leak the 128 bit value L. The attack procedure is, roughly, as in the AES-GCM case. Assume the adversary is provided with the OCB3 encryption $c=\mathsf {Enc}(k,m,d;n)$ for unknown k, m but chosen d, n, and assume the adversary knows L and thus $C_1,\ldots ,C_l$. Now let $1\le s<t\le l$ be any two indices, let $\varDelta =C_s+C_t$ and let $d'\ne d$, $|d'|=|d|$, be the associated data string with encoding $v'_1,\ldots ,v'_l$ such that we have $v'_s=v_t+\varDelta$ and $v'_t=v_s+\varDelta$ and $v'_i=v_i$ for all $i\ne s,t$. Then we have $E(v'_s+C_s)=E(v_t+\varDelta +C_s)=E(v_t+C_t)$ and $E(v'_t+C_t)=E(v_s+\varDelta +C_t)=E(v_s+C_s)$, which leads to $F_k(d)=F_k(d')$ and ultimately $\mathsf {Enc}(k,m,d';n)=\mathsf {Enc}(k,m,d;n)$. In a CCA attack environment, this can immediately be leveraged to the full recovery of m. As in the AES-GCM case, we note that many variants of our attack exist (against all versions of OCB), including some that manipulate message bits in a controlled way.

7 Conclusion

This work examines subversion attacks against decryption only, providing two examples of a new class of Algorithm Substitution Attack that provides a mass surveillance adversary with a powerful and attractive strategy to compromise the confidentiality of mass communication. Previous models of ASA against symmetric encryption only considered subverting the encryption algorithm, and seemed to suggest that decryption could only be subverted together with encryption (and that analysing such “total subversion” is uninteresting, as this gives an adversary too much power).

A Pseudo-Random Functions and Permutations

We recall standard notions of pseudo-random functions and permutations.

Definition 4

A keyed pseudo-random function (PRF) for range R is an efficiently computable function $F :{\{0,1\}}^\ell \times {\{0,1\}}^*\rightarrow R$ taking a key $L \in {\{0,1\}}^\ell$ and input $s \in {\{0,1\}}^*$ to return an output $F(L, s) \in R$. Consider game $\mathsf {PRF}_{F}(\mathcal {F})$ in Fig. 7 associated to F and adversary $\mathcal {F}$. Let

be the prf advantage of adversary $\mathcal {F}$ against function F. Intuitively, the function is pseudo-random if the prf advantage of any realistic adversary is negligible.

Definition 5

A keyed length-preserving pseudo-random permutation (lp-PRP) is an efficiently computable function E where $E :{\{0,1\}}^\ell \times {\{0,1\}}^*\rightarrow {\{0,1\}}^*$ takes a key $L \in {\{0,1\}}^\ell$ and input $s \in {\{0,1\}}^*$ to return an output $E(L, s) \in {\{0,1\}}^ {|s |}$. We require that any keyed instance of E is a permutation on ${\{0,1\}}^n$ for all $n\in \mathbb {N}$ and also that its inverse $E^{-1}$ is efficiently computable. Consider game $\mathsf {PRP}_{E}(\mathcal {F})$ in Fig. 7 associated to E and adversary $\mathcal {F}$. Let

be the prp advantage of adversary $\mathcal {F}$ against function E. Intuitively, the permutation is pseudo-random if the prp advantage of any realistic adversary is negligible.

Fig. 7.

Game to define prf and prp advantage of $\mathcal {F}$ with respect to F, E.