Symmetric-Key Authenticated Key Exchange (SAKE) with Perfect Forward Secrecy

Abstract

Key exchange protocols in the asymmetric-key setting are known to provide stronger security properties than protocols in symmetric-key cryptography. In particular, they can provide perfect forward secrecy, as illustrated by key exchange protocols based on the Diffie-Hellman scheme. However public-key algorithms are too heavy for low-resource devices, which can then not benefit from forward secrecy. In this paper, we describe a scheme that solves this issue. Using a shrewd resynchronisation technique, we propose an authenticated key exchange protocol in the symmetric-key setting that guarantees perfect forward secrecy. We prove that the protocol is sound, and provide a formal proof of its security.

1 Introduction

An authenticated key exchange (AKE) protocol executed between two parties aims at authenticating the parties, and computing a fresh shared session key. Well-known two-party authenticated key exchange protocols make use of digital signatures to provide authentication, and apply the Diffie-Hellman (DH) scheme [20] to compute a shared session key. However, such protocols are too heavy for low-resource devices. More suited protocols, solely based on symmetric-key functions, have been proposed (e.g., [12, 16, 23, 26, 29, 30, 33, 34] to cite a few), including widely deployed ones (e.g., in 3G/UMTS [2] and 4G/LTE [3]). Such symmetric-key protocols are needed in various applications, ranging from Wireless Sensor Networks (WSNs), Radio Frequency Identification (RFID) tags, smart cards, Controller Area Networks (CANs) for vehicular systems, smart home, up to industrial Internet of Things (IoT). Yet, existing symmetric-key based protocols lack a fundamental security property usually provided by the DH scheme: perfect forward secrecy (PFS) [21, 24]. PFS is a very strong form of long-term security which, informally, guarantees that future disclosures of some long-term secret keys do not compromise past session keys. It is widely accepted that PFS can only be provided by asymmetric schemes. Indeed, in protocols based on symmetric-key functions, the two parties must share a long-term symmetric key (which the session keys are computed from). Therefore the disclosure of this static long-term key allows an adversary to compute all the past (and future) session keys. In this paper, we introduce an AKE protocol in the symmetric-key setting, and, yet, that does guarantee PFS.

1.1 Related Work

Symmetric-key based protocols do not provide the same security guarantees as those based on asymmetric algorithms. In particular, they do not guarantee forward secrecy. Nonetheless, (a few) attempts aim at proposing symmetric-key protocols that incorporate forward secrecy, as illustrated by the following related work.

Dousti and Jalili [22] describe a key exchange protocol where the shared master key is updated based on time. Their protocol requires perfect synchronicity between the parties otherwise this leads to two main consequences. Firstly, in order to handle the key exchange messages, the parties may use different values of the master key corresponding to consecutive epochs, which causes the session to abort. Secondly, this allows an adversary to trivially break forward secrecy. Once a party deems the protocol run is correct and the session key can be safely used (i.e., once the party “accepts”), the adversary corrupts its partner (which still owns the previous, not updated yet, master key), and computes the current session key. Furthermore, achieving perfect time synchronisation may be quite complex in any context, in particular for low-resource devices. Contrary to Dousti et al., the protocol we propose explicitly deals with the issue of updating the master keys at both parties without requiring any additional functionality (such as a synchronised clock).

In the RFID field, the protocol proposed by Le, Burmester, and de Medeiros [28] aims at authenticating a tag to a server, and at computing a session key in order to establish a secure channel (which they do not describe). The master key is updated throughout the protocol run. To deal with the possible desynchronisation between the reader and the tag, the server keeps two consecutive values of the key: the current and the previous one. If the tag does not update its master key (which happens when the last message is dropped), the server is able to catch up during the next session. This implies that, in case of desynchronisation, the server computes the session key from the updated master key, whereas the tag still stores the previous value. Hence, an adversary that corrupts the tag can compute the previous session key with respect to the server. In fact, since the server always keeps the previous value of the master key, together with the current one, the scheme is intrinsically insecure in strong security models (i.e., models that allow the adversary to corrupt any of the partners, once the targeted party accepts). Yet, Le et al. analyse their protocol in a model where any server corruption is forbidden, and corrupting a tag is allowed only once it accepts. In our scheme, one of the parties also keeps in memory (a few) samples of a master key corresponding to different epochs (including a previous one). Yet the disclosure of all these values does not compromise past session keys. Furthermore, the (strong) security model we use allows the adversary to corrupt either partner as soon as the targeted party accepts.

Brier and Peyrin [17] propose a forward secret key derivation scheme in a client-server setting, that aims at improving a previous proposal [7]. In addition to forward secrecy, another constraint is that the amount of calculation to compute the master key (directly used as encryption key) on the server side must be low. Their solution implies the storage, on the client side, of several keys in parallel and to use a (short) counter, which is involved in the keys update. The keys belong to a tree whose each leaf (key) is derived from the previous one and the counter. The client must send the counter with the encrypted message for the server to be able to compute the corresponding key. The main drawback of this scheme is that the number of possible encryption keys is reduced. Increasing that limit implies increasing the counter size and the number of keys stored in parallel on the client side. Moreover, Brier et al. (as well as [7]) focus on forward secrecy with respect to the client only. The server is deemed as incorruptible, and is supposed to compute an encryption key only upon reception of a client’s message (the secure channel is unidirectional, and the server does not need to send encrypted messages to the client). Therefore, the scheme does not need to deal with the issue of both parties being in sync (with respect to the key computation), and providing forward secrecy. In addition, the purpose of Brier et al. (as well as [7]) is not to provide mutual authentication. More generally sending additional information in order to resynchronise (such as a sufficiently large counter) is a simple (and inefficient) way to build a forward secret protocol. But this yields several drawbacks. Firstly, the size of such a counter must be large enough in order to avoid any exhaustion. Secondly, sending the counter (at least periodically) is necessary for the two parties to resynchronise, which consumes bandwidth. Thirdly, resynchronisation may imply multiple updates of the master keys at once (the scheme of Brier et al. and [7] aims at limiting that amount of calculation, but it leads to a narrowed number of possible encryption keys). Our scheme avoids all these drawbacks.

The more general question of forward security in symmetric cryptography has been also investigated by Bellare and Yee [14]. They propose formal definitions and practical constructions of forward secure primitives (e.g., MAC, symmetric encryption algorithm). Their constructions protect against decryption of past messages, or antedated forgeries of messages (i.e., previously authenticated messages are made untrustworthy). Their algorithms are based on key-evolving schemes [10]. Nonetheless, Bellare et al. consider only algorithms (but not protocols) and they do not deal with the issue of synchronising the evolution of the shared key at both parties. That is, they propose out-of-context (non-interactive) solutions with respect to our purpose.

Abdalla and Bellare [4] investigate a related question which is “re-keying”. Their formal analysis show that appropriate re-keying techniques “increase” the lifetime of a key. They consider re-keying in the context of symmetric encryption (in order to thwart attacks based on the ability to get lots of encrypted messages under the same key), and forward security (in order to protect past keys). Yet, they confine their analysis to algorithms and not protocols. Hence, as Bellare et al. [14], they do not treat the synchronisation issues that arise from evolving a shared symmetric key.

The Signal messaging protocol [1] uses a key derivation scheme called “double ratchet algorithm” [31]. This scheme combines a DH based mechanism with a symmetric key-evolving mechanism (based on a one-way function). The first mechanism provides an asymmetric ratchet, whereas the second provides a symmetric ratchet. The asymmetric ratchet is applied when a fresh DH share is received (included in an application message) from the peer. The symmetric ratchet is applied when a party wants to send several successive messages without new incoming message from its partner. Thanks to the DH scheme, the asymmetric ratchet is supposed to provide forward secrecy.¹ Regarding the symmetric ratchet, each party is compelled to store the decryption keys of the not yet received messages. This is due to the asynchronous nature of the Signal protocol. Therefore, the symmetric ratchet in Signal does not provide forward secrecy, as stated in their security analysis by Cohn-Gordon, Cremers, Dowling, Garratt, and Stebila [19]: “old but unused receiving keys are stored at the peer for an implementation dependent length of time, trading off forward security for transparent handling of outdated messages. This of course weakens the forward secrecy of the keys”. Consequently, Cohn-Gordon et al. choose not to model this weakened property. In turn, Alwen, Coretti, and Dodis [6] incorporate the latter in the security analysis of their “generalised Signal protocol”. But the crucial difference in their notion of forward security is that, as soon as the receiver is compromised, no more security can be provided. On the contrary, we tackle the synchronisation issue, and solve it in our protocol. The security model we use captures forward secrecy and allows corrupting a party and its partner as soon as the targeted party “accepts” (i.e., deems the session key can be safely used). With regard to Signal, our protocol can be compared to the asymmetric ratchet (in synchronous mode), and yet does not implement asymmetric functions.

