Robust Authenticated Encryption and the Limits of Symmetric Cryptography

Abstract

Robust authenticated encryption (RAE) is a primitive for symmetric encryption that allows to flexibly specify the ciphertext expansion, i.e., how much longer the ciphertext is compared to the plaintext. For every ciphertext expansion, RAE aims at providing the best-possible authenticity and confidentiality. To investigate whether this is actually achieved, we characterize exactly the guarantees symmetric cryptography can provide for any given ciphertext expansion. Our characterization reveals not only that RAE reaches the claimed goal, but also, contrary to prior belief, that one cannot achieve full confidentiality without ciphertext expansion. This provides new insights into the limits of symmetric cryptography.

Moreover, we provide a rigorous treatment of two previously only informally stated additional features of RAE; namely, we show how redundancy in the message space can be exploited to improve the security and we analyze the exact security loss if multiple messages are encrypted with the same nonce.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Authenticity and confidentiality are arguably among the most important cryptographic objectives. Authenticated encryption is a symmetric primitive that aims to achieve both at the same time, allowing efficiency gains and reducing the risk of misuse compared to combined schemes. Several notions of authenticated encryption have emerged over a series of works [2, 3, 5, 7, 8, 13], including authenticated encryption with associated data [4, 12] and misuse-resistant authenticated encryption [14]. In this development, robust authenticated encryption (RAE), introduced by Hoang, Krovetz, and Rogaway [6], is the latest and most ambitious notion. Robust authenticated encryption allows to specify the ciphertext expansion $\lambda$ that determines how much longer ciphertexts are compared to the corresponding plaintexts. Its self-declared goal in [6] is to provide the best-possible authenticity and confidentiality for every choice of $\lambda$. This raises the question of what best-possible authenticity and confidentiality is, and whether RAE actually achieves it. We provide a formal model that allows us to investigate this question and answer it in the affirmative. We further show how to use verifiable redundancy to improve security, and we show what security guarantees remain if values intended as nonces are reused. Both questions were addressed in [6] but not proven formally.

1.1 Robust Authenticated Encryption

An RAE scheme consists of a key distribution $\mathcal {K}$, a deterministic encryption algorithm $\mathcal {E}$, and a deterministic decryption algorithm $\mathcal {D}$. The encryption algorithm takes as input a key K, a nonce N, associated data A, the ciphertext expansion $\lambda$, and a message $M$. It outputs a ciphertext $C$. The decryption algorithm takes as input K, N, A, $\lambda$, and $C$, and returns the corresponding message $M$ (or $\bot$ if $C$ is an invalid ciphertext). In [6], the security of an RAE scheme is defined via a game in which an adversary has access to two oracles and has to distinguish between two possible settings. In the first setting, the oracles correspond to the encryption and decryption algorithm of the RAE scheme, where the key is fixed in the beginning and chosen according to $\mathcal {K}$. In the second setting, the first oracle chooses for each N, A, $\lambda$, and message length $\ell$ an injective function that maps strings of length $\ell$ to strings of length $\ell + \lambda$. On input $(N, A, \lambda , M)$, the oracle answers by evaluating the corresponding function. The second oracle corresponds to the partially defined inverse of that function that answers $\bot$ if the given value has no preimage. An RAE scheme is secure if these two settings are indistinguishable for efficient adversaries. While this seems to be a strong guarantee, it is not clear which security such a scheme actually provides in a specific application and whether it is best-possible.

1.2 Security Definitions and Constructive Cryptography

Since game-based security definitions only capture what an adversary can do in a specific attack-scenario, they inherently fall short of providing guarantees that hold in any possible application of the scheme. To capture what RAE schemes achieve, we formulate our results using the constructive cryptography framework by Maurer and Renner [9, 10]. The central idea of this framework is that the resources available to the parties, such as communication channels or shared randomness like cryptographic keys, are made explicit. The goal of a cryptographic protocol is then to construct, from certain existing resources, another resource that can again be used by higher-level protocols or applications. For example, the goal of an authentication scheme can be formalized as constructing an authenticated channel from a shared secret key and an insecure channel. The insecure channel allows a sender, say Alice, to send messages to a receiver, say Bob, but entirely leaks the transmitted messages to the adversary and additionally allows the adversary to delete messages and inject arbitrary messages; an authenticated channel still leaks the messages but only allows the adversary to delete messages and to deliver the messages originally sent. A conventional encryption scheme is supposed to construct a secure channel from a shared secret key and an authenticated channel, where the secure channel restricts the leakage to the length of the transmitted messages. The composition theorem of constructive cryptography guarantees that if two protocols achieve these constructions, the composed protocol constructs a secure channel from two shared secret keys and an insecure channel, i.e., the security of the overall construction follows from the security of the individual construction steps. On the other hand, authenticated encryption directly achieves the overall construction.

1.3 Our Contributions

In the vein of [1] and accounting for the associated data RAE schemes support, we formalize the goal of RAE as constructing an augmented secure channel (ASC) from a shared secret key and an insecure channel. An ASC takes as input from the sender a tuple $(A, M)$, leaks A and the length of $M$ to the adversary, and allows the adversary to either deliver the pair $(A, M)$ or to terminate the channel. This channel provides authenticity for both A and $M$, but confidentiality is only guaranteed for the message $M$. The value A can for example be used to authenticate non-private header information; see [1] for an application of ASC in the context of TLS 1.3.

Uniform Random Injection Resource. Instead of directly constructing channels from a shared secret key and an insecure channel, we introduce an intermediate system URI (uniform random injection) that provides the sender and receiver access to the same uniform random injections and their inverses chosen as follows: For each combination of N, A, $\lambda$, and message length $\ell$, an injective function that maps strings of length $\ell$ to strings of length $\ell + \lambda$ is chosen uniformly at random.

