Unilaterally-Authenticated Key Exchange

Abstract

Key Exchange (KE), which enables two parties (e.g., a client and a server) to securely establish a common private key while communicating over an insecure channel, is one of the most fundamental cryptographic primitives. In this work, we address the setting of unilaterally-authenticated key exchange (UAKE), where an unauthenticated (unkeyed) client establishes a key with an authenticated (keyed) server. This setting is highly motivated by many practical uses of KE on the Internet, but received relatively little attention so far.

Unlike the prior work, defining UAKE by downgrading a relatively complex definition of mutually authenticated key exchange (MAKE), our definition follows the opposite approach of upgrading existing definitions of public key encryption (PKE) and signatures towards UAKE. As a result, our new definition is short and easy to understand. Nevertheless, we show that it is equivalent to the UAKE definition of Bellare-Rogaway (when downgraded from MAKE), and thus captures a very strong and widely adopted security notion, while looking very similar to the simple “one-oracle” definition of traditional PKE/signature schemes. As a benefit of our intuitive framework, we show two exactly-as-you-expect (i.e., having no caveats so abundant in the KE literature!) UAKE protocols from (possibly interactive) signature and encryption. By plugging various one- or two-round signature and encryption schemes, we derive provably-secure variants of various well-known UAKE protocols (such as a unilateral variant of SKEME with and without perfect forward secrecy, and Shoup’s A-DHKE-1), as well as new protocols, such as the first 2-round UAKE protocol which is both (passively) forward deniable and forward-secure.

To further clarify the intuitive connections between PKE/Signatures and UAKE, we define and construct stronger forms of (necessarily interactive) PKE/Signature schemes, called confirmed encryption and confidential authentication, which, respectively, allow the sender to obtain confirmation that the (keyed) receiver output the correct message, or to hide the content of the message being authenticated from anybody but the participating (unkeyed) receiver. Using confirmed PKE/confidential authentication, we obtain two concise UAKE protocols of the form: “send confirmed encryption/confidential authentication of a random key K.”

1 Introduction

Key exchange (KE) is one of the most fundamental cryptographic primitives. Using a KE protocol, two parties can securely establish a common, private, cryptographic key while communicating over an insecure channel. Although the basic idea of KE dates back to the seminal work of Diffie and Hellman [7], a proper formalization of this notion was proposed only much later by Bellare and Rogaway [2]. In particular, Bellare and Rogaway considered the problem of mutually authenticated key exchange where two parties (e.g., a client and a server), each holding a valid long-term key pair, want to agree on a fresh common cryptographic key, while being assured about the identity of their protocol’s partner. In [2], Bellare and Rogaway proposed a model for mutually-authenticated KE which allows to formally define security in this context, and in particular formalizes the adversary’s capabilities in a proper way.

Building on this remarkable work, many other papers addressed KE in multiple directions, such as efficient and provably-secure realizations [15], or alternative security models [1, 5, 6]. Notably, the vast majority of papers in this area considered only the mutually authenticated setting where both the server and the client have long-term keys. However, it is striking to observe that many practical uses of KE protocols on the Internet work in a restricted setting where only the server has a long-term (certified) public key. A notable example of this setting is perhaps the simple access to web servers using the well known SSL/TLS protocol. This notion of KE has been often called unilaterally-authenticated (or, sometimes, anonymous, one-way or server-only) KE. To emphasize the distinction, in our work we will denote unilaterally-authenticated KE as UAKE, and mutually-authenticated KE as MAKE.

In spite of the practical relevance of unilaterally-authenticated key-exchange, we notice that most prior KE definitions targeted MAKE, and those works that focused on UAKE (e.g., [10, 11, 17, 21]) used definitions that were obtained by slightly “downgrading” definitions of MAKE to the unilateral setting. The problem here is that existing definitions of MAKE are rigorous, but also pretty complex and hard to digest. Therefore, when analyzing the simple notion of UAKE by downgrading existing definitions of MAKE, one ends up with other complex definitions.

One goal of this work is thus to address this state of affairs by taking a different approach. Instead of considering UAKE as a downgraded version of MAKE, we propose a new definition of UAKE obtained by slightly “upgrading” the short and simple definitions of public key encryption and digital signatures. Precisely, we build on the recent work of Dodis and Fiore [8] that proposes a definitional framework for interactive message transmission protocols, and gives new notions of interactive public key encryption (PKE) and interactive public key message authentication (PKMA). These two notions naturally extend the classical notions of $\mathsf{IND\text{- }\!CCA}$ encryption (resp. strongly unforgeable signatures) to the interactive setting. By building on this framework, we obtain a UAKE definition which is (in our opinion) more intuitive and easier to digest.¹ Nevertheless, we show that our differently-looking UAKE definition is equivalent to the one of Bellare-Rogaway (BR) restricted to the single authenticated setting. This shows that we are not providing a new KE notion, but simply suggesting a different, simpler, way to explain the same notion when restricted to the unilateral setting. In fact, the BR UAKE definition “downgraded-from-MAKE ” is actually noticeably simpler than the MAKE definition, but still (in our opinion) not as intuitive as our new definition. Hence, by establishing our equivalence, we offer a new path of teaching/understanding MAKE: (1) present our definition of UAKE, and use it to design and prove simple UAKE protocols (see below); (2) point out new subtleties of MAKE, making it hard (impossible?) to have a simple “one-oracle” definition of MAKE; (3) introduce the “downgraded” BR-framework (which has more finer-grain oracles available to the attacker) which is equivalent to our UAKE framework; (4) extend the ”downgraded” BR framework to the full setting of MAKE. We view this philosophy as a major educational contribution of this work.

In the following, we describe our definitional framework and the remaining results (including simple and intuitive UAKE protocols) in more detail.

1.1 Our Results