We stress that the goals of several of the aforementioned protocols are not the same as ours. Nonetheless, the small number of existing symmetric-key protocols that provide forward secrecy, and the lukewarm security level they achieve illustrate that combining symmetric-key cryptography and (a strong form of) forward secrecy is a non-trivial task.

1.2 Contributions

We describe the SAKE protocol, a two-party authenticated key exchange protocol in the symmetric-key setting with the following characteristics.

• It guarantees forward secrecy.

• It is self-synchronising. That is, after a correct and complete session (and whatever the internal state of the parties prior to the session), the two parties involved in the protocol run share a new session key, and their internal state is updated and synchronised.

• It allows establishing an (virtually) unlimited number of sessions (as opposite to symmetric-key protocols that make use of a predefined list of master keys, each being used once only).

• The amount of calculation done by both parties in a single protocol run is strictly bounded. In particular we avoid the need of sending additional information in order to resynchronise, such as a (sufficiently large) counter that keeps track of the evolution of the master keys, and the subsequent drawbacks: periodically doing a great amount of computations at once (when resynchronisation is necessary), and consuming bandwidth (to transmit the additional data).

In addition, we provide a formal security proof for SAKE. We also present a complementary mode of SAKE (that we call SAKE-AM) which is an “aggressive mode” of the protocol. This mode inverts the role of the initiator and the responder in terms of calculations (in SAKE, the initiator performs – at most – two additional MAC computations compared to the responder). Using SAKE and SAKE-AM together results in an implementation (gathering all the aforementioned properties, starting with the forward secrecy property) that allows any party to be either initiator or responder of a session, and such that the smallest amount of calculation is always done by the same party. This is particularly convenient in the context of a set of (low-resource) end-devices communicating with a central server. In such a case, the end-device supports the smallest amount of calculation, whereas either the server or the end-device can initiate a session.

1.3 Our Approach

Key Concepts. The authenticated key exchange protocol we propose is solely based on symmetric-key functions. Not only does it provide mutual authentication and key agreement, but it guarantees perfect forward secrecy. We attain this very strong form of long-term security by using a key-evolving scheme. As soon as two parties make a shared (symmetric) key evolve, a synchronisation problem arises. We provide a simple and efficient solution to this issue. We require using neither a clock, nor an additional resynchronising procedure. Our solution is based on a second (independent) chain of master keys. These keys allow tracking the evolution of the internal state, and resynchronising the parties if necessary. The parties authenticate each other prior to updating their master keys. Hence the possible gap is bounded (as we prove it), and each party is always able to catch up in case of desynchronisation (of course, if the session is correct and complete). Mutual authentication, key exchange (with forward secrecy), and resynchronisation are done in the continuity of the protocol run.

Our protocol is based on two symmetric master keys: a derivation master key K and an authentication master key $K'$. The protocol makes use of symmetric-key functions only. Each pair of parties ($A$, $B$) shares distinct master keys. The main lines of the protocol are as follows. The two parties exchange pseudo-random values $r_A$, $r_B$ which are used to

• authenticate each other: each party sends back the value it has received in a message that is MAC-ed with the authentication master key $K'$. For instance, if $B$ receives $r_A$ it replies with $r_B\Vert \tau _B$ where $\tau _B = \mathsf {Mac}(K', B\Vert A\Vert r_B\Vert r_A)$.

• Compute a session key: a pseudo-random function $\mathsf {KDF}$ is keyed with the derivation master key K and uses the pseudo-random values as input. That is, $sk \leftarrow \mathsf {KDF}(K, f(r_A, r_B))$. $f(r_A, r_B)$ is deliberately left undefined, and designates an operation between $r_A$ and $r_B$ such as the concatenation or the bitwise addition.

Providing Forward Secrecy. The shared key K is used to compute the session keys. If this key remains unchanged throughout all protocol runs, its disclosure allows computing all past (and future) session keys. To solve this issue we apply a key-evolving technique. We update the master key such that a previous master key cannot be computed from an updated one. Each of the two parties involved in a session updates its own copy of the derivation master key K with a non-invertible function $\mathsf {update}$: $K \leftarrow \mathsf {update}(K)$. Hence this protects past sessions in case the (current value of) master key K is revealed. Each party authenticates its peer prior to updating the derivation master key. If the master key is updated throughout the session, it may happen that one of the two involved parties update its master key whereas the other does not. This leads to a synchronisation problem.

Fig. 1.

Master key chains in SAKE. At epoch j, the initiator stores four keys: $K = K_j$, and $K'_{j-1}$, $K'_j$, $K'_{j+1}$. The responder stores two keys: $K = K_j$ and $K' = K'_j$. (Illustration with $j = 2$)

The Synchronisation Problem. If two parties use a different key K, they are obviously not able to compute a shared session key. Hence they must resynchronise first. More fundamentally, if a party initiates a session with some derivation master key K, and its partner stores a master key corresponding to an earlier epoch, then an adversary that corrupts the partner can compute past session keys with respect to the initiator, hence trivially break forward secrecy. Therefore, it is of paramount importance that the parties know if the master key of its partner has actually been updated. We provide a solution to both issues in the continuity of a single session. In particular, no extra procedure is needed in order for a desynchronised party to catch up. We avoid the need of sending additional information in order to resynchronise, such as a (sufficiently large) counter that keeps track of the evolution of the master keys, and the subsequent drawbacks: periodically doing a great amount of computations at once (when resynchronisation is necessary), and consuming bandwidth (to transmit the additional data). We base our solution on the second master key $K'$ used to authenticate the messages exchanged during a session. The solution is to update $K'$ at the same time as K (see Fig. 1). Therefore the evolution of $K'$ follows that of K. The party that receives the first authenticated message uses the MAC tag to learn which epoch the sender belongs to. Of course, $K'$ can also be desynchronised in the same way as K. This is why, whereas one party (responder $B$) stores only one sample of the key $K'$, the other party (initiator $A$) stores several samples of the authentication master key $K'$ corresponding to several consecutive epochs. We prove that only three keys $K'_{j+1}$, $K'_{j}$, $K'_{j-1}$, corresponding respectively to the next, the current, and the previous epochs, are sufficient in order for $A$ and $B$ to resynchronise. The initiator ($A$) is the one able to deal with the synchronisation issue, and consequently tells $B$ how to behave. Each party “accepts” only after it has received a confirmation (final MAC-ed messages) that its partner has already updated its own master keys. In such a case, the party ending in accepting state deems that the fresh session key can be safely used. Otherwise (in particular when the parties are desynchronised), the session key is discarded.

Since two independent master keys are used (authentication and session key derivation), one can safely maintain a copy of $K'$ corresponding to an earlier epoch ($K'_{j-1}$) without risk of threatening forward secrecy. Only one sample of the derivation master key K is kept: the most up-to-date.

1.4 Outline of the Paper

In Sect. 2 we detail the security model used to analyse the protocol we propose. Our authenticated key exchange protocol in symmetric-key setting with forward secrecy is described in Sect. 3. In Sect. 4, we investigate the feasibility of a variant based on our protocol. Formal proofs of soundness and security for the main protocol are presented in Sect. 5. The differences between our approach and the DH scheme are highlighted in Sect. 6. Finally, we conclude in Sect. 7.

2 Security Model