As we shall see, this resource can be constructed from a shared secret key using an RAE scheme in a straightforward manner. We then construct several channels from URI and an insecure channel. The advantage of this approach is that all further constructions in this paper are information-theoretic, i.e., we do not have to relate the security of each construction step to the RAE security game. Instead, we can rely on the composition theorem to guarantee the security of the overall construction.

Random Injection Channel. We show that one can construct a channel we call RIC (random injection channel) from URI and an insecure channel by fixing $\lambda$ and using a counter as the nonce. RIC can be seen as a further intermediate step towards constructing ASC, that in addition allows us to analyze best-possible security.

The channel RIC takes as input a pair $(A, M)$ from the sender and leaks A and the length of $M$ to the adversary. The adversary can deliver the pair $(A, M)$, and further at any point in time try to inject a new message of length $\ell$ and some value A. The probability with which such an injection is successful depends on $\lambda$ and $\ell$. In case of a success, an almost uniform message of length $\ell$ from the message space together with A is delivered to the receiver. If an injection was successful and the tuple $(A, M)$ was received, and if the sender subsequently sends exactly the pair $(A, M)$, then the adversary is notified about this repetition.

Best Possible Authenticity and Confidentiality. If ASC is considered as the ultimate goal of RAE and authenticated encryption in general, the only shortcomings of RIC are that it is possible to inject messages with positive probability and that, if an attempted message injection was successful, the channel leaks a certain repetition to the adversary. While the first shortcoming is a lack of authenticity, the second one is a lack of confidentiality. While the type of leakage violating confidentiality might seem artificial, we describe an application in which such leakage might be problematic. Briefly, the leakage can reveal hidden information flow from the receiver to the sender.

We then analyze whether RAE really achieves the best-possible authenticity and confidentiality by bounding the probabilities of successful message injections and of leaking this particular repetition pattern for arbitrary schemes for achieving authenticity and confidentiality. While it is straightforward to see that authenticity requires redundancy and therefore a large ciphertext expansion, one might hope that the repetition leakage can be avoided. We prove that this is not the case, i.e., we show that the probability of an adversary being able to observe such a repetition is at least as high as in RIC, no matter what scheme is used or which setup assumptions are made.

To illustrate this lack of confidentiality for a concrete scheme, consider the following scenario in which the one-time pad is used over an insecure channel: Assume the attacker injects a ciphertext to Bob who decrypts it using the shared secret key and outputs the resulting message. Further assume Alice afterwards sends a message to Bob which results in the attacker seeing the same ciphertext. In that case, the attacker learns the fact that the message sent by Alice equals the message output by Bob. This contradicts the understanding of confidentiality as revealing nothing except the length of the transmitted message.¹ Our results generalize this observation to arbitrary schemes. We thereby refine the understanding of what symmetric cryptography can and cannot achieve by showing that confidentiality, quite surprisingly, also requires redundancy in the ciphertexts when only insecure channels and an arbitrary setup are assumed, even if the protocol can keep state.

Augmented Secure Channels and Message Redundancy. Since the probability of successful message injections decreases exponentially with $\lambda$, RIC is indistinguishable from ASC for large $\lambda$. We further provide a construction that incorporates an idea from [6] to exploit the redundancy in messages to achieve a better bound. Our construction reveals the exact trade-off between ciphertext expansion and redundancy to achieve a required security level.

Nonce-Reuse Resistance. It was claimed in [6] that reusing nonces only results in leaking the repetition pattern of messages, but does not compromise security beyond that. However, the claim was neither formalized nor proven. We fill this gap by introducing the channel resource RASC (Repetition ASC) that, aside of the length of each message, leaks the repetition pattern of the transmitted messages to the adversary. Furthermore, the adversary can deliver messages out-of-order and arbitrarily replay messages. We show that RASC can be constructed from URI and an insecure channel if the used nonce is always the same. This confirms the informal claim from [6] and makes explicit that some authenticity is lost by allowing the adversary to reorder messages.

2 Preliminaries

2.1 Notation for Systems and Algorithms

We describe our systems with pseudocode using the following conventions: We write $x \leftarrow y$ for assigning the value y to the variable x. For a distribution $\mathcal {X}$ over some set, $x \twoheadleftarrow \mathcal {X}$ denotes sampling x according to $\mathcal {X}$. For a finite set X, $x \twoheadleftarrow X$ denotes assigning to x a uniformly random value in X.

We denote the empty list by $[\, ]$ and for a list L, $L \ \Vert \ x$ denotes the list L with x appended. Furthermore, ${|{L}|}$ denotes the number of elements in L and the ith element in L is denoted by L[i] for $i \in \{1, \ldots , {|{L}|}\}$. For a FIFO queue $\mathcal {Q}$, we write $\mathcal {Q}.\texttt {enqueue}(x)$ to insert x into the queue and $\mathcal {Q}.\texttt {dequeue}()$ to retrieve (and remove) the element of the queue that was inserted first among all remaining elements.

For $n,m \in \mathbb {N}$, $\mathrm {Inj}\left( \varSigma ^{n}, \varSigma ^{m}\right)$ denotes the set of injective functions $\varSigma ^{n} \rightarrow \varSigma ^{m}$. For an injective function $f :X \rightarrow Y$, we denote by $f^{-1}$ the function $Y \rightarrow X \cup \{\bot \}$ that maps y to the preimage of y under f if existing, and to the distinct element $\bot$ otherwise.

Typically queries to systems consist of a suggestive keyword and a list of arguments (e.g., $(\mathsf {send}, M)$ to send the message $M$). We ignore keywords in writing the domains of arguments, e.g., $(\mathsf {send}, M) \in \mathcal {M}$ indicates that $M\in \mathcal {M}$.

