Privacy-Preserving Authenticated Key Exchange: Stronger Privacy and Generic Constructions

Abstract

Authenticated key-exchange (AKE) protocols are an important class of protocols that allow two parties to establish a common session key over an insecure channel such as the Internet to then protect their communication. They are widely deployed in security protocols such as TLS, IPsec and SSH. Besides the confidentiality of the communicated data, an orthogonal but increasingly important goal is the protection of the confidentiality of the identities of the involved parties (aka privacy). For instance, the Encrypted Client Hello (ECH) mechanism for TLS 1.3 has been designed for exactly this reason. Recently, a series of works (Zhao CCS’16, Arfaoui et al. PoPETS’19, Schäge et al. PKC’20) studied privacy guarantees of (existing) AKE protocols by integrating privacy into AKE models. We observe that these so called privacy-preserving AKE (PPAKE) models are typically strongly tailored to the specific setting, i.e., concrete protocols they investigate. Moreover, the privacy guarantees in these models might be too weak (or even are non-existent) when facing active adversaries.

In this work we set the goal to provide a single PPAKE model that captures privacy guarantees against different types of attacks, thereby covering previously proposed notions as well as so far not achieved privacy guarantees. In doing so, we obtain different “degrees” of privacy within a single model, which, in its strongest forms also capture privacy guarantees against powerful active adversaries. We then proceed to investigate (generic) constructions of AKE protocols that provide strong privacy guarantees in our PPAKE model. This includes classical Diffie-Hellman type protocols as well as protocols based on generic building blocks, thus covering post-quantum instantiations.

1 Introduction

Authenticated key exchange (AKE) protocols are among the most important cryptographic building blocks to enable secure communication over insecure networks. Essentially, an AKE allows two parties A and B, in possession of long term key pairs $(\textsf {pk}_A,\textsf {sk}_A)$ and $(\textsf {pk}_B,\textsf {sk}_B)$ respectively, to authenticate each other and securely establish a common session key. Security should thereby even hold in the presence of active attackers, which may intercept, read, alter, replay, or drop any message transmitted between these parties. Moreover, in state-of-the-art protocols one requires security of the session key (i.e., confidentiality) of past interactions of A and B, even if attackers are able to compromise the long term secrets $\textsf {sk}_A$ and $\textsf {sk}_B$. This is typically denoted as perfect forward secrecy (PFS). In current real world applications, such AKE protocols typically rely on the Diffie-Hellman (DH) protocol and digital signatures and are widely deployed in security protocols such as TLS, IPsec and SSH. The emerging threat of the feasibility of powerful quantum computers additionally revived the interest in AKE protocols that do not rely on DH key exchange, but instead are based generically on public key encryption (PKE) or key encapsulation mechanisms (KEMs) [16, 18, 31].

Privacy in AKE. While confidentiality of communicated data is the prime target for a security protocol, another important property is the confidentiality of the identities of the parties involved in the AKE. We will call this goal of hiding the identities from external parties privacy.¹ Schäge et al. [30] recently coined the term privacy-preserving authenticated key exchange (PPAKE) for AKE protocols with such privacy guarantees. While the study of PPAKE is an interesting subject on its own right, we currently can observe an increasing interest in such features in real world protocols. For instance, TLS 1.3 [27] aims to protect the identities of the server and client by encrypting messages as soon as possible during the authentication and in particular hiding the certificate sent by the server. Besides, many other protocols such as QUIC, IPsec IKE, SSH and certain patterns of the Noise protocol framework [26] aim to protect identity-related information such as identities, public keys or digital signatures. This is usually done by running an anonymous DH handshake where the derived keying material is then used to encrypt all subsequent messages (essentially the SIGMA-R template [21]). Moreover, the recent proposal of Encrypted Client Hello (ECH) mechanism for TLS encrypts the initial client message (the ClientHello) [28] with the aim of hiding the target domain for a given connection from attackers listening on the network. We also want to note that over the years various protocols have been designed to provide some intuitive identity protection measures, such as SKEME [20] or the SIGMA-I and SIGMA-R variants of the SIGMA protocol family [21]. The work of Schäge et al. [30], for instance, formally analyzes the privacy guarantees of SIGMA-R as used in IKEv2 within IPSec.

Relevance of PPAKE in Practice. From the above mentioned protocols that try to conceal identifying information, in particular encrypted Server Name Indication (ESNI) and its successor ECH have demonstrated its usefulness in practice. Especially when considering network censorship, ESNI/ECH can help to thwart censorship [7]. Consequently, all ESNI protected TLS connections have been blocked in China.² In general, one can observe a push towards an Internet infrastructure that reduces the amount of identifiable information. DNS over HTTPS/TLS [15, 17] for instance helps in hiding identifying information associated to a connection from an adversary listening to public network traffic.

While in the above cases typically only one party, i.e., the server, is authenticated, with the Internet-of-Things (IoT) [14, 29] or FIDO2 [3, 12] we see an adoption of mutually authenticated AKE protocols and interest towards identity privacy. For instance, Wu et al. [33] study protocols for private service discovery and private mutual authentication in both the IoT and the mobile landscape (with a case study on Apple AirDrop). Similarly, many VPN implementations also offer the ability to configure certificate-based client authentications during the initial handshake which is also the only option in WireGuard [10, 11] to establish connections.

Previous Work on PPAKE. To the best of our knowledge, the first work that specifically addresses privacy in key agreement is by Aiello et al. [1]. Informally, their privacy property wants to achieve that protocols must not reveal the identity of a participant to any unauthorized party, including an active attacker that attempts to act as the peer. They concretely propose two protocols, where one protects the identity of the initiator from an active attacker and the second one that of the responder. However, we note that this privacy property is neither modeled nor rigorously analyzed. Another informal discussion of how to achieve “identity concealment” by encrypting the identities was even earlier mentioned by Canetti and Krawczyk in [6]. Later Zhao in [34] introduced the notion of identity-concealed authenticated key exchange (CAKE), which enforces the notion of forward identity-privacy (which we simply call forward privacy) and some form of man-in-the-middle (MITM) privacy for completed sessions.