Before describing our symmetric-key protocol in Sect. 3 (which is self-sufficient and contains all the specifics required to understand the protocol), we present in this section the security model that we employ to formally prove its security.

In a nutshell, we use the model for authenticated key exchange protocols described by Brzuska, Jacobsen, and Stebila [18]. This model incorporates all the features that are usually considered when analysing key agreement protocols in the public-key setting (e.g., DH-based protocols with signature). In this model, the adversary has full control over the communication network. It can forward, alter, drop any message exchanged by honest parties, or insert new messages. Brzuska et al.’s model then captures adaptive corruptions but also perfect forward secrecy. This appears in the definition of the security experiment.

2.1 Execution Environment

In this section, we present the security model for authenticated key exchange protocols described by Brzuska et al. [18], and reuse the corresponding notation.

Parties. A two-party protocol is carried out by a set of parties $\mathcal {P} = \{P_0, \ldots , P_{n-1}\}$. Each party $P_i$ has an associated long-term key $\mathsf {ltk}$. Each pair of parties shares a distinct key $\mathsf {ltk}$.²

Instances. Each party can take part in multiple sequential executions of the protocol. We prohibit parallel executions of the protocol. Indeed, since the protocol we propose is based on shared evolving symmetric keys, running multiple instances in parallel may cause some executions to abort (we elaborate more on this in Sect. 6). This is the only restriction we demand compared to AKE security models used in the public-key setting.

Each run of the protocol is called a session. To each session of a party $P_i$, an instance $\pi _i^s$ is associated which embodies this (local) session’s execution of the protocol, and has access to the long-term key of the party. In addition, each instance maintains the following state specific to the session.

• $\mathsf {\rho }$: the role $\mathsf {\rho }\in \{\mathsf {init}, \mathsf {resp}\}$ of the session in the protocol execution, being either the initiator or the responder.

• $\mathsf {pid}$: the identity $\mathsf {pid}\in \mathcal {P}$ of the intended communication partner of $\pi _i^s$.

• $\mathsf {\alpha }$: the state $\mathsf {\alpha }\in \{\perp , \mathtt{running}, \mathtt{accepted}, \mathtt{rejected}\}$ of the instance.

• $\mathsf {sk}$: the session key derived by $\pi _i^s$.

• $\mathsf {\kappa }$: the status $\mathsf {\kappa }\in \{\perp , \mathtt{revealed}\}$ of the session key $\pi _i^s.\mathsf {sk}$.

• $\mathsf {sid}$: the identifier of the session.

• $\mathsf {b}$: a random bit $\mathsf {b}\in \{0, 1\}$ sampled at initialisation of $\pi _i^s$.

We put the following correctness requirements on the variables $\mathsf {\alpha }$, $\mathsf {sk}$, $\mathsf {sid}$ and $\mathsf {pid}$. For any two instances $\pi _i^s$, $\pi _j^t$, the following must hold:

$$\begin{aligned} \left( \pi _i^s.\mathsf {\alpha }= \mathtt{accepted}\right) \Rightarrow \left( \pi _i^s.\mathsf {sk}\ne \perp \wedge \pi _i^s.\mathsf {sid}\ne \perp \right) \end{aligned}$$

(1)