2.2 Constructive Cryptography

Constructive cryptography makes statements about constructions of resources from other resources. A resource is a system with interfaces via which the resource interacts with its environment and which can be thought of as being assigned to parties. All resources in this paper have an interface $\mathsf {A}$ for the sender (Alice), an interface $\mathsf {B}$ for the receiver (Bob), and an interface $\mathsf {E}$ for the adversary (Eve). In our security statements, we are interested in the advantage of a distinguisher $\mathbf {D}$ in distinguishing two resources, say $\mathbf {R}$ and $\mathbf {S}$ which is defined as

$$\begin{aligned} \varDelta ^{\mathbf {D}}\left( \mathbf {R},\mathbf {S}\right) \ = \ \mathsf {Pr}\left[ \mathbf {D}\mathbf {R} = 1\right] - \mathsf {Pr}\left[ \mathbf {D}\mathbf {S} = 1 \right] , \end{aligned}$$

where $\mathsf {Pr}\left[ \mathbf {D}\mathbf {R} = 1\right]$ denotes the probability that $\mathbf {D}$ outputs 1 when connected to resource $\mathbf {R}$. More concretely, $\mathbf {D}\mathbf {R}$ is a random experiment, where the distinguisher repeatedly provides an input to one of the interfaces $\mathsf {A}$, $\mathsf {B}$, or $\mathsf {E}$ and observes the output generated in reaction to that input before it decides on its output bit.

Converters are systems that can be attached to an interface of a resource to change the inputs and outputs at that interface, which yields another resource. A converter is a system with two interfaces: the inner interface $\mathsf {in}$ is connected to an interface of a resource and the outer interface $\mathsf {out}$, becomes the new connection point of that resource towards the environment. The protocols of the honest parties and simulators correspond to converters.

We directly state the central definition of a construction of [9] and briefly explain the relevant conditions.

Definition 1

Let $\mathbf {R}$ and $\mathbf {S}$ be resources and let $\mathsf {noAtck_\mathbf {R}}$ and $\mathsf {noAtck_\mathbf {S}}$ be converters that describe the default behavior at interface $\mathsf {E}$ when no attacker is present. Let $\varepsilon$ be a function that maps distinguishers to a value in $[-1,1]$ and let $\mathsf {sim}$ be a converter (the simulator). A protocol, i.e., a pair $(\mathsf {conv_1}, \mathsf {conv_2})$ of converters, constructs resource $\mathbf {S}$ from resource $\mathbf {R}$ within $\varepsilon$ and with respect to the pair $(\mathsf {noAtck_\mathbf {R}}, \mathsf {noAtck_\mathbf {S}})$ and the simulator $\mathsf {sim}$, if for all distinguishers $\mathbf {D}$,

$$\begin{aligned} \varDelta ^{\mathbf {D}}\left( \mathsf {conv_1}^\mathsf {A}\mathsf {conv_2}^\mathsf {B}\mathsf {noAtck_\mathbf {R}}^\mathsf {E}\, \mathbf {R},\mathsf {noAtck_\mathbf {S}}^\mathsf {E}\,\mathbf {S}\right)&\le \varepsilon (\mathbf {D})&\text {(Availability)}\\ \varDelta ^{\mathbf {D}}\left( \mathsf {conv_1}^\mathsf {A}\mathsf {conv_2}^\mathsf {B}\, \mathbf {R},\mathsf {sim}^\mathsf {E}\,\mathbf {S}\right)&\le \varepsilon (\mathbf {D}). \quad&\text {(Security)} \end{aligned}$$

The first condition ensures that the protocol implements the required functionality if there is no attacker. For example, for communication channels, all sent messages have to be delivered when no attacker interferes with the protocol.

The second condition ensures that whatever Eve can do with the assumed resource, she could do as well with the constructed resource by using the simulator $\mathsf {sim}$. Turned around, if the constructed resource is secure by definition, there is no successful attack on the protocol.

The notion of construction is composable, which intuitively means that the constructed resource can be replaced in any context by the assumed resource with the protocol attached without affecting the security. This is proven in [9].

2.3 Robust Authenticated Encryption

Let $\varSigma$ be an alphabet (a finite nonempty set). Typically an element of $\varSigma$ is a bit ($\varSigma = \{0,1\}$) or a byte ($\varSigma = \{0,1\}^8$). For a string $x \in \varSigma ^*$, ${|{x}|}$ denotes its length. We define the syntax of a robust authenticated encryption scheme following [6].

Definition 2

A robust authenticated encryption (RAE) scheme $\varPi = (\mathcal {K}, \mathcal {E}, \mathcal {D})$ consists of a key distribution $\mathcal {K}$, a deterministic encryption algorithm $\mathcal {E}$ that maps a key $K \in \mathcal {K}$, a nonce $N \in \mathcal {N}$, associated data $A \in \mathcal {A}$, ciphertext expansion $\lambda \in \mathbb {N}$, and a message $M \in \mathcal {M}$ to a ciphertext $C\in \mathcal {C}$, and a deterministic decryption algorithm $\mathcal {D}$ that maps $(K,N,A,\lambda ,C)$ to an element in $\mathcal {M}\cup \{\bot \}$. We assume the domains $\mathcal {N}$, $\mathcal {A}$, $\mathcal {M}$, and $\mathcal {C}$ are equal to $\varSigma ^*$. We write $\mathcal {E}_K^{N, A, \lambda }$ and $\mathcal {D}_K^{N, A, \lambda }$ for the functions $\mathcal {E}(K, N, A, \lambda , \cdot )$ and $\mathcal {D}(K, N, A, \lambda , \cdot )$, respectively. We require that $\mathcal {D}_K^{N, A, \lambda }\left( \mathcal {E}_K^{N, A, \lambda }(M)\right) = M$ for all $K,N,A, \lambda ,M$.