Definitional Framework. The definitional framework proposed by Dodis and Fiore [8] consists of two parts. The first part is independent of the particular primitive, and simply introduces the bare minimum of notions/notation to deal with interaction. For example, they define (a) what it means to have concurrent oracle access to an interactive party under attack; and (b) what it means to ‘act as a wire’ between two honest parties (this trivial, but unavoidable, attack is called a ‘ping-pong’ attack). Once the notation is developed, the actual definitions become as short and simple as in the non-interactive setting (e.g., see Definitions 5 and 6). So, by building on this framework, we propose a simple notion of UAKE (cf. Definition 8) which we briefly discuss now. The attacker $\mathcal{A}$ has concurrent oracle access to the honest secret key owner (the “server”), and simultaneously tries to establish a (wlog single) session key with an honest unauthenticated client (the “challenger”). If the challenger rejects, $\mathcal{A}$ ‘lost’.² If it accepts and the session is not a ping-pong of one of its conversations with the server, then $\mathcal{A}$ ‘won’, since it ‘fooled’ the challenger without trivially forwarding messages from the honest server. Otherwise, if $\mathcal{A}$ established a valid key with the challenger by a ping-pong attack, $\mathcal{A}$ ‘wins’ if it can distinguish a (well-defined) ‘real’ session key from a completely random key.³

Key Exchange Protocols. As we mentioned, our unilaterally-authenticated key-exchange (UAKE) definition can be seen as a natural extension of the interactive PKE/PKMA definitions in [8]. As a result, we show two simple and very natural constructions of UAKE protocols: from any possibly interactive PKE scheme and a PRF, depicted in Fig. 2, and from any possibly interactive PKMA scheme and CPA-secure key encapsulation mechanism (KEM), depicted in Fig. 3. By plugging various non-interactive or 2-round PKE/PKMA schemes (and KEMs, such as the classical Diffie-Hellman KE), we get a variety of simple and natural UAKE protocols. For example, we re-derive the A-DHKE-1 protocol from [21], the unilateral version of the SKEME protocol [14], and we get (to the best of our knowledge) the first 2-round UAKE, depicted in Fig. 4, which is both forward-deniable and forward-secure.

Hence, the main contribution of our work is not to design new UAKE protocols (which we still do due to the generality of our results!), but rather to have a simple and intuitive UAKE framework where everything works as expected, without any caveats (so abundant in the traditional KE literature). Namely, the fact that immediate corollaries of our work easily establish well known and widely used UAKE protocols is a big feature of our approach. Unlike prior work, however, our protocols: (1) work with interactive PKE/PKMA; (2) are directly analyzed in the unilateral setting using our simple definition, instead of being “downgraded” from more complex MAKE protocols.

Confirmed PKE and Confidential PKMA. To provide a further smoother transition from basic notions of PKE/PKMA towards KE, another contribution of our work is to define two strengthenings of PKE/PKMA which inherently require interaction. We call these notions confirmed encryption and confidential authentication, but for lack of space we present them in the full version of this work. In brief, confirmed encryption is an extension of the interactive encryption notion of Dodis and Fiore [8] in which the (unkeyed) sender gets a confirmation that the (keyed) receiver obtained the correct encrypted message, and thus accepts/rejects accordingly. Confidential authentication, instead, adds a privacy property to PKMA protocols [8] in such a way that no information about the message is leaked to adversaries controlling the communication channel (and, yet, the unkeyed honest receiver gets the message). Clearly, both notions require interaction, and we show both can be realized quite naturally with (optimal) two rounds of interaction. Moreover, these two notions provide two modular and “dual” ways to build secure UAKE protocols. Namely, we further abstract our UAKE constructions in Figs. 2 and 3 by using the notions of confirmed PKE and confidential PKMA, by showing that “confirmed encryption of random K” and “confidential authentication of random K” both yield secure UAKE protocols.

Summary. Although we do not claim a special novelty in showing a connection between PKE/signatures and KE, we believe that the novelty of our contribution is to formally state such connection in a general and intuitive way. In particular, our work shows a path from traditional non-interactive PKE/PKMA schemes, to interactive PKE/PKMA, to (interactive) confirmed PKE/confidential PKMA, to UAKE, to MAKE (where the latter two steps use the equivalence of our simple “one-oracle” definition with the downgraded Bellare-Rogaway definition). Given that unilaterally-authenticated key-exchange, aside from independent interest, already introduces many of the subtleties of mutually-authenticated key-exchange (MAKE), we hope our work can therefore simplify the introduction of MAKE to students. Indeed, we believe all our results can be easily taught in an undergraduate cryptography course.

1.2 Related Work

Following the work of Bellare and Rogaway [2], several works proposed different security definitions for (mutually-authenticated) KE, e.g., [1, 3,4,5, 18]. Notably, some of these works focused on achieving secure composition properties [6, 21]. Unilaterally-Authenticated Key-Exchange has been previously considered by Shoup [21] (who used the term “anonymous key-exchange”), Goldberg et al. [11] (in the context of Tor), Fiore et al. [10] (in the identity-based setting), and by Jager et al. [12] and Krawczyk et al. [17] (in the context of TLS). All these works arrived at unilaterally-authenticated key-exchange by following essentially the same approach: they started from (some standard definitions of) mutually-authenticated KE, and then they relaxed this notion by introducing one “dummy” user which can run the protocol without any secret (so, the unauthenticated party will run the protocol on behalf of such user), and by slightly changing the party-corruption condition.

Our authentication- (but not encryption-) based UAKE protocols also have conceptual similarities with the authenticator-based design of KE protocols by Bellare et al. [1]. Namely, although [1] concentrate on the mutually-authenticated setting, our UAKE of Fig. 3 is similar to what can be obtained by applying a (unilateral) authenticator to an unauthenticated protocol, such as a one-time KEM. As explained in Sect. 4, however, the derived protocols are not exactly the same. This is because there are noticeable differences between authenticators and interactive PKMA schemes. For example, authenticators already require security against replay attack (and, thus, standard signature schemes by themselves are not good authenticators), and also use a very different real/ideal definition than our simple game-based definition of PKMA. In summary, while the concrete protocols obtained are similar (but not identical), the two works use very different definitions and construction paths to arrive at these similar protocols.

In a concurrent and independent work, Maurer, Tackmann and Coretti [20] considers the problem of providing new definitions of unilateral KE, and they do so by building on the constructive cryptography paradigm of Maurer and Renner [19]. Using this approach, they proposed a protocol which is based only on a CPA-secure KEM and an unforgeable digital signature, and is very similar to one of our UAKE protocols.