$$\begin{aligned} \left( \pi _i^s.\mathsf {\alpha }= \pi _j^t.\mathsf {\alpha }= \mathtt{accepted}\wedge \pi _i^s.\mathsf {sid}= \pi _j^t.\mathsf {sid}\right) \Rightarrow \left\{ \begin{array}{l} \pi _i^s.\mathsf {sk}= \pi _j^t.\mathsf {sk}\\ \pi _i^s.\mathsf {pid}= P_j \\ \pi _j^t.\mathsf {pid}= P_i \end{array} \right. \end{aligned}$$

(2)

Adversarial Queries. The adversary $\mathcal {A}$ is assumed to control the network, and interacts with the instances by issuing the following queries to them.

• $\mathsf {NewSession}(P_i, \mathsf {\rho }, \mathsf {pid})$: this query creates a new instance $\pi _i^s$ at party $P_i$, having role $\mathsf {\rho }$, and intended partner $\mathsf {pid}$.

• $\mathsf {Send}(\pi _i^s, m)$: this query allows the adversary to send any message m to $\pi _i^s$. If $\pi _i^s.\mathsf {\alpha }\ne \mathtt{running}$, it returns $\perp$. Otherwise $\pi _i^s$ responds according to the protocol specification.

• $\mathsf {Corrupt}(P_i)$: this query returns the long-term key $P_i.\mathsf {ltk}$ of $P_i$. If $\mathsf {Corrupt}(P_i)$ is the $\nu$-th query issued by the adversary, then we say that $P_i$ is $\nu$-corrupted. For a party that has not been corrupted, we define $\nu = +\infty$.

• $\mathsf {Reveal}(\pi _i^s)$: this query returns the session key $\pi _i^s.\mathsf {sk}$, and $\pi _i^s.\mathsf {\kappa }$ is set to $\mathtt{revealed}$.

• $\mathsf {Test}(\pi _i^s)$: this query may be asked only once throughout the game. If $\pi _i^s.\mathsf {\alpha }\ne \mathtt{accepted}$, then it returns $\perp$. Otherwise it samples an independent key $sk_0 \xleftarrow {\$} \mathcal {K}$, and returns $sk_b$, where $sk_1 = \pi _i^s.\mathsf {sk}$. The key $sk_b$ is called the $\mathsf {Test}$-challenge.

Definition 1 (Partnership)

Two instances $\pi _i^s$ and $\pi _j^t$ are partners if $\pi _i^s.\mathsf {sid}= \pi _j^t.\mathsf {sid}$.

Definition 2 (Freshness)

An instance $\pi _i^s$ is said to be fresh with intended partner $P_j$, if

• (a) $\pi _i^s.\mathsf {\alpha }= \mathtt{accepted}$ and $\pi _i^s.\mathsf {pid}= P_j$ when $\mathcal {A}$ issues its $\nu _0$-th query,

• (b) $\pi _i^s.\mathsf {\kappa }\ne \mathtt{revealed}$ and $P_i$ is $\nu$-corrupted with $\nu _0 < \nu$, and

• (c) for any partner instance $\pi _j^t$ of $\pi _i^s$, we have that $\pi _j^t.\mathsf {\kappa }\ne \mathtt{revealed}$ and $P_j$ is $\nu '$-corrupted with $\nu _0 < \nu '$.

Note that the notion of freshness incorporates a requirement for forward secrecy.

An authenticated key exchange protocol (AKE) is a two-party protocol satisfying the correctness requirements 1 and 2, and where the security is defined in terms of an AKE experiment played between a challenger and an adversary. This experiment uses the execution environment described above. The adversary can win the AKE experiment in one of two ways: (i) by making an instance accept maliciously, or (ii) by guessing the secret bit of the $\mathsf {Test}$-instance.

Definition 3 (Entity Authentication (EA))

An instance $\pi _i^s$ of a protocol $\Pi$ is said to have accepted maliciously in the AKE security experiment with intended partner $P_j$, if

• (a) $\pi _i^s.\mathsf {\alpha }= \mathtt{accepted}$ and $\pi _i^s.\mathsf {pid}= P_j$ when $\mathcal {A}$ issues its $\nu _0$-th query,

• (b) $P_i$ and $P_j$ are $\nu$- and $\nu '$-corrupted with $\nu _0 < \nu , \nu '$, and

• (c) there is no unique instance $\pi _j^t$ such that $\pi _i^s$ and $\pi _j^t$ are partners.

The adversary’s advantage is defined as its winning probability:

$$\mathsf {adv}_{\Pi }^{\mathsf {ent\text{- }auth}}(\mathcal {A}) = \Pr [\mathcal {A} \text{ wins } \text{ the } \text{ EA } \text{ game }]\text{. }$$

Definition 4 (Key Indistinguishability)

An adversary $\mathcal {A}$ against a protocol $\Pi$, that issues its $\mathsf {Test}$-query to instance $\pi _i^s$ during the AKE security experiment, answers the $\mathsf {Test}$-challenge correctly if it terminates with output $b'$, such that

• (a) $\pi _i^s$ is fresh with some intended partner $P_j$, and

• (b) $\pi _i^s.\mathsf {b}= b'$.

The adversary’s advantage is defined as

$$\mathsf {adv}_{\Pi }^{\mathsf {key\text{- }ind}}(\mathcal {A}) = \left| \Pr [\pi _i^s.\mathsf {b}= b'] - \frac{1}{2}\right| \text{. }$$

Definitions 3 and 4 allow the adversary to corrupt an instance involved in the security experiment (once the targeted instance has accepted, in order to exclude trivial attacks). Therefore, protocols secure with respect to Definition 5 below provide perfect forward secrecy. Note that we do not allow the targeted instance to be corrupted before it accepts. This security model does not capture key-compromise impersonation attacks (KCI) [15] since that would allow trivially breaking key exchange protocols solely based on shared symmetric keys.

Definition 5 (AKE Security)

We say that a two-party protocol $\Pi$ is a secure AKE protocol if $\Pi$ satisfies the correctness requirements 1 and 2, and for all probabilistic polynomial time adversary $\mathcal {A}$, $\mathsf {adv}^{\mathsf {ent\text{- }auth}}_{\Pi }(\mathcal {A})$ and $\mathsf {adv}^{\mathsf {key\text{- }ind}}_{\Pi }(\mathcal {A})$ are a negligible function of the security parameter.

2.2 Security Definitions of SAKE’s Building Blocks

In this section, we recall the definitions of the main security notions we use in our results. The security definition of a pseudo-random function is taken from Bellare, Desai, Jokipii, and Rogaway [9], and that of a MAC strongly unforgeable under chosen-message attacks from Bellare and Namprempre [11]. We recall also the definition of matching conversations initially proposed by Bellare and Rogaway [12], and modified by Jager, Kohlar, Schäge, and Schwenk [27].

Secure PRF. A pseudo-random function (PRF) F is a deterministic algorithm which given a key $K\in \{0, 1\}^{\lambda }$ and a bit string $x \in \{0, 1\}^*$ outputs a string $y = F(K, x) \in \{0, 1\}^{\gamma }$ (with $\gamma$ being polynomial in $\lambda$). Let Func be the set of all functions of domain $\{0, 1\}^*$ and range $\{0, 1\}^{\gamma }$. The security of a PRF is defined with the following experiment between a challenger and an adversary $\mathcal {A}$:

• 1. The challenger samples $K \xleftarrow {\$} \{0, 1\}^{\lambda }$, $G \xleftarrow {\$} Func$, and $b \xleftarrow {\$} \{0, 1\}$ uniformly at random.

• 2. The adversary may adaptively query values x to the challenger. The challenger replies to each query with either $y = F(K, x)$ if $b = 1$, or $y = G(x)$ if $b = 0$.

• 3. Finally, the adversary outputs its guess $b' \in \{0, 1\}$ of b.

The adversary’s advantage is defined as

$$\mathsf {adv}_F^{\mathsf {prf}}(\mathcal {A}) = \left| \Pr [b = b'] - \frac{1}{2}\right| \text{. }$$

Definition 6 (Secure PRF)

A function $F{:} \{0, 1\}^{\lambda }\times \{0, 1\}^* \rightarrow \{0, 1\}^{\gamma }$ is said to be a secure pseudo-random function (PRF) if, for all probabilistic polynomial time adversary $\mathcal {A}$, $\mathsf {adv}_F^{\mathsf {prf}}(\mathcal {A})$ is a negligible function in $\lambda$.

Secure MAC. A message authentication code (MAC) consists of two algorithms $(\mathsf {Mac}, \mathsf {Vrf}$). The tagging algorithm $\mathsf {Mac}$ takes as input a key $K \in \{0, 1\}^{k}$ and a message $m \in \{0, 1\}^*$ and returns a tag $\tau \in \{0, 1\}^{\gamma }$ (with $\gamma$ being polynomial in k). The verification algorithm $\mathsf {Vrf}$ takes as input the key K, a message m, and a candidate tag $\tau$ for m. It outputs 1 if $\tau$ is a valid tag on message m with respect to K. Otherwise, it returns 0. The notion of strong unforgeability under chosen-message attacks (SUF-CMA) for a MAC $G = (\mathsf {Mac}, \mathsf {Vrf})$ is defined with the following experiment between a challenger and an adversary $\mathcal {A}$:

• 1. The challenger samples $K \xleftarrow {\$} \{0, 1\}^{k}$, and sets $S \leftarrow \emptyset$.

• 2. The adversary may adaptively query values m to the challenger. The challenger replies to each query with $\tau = \mathsf {Mac}(K, m)$ and records $(m, \tau )$: $S \leftarrow S \cup \{(m, \tau )\}$. In addition, the adversary may adaptively query values $(m', \tau ')$ to the challenger. The challenger replies to each query with $\mathsf {Vrf}(K, m', \tau ')$.

• 3. Finally, the adversary sends $(m^*, \tau ^*)$ to the challenger.

The adversary’s advantage is defined as

$$\mathsf {adv}_{G}^{\mathsf {suf\text{- }cma}}(\mathcal {A}) = \Pr [\mathsf {Vrf}(K, m^*, \tau ^*) = 1 \wedge (m^*, \tau ^*) \notin S]\text{. }$$

Definition 7 (SUF-CMA)

A message authentication code $G = (\mathsf {Mac}, \mathsf {Vrf})$ with $\mathsf {Mac}{:} \{0, 1\}^{k}\times \{0, 1\}^* \rightarrow \{0, 1\}^{\gamma }$ is said to be strongly unforgeable under chosen-message attacks (SUF-CMA) if, for all probabilistic polynomial time adversary $\mathcal {A}$, $\mathsf {adv}_{G}^{\mathsf {suf\text{- }cma}}(\mathcal {A})$ is a negligible function in k.

Matching Conversations. Let $T_{i, s}$ be the sequence of all (valid) messages sent and received by an instance $\pi _i^s$ in chronological order. For two transcripts $T_{i,s}$ and $T_{j,t}$, we say that $T_{i,s}$ is a prefix of $T_{j,t}$ if $T_{i,s}$ contains at least one message, and the messages in $T_{i,s}$ are identical to the first $|T_{i,s}|$ messages of $T_{j,t}$.

Definition 8 (Matching Conversations)

We say that $\pi _i^s$ has a matching conversation to $\pi _j^t$, if

• $\pi _i^s$ has sent all protocol messages and $T_{j,t}$ is a prefix of $T_{i,s}$, or

• $\pi _j^t$ has sent all protocol messages and $T_{i,s} = T_{j,t}$.

3 Our Symmetric-Key AKE Protocol with Perfect Forward Secrecy

In this section we describe our main protocol. Although all the calculations are based on shared master keys, forward secrecy is guaranteed by using a key-evolving scheme. More precisely, we use two types of keys: one to compute the session keys, the other to authenticate messages and resynchronise when necessary. This second type of keys allows tracking the master keys evolution, and limit the gap (in terms of keys update) between both parties. Mutual authentication, key exchange, and synchronised update of the master keys are done in the same session.

3.1 Description of the Protocol

The protocol is depicted by Fig. 2. The parameter $\delta _{AB}$ computed by $A$ corresponds to the gap between $A$ and $B$ with respect to the evolution of the master keys. We prove that $\delta _{AB} \in \{-1, 0, 1\}$ (see Sect. 5.1). That is, $A$ can only be either one step behind, or in sync, or one step ahead to $B$. During a session, $A$ uses the keys $K'_{j}$, $K'_{j-1}$, $K'_{j+1}$ (by order of likelihood) and the first message ($m_B$) sent by $B$ to learn $\delta _{AB}$. The message $m_B$ is computed with the current value $K'$ of $B$. Therefore $m_B$ indicates the current synchronisation state of $B$. Then $A$ informs $B$. One bit $\epsilon$ is enough (message $m_A$) because $B$ takes two behaviours only: if $\delta _{AB} \in \{-1, 0\}$ ($\epsilon = 0$), and if $\delta _{AB} = 1$ ($\epsilon = 1$). $A$ and $B$ behave as follows.

• If $A$ is in sync with $B$ ($\delta _{AB} = 0$), $A$ computes the new session key, and updates its master keys. Then, upon reception of $m_A$, $B$ does the same.

• If $A$ is in advance ($\delta _{AB} = 1$), $A$ waits for $B$ to resynchronise (i.e., $B$ updates its master keys a first time), and to proceed with the regular operations (i.e., $B$ computes the new session key, and updates its master keys a second time). Then, once $A$ receives a confirmation that $B$ is synchronised (message $\tau '_B$), $A$ performs the regular operations as well (session key computation, master keys update). Since $A$ waits for $B$ to resynchronise before proceeding, the gap between the parties is bounded (as proved in Sect. 5.1).

• If $A$ is late ($\delta _{AB} = -1$), it resynchronises (i.e., it updates its master keys a first time), and then performs the regular operations (session key computation, master keys update). Then (upon reception of message $m_A$), $B$ applies the regular operations.

Once a correct and complete session ends, three goals are achieved in the same protocol run: (i) the two parties have updated their master keys, (ii) they are synchronised (which stems in particular from the fact that the gap between $A$ and $B$ is bounded, i.e., $|\delta _{AB}| \le 1$), and (iii) they share a new session key. In other words, the protocol is self-synchronising.

Before the first session between $A$ and $B$, the master keys are initialised as follows:

• 1. K and $K'$ are uniformly chosen at random.

• 2. $K'_{j-1}\leftarrow \perp$

• 3. $K'_{j}\leftarrow K'$

• 4. $K'_{j+1}\leftarrow \mathsf {update}(K')$

Since $K'_{j+1}$ and $K'_{j}$ can be computed from $K'_{j-1}$, it is possible to store only $K'_{j-1}$, and to compute the two other keys when necessary during the session. Then, with respect to the security model presented in Sect. 2, the long-term key of $A$ and $B$ corresponds respectively to $A.\mathsf {ltk}= (K, K'_{j-1})$ and $B.\mathsf {ltk}= (K, K')$.

Although this does not appear explicitly in Fig. 2, a party aborts the session if it receives a message computed with an invalid identity. For the responder $B$ an invalid identity corresponds to an initiator party $A$ it does not share master keys with. For an initiator $A$, the particular case $B = A$, among other possibilities, yields an error (each party must have a distinct identity).

Number of Rounds. The session can be reduced from five to four messages in some cases. Indeed, regarding the synchronisation state, in two cases (when $\delta _{AB} \in \{-1, 0\}$, that is $\epsilon = 0$), $A$ and $B$ are synchronised, and share a session key once $B$ has received message $m_A$ and executed the subsequent operations. Therefore, in such a case, the session can end upon reception of message $\tau '_B$ by $A$. More precisely

• if $\delta _{AB} = 1$ ($\epsilon = 1$), then $A$ accepts upon reception of $\tau '_B$, and $B$ accepts upon reception of $\tau '_A$;

• if $\delta _{AB} \in \{-1, 0\}$ ($\epsilon = 0$), then $A$ accepts upon reception of $\tau '_B$, and $B$ accepts upon reception of $m_A$.

Fig. 2.

SAKE protocol

Each message of the protocol fulfills a specific task: party authentication, detecting desynchronisation, and then catching up. This eventually results in the forward secrecy property being ensured. Removing one message yields an attack, as shown by any of the numerous alternative versions we have analysed. Although we do not formally prove it, we do think that the figure of five rounds is the least achievable in order to take into account all cases.

3.2 Notation

For the sake of clarity, we use the following notation in Fig. 2:

• $\mathsf {kdf}$ corresponds to: $sk \leftarrow \mathsf {KDF}(K, f(r_A, r_B))$

• $\mathsf {upd}_A$ corresponds to

  • 1. $K \leftarrow \mathsf {update}(K)$

  • 2. $K'_{j-1}\leftarrow K'_{j}$

  • 3. $K'_{j}\leftarrow K'_{j+1}$

  • 4. $K'_{j+1}\leftarrow \mathsf {update}(K'_{j+1})$

• $\mathsf {upd}_B$ corresponds to

  • 1. $K \leftarrow \mathsf {update}(K)$

  • 2. $K' \leftarrow \mathsf {update}(K')$

Moreover, $\mathsf {Vrf}(k, m, \tau )$ denotes the MAC verification function that takes as input a secret key k, a message m, and a tag $\tau$. It outputs $\mathtt {true}$ if $\tau$ is a valid tag on message m with respect to k. Otherwise, it returns $\mathtt {false}$.

3.3 SAKE-AM: A Complementary Mode of SAKE

From SAKE, we can derive an aggressive mode that allows any party to be either initiator or responder, and such that the smallest amount of calculation is always done by the same party.

In SAKE the initiator $A$ owns the three keys $K'_{j+1}$, $K'_{j}$, $K'_{j-1}$, and the responder $B$ does the lightest computations. In this mode $B$ owns the three keys, and $A$ does the smallest amount of calculation. The main idea is to skip the first SAKE message $A\Vert r_A$. Hence the roles between the two parties are swapped. This leads to other minor changes in message format compared to SAKE. Despite these differences, the messages and the calculations are essentially the same as in SAKE. This mode remains a sound and secure AKE protocol (according to Definition 5).³ We call this mode SAKE in aggressive mode (SAKE-AM).

Fig. 3.

Symmetric-key authenticated key exchange with forward secrecy between a low-resource end-device and a back-end server. Both parties may initiate the session. In some cases, the last message can be skipped.

This can be applied in the context of industrial IoT when a set of end-devices (e.g., sensors, actuators) communicate with a central server. When the end-device wants to initiate a communication, protocol SAKE-AM is launched. Otherwise (the server is initiator), SAKE is used (see Fig. 3). Therefore, the end-device always does the lightest computations.

4 A Random-Free Variant of SAKE

From SAKE, one can devise several variants. First, the three authentication keys $K'_{j-1}$, $K'_{j}$, $K'_{j+1}$ can be replaced by two local counters $c_A$, $c_B$ (respectively stored by $A$ and $B$) that keep track of the evolution of the derivation master key K, with one static authentication master key $K'$.⁴ On the initiator’ side, the MAC verifications are then done with consecutive values of the counter $j-1$, j, $j+1$. Overall, the sequence of operations and the computations are similar to that of SAKE. This means mainly replacing function $x \mapsto \mathsf {Mac}(K'_{j}, x)$ with $x \mapsto \mathsf {Mac}(K', j\Vert x)$. Yet, this alternative implies the storage of two keys and one counter: K, $K'$ and $c_A$/$c_B$, instead of two keys only: K and $K'_{j-1}$/$K'$ (and, one the initiator’ side only, one or two additional calls to $\mathsf {update}$ in order to compute $K'_{j}$ and, possibly, $K'_{j+1}$).

Another, more interesting, variant is the following.⁵ In SAKE, the pseudo-random values $r_A$, $r_B$ are used to yield a fresh session key, and participate also in the authentication of the parties. Using new values during each session contributes to achieving these two tasks. Yet, these parameters are not the only ones to evolve throughout the successive protocol runs. The master keys do also. Therefore, one can consider removing the pseudo-random values from the messages. Without the pseudo-random values, several messages become cryptographically valid for each flow (instead of one only in SAKE). For instance, without $r_A$, party $A$ may accept as second message either $\tau _B = \mathsf {Mac}(K'_{j}, B\Vert A)$, or $\tau _B = \mathsf {Mac}(K'_{j-1}, B\Vert A)$, or $\tau _B = \mathsf {Mac}(K'_{j+1}, B\Vert A)$. Likewise, without $r_B$, $B$ may accept as third message either $0\Vert \tau _A$ or $1\Vert \tau _A$. Consequently, in this variant, we prefix each MAC-ed message with its index from 1 to 4 (but not the first one which carries only the initiator’s identity).

The removal of the pseudo-random values enables a “mismatch attack”. By “attack” we mean the following: an adversary is able to compel $B$ to compute a message (message 4) which is unaltered by the adversary and expected by $A$, and yet $A$ rejects this message as invalid. Although unpleasant, this “attack” does not break any claimed security property (in particular entity authentication). Moreover, this scenario cannot damage the synchronisation of the two parties. That is, if they start a new session, the latter completes successfully (if the adversary remains passive), as in SAKE.

In this variant, the length of the messages is shortened, and this avoids also calling the pseudo-random generation function. This is advantageous for low-resource devices. Nonetheless, the possibility provided by the aforementioned scenario is not what one usually expects from a security protocol. Consequently, for the practitioners for whom this mismatch attack is unacceptable, the SAKE protocol is more adequate.

5 Security and Soundness for SAKE

In this section we prove that (i) SAKE is sound, and (ii) it is a secure AKE protocol according to Definition 5 given above.

5.1 Soundness of SAKE

We want to show that SAKE is sound, which essentially means that, once a correct session is complete, both parties have updated their respective internal state, are synchronised, and share the same (new) session key. We call a “benign” adversary an adversary that faithfully forwards all messages between an initiator $A$ and a responder $B$.

Lemma 1

Let $A$ and $B$ be respectively the initiator and the responder of a SAKE session. Let $\delta _{AB}$ be the gap between $A$ and $B$ with respect to the evolution of the master keys of both parties. The following conditions always hold:

• 1. $\delta _{AB} \in \{-1, 0, 1\}$, and

• 2. whatever the synchronisation state of $A$ and $B$ (i.e., whatever $A$ and $B$ are synchronised or not) when a new session starts, when that session completes in presence of a benign adversary, then

  • (a) $A$ and $B$ have updated their master keys at least once, and

  • (b) $A$ and $B$ are synchronised (with respect to their master keys), and

  • (c) $A$ and $B$ share the same session key.

In order to prove Lemma 1, we use the following notation. The messages exchanged during a session are numbered from 1 to 5. The notation “$(i_A, i_B)$” means that, when the session ends, the last valid message received by $A$ is message of index $i_A$, and the last valid message received by $B$ is message of index $i_B$. We call a $(i_A, i_B)$ -session a session where the last message received by $A$ is message $i_A$, and the last message received by $B$ is message $i_B$. By convention $i_A = 0$ means that no message has been received by $A$.

It may happen that $A$ send a first message which is not received by $B$. $B$ cannot know if it has missed a first message. But this is of no consequence regarding the synchronisation between $A$ and $B$ ($A$ may simply run the protocol anew). Therefore we do not use the value $i_B = 0$ (it is equivalent to $i_B = 5$). At initialisation (i.e., before the first run of the protocol), $(i_A, i_B)$ is set to (4, 5). Since $A$ sends message $i \in \{3, 5\}$ only upon reception of a valid message $i-1$, and $B$ sends message $j \in \{2, 4\}$ only upon reception of a valid message $j-1$, the only possible values for $(i_A, i_B)$ are: (0, 1), (2, 1), (2, 3), (4, 3), and (4, 5).

Proof

We prove Lemma 1. We first prove item 1.

Let $c_A$ (resp. $c_B$) be a (virtual) monotonically increasing counter initialised to 0 that follows the evolution of the master keys held by $A$ (resp. $B$). That is, $c_A$ (resp. $c_B$) is increased each time the master keys K, $K'_{j+1}$, $K'_{j}$, $K'_{j-1}$ (resp. K, $K'$) are updated. The parameter $\delta _{AB}$ corresponds to the gap between $A$ and $B$ with respect to the evolution of their master keys, hence $\delta _{AB} = c_A - c_B$.

We prove item 1 by constructing iteratively Table 1b.

Before the first protocol run, $A$ and $B$ are synchronised. That is $\delta _{AB} = c_A - c_B = 0$, and $(c_A, c_B) = (i, i)$ (with $i = 0$). Therefore, $A$ can validate $\tau _B$ (in message $m_B$) with the same key $K'_{j}= K'$ as $B$. Hence $A$ computes $\delta _{AB} = 0$, and $\epsilon = 0$. Consequently, if one carries out the protocol run starting with $\delta _{AB} = 0$ and $\epsilon = 0$, for each possible value $(i_A, i_B)$, one eventually gets the following:

• $(c_A, c_B) = (i, i)$ and $\delta _{AB} = 0$ after a (0, 1)-session,

• $(c_A, c_B) = (i+1, i)$ and $\delta _{AB} = 1$ after a (2, 1)-session,

• $(c_A, c_B) = (i+1, i+1)$ and $\delta _{AB} = 0$ after a (2, 3)-session,

• $(c_A, c_B) = (i+1, i+1)$ and $\delta _{AB} = 0$ after a (4, 3)-session,

• $(c_A, c_B) = (i+1, i+1)$ and $\delta _{AB} = 0$ after a (4, 5)-session.

This corresponds to the first column of Tables 1a and b. As we can see, the only possible values for $\delta _{AB}$ after any session are 0 and 1. $\delta _{AB} = 0$ has already been investigated. Hence, starting with $\delta _{AB} = 1$ (i.e., $(c_A, c_B) = (i+1, i)$), we look for all the values $\delta _{AB}$ may have when the session ends, considering any possible session.

$(c_A, c_B) = (i+1, i)$ means that $A$ is in advance with respect to $B$. In such a case, $A$ succeeds in validating $\tau _B$ with $K'_{j-1}$ (and, indeed, finds $\delta _{AB} = 1$). Then $A$ uses $\delta _{AB} = 1$ and $\epsilon = 1$. If one carries out the protocol run using these two values, one gets three possible values for $\delta _{AB}$: 1, 0, $-1$. This corresponds to the second column of Table 1b, and shows that a third value is possible for $\delta _{AB}$, which is $-1$ (i.e., $(c_A, c_B) = (i, i+1)$).

Then we restart the protocol with all possible sessions, assuming that $(c_A, c_B) = (i, i+1)$ at the beginning of the run. This means that $A$ is one step late with respect to $B$. In such a case, $A$ succeeds in validating $\tau _B$ with key $K'_{j+1}$ (and, indeed, finds $\delta _{AB} = -1$). Then $A$ uses $\delta _{AB} = -1$ and $\epsilon = 0$. If one carries out the protocol run using these two values, we end with three possible values for $\delta _{AB}$ (third column of Table 1b): $-1$, 0 and 1, that have been explored already. This proves that, whatever the sequences of sessions, the only possible values for $\delta _{AB}$ are in $\{-1, 0, 1\}$.

Now we prove item 2 of Lemma 1.

We know that $\delta _{AB} \in \{-1, 0, 1\}$. For each possible value of $\delta _{AB}$ at the beginning of the session, the last line of Table 1b indicates the value of that parameter after a correct and complete session (i.e., a (4, 5)-session). As we can see, $A$ and $B$ are always synchronised (i.e., $\delta _{AB} = 0$) in such a case whatever the value of $\delta _{AB}$ when the session starts. Furthermore, the session key computation immediately precedes the last update of the derivation master key K. Hence, when a correct and complete session ends, $A$ and $B$ use the same derivation master key K to compute the session key. Therefore, using the same values $r_A$, $r_B$, $A$ and $B$ compute the same session key.

In addition, Table 1a shows that, whatever the synchronisation state of $A$ and $B$ (i.e., $c_A$ and $c_B$) at the beginning of the session, after a correct and complete session, $A$ and $B$ have updated their internal state at least once (as the last line of the table, corresponding to a (4, 5)-session, indicates).    $\square$

Table 1. Possible values for $\delta _{AB}$ and $(c_A, c_B)$ among all sequences of sessions in SAKE

5.2 Security of SAKE

In order to prove that the protocol SAKE is a secure AKE protocol, we use the execution environment described in Sect. 2.1. We define the partnering between two instances with the notion of matching conversations (see Definition 8). That is, we define $\mathsf {sid}$ to be the transcript, in chronological order, of all the (valid) messages sent and received by an instance during the key exchange, but, possibly, the last one. Furthermore, we choose the function $\mathsf {update}$ to be a PRF, that is $\mathsf {update}: K \mapsto \mathsf {PRF}(K, x)$ for some (constant) value x.

Theorem 1

The protocol SAKE is a secure AKE protocol, and for any probabilistic polynomial time adversary $\mathcal {A}$ in the AKE security experiment against protocol SAKE, we have

$$\begin{aligned} \mathsf {adv}^{\mathsf {ent\text{- }auth}}_{SAKE}(\mathcal {A})\le & {} nq \left( (nq -1)2^{-\lambda } + (q + 1)\mathsf {adv}_{\mathsf {update}}^{\mathsf {prf}}(\mathcal {B}) + 2\mathsf {adv}_{\mathsf {Mac}}^{\mathsf {suf\text{- }cma}}(\mathcal {C})\right) \\ \mathsf {adv}^{\mathsf {key\text{- }ind}}_{SAKE}(\mathcal {A})\le & {} nq\left( (q-1)\mathsf {adv}_{\mathsf {update}}^{\mathsf {prf}}(\mathcal {B}) + \mathsf {adv}_{\mathsf {KDF}}^{\mathsf {prf}}(\mathcal {D})\right) + \mathsf {adv}^{\mathsf {ent\text{- }auth}}_{SAKE}(\mathcal {A}) \end{aligned}$$

where n is the number of parties, q the maximum number of instances (sessions) per party, $\lambda$ the size of the pseudo-random values ($r_A$, $r_B$), and $\mathcal {B}$ is an adversary against the PRF-security of $\mathsf {update}$, $\mathcal {C}$ an adversary against the SUF-CMA-security of $\mathsf {Mac}$, and $\mathcal {D}$ an adversary against the PRF-security of $\mathsf {KDF}$.

Proof

In order for an initiator instance $\pi _i^s$ at some party $P_i$ to accept, two valid messages (i.e., with valid MAC tags) must be received by $\pi _i^s$ ($m_B$ and $\tau '_B$). We reduce the security of the $\mathsf {Mac}$ function to the (in)ability to forge a valid output. Therefore we use the fact that the key $K'$ is random. By assumption, the genuine value of $K'$ (i.e., the value used during the first session between two same parties) is uniformly chosen at random. Yet $K'$ (and K) is updated throughout the session with the function $\mathsf {update}$. If $K'$ is random, we can rely on the pseudo-randomness of $\mathsf {update}(\cdot ) = \mathsf {PRF}(\cdot , \cdot )$. In turn, since $\mathsf {PRF}(K', \cdot )$ can be replaced with a truly random function, its output (updated $K'$) is random. Therefore, one can rely upon the pseudo-randomness of the function $\mathsf {update}$ keyed with this new value $K'$, and so forth. Each transition (i.e., each update of $K'$) implies a loss equal to $\mathsf {adv}_{\mathsf {update}}^{\mathsf {prf}}(\mathcal {B})$ corresponding to the ability of an adversary $\mathcal {B}$ to distinguish $\mathsf {update}$ from a random function.

If $P_i$ is synchronised with the responder ($\delta _{AB} = 0$), $P_i$ updates its master keys once (upon reception of $m_B$). If $P_i$ is in advance ($\delta _{AB} = 1$), it updates its keys at most once (if a valid message $\tau '_B$ is received). If $P_i$ is late ($\delta _{AB} = -1$), it updates its keys twice. Yet, in that case, $P_i$ did not update its keys during the previous session. Therefore, on average, $P_i$ updates its keys at most once per session. Hence, when the u-th session starts, $P_i$ has updated its keys at most $u-1$ times on average, and, upon reception of $\tau '_B$, $P_i$ updates the keys at most two times.

This is similar regarding the responder. A responder instance $\pi _j^t$ at some party $P_j$ accepts only if the two messages $m_A$ and $\tau '_A$ are valid. Upon reception of a valid message $m_A$, the keys are updated once ($\epsilon = 0$) or twice ($\epsilon = 1$). In the latter case, the keys have not been updated during the previous session. This means that the keys are updated on average at most once per session. Therefore, when the u-th session starts, $P_j$ has updated its keys at most $u-1$ times on average, and, upon reception of $m_A$, the keys are updated at most two times.

We can now proceed with the proof. We proceed through a sequence of games [13, 32], where each consecutive game aims at reducing the challenger’s dependency on the functions $\mathsf {Mac}$, $\mathsf {update}$ and $\mathsf {KDF}$. We first prove the entity authentication security. Let $E_i$ be the event that the adversary win the entity authentication experiment in Game i.

Game 0. This game corresponds to the entity authentication security experiment described in Sect. 2.1. Therefore

$$\Pr [E_0] = \mathsf {adv}^{\mathsf {ent\text{- }auth}}_{SAKE}(\mathcal {A})$$

Game 1. The challenger aborts if there exists any instance that chooses a random value $r_A$ or $r_B$ that is not unique. There is at most $n\times q$ random values, each uniformly drawn at random in $\{0, 1\}^{\lambda }$. Therefore the probability that at least two random values be equal is at most $\frac{nq(nq-1)}{2^{\lambda }}$. Hence

$$\Pr [E_0] \le \Pr [E_1] + \frac{nq(nq-1)}{2^{\lambda }}$$

Game 2. The challenger tries to guess which instance will be the first to accept maliciously. If the guess is wrong, the game is aborted. The number of instances is at most nq. Therefore

$$\Pr [E_2] = \Pr [E_1]\times \frac{1}{nq}$$

Game 3. Let $\pi$ be the instance targeted by the adversary. In this game, we add an abort rule. The challenger aborts the experiment if $\pi$ ever receives a valid message $m_B$ (resp. $m_A$) if it is an initiator (resp. responder) instance, but no instance having a matching conversation to $\pi$ has output that message. We reduce the probability of this event to the security of the functions $\mathsf {Mac}$ and $\mathsf {update}$. As explained above, when the u-th session starts, the master keys have been updated at most $u-1$ times already. The genuine value of $K'$ is uniformly chosen at random. In order to be able to replace, during the current session, the key used to compute the MAC tag in $m_A$ (resp. $m_B$) with a random value, one must rely upon the pseudo-randomness of the function $\mathsf {update}$ that outputs (the new value of) $K'$. In turn, this relies upon the (previous) key $K'$ being random (and on the pseudo-randomness of $\mathsf {update}$). Therefore, in order to replace $K'$ with a random value one must take into account the successive losses $\mathsf {adv}_{\mathsf {update}}^{\mathsf {prf}}(\mathcal {B})$, each corresponding to the ability of an adversary $\mathcal {B}$ to distinguish the function $\mathsf {update}$ (keyed with a different key $K'$) from a random function. Since there is at most q sessions, this loss is at most $(q-1)\mathsf {adv}_{\mathsf {update}}^{\mathsf {prf}}(\mathcal {B})$. Then we reduce the probability of the adversary $\mathcal {A}$ to win this game to the ability of an adversary $\mathcal {C}$ to forge a valid tag $\tau _B$ (resp. $\tau _A$).

Therefore, we replace each function $\mathsf {update}(K') = \mathsf {PRF}(K', x)$ (keyed with a different key $K'$ throughout the, at most, $q-1$ successive sessions established, prior to that current session, by the same party that owns $\pi$) with truly random functions $\mathsf {F}^{\mathsf {update}}_0$, $\ldots$, $\mathsf {F}^{\mathsf {update}}_{q-2}$. Moreover, if an instance uses the same key $K' = K'_i$, $0 \le i < q-1$, to key $\mathsf {update}$, then we replace $\mathsf {update}$ with the corresponding random function $\mathsf {F}^{\mathsf {update}}_i$. Since, to that point, the key $K' = K'_{q-1}$ used to compute the authentication tag $\tau _B$ (resp. $\tau _A$) is random, we reduce the ability of $\mathcal {A}$ to win to the security of the $\mathsf {Mac}$ function. Hence

$$\Pr [E_2] \le \Pr [E_3] + (q-1)\mathsf {adv}_{\mathsf {update}}^{\mathsf {prf}}(\mathcal {B}) + \mathsf {adv}_{\mathsf {Mac}}^{\mathsf {suf\text{- }cma}}(\mathcal {C})$$

Game 4. The challenger aborts the experiment if $\pi$ ever receives a valid message $\tau '_B$ (resp. $\tau '_A$), but no instance having a matching conversation to $\pi$ has output that message. Between the message $m_B$ (resp. $m_A$) being received by $\pi$, and the message $\tau '_B$ (resp. $\tau '_A$) being received by $\pi$, the master keys are updated at most twice. We reduce the probability of the adversary to win this game to the security of the $\mathsf {Mac}$ function used to compute the message $\tau '_B$ (resp. $\tau '_A$). In turn we must rely on the randomness of the $\mathsf {Mac}$ key, hence on the security of the function $\mathsf {update}$ used to update the $\mathsf {Mac}$ key $K'$ (recall that, due to Game 3, the current key $K'$ is random). Therefore

$$\Pr [E_3] \le \Pr [E_4] + 2\mathsf {adv}_{\mathsf {update}}^{\mathsf {prf}}(\mathcal {B}) + \mathsf {adv}_{\mathsf {Mac}}^{\mathsf {suf\text{- }cma}}(\mathcal {C})$$

To that point, the only way for the adversary to make $\pi$ accept maliciously is to send a valid message $\tau '_B$ (resp. $\tau '_A$) different from all the messages sent by all the instances. However, in such a case, the challenger aborts. Therefore $\Pr [E_4] = 0$.

Collecting all the probabilities from Game 0 to 4, we get the indicated bound.

Now we prove the key indistinguishability security. Let $E'_i$ be the event that an adversary win the key indistinguishability experiment in Game i, and $\mathsf {adv}_i = \Pr [E'_i] - \frac{1}{2}$.