3 Shared Uniform Random Injections and RAE Security

In this section, we describe the resource $\mathbf {URI}$ that grants access to shared uniform random injections and their inverses at interfaces $\mathsf {A}$ and $\mathsf {B}$, and no access at interface $\mathsf {E}$. We then use $\mathbf {URI}$ to define the security of RAE schemes and show that any RAE scheme that satisfies this definition can be used to construct $\mathbf {URI}$ from a shared secret key. Though syntactically different, it is easy to see that our definition is equivalent to the security definition from [6]. We recall that definition and prove the equivalence in the full version of this paper.

We first give a definition for the uniform random injection system $\mathbf {URI}$.

Definition 3

The resource $\mathbf {URI}$ has interfaces $\mathsf {A}$, $\mathsf {B}$, and $\mathsf {E}$ and takes inputs of the form $(\mathsf {fun}, N, A, \lambda , x)$ and $(\mathsf {inv}, N, A, \lambda , y)$ at interfaces $\mathsf {A}$ and $\mathsf {B}$ for $N \in \mathcal {N}$, $A \in \mathcal {A}$, $\lambda \in \mathbb {N}$, $x\in \mathcal {M}$, and $y \in \mathcal {C}$. Any input at interface $\mathsf {E}$ is ignored. We assume the domains $\mathcal {N}$, $\mathcal {A}$, $\mathcal {M}$, and $\mathcal {C}$ are equal to $\varSigma ^*$. On input $(\mathsf {fun}, N, A, \lambda , x)$ at interface $\mathsf {A}$ or $\mathsf {B}$, it returns $f_{N, A, \lambda , {|{x}|}}(x)$ at the same interface. On input $(\mathsf {inv}, N, A, \lambda , y)$, it returns $f_{N, A, \lambda , {|{y}|}-\lambda }^{-1}(y)$ if ${|{y}|} > \lambda$, and $\bot$ otherwise. The function $f_{N, A, \lambda , \ell }$ is chosen uniformly at random from the set $\mathrm {Inj}\left( \varSigma ^{\ell }, \varSigma ^{\ell + \lambda }\right)$ when needed for the first time and reused for later inputs.

3.1 Definition of RAE Security and Construction of URI

We define a shared key resource $\mathbf {SK}_{\mathcal {K}}$ for some key distribution $\mathcal {K}$. The resource initially chooses a key according to $\mathcal {K}$ and outputs this key to interfaces $\mathsf {A}$ and $\mathsf {B}$ while interface $\mathsf {E}$ remains inactive, see Fig. 1. Slightly abusing notation, we will also refer to the key space by $\mathcal {K}$ whenever no confusion can arise. We further define the converter $\mathsf {rae}_\varPi$ that is based on an RAE scheme $\varPi = (\mathcal {K}, \mathcal {E}, \mathcal {D})$. First, $\mathsf {rae}_\varPi$ requests the key from $\mathbf {SK}_{\mathcal {K}}$. For any input at the outer interface, it evaluates $\mathcal {E}$ or $\mathcal {D}$ using that key (and the arguments provided in the input) and returns the result. The code is given in Fig. 1.

We consider an RAE scheme secure if all efficient distinguishers have poor advantage with respect to the following definition.

Definition 4

The advantage of a distinguisher $\mathbf {D}$ for an RAE scheme $\varPi$ is quantified as

$$\begin{aligned} \mathbf {Adv}_{\varPi }^{\mathrm {rae}}(\mathbf {D}) := \varDelta ^{\mathbf {D}}\left( {\mathsf {rae}_\varPi }^\mathsf {A}\, {\mathsf {rae}_\varPi }^\mathsf {B}\, \mathbf {SK}_{\mathcal {K}},\mathbf {URI}\right) . \end{aligned}$$

It is straightforward to see that the definition implies the following construction statement, where the converters $\mathsf {sim}$ and $\mathsf {noAtck}$ are defined as the converter that blocks any interaction at the interface it is connected to.

Lemma 1

The protocol $(\mathsf {rae}_\varPi ,\mathsf {rae}_\varPi )$ constructs $\mathbf {URI}$ from $\mathbf {SK}_{\mathcal {K}}$ within $\mathbf {Adv}_{\varPi }^{\mathrm {rae}}$ with respect to $(\mathsf {noAtck}, \mathsf {noAtck})$ and simulator $\mathsf {sim}$ defined above.

Proof

Since interface $\mathsf {E}$ of $\mathbf {SK}_{\mathcal {K}}$ and $\mathbf {URI}$ are inactive, the converters $\mathsf {sim}$ and $\mathsf {noAtck}$ have no effect when connected to that interface, i.e., $\mathsf {noAtck}^\mathsf {E}\, \mathbf {SK}_{\mathcal {K}} = \mathbf {SK}_{\mathcal {K}}$ and $\mathsf {noAtck}^\mathsf {E}\, \mathbf {URI} = \mathsf {sim}^\mathsf {E}\, \mathbf {URI} = \mathbf {URI}$. Thus, both the availability and the security condition of the construction are equivalent to

$$\begin{aligned} \varDelta ^{\mathbf {D}}\left( {\mathsf {rae}_\varPi }^\mathsf {A}\, {\mathsf {rae}_\varPi }^\mathsf {B}\, \mathbf {SK}_{\mathcal {K}},\mathbf {URI}\right) \le \mathbf {Adv}_{\varPi }^{\mathrm {rae}}(\mathbf {D}) \end{aligned}$$

for all distinguishers $\mathbf {D}$, which trivially holds by definition of $\mathbf {Adv}_{\varPi }^{\mathrm {rae}}$.    $\square$