Recently, Schäge et al. [30] provided a PPAKE model, which similarly to Zhao [34] incorporates forward privacy and some form of MITM privacy for completed sessions, but considers a different setting. In their model, the identity of any two communicating parties are known (so it is visible who communicates with whom), but each party has two additional identities associated to it and it should be hard to figure out which identities the parties are using. Consequently, this model is tailored to a specific setting, e.g., where one server hosts multiple virtual machines or services and these identities need to be protected. Schäge et al. then use their model to analyze the privacy of the IKEv2 protocol [19]. Also recently Arfaoui et al. [2] investigate privacy in TLS 1.3 including session resumption. They capture a weaker notion of privacy than what is required by forward privacy, as they do not allow any corruptions. Their model also only considers uni-lateral authentication and models privacy as a separate property using the concept of a virtual identifier known from privacy analysis of RFID protocols (cf. [30] for a discussion why this is not desirable). Interestingly, none of the previously proposed formal models (including [34]) considers strong active adversaries against the privacy of the AKE protocols. To be more precise, while they actually allow active attacks, they only allow the adversaries to attack accepted sessions. And for any reasonable AKE, this essentially boils down to passive attacks (we will discuss this in more detail in Sect. 2).

Our Contribution. Subsequently, we briefly summarize our contributions:

• We revisit privacy in context of AKE and introduce a comprehensive PPAKE model building upon and extending the recent AKE model in [8]. It is more general than the recent PPAKE by Schäge et al. [30] and among variants of privacy notions known from previous works [30, 34] supports stronger notions against active adversaries.

• The main contribution of this work is that we deal with incomplete session attacks, i.e., active MITM adversaries that learn the identity of one party but are unable to then complete the protocol run. This is typically due to the inability to authenticate themselves, which is caused by a lack of secret key material. The models and protocols of Schäge et al. [30] and Zhao [34], as noted by the authors, do not prevent such attacks. In each case the adversary can create the first message(s) of either the initiator or the responder without having access to the user’s long-term secret key. This is due to the fact that the first messages only serve the purpose of exchanging ephemeral randomness, e.g., via an anonymous DH key exchange. Then the other side will authenticate itself, allowing the adversary to trivially learn the identity. We stress that this attack can be done by any MITM adversary without corrupting any user.

• We present generic constructions of PPAKE protocols with strong privacy guarantees. Our constructions rely on standard primitives such as public-key encryption or key-encapsulation mechanisms, signature schemes and unauthenticated two-move key exchange protocols. Thus, our constructions can be instantiated with post-quantum secure building blocks. In contrast, previous works exclusively focused on DH based protocols.

2 On Modeling Privacy in AKE

There are different privacy properties that are considered to be relevant, some of which that can and others that cannot be covered within PPAKE. In this section we discuss these issues, highlight aspects that have not been considered so far in PPAKE models and present a comprehensive overview of the different privacy properties and their relations.

2.1 What Can(not) Be Handled by PPAKE

Identity-related information such as client specific identifiers, public keys (certificates in particular) and digital signatures can be used by an adversary to break privacy. All these information are available on the layer of the AKE protocol, but there are clearly other network dependent information outside the AKE layer and our model, e.g., network addresses such as IP or MAC addresses, that allow adversaries to break privacy. Consequently, as discussed in [30] for PPAKE, the assumptions on the network are stronger than those required by network anonymization protocols like Tor [9]. Latter implement an overlay network and provide privacy against an adversary who controls large parts of the underlying network (i.e., the Internet) but not the complete network, as well as parts of the overlay network (e.g., Tor) itself.

PPAKE considers an adversary that is weaker and in particular assumes an active MITM attacker that controls a large, but well-defined part of the network. Consequently, one omits the consideration of network identifiers like IP or MAC addresses in PPAKE. This firstly allows to make the model simpler and independent of any network technology and topology. Secondly, as argued in [30], by using trustworthy proxies at the entry points of the adversary controlled network the usefulness of these information to an adversary can be significantly reduced. Nevertheless, we argue that even in case of absence of such proxies PPAKE still provides a meaningful countermeasure to large scale privacy attacks. In particular, it is easily possible to record identity-related information such as certificates (which can simply be parsed locally) on the AKE layer. Consequently, compared to basing the analysis on network address information, which might be additionally complicated by Network Address Translation (NAT), this is much more efficient and easily leads to a unique identification of the entities.

While it is clear that fully hiding all identity information is not possible in practice, privacy can only be lost. Consequently, guaranteeing an adequate level of privacy via PPAKE is a first step to reduce privacy risks.

2.2 Privacy Goals in PPAKE

Now we are going to discuss privacy goals relevant to PPAKE and distill a set of privacy properties from that. Unlike previous works [2, 30, 34], which basically design PPAKE models in a way that they allow to analyze a specific AKE protocol (family) such as used in TLS 1.3 or IKEv2, in this work we ask what are desirable properties and how to design PPAKE protocols providing strong privacy guarantees. In doing so we do not consider a single privacy notion (as done in previous work), but propose a set of privacy notions that allow to cover properties relevant to diverse use-cases.

Roughly, we can classify privacy attacks in either passive or active attacks and whether we either consider only completed sessions or we allow even incomplete sessions to be the target of an attack. Thereby, a passive adversary only behaves passive during the session establishment but can corrupt parties after the session-establishment. Note that for incomplete sessions, a purely passive adversary is not reasonable and is thus not considered. Active adversaries and incomplete sessions are however reasonable, i.e., actively trying to identify peers that are establishing a session which might already provide a sufficient amount of compromising information. Nevertheless, such notions have not been considered in previous models. See Table 1 for an overview.