Game 0. This game corresponds to the key indistinguishability experiment described in Sect. 2.1. Therefore

$$\Pr [E'_0] = \frac{1}{2} + \mathsf {adv}^{\mathsf {key\text{- }ind}}_{SAKE}(\mathcal {A}) = \frac{1}{2} + \mathsf {adv}_0$$

Game 1. The challenger aborts the experiment and chooses $b' \in \{0, 1\}$ uniformly at random if there exists an instance that accepts maliciously. In other words, in this game we make the same modifications as in the games performed during the entity authentication proof. Hence

$$\mathsf {adv}_0 \le \mathsf {adv}_1 + \mathsf {adv}^{\mathsf {ent\text{- }auth}}_{SAKE}(\mathcal {A})$$

Game 2. The challenger tries to guess which instance is targeted by the adversary. If the guess is wrong, the game is aborted. The number of instances is at most nq. Therefore

$$\mathsf {adv}_2 = \mathsf {adv}_1 \times \frac{1}{nq}$$

Game 3. Let $\pi$ be the instance targeted by the adversary. We reduce the advantage of the adversary to win this game to the security of the function $\mathsf {KDF}$ used to compute the session key. That is, we rely upon the pseudo-randomness of the $\mathsf {KDF}$ function. This is possible if the key K is random. The genuine value of K is uniformly chosen at random by assumption. Then K is updated with $\mathsf {update}$ at most once per session on average. Therefore, when the u-th session starts, K has been updated at most $u-1$ times already. Therefore we must take into account the successive losses due to the key update with respect to the pseudo-randomness of $\mathsf {update}$. Since there is at most q sessions per party (i.e., per original key K), this loss is at most $(q-1)\mathsf {adv}_{\mathsf {update}}^{\mathsf {prf}}(\mathcal {B})$. Hence we replace each function $\mathsf {update}(K) = \mathsf {PRF}(K, x)$ (keyed with a different key K throughout the, at most, $q-1$ successive sessions established, prior to that current session, by the same party that owns $\pi$) with truly random functions $\mathsf {G}^{\mathsf {update}}_0$, $\ldots$, $\mathsf {G}^{\mathsf {update}}_{q-2}$. Moreover, if an instance uses the same key $K = K_i$, $0 \le i < q-1$, to key $\mathsf {update}$, then we replace $\mathsf {update}$ with the corresponding random function $\mathsf {G}^{\mathsf {update}}_i$. Since, to that point, the key $K = K_{q-1}$ used to compute the session key is random, we reduce the ability of $\mathcal {A}$ to win to the security of $\mathsf {KDF}$. Therefore

$$\mathsf {adv}_2 \le \mathsf {adv}_3 + (q-1)\mathsf {adv}_{\mathsf {update}}^{\mathsf {prf}}(\mathcal {B}) + \mathsf {adv}_{\mathsf {KDF}}^{\mathsf {prf}}(\mathcal {D})$$

To that point the session key is random, therefore the adversary has no advantage in guessing whether $\pi .\mathsf {b}= b'$. That is

$$\mathsf {adv}_3 = 0$$

Collecting all the probabilities from Game 0 to 3, we get the indicated bound. $\square$

6 Comparison with the DH Paradigm

The protocol SAKE provides a strong form of forward secrecy. Despite this result, it differs from a DH scheme in several ways beyond the intrinsic distinction between public-key and symmetric-key cryptography.

Concurrent Executions. Our protocol does not allow parallel executions. Indeed, since it is based on shared evolving symmetric keys, running multiple instances in parallel may cause some sessions to abort. A way to relax this restriction is that each party use separate master keys for concurrent executions. On the contrary, the DH scheme allows an (virtually) unlimited number of parallel executions.

KCI Attacks. The ephemeral DH scheme is resistant against KCI attacks, whereas our protocol is not (due to the dependency between the (updated) master keys). Moreover if an adversary succeeds in getting the key $K'$ (or $K'_{j}$), it can compute the subsequent key (corresponding to $K'_{j+1}$). Hence the adversary can forge a message $m_B$ in SAKE that brings the initiator to update its master keys twice consecutively. Therefore, that party is desynchronised with respect to an honest partner, with no possibility to resynchronise.

Note that KCI attacks affect also the static DH scheme (when a party uses a fixed DH share, whereas the other generates a fresh ephemeral one [25]).

Another consequence of the dependency of the master keys in SAKE, is that once the keys are compromised, an adversary can passively compromise all subsequent session keys. This is not the case in general with ephemeral DH. Yet, this is also true regarding non-DH public-key protocols (e.g., TLS-RSA), but also ephemeral DH (in some pathological cases) when reduced size (fixed) public parameters are used [5].

Computations. The DH scheme implies heavier computations (modular exponentiations, elliptic curve point multiplication) than SAKE which is solely built on symmetric-key functions. In practice, SAKE is likely more suitable to be implemented on constrained devices which have limited computational (and communication) capabilities.

7 Conclusion

We have described SAKE, an authenticated key exchange protocol in the symmetric-key setting. Although this protocol is solely based on symmetric-key algorithms, it provides perfect forward secrecy without requiring any additional procedure (e.g., resynchronisation phase) or functionality (e.g., shared clock). The underlying idea is to make the shared master keys evolve. We solve the synchronisation problem that stems from this evolving principle with an elegant and efficient solution.

SAKE guarantees that, whatever the synchronisation state of the involved parties prior to the session, both parties share a new session key, and their internal state is updated and synchronised, once a correct session is complete: SAKE is self-synchronising. As in the public-key setting, our protocol allows an (virtually) unlimited number of sessions. Furthermore, we prove that SAKE is sound, and provide a formal proof of its security in a strong model.

Finally, we describe SAKE-AM, a complementary mode of our protocol, which, used in conjunction with SAKE, results in an implementation that gathers all the aforementioned properties (starting with forward secrecy). This implementation allows any party to be initiator or responder of a session, such that the smallest amount of calculation is always done by the same party. This is particularly convenient in the context of IoT where a set of (low-resource) end-devices communicates with a back-end server.

To the best of our knowledge, this is the first protocol with perfect forward secrecy in the symmetric-key setting that is comparable to the DH scheme, beyond the intrinsic distinction between public-key and symmetric-key cryptography.