Fig. 1.

Protocol that constructs $\mathbf {URI}$ from a shared secret key (left) and the shared secret key resource (right). For the shared key resource, interface $\mathsf {E}$ remains inactive.

4 Random Injection Channels: Security for any Expansion

The goal of the current section is to examine the exact security achieved by RAE schemes when used to protect communication. We present constructions of specific secure channels from insecure channels and resource $\mathbf {URI}$ where each type of secure channel precisely captures the amount of leakage to an eavesdropper and the possible influence of an adversary interfering with the protocol execution. As an additional result, we are able to answer what best-possible communication security is and observe that RAE schemes achieve this level of security.

The insecure channel $\mathbf {IC}$ allows messages $m \in \mathcal {M}$ to be input repeatedly at interface $\mathsf {A}$. Each message is subsequently leaked at the $\mathsf {E}$-interface. At interface $\mathsf {E}$, arbitrary messages (including those that were previously input at interface $\mathsf {A}$) can be injected such that they are delivered to $\mathsf {B}$. This channel does not give any security guarantees to Alice and Bob. A formal description is provided in Fig. 2. For the rest of this paper, the message space of the insecure channel is $\varSigma ^*$.

Fig. 2.

The insecure channel resource.

4.1 Constructing Random Injection Channels

The Constructed Channel. The channel we construct in this section is defined in Fig. 3 and can be roughly described as follows: It allows to repeatedly send pairs $(A_i, M_i)$ in an ordered fashion from a sender to a receiver. Each pair consists of the associated data $A_i$ and the message $M_i$. The attacker is limited to seeing the associated data $A_i$ and the length of the message ${|{M_i}|}$ of each transmitted pair. Additionally, the attacker learns whether the ith injected pair equals the one that is currently sent.

The attacker can either deliver the next legitimate pair $(A_i, M_i)$ or try to inject a pair $(A,M)$ that is different from $(A_i, M_i)$. Such an injection is only successful with a certain probability. The associated data $A$ and the length $\ell$ of the message are chosen by the attacker and $M$ is a uniformly random message of length $\ell$ if $A\ne A_i$. Otherwise, $M$ is a uniformly random message $M\ne M_i$ of length $\ell$. If an injection attempt is not successful, the resource does not deliver messages at interface $\mathsf {B}$ any more and signals an error by outputting $\bot$. If the adversary injects the ith message, the legitimate ith message cannot be delivered anymore.²

The success probability of an injection attempt depends on the expansion $\lambda$ and the specified message length $\ell$ and whether the sender’s queue $\mathcal {S}$ is empty or not. The exact probabilities are quantified by the two sampling functions Sample and SamplExcl. The function Sample first samples a bit according to the probability that a fixed element from $\varSigma ^{\ell +\lambda }$ has a preimage under a uniform random injection $\varSigma ^\ell \rightarrow \varSigma ^{\ell +\lambda }$. If the bit is 1, a uniform random preimage is returned. The function SampleExcl essentially does the same, but the domain and codomain are both reduced by one element.³

Protocol. We construct resource $\mathbf {RIC}_\lambda$ from $[\mathbf {URI}, \mathbf {IC}]$ which denotes the resource that provides at each interface access to the corresponding interface of both resources. Our protocol specifies a particular but very natural usage of $\mathbf {URI}$ where the nonce is implemented as a counter value.⁴ We present the protocol as pseudocode in Fig. 4. The converter for the sender, $\mathsf {snd}_\lambda$, accepts inputs of the form $(\mathsf {send},A,M)$ at its outer interface. It outputs $(\mathsf {fun}, i, A, \lambda , M)$ at the inner interface to $\mathbf {URI}$. The nonce is implemented as a counter and $\lambda$ is the parameter of the protocol. Once a ciphertext is received as a return value from $\mathbf {URI}$, it is output together with its associated data at the inner interface for the insecure channel $\mathbf {IC}$. The receiver converter $\mathsf {rcv}_\lambda$ receives ciphertexts together with the associated data at its inner interface from $\mathbf {IC}$ and decrypts $C$ using parameters $A$, i and $\lambda$. On success, the corresponding plaintext is output at the outer interface. If decryption fails, the converter stops and signals an error by outputting $\bot$.

Fig. 3.

Description of $\mathbf {RIC}_\lambda$. In the description, $\mathrm {Bernoulli}(p)$ denotes the distribution over $\{0,1\}$, where 1 has probability p and 0 has probability $1-p$.

Fig. 4.

The converters for the sender (left) and the receiver (right) to construct $\mathbf {RIC}_\lambda$.

Construction Statement. In order to show that the protocol $(\mathsf {snd}_\lambda , \mathsf {rcv}_\lambda )$ constructs $\mathbf {RIC}_\lambda$ from $[\mathbf {URI}, \mathbf {IC}]$, we prove both conditions of Definition 1. For all channels, the converter $\mathsf {noAtck}$ corresponds to the converter $\mathsf {dlv}$ that on any input at its inner interface, outputs $\mathsf {deliver}$ to the channel connected to its inner interface and blocks any interaction at its outer interface.

Theorem 1

Let $\lambda \in \mathbb {N}$. The protocol $(\mathsf {snd}_\lambda ,\mathsf {rcv}_\lambda )$ constructs resource $\mathbf {RIC}_\lambda$ from $[\mathbf {URI}, \mathbf {IC}]$ with respect to $(\mathsf {dlv}, \mathsf {dlv})$ and simulator $\mathsf {sim}_{\mathrm {RIC}}$ as defined in Fig. 5. More specifically, for all distinguishers $\mathbf {D}$