Finally, we note that a recent paper by Krawczyk [16] considers unilaterally authenticated key exchange and studies the question of building compilers for transforming UAKE protocols into MAKE ones.

2 Background and Definitions

In our paper we use relatively standard notation. Before giving the definitions of message transmission protocols and unilateral key exchange, we discuss two aspects of our definitions.

Session IDs. Throughout this paper, we consider various protocols (e.g., message transmission or key exchange) that may be run concurrently many times between the same two parties. In order to distinguish one execution of a protocol from another, one typically uses session identifiers, denoted $\mathsf{sid}$, of which we can find two main uses in the literature. The first one is to consider purely “administrative” session identifiers, that are used by a user running multiple session to differentiate between them, i.e., to associate what session a message is going to or coming from. This means that the honest parties need some concrete mechanism to ensure the uniqueness of $\mathsf{sid}$’s, when honestly running multiple concurrent sessions. E.g., administrative $\mathsf{sid}$ can be a simple counter or any other nonce (perhaps together with any information necessary for communication, such as IP addresses or some mutually agreed upon timing information), or could be jointly selected by the parties, by each party providing some part of the $\mathsf{sid}$. However, rather than force some particular choice which will complicate the notation, while simultaneously getting the strongest possible security definition, in our definitions we let the adversary completely control all the administrative $\mathsf{sid}$’s (as the adversary anyway controls all the protocol scheduling). In order not to clutter the notation with this trivial lower level detail, in our work we will ignore such administrative $\mathsf{sid}$’s from our notation, but instead implicitly model them as stated above.

The second use of session identifiers in the literature is more technical as $\mathsf{sid}$’s are used in security definitions in order to define “benign” adversaries that simply act as a wire in the network. With respect to the use of $\mathsf{sid}$’s in security definitions we see three main approaches in the literature. The modern KE approach lets parties define $\mathsf{sid}$’s as part of the protocol. While this is more relaxed and allows for more protocols to be proven secure, it also somewhat clutters the notation as the choice of the $\mathsf{sid}$ is now part of the protocol specification. The second approach is to let $\mathsf{sid}$ be the transcript of a protocol execution, which simplifies the notation and implies the previous approach. In both the first and second approach, benign adversaries are those that cause two sessions have equal $\mathsf{sid}$’s. The third approach instead does not use explicit $\mathsf{sid}$’s, and considers benign adversaries those that cause two sessions have same transcript (seen as a “timed object”). All the approaches have pros and cons. For example, both the second and the third approach rule out some good protocols, but save on syntax and notation. Moreover, the third approach is the strongest one for security: it leaves to protocol implementers the freedom of picking the most convenient “administrative” $\mathsf{sid}$ selection mechanism, without worrying about security, since in this model adversaries can arbitrarily control the administrative $\mathsf{sid}$’s. For these reasons, in this work we follow the third approach, which also gives us the possibility of making our definitions more in line with those of PKE/signatures, where there are no explicit session identifiers.

Party Identities. Unlike the traditional setting of encryption and authentication, in the KE literature parties usually have external (party) identities in addition to their public/secret keys. This allows the same party to (claim to) have multiple keys, or, conversely, the same key for multiple identities. While generality is quite useful in the mutually authenticated setting, and could be easily added to all our definitions and results in the unilateral setting, we decided to avoid this extra layer of notation. Instead, we implicitly set the identity of the party to be its public key (in case of the server), or null (in case of the client). Aside from simpler notation, this allowed us to make our definitions look very similar to traditional PKE/signatures, which was one of our goals. We remark that this is a trivial and inessential choice which largely follows a historic tradition for PKE/PKMA. Indeed, having party identities is equally meaningful for traditional PKE/PKMA schemes, but is omitted from the syntax, because it can always be trivially achieved by appending the identities of the sender and/or recipient to the message. We stress, we do not assume any key registration authority who checks knowledge of secret keys. In fact, in our definition the attacker pretends to be the owner of the victim’s secret key (while having oracle access to the victim), much like in PKE/PKMA the attacker tries to “impersonate” the honest party (signer/decryptor) with only oracle access to this party.

2.1 Message Transmission Protocols

In this section, we recall the definitional framework of message transmission protocols as defined in [8], along with suitable security definitions for confidentiality (called $\mathsf{iCCA}$ security) and authenticity (called $\mathsf{iCMA}$ security).

A message transmission protocol involves two parties, a sender $\mathsf{S}$ and a receiver $\mathsf{R}$, such that the goal of $\mathsf{S}$ is to send a message m to $\mathsf{R}$ while preserving certain security properties on m. Formally, a message transmission protocol $\mathsf{\Pi }$ consists of algorithms $(\mathsf{Setup}, \mathsf{S}, \mathsf{R})$ defined as follows:

• $\mathsf{Setup}(1^{\lambda })$: on input the security parameter $\lambda$, the setup algorithm generates a pair of keys $(\mathsf{sendk}, \mathsf{recvk})$. In particular, these keys contain an implicit description of the message space $\mathcal{M}$.

• $\mathsf{S}(\mathsf{sendk}, m)$: is a possibly interactive Turing machine that is run with the sender key $\mathsf{sendk}$ and a message $m \in \mathcal{M}$ as private inputs.

• $\mathsf{R}(\mathsf{recvk})$: is a possibly interactive Turing machine that takes as private input the receiver key $\mathsf{recvk}$, and whose output is a message $m \in \mathcal{M}$ or an error symbol $\bot$.

We say that $\mathsf{\Pi }$ is an n-round protocol if the number of messages exchanged between $\mathsf{S}$ and $\mathsf{R}$ during a run of the protocol is n. If $\mathsf{\Pi }$ is 1-round, then we say that $\mathsf{\Pi }$ is non-interactive. Since the sender has no output, it is assumed without loss of generality that the $\mathsf{S}$ always speaks last. This means that in an n-round protocol, $\mathsf{R}$ (resp. $\mathsf{S}$) speaks first if n is even (resp. odd). For compact notation, $\langle \mathsf{S}(\mathsf{sendk}, m), \mathsf{R}(\mathsf{recvk}) \rangle =m'$ denotes the process of running $\mathsf{S}$ and $\mathsf{R}$ on inputs $(\mathsf{sendk}, m)$ and $\mathsf{recvk}$ respectively, and assigning $\mathsf{R}$’s output to $m'$. In our notation, we will use $m\in \mathcal{M}$ for messages (aka plaintexts), and capital M for protocol messages.