Table 1. Type of adversary $\mathcal A$ and state of the attacked session. $(\times )$ denotes no corruption; $(\checkmark )$ denotes corruption of all but the users in the target session (i.e., the session to be attacked); $(\checkmark \checkmark )$ denotes corruption of all users. Corruption always refers to the long-term secrets.

Passive Adversaries. We start with a property that is implicitly covered by the privacy notion in previous PPAKE [30, 34]. We call it forward privacy and it can be seen as the privacy analogue of forward secrecy. Namely, it requires that for any completed session even if an adversary can later on corrupt the long term secrets of all parties, the identities of the actual parties that were involved in the session are not revealed.

For instance, the signed DH protocol does not provide any privacy, but one could imagine to add public-key encryption (PKE), i.e., party A sends $g^x$ in plain but the value $\mathsf{Sig}_{\textsf {sk}_A}(g^x\Vert id_B)$ is encrypted under the public key of B and vice versa (this pattern is similar to what is done to achieve identity protection in SKEME [20]). This will conceal the identities from any eavesdropper as long as no corruptions happen. If, however, the long-term secret keys of A and B corresponding to their PKE public keys are leaked, their identities are clearly revealed from a recorded transcript. The same holds for other protocols such as KEA or KEA+ [22] when in addition all messages are encrypted with a PKE.

Note that with such a fix (that unfortunately does not give forward privacy), the initiator, besides needing to know the responders identity, would also needs to know its public key. However, we want to stress that this is a quite reasonable assumption as in many scenarios the public keys can already be deployed on the devices or can be fetched from key repositories. Clearly, in the latter case it is not advisable to do this immediately before running the AKE as this yields another channel that leaks privacy relevant information. But in many real world settings, e.g., Encrypted Client Hello (ECH) in TLS 1.3, responder’s public keys are assumed to be fetched out-of-band.

Active Adversaries. First, we note that several works [1, 2, 21] state that active adversaries against privacy are hard to handle:

“...it is not possible for a protocol to protect both the initiator and the responder against an active attacker; one of the participants must always go first.” [1]

However, this statement seems to implicitly assume that the parties do not know public keys of the other parties beforehand or have no means to detect whether the public keys are revoked. Recent PPAKE models [30, 34] indeed achieve privacy against active adversaries, though in only a limited setting. In particular, they consider active man-in-the-middle (MITM) adversaries but restrict them to completed sessions and thus requiring the involved entities have not been corrupted, i.e., the respective long term secret keys are not compromised/revoked.

To illustrate this, we consider a template analyzed in [30] representing a variant of the SIGMA protocol family [21] covering protocols such as TLS 1.3, QUIC, IPsec IKE or SSH. In particular, the SIGMA-R protocol that is designed to provide receiver identity protection is investigated. This template uses an anonymous DH key exchange, i.e., party A sends $g^x$ for ephemeral x and party B responds with $g^y$ for ephemeral y. Subsequently, parties authenticate using digital signatures, where these authentication messages are encrypted using a symmetric key derived from the shared secret $g^{xy}$. This protocol can provide privacy against active MITM attackers, but only if the session completes (requiring that the involved entities are not corrupted). So this only can happen “after the fact”. Nevertheless, it is easy to see that for incomplete sessions there is no privacy guarantee as the initiator “goes first” and thus anyone can identify the initiator. Schäge et al. in [30] explicitly discuss this limitation of their model which allows to always reveal the server identity in TLS or QUIC or the client identity in IPsec IKE and mention that “It is therefore conceivable to formalize a stronger property for the secrecy of identities selected by the responder which does not rely on session acceptance.” Indeed, this is a setting we want to cover with our privacy notion. Consequently, we will formalize adequate properties for privacy against active adversaries even if sessions are not completed.

Fig. 1.

Overview of implications and separations between privacy notions. $\leftrightsquigarrow$ denotes two incomparable properties and EEA denotes explicit entity authentication.

Summarizing, such a stronger notion cannot work in the PPAKE model by Schäge et al. in [30]. Also the model and the protocols by Zhao [34] do not consider adversaries that do not need to know the long-term secret key to perform the attack (and thus only consider completed sessions). Note there are simple attack strategies against these protocols that do not require the attacker to obtain any long-term keys or otherwise compromise any party and can be performed by anyone. But we stress that such attacks are outside the model of [34].

Previous PPAKE models only achieve the notion of active MITM attacks against completed sessions (which implicitly covers forward privacy), but not against incomplete sessions. In order to also capture such attacks, we introduce the notion of MITM privacy in two flavors. The first and easier to achieve variant allows adversaries to also attack incomplete sessions but require that no user corruption happens. The second and stronger notion removes this requirement and also allows corruption of users (clearly with exception of the attacked ones). Looking ahead, to achieve MITM privacy requires that even in case of failure protocol messages that look like real protocol messages needs to be send. Whether this notion is meaningful consequently depends on the context of the use of the protocol and might not be meaningful if used within some higher level protocols where the required behavior cannot be realized.

In Fig. 1 we provide an overview of the privacy notions captured in this paper and how they relate to each other (cf. Sect. 3.2 for a formal treatment). We note that completed-session privacy essentially reflects the privacy notions proposed by Zhao [34] as well as Schäge et al. [30].

Initiator and Responder Privacy. Another aspect, which typically depends on the structure of the protocol as well as the application, is whether privacy only holds for either the initiator or the responder or both of them. For instance, in the most common TLS application scenario clients do not authenticate and thus, unless client authentication is used, only responder privacy is important. Schäge et al. in [30] model privacy in a way that the adversary can explicitly trigger (via a bit) whether to attack the initiator or the responder. In our model, we also consider both aspects simultaneously (which we denote as 2-way privacy), but the adversary controls whom to attack by means of how it engages with the respective oracles. We discuss how to restrict the adversary in our model to model either initiator or responder privacy in the next section.

3 Our PPAKE Model

3.1 Security Model