$$\begin{aligned} \varDelta ^{\mathbf {D}}\left( \mathsf {snd}_\lambda ^\mathsf {A}\mathsf {rcv}_\lambda ^\mathsf {B}\mathsf {dlv}^\mathsf {E}[\mathbf {URI}, \mathbf {IC}],\mathsf {dlv}^\mathsf {E}\mathbf {RIC}_\lambda \right)&= 0 \end{aligned}$$

(1)

$$\begin{aligned} and \quad \varDelta ^{\mathbf {D}}\left( \mathsf {snd}_\lambda ^\mathsf {A}\mathsf {rcv}_\lambda ^\mathsf {B}[\mathbf {URI}, \mathbf {IC}],\mathsf {sim}_{\mathrm {RIC}}^\mathsf {E}\mathbf {RIC}_\lambda \right)&= 0. \end{aligned}$$

(2)

We prove Theorem 1 in the full version of this paper.

4.2 What is Best-Possible Security?

We observe that $\mathbf {RIC}_\lambda$ has two undesirable properties: messages can be injected and the output at interface $\mathsf {E}$ leaks more than only the length of the payload in that it reveals whether Alice sends the pair $(A,M)$ that has been output by Bob upon an adversarial injection. In contrast, a channel that only leaks the message length is considered fully confidential.

We first illustrate an application in which this lack of full confidentiality is problematic. The main purpose of our example is to show that one cannot exclude the existence of an application where exactly this (intuitively small) difference to full confidentiality yields a security problem.

Second, we show that a successful injection followed by the undesired information leakage about the repetition is possible for any scheme, even if it is stateful and uses an arbitrary setup before starting communication, and that the probability of this is minimized if $\mathbf {RIC}_\lambda$ is used.

Fig. 5.

Simulator for the security condition of the construction of $\mathbf {RIC}_\lambda$.

Sample Scenario: On the Difference to Full Confidentiality. Assume a setting in which party $\mathsf {A}$ is allowed to send information to party $\mathsf {B}$ via a fully confidential channel but not vice versa. Suppose now that $\mathsf {B}$ finds a possibility to send information to $\mathsf {A}$ via a covert channel and the two parties use the confidential channel for messages from $\mathsf {A}$ to $\mathsf {B}$ and the covert channel for messages from $\mathsf {B}$ to $\mathsf {A}$. Suppose now that the confidential channel is in fact a channel that leaks the above repetition event instead of only the message length. This gives an investigator $\mathsf {E}$ a means to test for the existence of a covert channel from $\mathsf {B}$ to $\mathsf {A}$ as follows: At some point, $\mathsf {E}$ injects a random message $M$ to $\mathsf {B}$. Assuming information flow from $\mathsf {B}$ to $\mathsf {A}$, party $\mathsf {B}$ might start a discussion about $M$ with party $\mathsf {A}$. As part of this conversation, $\mathsf {A}$ might send $M$ to $\mathsf {B}$, which would signal a repetition-event to $\mathsf {E}$. For large message spaces, it is very unlikely that $\mathsf {A}$ comes up with the exact same message that was randomly injected to $\mathsf {B}$ before, unless there is a (hidden) flow of information. The occurrence of the event is therefore a witness for the existence of a channel from $\mathsf {B}$ to $\mathsf {A}$. In contrast, a fully confidential channel would not reveal the existence of the covert channel.

RIC Provides Best-Possible Security. In $\mathbf {RIC}_\lambda$, an injection attempt is successful with probability at most $\frac{{|{\mathcal {M}}|}}{{|{\mathcal {C}}|}} = {|{\varSigma }|}^{-\lambda }$ and given a successful injection and that Alice subsequently sends the corresponding output of Bob, the above described leakage occurs with probability 1. Overall, the total probability that an undesired property can be observed is bounded by ${|{\varSigma }|}^{-\lambda }$.

We show that this probability is optimal and that no protocol can achieve a better bound. Hence, $\mathbf {RIC}_\lambda$ maximizes authenticity and confidentiality. We first prove the following general lemma.

Lemma 2

Let $\mathcal {M}$ and $\mathcal {C}$ be finite nonempty sets and let E and D be random variables over functions $\mathcal {A}\times \mathcal {M}\rightarrow \mathcal {C}$ and $\mathcal {A}\times \mathcal {C}\rightarrow \mathcal {M}\cup \{\bot \}$, respectively, such that

$$\begin{aligned} \forall m \in \mathcal {M},a \in \mathcal {A}: \ \ \mathsf {Pr}[D(a, E(a, m)) = m] \ge p \end{aligned}$$

for some $p \in [0,1]$. We then have for all $a \in \mathcal {A}$ and any random variable C that is distributed uniformly over $\mathcal {C}$ and independent from E and D,

$$\begin{aligned} \mathsf {Pr}[D(a, C) \ne \bot \wedge E(a, D(a, C)) = C] \ge p \cdot \frac{{|{\mathcal {M}}|}}{{|{\mathcal {C}}|}}. \end{aligned}$$

Proof

We have for all $a \in \mathcal {A}$

$$\begin{aligned} \mathsf {Pr}[D(a, C) \ne \bot \wedge E(a,&D(a, C)) = C] \\&= \sum _{m \in \mathcal {M}} \sum _{c \in \mathcal {C}} \mathsf {Pr}[D(a, c) = m \wedge E(a, m) = c \wedge C = c] \\&= \frac{1}{{|{\mathcal {C}}|}} \sum _{m \in \mathcal {M}} \underbrace{\sum _{c \in \mathcal {C}} \mathsf {Pr}[D(a, c) = m \wedge E(a, m) = c]}_{= \, \mathsf {Pr}[D(a, E(a, m)) = m] \ \ge \ p} \\&\ge \ p \cdot \frac{{|{\mathcal {M}}|}}{{|{\mathcal {C}}|}}, \end{aligned}$$