Definition 1

(Correctness). A message transmission protocol $\mathsf{\Pi }=(\mathsf{Setup}, \mathsf{S}, \mathsf{R})$ is correct if for all honestly generated keys $(\mathsf{sendk}, \mathsf{recvk}) {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathsf{Setup}(1^{\lambda })$, and all messages $m \in \mathcal{M}$, we have that $\langle \mathsf{S}(\mathsf{sendk}, m), \mathsf{R}(\mathsf{recvk}) \rangle =m$ holds with all but negligible probability.

Defining Security: Man-in-the-Middle Adversaries. Here we recall the formalism needed to define the security of message transmission protocols. The basic idea is that an adversary with full control of the communication channel has to violate a given security property (say confidentiality or authenticity) in a run of the protocol that is called the challenge session. Formally, this session is a protocol execution $\langle \mathsf{S}(\mathsf{sendk}, m), \mathcal{A}^{\mathsf{R}(\mathsf{recvk})} \rangle$ or $\langle \mathcal{A}^{\mathsf{S}(\mathsf{sendk}, \cdot )}, \mathsf{R}(\mathsf{recvk}) \rangle$ where the adversary runs with an honest party ($\mathsf{S}$ or $\mathsf{R}$). $\mathcal{A}^{\mathsf{P}}$ denotes that the adversary has oracle access to multiple honest copies of party $\mathsf{P}$ (where $\mathsf{P}=\mathsf{R}$ or $\mathsf{P}=\mathsf{S}$), i.e., $\mathcal{A}$ can start as many copies of $\mathsf{P}$ as it wishes, and it can run the message transmission protocol with each of these copies. In order to differentiate between several copies of $\mathsf{P}$, formally $\mathcal{A}$ calls the oracle providing a session identifier $\mathsf{sid}$. However, as mentioned earlier, to keep notation simple we do not write $\mathsf{sid}$ explicitly. The model assumes that whenever $\mathcal{A}$ sends a message to the oracle $\mathsf{P}$, then $\mathcal{A}$ always obtains $\mathsf{P}$’s output. In particular, in the case of the receiver oracle, when $\mathcal{A}$ sends the last protocol message to $\mathsf{R}$, $\mathcal{A}$ obtains the (private) output of the receiver, i.e., a message m or $\bot$.

Due to its power, the adversary might entirely replay the challenge session by using its oracle. Since this can constitute a trivial attack to the protocol, in what follows we recall the formalism of [8] to capture replay attacks. The approach is similar to the one introduced by Bellare and Rogaway [2] in the context of key exchange, based on the idea of “matching conversations”.

Let t be a global counter which is progressively incremented every time a party (including the adversary) sends a message. Every message sent by a party ($\mathsf{S}$, $\mathsf{R}$ or $\mathcal{A}$) is timestamped with the current time t. Using this notion of time,⁴ the transcript of a protocol session is defined as follows:

Definition 2

(Protocol Transcript). The transcript of a protocol session between two parties is the timestamped sequence of messages (including both sent and received messages) viewed by a party during a run of the message transmission protocol $\mathsf{\Pi }$. If $\mathsf{\Pi }$ is n-round, then a transcript T is of the form $T=\langle (M_1, t_1), \ldots , (M_n, t_n) \rangle$, where $M_1, \ldots , M_n$ are the exchanged messages, and $t_1, \ldots , t_{n}$ are the respective timestamps.

In a protocol run $\langle \mathsf{S}(\mathsf{sendk}, m), \mathcal{A}^{\mathsf{R}(\mathsf{recvk})} \rangle$ (resp. $\langle \mathcal{A}^{\mathsf{S}(\mathsf{sendk}, \cdot )}, \mathsf{R}(\mathsf{recvk}) \rangle$) we denote by $T^{*}$ the transcript of the challenge session between $\mathsf{S}$ and $\mathcal{A}$ (resp. $\mathcal{A}$ and $\mathsf{R}$), whereas $T_1, \ldots , T_{Q}$ are the Q transcripts of the sessions established by $\mathcal{A}$ with $\mathsf{R}$ (resp. $\mathsf{S}$) via the oracle.

Definition 3

(Matching Transcripts). Let $T = \langle (M_1, t_1), \ldots , (M_n, t_n) \rangle$ and $T^{*} = \langle (M^{*}_1, t^{*}_1), \ldots , (M^{*}_n, t^{*}_n) \rangle$ be two protocol transcripts. We say that T matches $T^{*}$ ($T \subseteq T^{*}$, for short) if  $\forall i\,=\,1, \ldots , n$, $M_i = M^{*}_i$ and the two timestamp sequences are “alternating”, i.e., $t_1< t^{*}_1< t^{*}_2< t_2< t_3< \cdots< t_{n\,-\,1}< t_{n} < t^{*}_{n}$ if $\mathsf{R}$ speaks first, or $t^{*}_1< t_1< t_2< t^{*}_2< t^{*}_{3}< \cdots< t_{n\,-\,1}< t_{n} < t^{*}_{n}$ if $\mathsf{S}$ speaks first. Note that the notion of match is not commutative.

Using the above definitions, we recall the notion of ping-pong  adversary:

Definition 4

(Ping-pong Adversary). Consider a run of the protocol $\mathsf{\Pi }$ involving $\mathcal{A}$ and an honest party (it can be either $\langle \mathsf{S}(\mathsf{sendk}, m), \mathcal{A}^{\mathsf{R}(\mathsf{recvk})} \rangle$ or $\langle \mathcal{A}^{\mathsf{S}(\mathsf{sendk}, \cdot )}, \mathsf{R}(\mathsf{recvk}) \rangle$), and let $T^*$ be the transcript of the challenge session, and $T_1, \ldots , T_{Q}$ be the transcripts of all the oracle sessions established by $\mathcal{A}$. Then we say that $\mathcal{A}$ is a ping-pong  adversary if there is a transcript $T \in \{ T_1, \ldots , T_Q \}$ such that T matches $T^{*}$, i.e., $T \subseteq T^{*}$.

Now that we have introduced all the necessary definitions, we recall the two notions of interactive chosen-ciphertext PKE ($\mathsf{iCCA}$) and interactive chosen-message secure PKMA ($\mathsf{iCMA}$) that capture, respectively, confidentiality and authenticity of the messages sent by $\mathsf{S}$ to $\mathsf{R}$. Let $\mathsf{\Pi }= (\mathsf{Setup}, \mathsf{S}, \mathsf{R})$ be a message transmission protocol, and $\mathcal{A}$ be an adversary. The two notions are defined as follows by considering the experiments in Fig. 1.

Fig. 1.

Security experiments of iCCAand iCMAsecurity.

Definition 5

($\mathsf{iCCA}$ security). For any $\lambda \in \mathbb N$, we define the advantage of an adversary $\mathcal{A}$ in breaking $\mathsf{iCCA}$ security of a message transmission protocol $\mathsf{\Pi }$ as $\mathbf {Adv}^{\mathsf{iCCA}}_{\mathsf{\Pi }, \mathcal{A}}(\lambda ) = \Pr [\mathbf {Exp}^{\mathsf{iCCA}}_{\mathsf{\Pi }, \mathcal{A}}(\lambda ) = 1] - \frac{1}{2}$, and we say that $\mathsf{\Pi }$ is $\mathsf{iCCA}$-secure if for any PPT $\mathcal{A}$, $\mathbf {Adv}^{\mathsf{iCCA}}_{\mathsf{\Pi }, \mathcal{A}}(\lambda )$ is negligible.

Note that for 1-round protocols, the above notion is the same as the classical $\mathsf{IND\text{- }\!CCA}$ security.

Definition 6

($\mathsf{iCMA}$ security). For any $\lambda \in \mathbb N$, the advantage of $\mathcal{A}$ in breaking the $\mathsf{iCMA}$ security of a message transmission protocol $\mathsf{\Pi }$ is $\mathbf {Adv}^{\mathsf{iCMA}}_{\mathsf{\Pi }, \mathcal{A}}(\lambda ) = \Pr [\mathbf {Exp}^{\mathsf{iCMA}}_{\mathsf{\Pi }, \mathcal{A}}(\lambda ) = 1]$, and we say that $\mathsf{\Pi }$ is $\mathsf{iCMA}$-secure if for any PPT $\mathcal{A}$, $\mathbf {Adv}^{\mathsf{iCMA}}_{\mathsf{\Pi }, \mathcal{A}}(\lambda )$ is negligible.

Note that for 1-round protocols, the above notion is the same as the notion of strong unforgeability for digital signatures.

3 Unilaterally-Authenticated Key-Exchange

In this section we build on the notions of $\mathsf{iCCA}$/$\mathsf{iCMA}$ secure message transmission protocols recalled in the previous section in order to obtain a smoother and clean transition from encryption/authentication towards key exchange. In particular, in this work we focus on unilaterally-authenticated key-exchange (UAKE, for short). UAKE is a weaker form of mutually-authenticated key-exchange in which only one of the two protocol parties is authenticated.

Following the definitional framework of message transmission protocols [8], we define UAKE as a protocol between two parties—in this case, an un-keyed user $\mathsf{U}$ and a keyed (aka authenticated) user $\mathsf{T}$—so that, at the end of a successful protocol run, both parties (privately) output a common session key.

Formally, a UAKE protocol $\mathsf{\Pi }$ consists of algorithms $(\mathsf{KESetup}, \mathsf{U}, \mathsf{T})$ working as follows:

• $\mathsf{KESetup}(1^{\lambda })$: on input the security parameter $\lambda$, the setup algorithm generates a pair of keys $(\mathsf{uk}, \mathsf{tk})$. Implicitly, it also defines a session key space $\mathcal{K}$.

• $\mathsf{U}(\mathsf{uk})$: is a possibly interactive algorithm that takes as input the public key $\mathsf{uk}$ of the authenticated user, and outputs a session key or a symbol $\bot$.

• $\mathsf{T}(\mathsf{tk})$: is a possibly interactive algorithm that takes as input the private key $\mathsf{tk}$, and outputs a session key K or an error symbol $\bot$.

In our security definitions we explicitly include the property that $\mathsf{U}$ terminates correctly (i.e., no $\bot$ output) only if $\mathsf{U}$ gets confirmation that $\mathsf{T}$ can terminate correctly. For this reason, we assume without loss of generality that $\mathsf{T}$ always speaks last. For compact notation, we denote with $\langle \mathsf{U}(\mathsf{uk}), \mathsf{T}(\mathsf{tk}) \rangle =(\mathsf{K_{\mathsf{U}}}, \mathsf{K_{\mathsf{T}}})$ a run of the protocol in which $\mathsf{U}$ and $\mathsf{T}$ output session keys $\mathsf{K_{\mathsf{U}}}$ and $\mathsf{K_{\mathsf{T}}}$ respectively.

Definition 7

(Correctness). An unilaterally-authenticated key-exchange protocol $\mathsf{\Pi }=(\mathsf{KESetup}, \mathsf{U}, \mathsf{T})$ is correct if for all honestly generated key pairs $(\mathsf{uk}, \mathsf{tk}) {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathsf{KESetup}(1^{\lambda })$, and all session keys $\langle \mathsf{U}(\mathsf{uk}), \mathsf{T}(\mathsf{tk}) \rangle =(\mathsf{K_{\mathsf{U}}}, \mathsf{K_{\mathsf{T}}})$, we have that, when $\mathsf{K_{\mathsf{U}}}, \mathsf{K_{\mathsf{T}}}\ne \bot$, $\mathsf{K_{\mathsf{U}}}= \mathsf{K_{\mathsf{T}}}$ holds with all but negligible probability.

Security. For UAKE protocols we aim at formalizing two main security properties: authenticity and confidentiality. Intuitively, authenticity says that the only way for an adversary to make the un-keyed party terminate correctly (no $\bot$ output) is to be ping-pong. Confidentiality aims to capture that, once the un-keyed party $\mathsf{U}$ accepted, then the adversary cannot learn any information about the session key (unless it is ping-pong  up to learning the key). We formalize these two properties in a single experiment in which $\mathcal{A}$ runs a challenge session with the un-keyed party $\mathsf{U}$ while having access to the keyed party $\mathsf{T}$. As for the case for message transmission protocols, the adversary formally refers to the keyed party $\mathsf{T}$ oracle by specifying a session id $\mathsf{sid}$. For simplicity of notation, however we do not write explicitly these session identifiers.

Since in UAKE $\mathsf{T}$ speaks last, we allow the adversary to make one additional query to $\mathsf{T}$ after $\mathsf{T}$ generated the last message: in this case $\mathsf{T}$ reveals its private output $\mathsf{K_{\mathsf{T}}}$. If $\mathcal{A}$ makes such an additional query in a ping-pong session then we say that $\mathcal{A}$ is “full-ping-pong”.

Although the resulting experiment looks a bit more complex compared to the ones of $\mathsf{iCCA}$ and $\mathsf{iCMA}$ security, we stress that it can be seen as a natural combination of these two security notions. At a high level, the experiment consists in first running $(K_0, \cdot ) {\leftarrow }\langle \mathsf{U}(\mathsf{uk}), \mathcal{A}^{\mathsf{T}(\mathsf{tk})}(\mathsf{uk}) \rangle$ and then analyzing $\mathsf{U}$’s output $K_0$ ($\cdot$ means that we do not care about $\mathcal{A}$’s output at this stage). If $K_0 \ne \bot$ and $\mathcal{A}$ is not ping-pong, then $\mathcal{A}$ wins (it broke authenticity). Otherwise, we give to $\mathcal{A}$ a real-or-random key $K_b$ and $\mathcal{A}$ wins if it can tell these two cases apart without, of course, pushing the ping-pong  attack up to getting $K_0$ revealed from the oracle $\mathsf{T}$. Notice that when $K_0 = \bot$ (i.e., the honest sender did not accept in the challenge session), we also set $K_1 = \bot$. This is meant to capture that if $\mathsf{U}$ does not accept, then there is no common session key established by the two parties (essentially, no secure channel will be established). In this case the adversary will have no better chances of winning the game than guessing b.

Definition 8

(Security of UAKE). We define the advantage of an adversary $\mathcal{A}$ in breaking the security of $\mathsf{\Pi }$ as $\mathbf {Adv}^{\mathsf{UAKE\mathrm {-}Sec}}_{\mathsf{\Pi }, \mathcal{A}}(\lambda ) = \left| \Pr [\mathbf {Exp}^{\mathsf{UAKE\mathrm {-}Sec}}_{\mathsf{\Pi }, \mathcal{A}}(\lambda ) = 1] - \frac{1}{2} \right|$, and we say that a UAKE protocol $\mathsf{\Pi }$ is secure if for any PPT $\mathcal{A}$, $\mathbf {Adv}^{\mathsf{UAKE\mathrm {-}Sec}}_{\mathsf{\Pi }, \mathcal{A}}(\lambda )$ is negligible.

Multi-user Extension of Our Notion. While we defined unilaterally-authenticated key-exchange in the single-user setting, we stress that the definition easily extends to the multi-user setting. The reason is that in our notion there is only one keyed user, $\mathsf{T}$. So, when considering the multi-user setting with keyed users $\mathsf{T}_1, \ldots , \mathsf{T}_n$, we can assume that an adversary attacking a given $\mathsf{T}_j$ could simulate the keys of all remaining users $\mathsf{T}_i \ne \mathsf{T}_j$. In contrast, such an extension is not equally straightforward in MAKE, where, for example, the adversary could choose arbitrary keys for one of the two parties in the challenge session. We also refer the interested reader to [17] for a discussion on the multi-user extension of UAKE.

Single-Challenge vs. Multiple Challenges. Similarly to CCA-secure encryption and other privacy primitives, our attacker has only a single challenge session. Using a standard hybrid argument, this is asymptotically equivalent to the multi-challenge extension of our notion (with all challenge sessions sharing the same challenge bit b). We stress, however, that single-challenge does not mean single oracle access to $\mathsf{T}$. Indeed, the attacker $\mathcal{A}^{\mathsf{T}}$ can start arbitrarily many interleaved sessions with the keyed user $\mathsf{T}$, both before and after receiving the (single) challenge $K_b$. In particular, any UAKE protocol where one can recover the secret key $\mathsf{tk}$ given (multiple) oracle access to $\mathsf{T}$ will never be secure according to our definition, as then the attacker will trivially win the (single) challenge session by simulating honest $\mathsf{T}$.

Relation with Existing Definitions. As we mentioned earlier in this section, the notion of UAKE has been considered in prior work with different definitions. Notably, two recent works [12, 13, 17] use a definition (Server only Authenticated and Confidential Channel Establishment – SACCE) which formally captures whether a party accepts or not in a protocol session, and requires that the adversary $\mathcal{A}$ should not let the party accept if $\mathcal{A}$ does not correctly relay messages. If we compare our security definition of UAKE given above and the SACCE notion, we then observe the following main facts. (i) Our notion of ping-pong is stronger than the notion of matching conversations used in SACCE in that ping-pong takes into account the timing of the messages included in the transcripts. (ii) While UAKE and SACCE are very similar w.r.t. capturing the authenticity property, they instead differ w.r.t. confidentiality. In particular, our notion aims to capture indistinguishability of the keys, whereas SACCE aims to capture the security of the channel built by using the established session key. As observed in [12], the latter security notion is weaker than mere session key indistinguishability, and might thus be realized from weaker assumptions.

Finally, we formally consider the relation between our security notion of UAKE and the security notion obtained by downgrading the Bellare-Rogaway [2] definition for mutually-authenticated key exchange to the case of a single authenticated party. Although the two definitions use a slightly different formalism, below we show that the notions are essentially the same. The interested reader can see the full version of this work for the Bellare-Rogaway security definition.

The motivation of proving the equivalence to the BR model is to show that our notion does not weaken existing, well studied notions, and can in fact be used in place of them. Indeed, we believe our notion is shorter and more intuitive to work with, as we illustrate in this work. It is worth noting that this is not surprising. Overall, the one-way authenticated setting is simpler than the mutually-authenticated one as there are fewer attacks to be modeled. For example, in UAKE the security definition can involve only one long-term key, and some advanced security properties such as key-compromise impersonation no longer apply to the unilateral setting. In other words, this equivalence gives the opportunity of modeling UAKE using our definition, and perhaps using the equivalence to BR as a transition towards the more complex MAKE definition.

Theorem 1

$\mathsf{\Pi }$ is a secure UAKE protocol if and only if $\mathsf{\Pi }$ is secure in the (unilateral version of) Bellare-Rogaway model.

For lack of space the proof appears in the full version.

Uniqueness of Matching Transcript. It is interesting to note that our security definition implies that for any secure protocol there can be at most one matching transcript. This for instance means that it is hard for an adversary to force two distinct protocol sessions (in which one of the two parties is honest) to have the same session key.⁵ Bellare and Rogaway prove in [2] that such property is achieved by any protocol secure according to their (mutually-authenticated) definition. By the equivalence of our UAKE notion to BR security one might be tempted to conclude that this uniqueness property holds for UAKE-secure protocols as well. This is only partially true as the proof in [2] is done for the mutually-authenticated case, and in particular one case of the proof uses the fact mutually-authenticated (BR-secure) protocols require at least 3 rounds. Below we give a separate proof of this statement for UAKE protocols (the proof appears in the full version)

Proposition 1

Let $\mathsf{MultipleMatch}$ be the event that in a run of $\mathbf {Exp}^{\mathsf{UAKE\mathrm {-}Sec}}_{\mathsf{\Pi }, \mathcal{A}}(\lambda )$ $\mathcal{A}$ is ping-pong and there are at least two sessions i and j, with transcripts $T_i$ and $T_j$, such that both $T_i \subseteq T^{*}$ and $T_j \subseteq T^{*}$. Then if $\mathsf{\Pi }$ is a secure UAKE protocol, $\Pr [\mathsf{MultipleMatch}]$ is negligible.

4 Constructions of UAKE Protocols Based on $\mathsf{iCCA}$ and $\mathsf{iCMA}$ Security

In this section we show two realizations of unilaterally-authenticated key-exchange based on message transmission protocols. The constructions are simple and they essentially show how to obtain a clean and smooth transition from encryption/authentication towards key exchange. The first construction (described in Fig. 2) uses an $\mathsf{iCCA}$-secure protocol $\mathsf{\Pi }'$ and a pseudorandom function. Our second construction of UAKE (described in Fig. 3) uses an $\mathsf{IND\text{- }\!CPA}$-secure key encapsulation mechanism and an $\mathsf{iCMA}$-secure protocol $\mathsf{\Pi }'$.

Fig. 2.

UAKE from $\mathsf{iCCA}$-secure encryption.

Fig. 3.

UAKE from $\mathsf{iCMA}$-secure PKMA and $\mathsf{IND\text{- }\!CPA}$-secure KEM.

The security of these protocols is proven via the following theorems  (whose proofs appear in the full version):

Theorem 2

If $\mathsf{\Pi }'$ is $\mathsf{iCCA}$-secure, and F is a pseudo-random function, then the protocol $\mathsf{\Pi }$ in Fig. 2 is a secure UAKE.

Theorem 3

If $\mathsf{\Pi }'$ is $\mathsf{iCMA}$-secure, and $\mathcal{E}$ is an $\mathsf{IND\text{- }\!CPA}$-secure KEM, then the protocol $\mathsf{\Pi }$ in Fig. 3 is a secure UAKE.

On the connection to authenticators [1]. We note that, due to the similarity between $\mathsf{iCMA}$-secure message transmission and the notion of authenticators from [1], our design approach of Fig. 3 is similar to what can be obtained by applying a (unilateral) authenticator to an unauthenticated protocol, such as a one-time KEM. However, the derived protocols are not exactly the same. For example, to obtain our same protocols when using the signature-based authenticator one should slightly deviate from the approach of [1] and consider $\mathsf{ek}'$ as the nonce of the authenticator.

More conceptually, while the concrete protocols obtained are similar (but not identical), the two works use very different definitions and construction paths to arrive at these similar protocols. Our interactive PKMA notion is game-based and essentially extends the simple notion of signature schemes, whereas authenticators follow the real/ideal paradigm and also require built-in protection against replay attacks. For instance, a regular signature scheme is a 1-round $\mathsf{iCMA}$ secure message transmission, whereas it can be considered an authenticator only with certain restrictions, (as per Remark 1 in [1]).

Instantiations of our protocols. In Sect. 5.1, we discuss four efficient UAKE protocols resulting from instantiating the generic protocols in Figs. 2 and 3 with specific 1- or 2-round $\mathsf{iCCA}$- and $\mathsf{iCMA}$-secure schemes.

About freshness of session keys. It is worth noting that both above protocols have the property that the keyed party $\mathsf{T}$ generates the session key in a “fresh” way (by sampling a fresh random s in the protocol of Fig. 2, or by running $\mathsf{Encap}$ with fresh coins in the protocol of Fig. 3), even if the first part of the protocol is replayed. Such a freshness property is necessary for the security of the protocols in our model. For instance, one might consider a simpler version of the protocol of Fig. 2 in which $\mathsf{T}$ generates $\mathsf{K_{\mathsf{T}}}| c' {\leftarrow }G(r)$ using a PRG G. Such a protocol however would not be secure because of the following attack. Consider an instantiation of $\mathsf{\Pi }'$ with a non-interactive CCA encryption scheme. First the adversary plays a ping-pong attack between the challenge session and an oracle session with $\mathsf{T}$: it obtains a real-or-random key $K_{b}$. In the second part of the experiment, the adversary starts a new oracle session with $\mathsf{T}$ by sending to it the first message of the challenge session. Finally, the adversary makes a last query to $\mathsf{T}$ in this second session in order to obtain the corresponding session key. Now, observe that the session key will be the same key as the real key $K_0$ of the challenge session, and thus the adversary can trivially use it to test whether $K_b = K_0$. To see the legitimacy of the attack note that the second oracle session began after the challenge session ended, and thus it does not constitute a full ping-pong. In contrast this attack does not apply to our protocol of Fig. 2: there, even if one replays the first messages, every new session will sample a fresh session key with overwhelming probability.

5 Advanced Security Properties and Concrete Protocols

In this section, we discuss advanced properties of forward security and deniability for unilaterally-authenticated key-exchange, and then we discuss four possible concrete instantiations of our protocols given in Sect. 4. Informally, forward security guarantees that once a session is completed, the session key remains secure even if the adversary learns the long-term secret keys (in the case of UAKE, only the authenticated party $\mathsf{T}$ has a long-term secret key). Deniability is considered with respect to the keyed party $\mathsf{T}$. Informally, deniability says that the unkeyed party $\mathsf{U}$ cannot use the transcript of its conversation with $\mathsf{T}$ to convince third parties that $\mathsf{T}$ took part in that session. For lack of space, more formal definitions appear in the full version.

5.1 Concrete Protocol Instantiations

Here we discuss four efficient UAKE protocols resulting from instantiating the generic protocols in Figs. 2 and 3 with specific 1- or 2-round $\mathsf{iCCA}$- and $\mathsf{iCMA}$-secure schemes. Before proceeding to the analysis, let us briefly recall the instantiations of the $\mathsf{iCCA}$- and $\mathsf{iCMA}$-secure schemes that we consider. First, note that any $\mathsf{IND\text{- }\!CCA}$ encryption scheme is a 1-round $\mathsf{iCCA}$ protocol, and similarly any strongly unforgeable signature scheme is a 1-round $\mathsf{iCMA}$ protocol. Second, Dodis and Fiore [8] show a 2-round $\mathsf{iCCA}$-secure protocol based solely on $\mathsf{IND\text{- }\!CPA}$ security and a 2-round $\mathsf{iCMA}$-secure protocol based on $\mathsf{IND\text{- }\!CCA}$ encryption and a MAC. Briefly, the $\mathsf{iCCA}$ protocol works as follows: the receiver chooses a “fresh” public key $\mathsf{ek}$ (of a 1-bounded $\mathsf{IND\text{- }\!CCA}$ encryption) and sends this key, signed, to the sender; the sender encrypts the message using $\mathsf{ek}$. The $\mathsf{iCMA}$ protocol instead consists in the receiver sending a random MAC key r to the sender using the $\mathsf{IND\text{- }\!CCA}$ encryption, while the sender sends the message authenticated using r.

If we plug these concrete schemes in our UAKE protocols of Figs. 2 and 3, we obtain the following four UAKE instantiations that we analyze with a special focus on the properties of forward security vs. deniability:

• 1. Protocol of Fig. 2 where the $\mathsf{iCCA}$ protocol $\mathsf{\Pi }'$ is a non-interactive $\mathsf{IND\text{- }\!CCA}$ scheme: we obtain a 2-round UAKE based on $\mathsf{IND\text{- }\!CCA}$ that is (forward) passive deniable (a perfectly indistinguishable transcript for an honest $\mathsf{U}$ is easily simulatable), but it is not forwardœsecure (recovering the long-term key $\mathsf{recvk}'$ trivially allows to recover r). This protocol recover the unilateral version of SKEME [14] (without PFS).

• 2. Protocol of Fig. 2 where the $\mathsf{iCCA}$ protocol $\mathsf{\Pi }'$ is the 2-round protocol in [8] based on $\mathsf{IND\text{- }\!CPA}$ security: we obtain a 3-round UAKE based on $\mathsf{IND\text{- }\!CPA}$ security that is not deniable (as $\mathsf{T}$ signs the first message with a digital signature) but it is passive forward secure (since so is the 2-round $\mathsf{iCCA}$ protocol, as shown in [8]).

• 3. Protocol of Fig. 3 where the $\mathsf{iCMA}$ protocol $\mathsf{\Pi }'$ is a digital signature: we obtain a 2-round UAKE based on $\mathsf{IND\text{- }\!CPA}$ security that is clearly not deniable (as $\mathsf{T}$ signs c) but it can be shown passive forward-secure (as $\mathsf{dk}'$ is a short-term key which is deleted once the session is over). It is worth noting that when implementing the KEM with standard DH key-exchange ($\mathsf{ek}'=g^{x}, c=g^{y}, K=g^{xy}$) we essentially recover protocol A-DHKE-1 in [21]. A very similar protocol based on $\mathsf{IND\text{- }\!CPA}$ KEM is also recovered in the recent, independent, work of Maurer et al. [20].

• 4. Protocol of Fig. 3 where the $\mathsf{iCMA}$ protocol $\mathsf{\Pi }'$ is the 2-round PKMA proposed in [8] (called $\mathsf{\Pi }_{mac}$) which is based on $\mathsf{IND\text{- }\!CCA}$ encryption and MACs: we obtain a 2-round UAKE (as we can piggy-back the first round of $\mathsf{\Pi }_{mac}$ on the first round of the UAKE). Somewhat interestingly, this instantiation achieves the best possible properties for a 2-round protocol: it enjoys both passive forward deniability (as $\mathsf{\Pi }_{mac}$ is passive forward-deniable) and passive forward security (since $\mathsf{dk}'$ is short-term, as in the previous case). The resulting protocol is depicted in Fig. 4, and we note that it essentially recovers the unilateral version of SKEME [14]. Moreover, by using the MAC of [9] and by applying some optimizations⁶, we obtain a UAKE protocol based only on CCA security. While for practical efficiency one may use faster MACs, we show this protocol based only on CCA security mostly for elegance. The resulting protocol is depicted in Fig. 5, where we use a “labeled” CCA-secure PKE: $\mathsf{Enc}^{L}(\mathsf{ek}, m)$ denotes a run of the encryption algorithm to encrypt a message m w.r.t. label L; analogously $\mathsf{Dec}^{L}(\mathsf{dk}, c)$ denotes decryption w.r.t. label L. We recall that decryption of a ciphertext c w.r.t. L succeeds only if c was created with the same label L.

Fig. 4.

A 2-round forward-deniable and forward-secure UAKE.

Fig. 5.

A 2-round forward-deniable and forward-secure UAKE based on CCA encryption.