Our formal security model builds upon the model in [8] which we extend to cover privacy features. Like [8], our model accounts for key impersonation (KCI) security and weak forward secrecy and we use their notion of origin-oracle partnering. We note that [8] avoid no-match attacks [23] as their concrete protocol’s messages only contain group elements and deterministic functions of them. We consider the generic countermeasure from [23] by including all exchanged messages (the context) in the final key derivation.

Execution Environment. We consider $\mu$ parties $1,\ldots ,\mu$. Each party $P_i$ is represented by a set of oracles, $\{\pi ^1_{i}, \ldots , \pi ^\ell _{i} \}$, where each oracle corresponds to a session, i.e., a single execution of a protocol role, and where $\ell \in \mathbb {N}$ is the maximum number of protocol sessions per party. Each oracle $\pi ^s_{i}$ is equipped with a randomness tape $r^s_i$ containing random bits, but is otherwise deterministic. Each oracle $\pi ^s_{i}$ has access to the long-term key pair $(\textsf {sk}_i, \textsf {pk}_i)$ of party $P_i$³ and to the public keys of all other parties, and maintains a list of internal state variables that are described in the following:

• $\mathsf {Pid^s_i}$ (“peer id”) stores the identity of the intended communication partner. We assume the initiator of a protocol to know who she contacts, hence for the initiator this value is set immediately. Due to the nature of PPAKE the responder might not immediately know the identity of the initiator, hence for the responder this value is initialized to $\bot$ and only set once he receives a message containing the initiator’s identity.

• $\varPsi ^s_i\in \{ \emptyset , \mathsf {Accept}, \mathsf {Reject}\}$ indicates whether $\pi ^s_{i}$ has successfully completed the protocol execution and “accepted” the resulting key.

• $k^s_i$ stores the session key computed by $\pi ^s_{i}$

• $\mathsf {role}^s_i \in \{ \emptyset , \mathsf {Initiator}, \mathsf {Responder}\}$ indicates $\pi _{i}^{s}$’s role during the protocol execution.

For each oracle $\pi ^s_{i}$ these variables are initialized to the empty string $\emptyset$. The computed session key is assigned to the variable $k^s_i$ if and only if $\pi ^s_{i}$ reaches the $\mathsf {Accept}$ state, that is we have $k^s_i\ne \emptyset \Leftrightarrow \varPsi ^s_i= \mathsf {Accept}$. Furthermore the environment maintains three initially empty lists $\mathsf {L_{corr}}$, $\mathsf {L_{Send}}$ and $\mathsf L_\mathsf {SessKey}$ of all corrupted parties, sent messages and session keys respectively.

Partnering. We use the following partnering definitions (cf. [8]).

Definition 1 (Origin-oracle)

An oracle $\pi ^t_{j}$ is an origin-oracle for an oracle $\pi ^s_{i}$ if $\varPsi ^t_j\ne \emptyset$, $\varPsi ^s_i= \mathsf {Accept}$ and the messages sent by $\pi ^t_{j}$ equal the messages received by $\pi ^s_{i}$, i.e., if $\mathsf {sent^t_j} = \mathsf {recv^s_i}$.

Definition 2 (Partner oracles)

We say that two oracles $\pi ^s_{i}$ and $\pi ^t_{j}$ are partners if (1) each is an origin-oracle for the other; (2) each one’s identity is the other one’s peer identity, i.e., $\mathsf {Pid^s_i} = j$ and $\mathsf {Pid^t_j} = i$; and (3) they do not have the same role, i.e., $\mathsf {role}^s_i \ne \mathsf {role}^t_j$.

Oracles and Attacker Model. The adversary $\mathcal {A}$ interacts with the oracles through queries. It is assumed to have full control over the communication network, modeled by a $\mathsf {Send}(i, s, m)$ query which allows it to send arbitrary messages to any oracle. The adversary is also granted a number of additional queries that model the fact that various secrets might get lost or leaked. The queries are described in detail below.

• $\mathsf {Send}(i, s, m)$: This query allows $\mathcal {A}$ to send an arbitrary message m to oracle $\pi ^s_{i}$. The oracle will respond according to the protocol specification and its current internal state. To start a new oracle, the message m takes the form:

  • $(\texttt {START}:\mathsf {role},j):$ If $\pi ^s_{i}$ was already initialized before, return $\bot$. Otherwise this initializes $\pi ^s_{i}$ in the role $\mathsf {role}$, having party $P_j$ as its intended peer. Thus, it sets and . If $\pi ^s_{i}$ is started in the initiator role ($\mathsf {role}= \mathsf {Initiator}$), then it outputs the first message of the protocol.

  All $\mathsf {Send}(i, s, m)$ calls are recorded in the list $\mathsf {L_{Send}}$.

• $\mathsf {RevLTK}(i)$: For $i \le \mu$, this query returns the long-term private key $sk_i$ of party $P_i$. After this query, $P_i$ and all its protocol instances $\pi ^s_{i}$ (for any s) are said to be corrupted and $P_i$ is added to $\mathsf {L_{corr}}$.

• $\mathsf {RegisterLTK}(i, \textsf {pk}_i)$: For $i > \mu$, this query allows the adversary to register a new party $P_i$ with the public key $\textsf {pk}_i$. The adversary is not required to know the corresponding private key. After the query, the pair $(i, \textsf {pk}_i)$ is distributed to all other parties. Parties registered by $\mathsf {RegisterLTK}(i, \textsf {pk}_i)$ (and their protocol instances) are corrupted by definition and are added to $\mathsf {L_{corr}}$.