where we used in the second step that C is distributed uniformly over $\mathcal {C}$ and independent from E and D.    $\square$

Lemma 2 can be applied to our usual setting $\mathsf {enc}_\lambda ^\mathsf {A}\mathsf {dec}_\lambda ^\mathsf {B}[\mathbf {SK}_{\mathcal {K}}, \mathbf {IC}]$ for a generic protocol $(\mathsf {enc}_\lambda ,\mathsf {dec}_\lambda )$ in a straightforward manner: we only have to observe that for the ith input $(\mathsf {send}, A_i, M_i)$, for all $i \in \mathbb {N}$, converter $\mathsf {enc}_\lambda$ is characterized by a probabilistic map $\mathcal {A}\times \mathcal {M}\rightarrow \mathcal {C}$, that may depend on previous inputs and outputs and on the key k. Similarly, the converter $\mathsf {dec}_\lambda$ is characterized by a probabilistic map $\mathcal {A}\times \mathcal {C}\rightarrow \mathcal {M}\cup \{\bot \}$ for any $i \in \mathbb {N}$.

Correctness of the protocol implies that if $(\mathsf {send}, A_i, M_i)$ is input to $\mathsf {enc}_\lambda$ as the ith query and yields ciphertext $C_i$, then the probability that on the ith input $(A_i, C_i)$ to $\mathsf {dec}_\lambda$, and if $\mathsf {dec}_\lambda$ has not halted yet, the converter decrypts the ciphertext to $M_i$ with probability p; note that $p=1$ for RAE schemes. Hence, Lemma 2 implies that the probability that any of the two undesirable properties can be observed during protocol execution is at least ${|{\varSigma }|}^{-\lambda }$.

5 Augmented Secure Channels and Verifiable Redundancy

Looking at the specification of $\mathbf {RIC}_\lambda$, we observe that for large values $\lambda$, the probability of successful injections becomes exponentially small, and so are the repetition events at interface $\mathsf {E}$. We are particularly interested in the resource that specifies this abstraction: a channel that allows to securely transmit messages consisting of an associated data and a payload part such that an attacker is limited to seeing the associated data and the length of the payload, to deliver the next message, or to abort the whole communication. This channel abstraction corresponds to an augmented secure channel. Such channels were introduced in [1] and shown to be achievable by the AEAD notion of [12]. Not surprisingly, this confirms that RAE and AEAD achieve the same security goals for large ciphertext expansion.

Additionally, we formally show how redundancy in messages can be exploited to improve authenticity, where redundancy restricts the set of valid messages to a subset of $\mathcal {M}= \varSigma ^*$.

The following theorem provides the exact security bound in terms of redundancy in the message space and ciphertext expansion $\lambda$. We thereby confirm a conjecture of [6]. Let $v: \mathcal {M}\mapsto \{\mathsf {true},\mathsf {false}\}$ be a predicate on the message space. We define the subset $\mathcal {M}_v := \{M\mid M\in \mathcal {M}\ \wedge \ v(M)\}$ which we call the set of valid messages. Following [6], the density of $\mathcal {M}_v$ is defined as

$$\begin{aligned} d_v:= \max _{\ell \in \mathbb {N}}\frac{|\varSigma ^\ell \cap \mathcal {M}_v|}{{|{\varSigma ^\ell }|}}. \end{aligned}$$

Fig. 6.

Description of $\mathbf {ASC}$, an augmented secure channel.

The Constructed Channel. The augmented secure channel $\mathbf {ASC}_{\mathcal {M}_v}$ is described in Fig. 6. The channel is derived from $\mathbf {RIC}_\lambda$ by requiring that $M\in \mathcal {M}_v$ and by removing undesired capabilities that vanish due to the exponentially small success probability for large $\lambda$.

Protocol. The protocol for the sender, $\mathsf {sndChk}_v$, accepts inputs of the form $(\mathsf {send}, A, M)$ at its outer interface and forwards the pair to the channel $\mathbf {RIC}_\lambda$ if and only if v(M) (and otherwise ignores the request). The receiver converter $\mathsf {rcvChk_v}$, on receiving the pair $(A,M)$ from $\mathbf {RIC}_\lambda$, outputs $(A,M)$ at its outer interface if and only if v(M). If $\mathsf {rcvChk_v}$ receives $\bot$ from $\mathbf {RIC}_\lambda$ or if $\lnot v(M)$, it outputs $\bot$ at its outer interface and halts.

Theorem 2

Let $\lambda \in \mathbb {N}$. The protocol $(\mathsf {sndChk}_v,\mathsf {rcvChk_v})$ constructs $\mathbf {ASC}_{\mathcal {M}_v}$ from $\mathbf {RIC}_\lambda$ with respect to $(\mathsf {dlv},\mathsf {dlv})$ and simulator $\mathsf {sim}_{\mathrm {ASC}}$ defined in Fig. 7. More specifically, for all distinguishers $\mathbf {D}$

$$\begin{aligned} \varDelta ^{\mathbf {D}}\left( \mathsf {sndChk}_v^\mathsf {A}\mathsf {rcvChk_v}^\mathsf {B}\mathsf {dlv}^\mathsf {E}\mathbf {RIC}_\lambda ,\mathsf {dlv}^\mathsf {E}\mathbf {ASC}_{\mathcal {M}_v}\right)&= 0 \end{aligned}$$

(3)

$$\begin{aligned} and \quad \varDelta ^{\mathbf {D}}\left( \mathsf {sndChk}_v^\mathsf {A}\mathsf {rcvChk_v}^\mathsf {B}\mathbf {RIC}_\lambda ,\mathsf {sim}_{\mathrm {ASC}}^\mathsf {E}\mathbf {ASC}_{\mathcal {M}_v}\right)&\le d_v\cdot {|{\varSigma }|}^{-\lambda }. \end{aligned}$$

(4)

Fig. 7.

Simulator for the security condition of the construction of $\mathbf {ASC}_{\mathcal {M}_v}$.

Fig. 8.

Description of $\mathbf {RASC}$.

Fig. 9.

The converters for the sender (left) and the receiver (right).

Fig. 10.

Simulator for the security condition of the construction of $\mathbf {RASC}_{\mathcal {M}_v}$.

Proof

The availability condition (3) is straightforward to verify. We only prove the security condition (4). It is easy to see that the two systems behave identically as long as no injection attempt is successful. This is because successful injections are necessary for observing $\mathsf {repeat}$: as long as no injection is successful, for any $\mathsf {send}$-query to $\mathbf {RIC}_\lambda$, the condition $i \le {|{\mathcal {R}}|}$ is not satisfied after incrementing i. We thus only have to bound this probability. We hence consider the event that in an interaction of a distinguisher with the real system $\mathsf {sndChk}_v^\mathsf {A}\mathsf {rcvChk_v}^\mathsf {B}\mathbf {RIC}_\lambda$ the first attempt to inject a random message is successful (since in case of an unsuccessful attempt, both channels stop delivering messages). In any interaction of $\mathbf {D}$ with the resource, the probability of the event is determined by $\mathbf {RIC}_\lambda$ as one out of two possibilities, see Fig. 3. For any $i \in \mathbb {N}$, if the ith query at interface $\mathsf {E}$ is the first attempt to inject a message, then the probability depends on whether the specified associated data and the length coincides with the length of the message and the associated data of the ith input at interface $\mathsf {A}$. Both probabilities are upper bounded by

$$\begin{aligned} \max \left\{ \frac{{|{\varSigma ^{{|{C_i}|} - \lambda } \cap \mathcal {M}_v}|} - 1}{{|{\varSigma ^{{|{C_i}|}}}|} - 1}, \frac{{|{\varSigma ^{{|{C_i}|} - \lambda } \cap \mathcal {M}_v}|}}{{|{\varSigma ^{{|{C_i}|}}}|}} \right\} \le \frac{{|{\varSigma ^{{|{C_i}|} - \lambda } \cap \mathcal {M}_v}|}}{{|{\varSigma ^{{|{C_i}|}}}|}} \\ = \frac{{|{\varSigma ^{|C_i|-\lambda } \cap \mathcal {M}_v}|}}{{|{\varSigma ^{{|{C_i}|} - \lambda }}|}} \cdot {|{\varSigma }|}^{-\lambda } \le d_v\cdot {|{\varSigma }|}^{-\lambda }, \end{aligned}$$

where we used $\frac{x-1}{y-1} \le \frac{x}{y}$ for $x \le y$ in the first step, and the definition of $d_v$ in the last step.    $\square$

6 Guarantees for Nonce-Reuse

One goal of robust authenticated encryption is to provide resilience to the misuse when nonces are repeated. While the expected security loss was only informally stated in [6], we rigorously derive the exact guarantees that can still be expected in such a scenario. To this end, we consider the extreme case where the nonce is a constant value.

Repetition ASC. The channel that is achieved if the nonce is repeating is denoted $\mathbf {RASC}_{\mathcal {M}_v}$ and its description is given in Fig. 8. There are two differences to $\mathbf {ASC}_{\mathcal {M}_v}$: First, not only the length of the message is leaked at interface $\mathsf {E}$ but also the number i of the first transmitted message that equals the current message. This leaks the repetition pattern of transmitted values. Second, the adversary can replay messages and induce arbitrary out-of-order delivery.

Protocol. The protocol, which we denote by $(\mathsf {rsnd},\mathsf {rrcv})$, invokes $\mathbf {URI}$ using the constant nonce 0. Furthermore, the protocol verifies that all messages are from the set $\mathcal {M}_v$. The protocol is specified in Fig. 9.

Theorem 3

Let $\lambda \in \mathbb {N}$. The protocol $(\mathsf {rsnd}_\lambda ,\mathsf {rrcv}_\lambda )$ constructs $\mathbf {RASC}_{\mathcal {M}_v}$ from $[\mathbf {URI}, \mathbf {IC}]$ with respect to $(\mathsf {dlv},\mathsf {dlv})$ and simulator $\mathsf {sim}_{\mathrm {RASC}}$ defined in Fig. 10. More specifically, we have for all distinguishers $\mathbf {D}$

$$\begin{aligned} \varDelta ^{\mathbf {D}}\left( \mathsf {rsnd}_\lambda ^\mathsf {A}\mathsf {rrcv}_\lambda ^\mathsf {B}\mathsf {dlv}^\mathsf {E}[\mathbf {URI}, \mathbf {IC}],\mathsf {dlv}^\mathsf {E}\mathbf {RASC}_{\mathcal {M}_v}\right) \le \frac{2 d_v+ q \cdot (q-1)}{2} \cdot {|{\varSigma }|}^{-\lambda } \end{aligned}$$

(5)

and

$$\begin{aligned} \varDelta ^{\mathbf {D}}\left( \mathsf {rsnd}_\lambda ^\mathsf {A}\mathsf {rrcv}_\lambda ^\mathsf {B}[\mathbf {URI}, \mathbf {IC}],\mathsf {sim}_{\mathrm {RASC}}^\mathsf {E}\mathbf {RASC}_{\mathcal {M}_v}\right) \le \frac{2 d_v+ q \cdot (q-1)}{2} \cdot {|{\varSigma }|}^{-\lambda }, \end{aligned}$$

(6)

where q is the total number of inputs made by $\mathbf {D}$.

We prove Theorem 3 in the full version of this paper.