• $\mathsf {RevSessKey}(i, s)$: This query allows the adversary to learn the session key derived by an oracle. If $\varPsi ^s_i= \mathsf {Accept}$, return $k^s_i$. Otherwise return a random key $k^*$ and add $(\pi ^s_{i}, k^*)$ to $\mathsf L_\mathsf {SessKey}$. After this query, $\pi ^s_{i}$ is said to be revealed. If this query is called for an oracle $\pi ^s_{i}$, while there is an entry $(\pi ^t_{j}, k^*)$ in $\mathsf L_\mathsf {SessKey}$, so that $\pi ^s_{i}$ and $\pi ^t_{j}$ have matching conversations, then $k^*$ is returned.⁴

Security. Formally, we have a security game, played between an adversary $\mathcal {A}$ and a challenger $\mathcal C$, where $\mathcal {A}$ can issue the queries defined above. Additionally, it is given access to a special query $\mathsf {Test}(m)$, which, depending on a secret bit b chosen by the challenger, either returns real or random keys (for key indistinguishability) or an oracle to communicate with one of two specified parties in the sense of a left-or-right oracle for the privacy notions. The goal of the adversary is to guess the bit b. The adversary is only allowed to call $\mathsf {Test}(m)$ once and we distinguish the following two cases:

• Case $m = (\mathsf {TestKeyIndist}, i, s)$: If $\varPsi ^s_i$ $\ne$ $\mathsf {Accept}$, return $\bot$. Else, return $k_b$ where $k_0 = k^s_i$ and $k_1 {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathcal {K}$ is a random key. After this query, oracle $\pi ^s_{i}$ is said to be tested.

• Case $m = (Y, i, j)$, $Y \in \{ \mathsf {Test\text {-}w\text {-}MITMPriv}, \mathsf {Test\text {-}s\text {-}MITMPriv}, \mathsf {TestForwardPriv}, \mathsf {TestCompletedSessionPriv} \}, i,j\le \mu$: Create a new Party $P_{i|j}$ with identifier i|j. This party has all properties of $P_i$ (if $b=0$) or $P_j$ (if $b=1$), but no active sessions. The public key of $P_{i|j}$ is not announced to the adversary and the query $\mathsf {RevLTK}(i|j)$ always returns $\bot$. Furthermore create exactly one session $\pi ^1_{i|j}$. Return the new handle i|j.

One-Way Privacy. The second case in $\mathsf {Test}(m)$ above models two-way privacy, i.e., we are considering that privacy needs to hold for the initiator and the responder. In case of one-way privacy, i.e., the privacy only holds either for the initiator or the responder (depending on the protocol), we need to restrict the adversary in a way such that the first message sent to $\pi ^1_{i|j}$ via $\mathsf {Send}(i|j, 1, m)$ must be a $\texttt {START}$ command. Analogously, we can model scenarios where we only consider privacy of the responder involved in a session.

Security Experiment. The experiment $\mathsf {Exp}^{\mathsf {\text {X}}}_{\text {PPAKE},\mathcal {A}}$ is defined as follows.

• 1. Let $\mu$ be the number of parties in the game and $\ell$ the number of sessions per user. $\mathcal {C}$ begins by drawing a random bit $b {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\{0,1\}$ and generating key pairs $\{(\textsf {sk}_i, \textsf {pk}_i) \,|\, 1 \le i \le \mu \}$ as well as oracles $\{ \pi ^s_{i} \,|\, 1 \le i \le \mu , 1 \le s \le \ell \}$.

• 2. $\mathcal {C}$ now runs $\mathcal {A}$, providing all the public keys as input. During its execution, $\mathcal {A}$ may adaptively issue $\mathsf {Send}(i, s, m)$, $\mathsf {RevLTK}(i)$, $\mathsf {RevSessKey}(i, s)$ and $\mathsf {RegisterLTK}(i, \textsf {pk}_i)$ queries any number of times and the $\mathsf {Test}(m)$ query once.

• 3. Depending on what argument Y the $\mathsf {Test}(m)$ oracle was called with, we require the corresponding property below to hold through the entire game.

  • (a) $\mathsf {TestKeyIndist}$: The tested oracle remains fresh (cf. Definition 3).

  • (b) $\mathsf {Test\text {-}w\text {-}MITMPriv}$: No oracle is ever corrupted.

  • (c) $\mathsf {Test\text {-}s\text {-}MITMPriv}$: $P_i$ and $P_j$ are never corrupted. Furthermore we require that $\mathsf {Pid^1_{i|j}} = \bot$ or $\mathsf {Pid^1_{i|j}} = k$ for some k, while $P_k$ is never corrupted.

  • (d) $\mathsf {TestForwardPriv}$: The returned oracle $\pi ^1_{i|j}$ has a partner oracle $\pi ^r_{k}$ at the end of the game. Furthermore no oracle besides $\pi ^r_{k}$ may be instructed to start a protocol run with intended partner $P_{i|j}$.

  • (e) $\mathsf {TestCompletedSessionPriv}$: The returned oracle $\pi _{i|j}^1$’s state is $\mathsf {Accept}$ at the end of the game. Let $k = \mathsf {Pid^1_{i|j}}$. $P_k$ are not corrupted, $\mathsf {RevSessKey}(i|j, 1)$ was never queried and $\mathsf {RevSessKey}(k, r)$ (for any $\pi ^r_{k}$ that has matching conversations) was never queried.

    Furthermore no oracle besides $\pi ^r_{k}$ may be instructed to start a protocol run with intended partner $P_{i|j}$.

• 4. The game ends when $\mathcal {A}$ terminates with output $b'$, representing the guess of the secret bit b. If $b' = b$, output 1. Otherwise output 0.

Definition 3 (Freshness)

An oracle $\pi ^s_{i}$ is fresh if

• 1. $\mathsf {RevSessKey}(i, s)$ has not been issued

• 2. no query $\mathsf {RevSessKey}(j, t)$ has been issued, where $\pi ^t_{j}$ is a partner of $\pi ^s_{i}$.

• 3. $\mathsf {Pid^s_i}$ was:

  • (a) not corrupted before $\pi ^s_{i}$ accepted if $\pi ^s_{i}$ has an origin-oracle, and

  • (b) not corrupted at all if $\pi ^s_{i}$ has no origin-oracle.

PPAKE Security. The above model can be parameterized by allowing or prohibiting the different types of $\mathsf {Test}(m)$ queries. This leads to the following:

Definition 4

A key-exchange protocol $\varGamma$ is called X for if for any PPT adversary $\mathcal {A}$ with access to the oracle $\mathsf {Test}(m)$ with queries of the form defined below, the advantage function

is negligible in , where

• $\mathcal {A}$ queries $\mathsf {TestKeyIndist}$: X = secure.

• $\mathcal {A}$ queries $\mathsf {Test\text {-}w\text {-}MITMPriv}$: X = 2-way MITM private.

• $\mathcal {A}$ queries $\mathsf {Test\text {-}s\text {-}MITMPriv}$: X = strongly 2-way MITM private.

• $\mathcal {A}$ queries $\mathsf {TestForwardPriv}$: X = forward private.

• $\mathcal {A}$ queries $\mathsf {TestCompletedSessionPriv}$: X = completed-session private.

In the above definition, secure corresponds to having indistinguishable session keys, weak forward secrecy and security against key compromise impersonation (KCI). We now show how to integrate explicit entity authentication in our model, which allows to simplify the proofs of the protocols in Sect. 4. Therefore, we require the following:

Definition 5 (Matching Conversation)

Let $\varPi$ be an N-message two-party protocol in which all messages are sent sequentially.

• If a session oracle $\pi ^s_{i}$ sent the last message of the protocol, then $\pi ^t_{j}$ is said to have matching conversations to $\pi ^s_{i}$ if the first $N-1$ messages of $\pi _{i}^s$’s transcript agrees with the first $N-1$ messages of $\pi _{j}^t$’s transcript.

• If a session oracle $\pi ^s_{i}$ received the last message of the protocol, then $\pi ^t_{j}$ is said to have matching conversations to $\pi ^s_{i}$ if all N messages of $\pi _{i}^s$’s transcript agrees with $\pi _{j}^t$’s transcript.

We define implicit authentication through the fact that even a MITM adversary would not be able to derive the session key. This can be done in two moves. Explicit authentication is characterized by the fact that, additionally to providing implicit authentication, the protocol fails if a party does not possess a valid secret key, i.e., an active MITM adversary.

Definition 6 (Explicit entity authentication)

On game $\mathsf {PPAKE^{2\text {-}way\text {-}priv}_\mathcal {A}}$ define $\mathsf {break_{EA}}$ to be the event that there exists an oracle $\pi ^s_{i}$ for which all the following conditions are satisfied.

• 1. $\pi ^s_{i}$ has accepted, that is, $\varPsi ^s_i= \mathsf {Accept}$.

• 2. $\mathsf {Pid^s_i} = j$ and party j is not corrupted.

• 3. There is no oracle $\pi ^t_{j}$ having:

  • 1. matching conversations to $\pi ^s_{i}$ and

  • 2. $\mathsf {Pid^t_j} = i$ and

  • 3. $\mathsf {role}^t_j \ne \mathsf {role}^s_i$

Definition 7

A key-exchange protocol $\varGamma$ has explicit authentication, if, for any PPT adversary $\mathcal {A}$, the event $\mathsf {break_{EA}}$ (see Definition 6) occurs with at most probability.

3.2 Relation Between Privacy Notions

Subsequently, we investigate the relations between the different privacy notions (as informally shown in Fig. 1).

Lemma 1

Strong 2-way MITM privacy is strictly stronger than (weak) 2-way MITM privacy.

Proof

This immediately follows from the tighter restrictions put on the attacker in the (weak) 2-way MITM privacy test. Furthermore, there are protocols that are (weak) 2-way MITM anonymous but not strongly 2-way MITM anonymous (see, e.g., $\varPi _\mathsf { {ss} }$ in Protocol 1).   $\square$

Lemma 2

The 2-way MITM privacy notions are independent of forward privacy.

Proof

Note that the privacy notions do not allow corruptions of the test oracle and forward privacy does not allow the attacker modify any sent messages (i.e. does not allow the attack to act as an active MITM). $\varPi _\mathsf { {PKE} } ^2$ (see Protocol 3) for instance is strongly 2-way MITM private (see Theorem 4) and hence also (weakly) 2-way MITM private, but it is not forward private as the identities are only encrypted using long term keys. On the other hand a protocol that runs the classic Diffie-Helman key exchange followed by transmitting their identities symmetrically encrypted would reach forward privacy, but no 2-way MITM privacy, as any MITM adversary could simply run the protocol.   $\square$

Completed-session privacy is implied by the other privacy notions: if a protocol is strong MITM private or has explicit authentication and is forward private, then it also provides completed session-privacy. The following lemma shows the implication starting from strong MITM privacy.

Lemma 3

Let $\varGamma$ be a PPAKE protocol. If $\varGamma$ is strong MITM private, then it is completed-session private.

Proof

Strong 2-way MITM privacy test puts less restrictions on the attacker.   $\square$

Finally, the following Theorem covers completed-session privacy from explicit authentication and forward privacy.

Theorem 1

Let $\varGamma$ be a PPAKE protocol. If $\varGamma$ has explicit authentication and is forward private, then it is completed-session private.

Proof

Assume for contradiction that some $\varGamma$ has explicit authentication and is forward private, but is not completed-session private. This means a PPT-adversary $\mathcal {A}$ is able to call $\mathsf {TestCompletedSessionPriv}$ and not violate the imposed restrictions, while also correctly guessing the challenge bit b with non-negligible probability. Since $\varGamma$ is forward private, the adversary violates a necessary restriction for calling $\mathsf {TestForwardPriv}$ while correctly guessing the challenge bit b. (Note that otherwise the exact same adversary $\mathcal {A}$ breaks forward privacy by simply using the argument $\mathsf {TestForwardPriv}$ instead).

It follows that after $\mathcal {A}$ is done, $\pi ^1_{i|j}$ does not have a partner oracle with non-negligible probability. As per requirement of winning $\mathsf {TestCompletedSessionPriv}$, there is the oracle $\pi ^1_{i|j}$ which has accepted and party $P_k$, where $k = \mathsf {Pid^1_{i|j}}$, is not corrupted. Due to $\varGamma$ providing explicit authentication, there is an oracle $\pi ^r_{k}$ s.t. $\pi ^r_{k}$ has matching conversations to $\pi ^1_{i|j}$, $\mathsf {Pid^r_k} = i|j$ and $\mathsf {role}^r_k \ne \mathsf {role}^{1}_{i|j}$ (see Definition 6 detailing explicit entity authentication). Then $\mathcal {A}$ could simply not drop the last message (if it did before) thereby making $\pi ^1_{i|j}$ and $\pi ^r_{k}$ have matching conversations to each other. This also makes $\pi ^1_{i|j}$ and $\pi ^r_{k}$ be partnered to each other, without making it less likely for $\mathcal {A}$ to correctly guess the challenge bit b. Hence $\mathcal {A}$ is able to break forward privacy, which is a contradiction.   $\square$

3.3 Discussion and Limitations of Our PPAKE Model

Completed Session Privacy. $\mathsf {TestCompletedSessionPriv}$ is intended to represent the privacy notions of the literature, specifically Schäge et al. [30] and Zhao [34]. The only addition we made is the requirement that “no oracle besides $\pi ^r_{k}$ may be instructed to start a protocol run with intended partner $P_{i|j}$”. This is a necessary addition since due to the nature of our model there are otherwise trivial attacks against a large class of protocols: First of all the adversary makes the test oracle complete its session without interfering and hence fulfills the experiment’s requirements. It then corrupts both of the test oracle’s possible identities. Finally it instructs a new oracle to initiate the protocol with the test oracle being the intended recipient, but answers all messages itself using the information obtained with the corruptions. If the imitator at any point uses the intended recipient’s public key, e.g. for PKE, then the adversary learns the test oracle’s identity.

This problem does not exist in the model of [30], since they let each initiator determine the identity of the test oracle (if configured correspondingly), instead of having the identity of the test oracle fixed throughout the entire experiment. We note that while [30] always model two identities per party, in our model every party only has a single identity.⁵

Revocation. In our model, corruptions are immediately publicly known. While this is an idealization, defending against secret corruptions is infeasible, since an adversary could perfectly impersonate the corrupted user.

As typically done in AKE, we do not formally cover revocation of long term keys in our model. There is previous work that explicitly models revocation for AKE protocols [5], but we want to avoid this added complexity since at this point we are not interested in the specifics of the respective revocation mechanism. Nevertheless, we note that for any revocation mechanism, the revocation status of a communication partner can only be checked after they revealed their identity. For this reason, we model strong MITM privacy so that the adversary can corrupt users as long as it does not openly identify itself as that user.

MITM Cross Tunnel Attack. We now discuss a generic MITM attack on privacy that does not require the corruption of any party, dubbed MITM cross tunnel attack. The goal of the attack is to de-anonymize a party that acts as a responder in the protocol. Specifically, the attack targets MITM privacy (both weak and strong). Let the responder be called $P_{i|j}$ and $\pi ^1_{i|j}$ its corresponding session. Assume $\pi ^r_{k}$ is trying to communicate with $\pi ^1_{i|j}$, but the adversary is a MITM in that communication channel. Assume at the same time, the adversary is MITM on another channel, where it knows that some $\pi ^z_{y}$ is trying to communicate with $\pi ^s_{i}$. The adversary now relays all messages of $\pi ^z_{y}$ (of the second channel) to $\pi ^1_{i|j}$ (of the first channel) and vice versa. Clearly, if either party produces an error or otherwise noticeably changes its behavior (e.g. by initiating the protocol again), then the adversary knows that $\pi ^1_{i|j}$ cannot be the intended partner of $\pi ^z_{y}$. Therefore $P_{i|j}$ must be $P_{j}$.

Defining protocols such that the parties – from an eavesdropper’s view – do not behave noticeably different on errors (e.g. a party cannot decrypt a received ciphertext) prevents this attack as well as trivial distinguishers in case a party is revoked. Specifically, protocols need to continue similar to a normal execution, but with randomly sampled messages and the sessions are internally marked as invalid. Our protocols in Sect. 4 are designed to counter these attacks. As noted before, fully preventing this attack in practice is only possible if higher level protocols do not reveal the session status, e.g. by restarting the AKE protocol.

4 Constructing PPAKE with Strong Privacy

In this section we discuss generic construction methodologies to achieve weak and strong MITM privacy, respectively. While not made explicit, all protocols are assumed to behave indistinguishable to real executions (from an eavesdropper’s view) even if some verification (indicated using boxes) fails, i.e., either a random bitstring or encryption of a random message is returned. Also, we assume that communication partners check the revocation status of the respective peers prior to engaging in a session initiation. All used encryption schemes are required to be length-hiding (cf. [32]), which we make explicit in the theorems.

User Certification and PKIs. In our protocols $\mathsf {Cert} _A$ indicates a certificate that binds the identity of A to the long term public key(s). We assume all users have their keys certified by some certification authority (CA) and that there is a mechanism in place for checking the revocation status of certificates. All these features are typically realized via a public-key infrastructure (PKI), i.e., PKIX. As already mentioned, we do not make such a mechanism explicit in our model.

4.1 Achieving Weak MITM Private PPAKE Using Shared Secrets

For the first protocol, we assume all honest parties belong to the same group and have a shared secret s only known to the members of the group. In terms of our model, the shared secret s is part of the secret keys and can hence be compromised by corrupting any party. With this shared secret, we can preserve anonymity against an active MITM adversary, that does not have access to s. But compromise of s does not endanger the usual key indistinguishability. The idea is to derive all session keys by additionally including this shared secret. So, even an active MITM attacker will be unable to use its knowledge of its share of the ephemeral keys due to the lack of knowledge of s. The scheme extending anonymous Diffie-Hellman with a shared secret and encrypted transfer of the peer’s certificates is presented in Protocol 1. Similar to the protocols we discuss later, this protocol can also be rewritten in terms of any unauthenticated KE replacing the ephemeral DH shares and a signature scheme replacing the long term keys. We can show the following:

Theorem 2

If the Oracle Diffie-Hellman (ODH) assumption holds and symmetric encryption scheme $\varOmega$ is SE-LH-IND-CCA-secure, then $\varPi _\mathsf { {ss} }$ in Protocol 1 provides explicit entity authentication, is secure, weakly 2-way MITM private and forward private.

For the proof we refer to the full version. Similar to the protocols from Wu et al. [33], the protocol in Protocol 1 is useful for managed groups. While their approach based on prefix encryption (PE) built from identity-based encryption (IBE) is more expressive, only their second protocol is able to provide weak MITM privacy. Our protocol highlights that weak MITM privacy can be obtained using less heavy tools than IBE. Note that Wu et al. [33] also require a trusted party (e.g., the CA) to generate and hand out secret keys to users. So this can be regarded as being similar to having a shared secret as in our approach.

4.2 Generic Construction of Strongly MITM Private PPAKE

Next, we introduce a protocol that achieves MITM privacy, in this case even strong MITM privacy, without relying on a shared secret. For this protocol and the protocol in Sect. 4.3, we consider a setting where the public keys (certificates) of responders are known a priori. Therefore, the initiator has all the information including all public keys of the responder available. Note however, that the first message cannot contain the initiator’s certificate. Otherwise, if the long-term key of the responder is compromised, privacy of the initiator cannot be guaranteed (a trade-off that we make in Sect. 4.3). So, authentication of the initiator can only be performed after establishing an initial session key.

Similar to $\varPi _\mathsf { {ss} }$ we run a two-move KE and let the initiator sample a nonce which takes over the role of the shared secret of $\varPi _\mathsf { {ss} }$, i.e., the (temporary) session keys are derived from the nonces and the result of the two-move KE. However, we now encrypt the nonce under the receivers public key. Moreover, after the initial shared key has been computed, the initiator is able to send its certificate to the responder and authenticate itself using a signature (which is encrypted together with the senders certificate). The protocol is depicted in Protocol 2.

We note that due to active attacks the PKE is required to provide key-privacy, i.e., be PKE-IK-CCA-secure. Otherwise, an active attacker may determine the senders identity purely by means of the PKE ciphertext. This additional requirement on the PKE is fulfilled by many natural schemes (cf. [4, 25]). Moreover, to obtain forward privacy the PKE ciphertext needs to be encrypted using the key from the anonymous two-move KE.⁶

Theorem 3

If KE $\varGamma$ is unauthenticated and secure, the PKE $\mathsf {PKE}$ is PKE-IND-CCA- and PKE-IK-CCA-secure, symmetric encryption scheme $\varOmega$ is SE-LH-IND-CCA-secure, and the signature scheme $\varSigma$ is EUF-CMA-secure, then $\varPi _\mathsf { {PKE} } ^4$ provides explicit entity authentication, is secure, strongly MITM private and forward private.

For the proof we refer to the full version.

4.3 Two-Move PPAKE Protocol Without Forward Privacy

Finally, let us now present a two move variant of $\varPi _\mathsf { {PKE} } ^4$. Here, the initiator already includes the certificate in the first message and thus allows the responder to respond with a message encrypted with respect to the initiators public key and thus the protocol is authenticated after two moves. The resulting protocol, $\varPi _\mathsf { {PKE} } ^2$, is depicted in Protocol 3 and achieves strong MITM privacy, but obviously forward privacy can not be satisfied by this construction. In comparison to $\varPi _\mathsf { {PKE} } ^4$, the construction also requires the PKE to be length-hiding. Note though, when using anonymous DH as in $\varPi _{ss}$ one can avoid the signatures.

Theorem 4

If KE $\varGamma$ is secure, the PKE $\mathsf {PKE}$ is length-hiding, PKE-IND-CCA- and PKE-IK-CCA-secure, and the signature scheme $\varSigma$ is EUF-CMA-secure, then $\varPi _\mathsf { {PKE} } ^2$ provides explicit entity authentication, is secure, strongly MITM private and completed-session private.

Table 2. Comparison of our protocols. “$\mathsf ss$” denotes the requirement of a shared secret and “$\textsf {pk}$” the requirement to know the public key of the intended responder upfront.

For the proof we refer to the full version.

5 Discussion and Future Work

In Table 2, we present an overview of the protocols presented in Sect. 4. All protocols provide completed-session privacy as well as weak MITM privacy, but for forward privacy and strong MITM privacy the picture looks different. Due the use of shared secret in $\varPi _\mathsf { {ss} }$, strong MITM privacy does not hold. Yet this approach can be viewed as mitigation strategy for existing protocols to at least guarantee weak MITM privacy guarantees (e.g., for the IoT setting as targeted in [33]). For the PKE-based approach $\varPi _\mathsf { {PKE} } ^4$ we require more than two moves to achieve forward privacy, but all other notions can already be achieved with the two move protocol $\varPi _\mathsf { {PKE} } ^2$.

Our motivation in this work was primarily to investigate the space of meaningful privacy notions and whether there are protocols that satisfy strong notions of privacy. An interesting question is the efficiency and privacy trade-off of concretely instantiated protocols as well as a strengthening of the model to support session state reveal queries. Currently only trivial ones would be supported and thus we decided to omit this feature. Another interesting direction, as done for IKE v2 in [30], is to study which privacy properties deployed AKE protocols satisfy or how they can be modified in a way that they provide strong privacy guarantees.