Advanced Topics

Authenticated Key Exchange

Key exchange allows two participants to establish a shared key. But how can you be sure that your KE partner is who you think they are? Consider the following classical person-in-the-middle attack scenario against Diffie-Hellman KE:

Alice believes she shares a key $g^{ab}$ with Bob, and Bob believes he shares a key $g^{cd}$ with Alice. In reality, they each share a key with the adversary. If Alice encrypts a message using $g^{ab}$ , intending it for Bob, the adversary can decrypt it. The adversary can re-encrypt it (or even a different message) under $g^{cd}$ and Bob will believe that the message comes from Alice.

This chapter is about how to authenticate key exchange. How can Alice be sure that she has established a shared key with Bob, and not with some impostor?

18.1. Defining the problem

The informal goal of authenticated key exchange (AKE) is to establish a shared key with a particular person. In cryptography, we talk about identity in terms of knowledge of keys. Expressed in those terms, the goal of AKE becomes:

I know a public key that I associate with a particular person.
I want to establish a key that only someone with the corresponding private key can learn.

Plain, unauthenticated KE protocols require no inputs; their goal is to establish a shared secret starting from literally nothing. An authenticated KE protocol must start from something because it authenticates with respect to a pre-existing understanding of someone's identity. To run an AKE protocol, each user must provide:

their own private key, needed to authenticate themselves to their partner; and
the public key of their intended partner.

Right now we are being intentionally vague about the nature of these public/private keys—are they digital signature keys, are they something else? The following sections will explore two very different approaches to AKE involving different kinds of public key material.

Regardless of its structure, a user's private key is considered their long-term secret. In each execution of the AKE protocol, the users will additionally use randomness that is unique/fresh to this execution. This randomness is called their ephemeral secret. When reasoning about AKE security, long-term and ephemeral secrets contribute different properties.

18.1.1. The security model

The intuitive goal of AKE is simple (although subtle) to state:

If I run an AKE protocol, intending to authenticate to a particular public key, then I should either fail with an error, or obtain a key that only myself and someone who knows the corresponding private key could know.

Yet formalizing this simple goal is surprisingly difficult. The standard security definition for AKE from the research literature is much more complicated than anything we have seen in this book. I tried to formulate a simpler definition that illustrates the main principles but failed to write one that fits in one page. (So instead, I wrote three pages explaining it informally.)

What is it about AKE that makes a formal definition so complicated? First, AKE is an interactive protocol. And unlike the case of plain KE, where we considered an adversary who merely passively eavesdrops, the AKE security involves an adversary who actively participates. Some attacks, like the person-in-the-middle attack, inherently involve more than one victim and more than one protocol session. Second, the precise security guarantees are subtle and require the library to do a great deal of bookkeeping.

What follows is a summary of how AKE security is formally defined:

Basic Adversarial Capabilities: The adversary can perform the following actions:

The adversary can instantiate new victims. For each victim, the library generates a keypair, stores the private key and gives the public key to the adversary.
The adversary can instruct any victim to start a new session of the AKE protocol. Remember, the AKE protocol requires two inputs: the user's private key and the public key of their intended partner. The adversary can specify the choice of victim, which determines the private key, and can choose the intended partner public key. This key can be that of another victim, or one completely chosen by the adversary.
For any initialized session, the adversary can choose its next incoming protocol message and see the resulting outgoing protocol message. Think of an adversary with complete control over the network, a built-in person in the middle. So the adversary could choose to initialize two sessions with two victims, and reliably route protocol messages between them. But they could also choose arbitrarily tamper with protocol messages, or completely play the role of the protocol partner.
When a session finishes, the adversary can observe its output key.

A library that implements this complex interface must keep track of victims' private keys, as well as the secret state information that each session maintains between protocol rounds. It can also help for the library to keep track of the entire transcript of each session, including both its incoming and outgoing messages.

Pseudorandom Keys and Partnered Sessions: An AKE protocol should output a key that looks pseudorandom to the adversary. We formalized this property for plain KE (definition 13.3.3) by defining two libraries: one that outputs the KE session's key and another that outputs an unrelated, uniformly chosen key. We can take the same approach for AKE, with one important caveat.

Suppose the adversary creates two sessions where victims Alice and Bob intend to partner with each other, and then the adversary faithfully relays protocol messages between these sessions, without any modifications. We call these sessions partnered. Essentially, the two victims are running an AKE session completely as intended, so we expect them to output the same key, not unrelated keys!

Thus, the libraries for AKE security must keep track of which pairs of sessions are partnered, and ensure that partnered sessions always output the same key. In one library this will be the actual AKE output key, and in the other it will be uniformly chosen.

Forward Secrecy: Complicating the situation even further, AKE security definitions generally strive for forward secrecy. The definitions capture this property by giving the adversary an additional capability:

The adversary can reveal a victim's long-term secret, and/or the ephemeral secrets of any session.

If the adversary obtains these secrets, some problematic consequences are simply inevitable. In particular:

Alice's long-term private key is what allows Alice to authenticate herself to others. An adversary who steals it will inevitably be able impersonate Alice to anyone.
Alice computes the session key as a function of the session's transcript, her long-term secret, and her ephemeral secret for this session. The adversary already sees (and controls) the transcript, so if they additionally steal Alice's long-term secret and her ephemeral secret from some session, they will inevitably be able to learn the session key. In other words, the key for that session cannot look pseudorandom.

The philosophy behind AKE security is that inevitable losses of security are the only losses of security. For example, here are a few outcomes that are not inevitable, and therefore the AKE security definition forbids them:

An adversary who steals Alice's long-term secret should not gain the ability to compute the key from a previous session. This is the classic scenario outlawed by forward secrecy.
An adversary who steals Alice's long-term secret should not gain the ability to compute the key from a subsequent session that Alice herself participates in. This should be possibly only if the adversary also steals the ephemeral secret of that target session.
An adversary who steals Alice's long-term secret should not gain the ability to impersonate others to Alice, only to impersonate Alice to others.
An adversary who steals Alice's ephemeral secret from a session should not gain the ability to impersonate Alice to others.
An adversary who steals Alice's ephemeral secret from a session should not gain the ability to compute the key from a different session (without also stealing that session's ephemeral randomness and Alice's long-term secret).
An adversary who steals both Alice and Bob's long-term secrets should not gain the ability to compute the key from a session between the two of them, without also stealing the ephemeral secret from at least one of them.

Even more things to worry about: The discussion so far reflects the standard way to define security for AKE. As if that weren't complicated enough, there are yet more security properties that one might want to consider in an AKE protocol:

Deniability: When Alice authenticates to Bob, does their interaction leave Bob with proof that they communicated? Could Bob blackmail Alice with this proof?
Anonymity: In an AKE interaction, a user might not know their partner's identity in advance. Instead, they might expect to learn their partner's identity in the process of the protocol. When exactly should Alice's identity be revealed to her partner? Can it be hidden until after Alice is convinced of her partner's identity?

These extra properties can be incorporated into the security definition, complicating it even further.

18.2. Authenticating with signatures

Signatures are a natural way to add authentication to a KE protocol. However, there are many potential pitfalls that make it tricky to apply them correctly. This section explores several ways to incorporate signatures into KE, and the resulting consequences on security.

We will assume that each user's long-term public key is the verification key from a signature scheme. The corresponding signing key is their long-term secret. All of the protocols in this chapter will be based on Diffie-Hellman KE.

18.2.1. Attempt: sign your Diffie-Hellman message

Anyone who has learned about key exchange and digital signatures would probably propose the following AKE protocol. Each user simply signs their KE protocol message and verifies their partner's corresponding signature.

This simple protocol has several problems, but for the purposes of illustration, let's focus on just one. Alice's ephemeral secret is her DH exponent $a$ . Consider an adversary who eavesdrops on one of Alice's sessions and also steals her ephemeral secret. This adversary now knows a value $g^a$ , its discrete log $a$ , and a signature from Alice of $g^a$ ; this is enough to impersonate Alice to anyone!

Remember, the ability to impersonate Alice is inevitable only when the adversary steals her long-term secret, not her ephemeral secrets. Since the attack in this example is not inevitable, it is outlawed by the AKE security definition.

18.2.2. Attempt: sign both Diffie-Hellman messages

Perhaps the problem with the previous protocol can be repaired by signing more information. Suppose the users sign both Diffie-Hellman messages, as below. This change requires them to wait until both Diffie-Hellman messages have been sent.

This modified protocol indeed fixes the problem from before; can you see why? The adversary now has a signature from Alice on the pair $(g^a, g^b)$ , which is useless unless the adversary participates in a session where the DHKE messages are $g^a$ and $g^b$ . The adversary may attempt to impersonate Alice to some victim by replaying $g^a$ , but it cannot control the victim's choice of $g^b$ . Only with negligible probability will a victim repeat the $g^b$ from the original session. In order to successfully impersonate Alice, the adversary will need to produce a signature under her (Alice's) public key of a new, different DHKE transcript.

However, the new protocol is still susceptible to another subtle attack, called an identity misbinding attack. (The previous protocol also suffers from the same flaw.) Consider the following attack scenario involving Alice, Bob, and Charlie.

Alice is attempting to establish a connection with Charlie.
Bob is attempting to establish a connection with Alice.
Charlie is mounting an attack.

Charlie simply forwards protocol messages between Alice and Bob, with one exception: He replaces Bob's signature $S_B$ with a signature (of the same data) under his own signing key, which is of course possible since he knows his own signing key. Now consider the situation from Alice's and Bob's perspective:

Alice sees a valid signature of $(A,B)$ under Charlie's key, so she computes the session key as $g^{ab}$ and concludes that she has successfully established a session with Charlie.
Bob sees a valid signature of $(A,B)$ under Alice's key, so he computes the session key as $g^{ab}$ and concludes that he has successfully established a session with Alice.

Thus, Alice and Bob share a common key, but they disagree on whom they share it with!

It's important to acknowledge that in this scenario Charlie does not know their key $g^{ab}$ . Still, it violates our intuitive understanding of AKE security. Specifically, Alice intends to partner with Charlie, so her AKE protocol session should result in a key that only she and Charlie know. That's not the case here, since Bob knows the key.

To make the security problems more concrete, imagine that Bob uses his session key $g^{ab}$ to encrypt a message. Charlie can forward that ciphertext to Alice, and she can decrypt it using her key $g^{ab}$ . She believes—incorrectly!—that only she and Charlie know $g^{ab}$ , so she will attribute the contents of the ciphertext to Charlie. So although Charlie does not know the contents of this ciphertext, he has stolen credit for it. Proper authentication should attribute actions to the correct identities.

18.2.3. Sign the identities, too!

Although it seemed like the users in the previous example were signing “everything,” that's not entirely accurate. They authenticate their Diffie-Hellman messages, but not anything about the identities of the intended protocol participants.

In the following protocol, each user now signs the public key of their intended partner. Public keys are the technical manifestation of identity in an AKE protocol, so you can think of the users in this protocol as signing their intended partner's identity.

The identity misbinding attack from the previous section fails against this protocol. In that attack, Alice intends to establish a key with Charlie, so she will include Charlie's identifier in her signature. But Bob is expecting a signature from Alice that names himself; Charlie cannot produce such a signature, so the attack fails.

This protocol achieves the important security properties that we have been discussing so far, and it can be proven secure with respect to the standard AKE definition. However, there's still more to say about its security. When Alice participates in this protocol, she generates a signature of the tuple $(A,B,\pk_B)$ , which includes Bob's identity/public key. Bob obtains this signature, and if he shares it with others, he can use it to prove that Alice attempted to establish a key with him. Only Alice could have generated such a signature that verifies under her public key—this is, after all, the defining purpose of signatures. This authentication method is not deniable.

18.2.4. The SIGMA protocol

The ISO protocol from the previous section presents an interesting dilemma: On the one hand, Alice must sign Bob's identity; without this signature, the protocol is vulnerable to identity misbinding attacks. On the other hand, her signature leaves behind proof of her intention to interact with Bob; it is not deniable. It might seem impossible to authenticate Alice without sacrificing deniability.

The SIGMA key exchange protocol (which stands for SIGn and MAc) is a clever way to improve the deniability properties of the ISO protocol. The main idea is to authenticate the Diffie-Hellman messages $(g^a, g^b)$ with a signature, but authenticate the participant identities using symmetric-key authentication (i.e., a MAC/PRF).

A MAC is deniable because, unlike in a signature scheme, the same information is used to generate a MAC tag and to verify it. If Bob can verify a tag from Alice during a protocol, then he could have also generated the tag himself. The tag is no proof of anything; at best, it might be proof that someone who knew the MAC key generated the tag (either Bob or whoever was his protocol partner).

Going back to the SIGMA protocol, since a MAC is a symmetric-key primitive, we must ask what shared key Alice and Bob can use as the MAC key. Remember: The reason to authenticate each other's identities is to thwart an identity misbinding attack. In such an attack, the adversary doesn't learn the Diffie-Hellman key. Thus, they can use the Diffie-Hellman key as a MAC key to authenticate their identities.

This is the main idea behind SIGMA, but there are some minor details to attend to: A key exchange protocol should output a key that is independent of everything else that happened within the protocol itself. So it is not advisable to use the Diffie-Hellman key as both the AKE output and as a MAC key within the protocol. Instead, users must first expand the Diffie-Hellman key using a PRG into three keys: one for Alice's MAC, one for Bob's MAC, and one to output as the session key. (Alice and Bob can't use the same MAC key, for subtle reasons.)

Construction 18.2.1 (SIGMA protocol)

Let $G$ be a secure PRG with output length $3\secpar$ , and let $F$ be a secure PRF. Then the SIGMA protocol for key exchange is defined as follows:

The SIGMA protocol can be proven secure in the standard AKE security model.

Deniability properties: The SIGMA protocol is better than the ISO protocol with respect to deniability. When Alice and Bob run the protocol, Alice leaves behind a signature only on the pair $(A,B)$ , but not including any partner identity. This signature still serves as proof that Alice ran the protocol, but it does not implicate her choice of intended partner as in the ISO protocol. The MAC she generates proves nothing because she is not the only one who could have generated it.

Later in chapter 19 we discuss approaches to authentication that achieve an even stronger level of deniability. Alice can authenticate herself to Bob in a way that leaves absolutely no trace.

18.3. Authenticating implicitly

Given the importance of signatures in the previous section, you might expect signatures to be a necessary ingredient in any AKE protocol. This section describes a completely different approach to AKE, in which the users' long-term keys are not signature keys but simple DHKE messages. Alice's private key is $a \in \Z_\nmod$ and her public key is $A = g^a$ . Bob's private key is $b \in \Z_\nmod$ , and his public key is $B = g^b$ .

Without signatures, you might wonder how the users can possibly authenticate each other. The answer is to think about authentication in a new way. Suppose Alice intends to establish a key with Bob; her key exchange protocol can authenticate him in one of two ways:

Explicit authentication: If Bob is being impersonated, then the key exchange protocol will raise an error. The protocols from the previous section have this flavor; they raise an error when a signature fails to verify.
Implicit authentication: The protocol always terminates with a key that only Alice and Bob could possibly know. If Alice is interacting with someone impersonating Bob, then Alice gets no overt indication (yet) that Bob is being impersonated, but she outputs a key that the impostor will not know.

Implicit authentication assumes that either something “downstream” of the key exchange will fail noticeably when the two users use different keys (e.g., an authenticated encryption scheme will raise a decryption error), or that the consequences of using the wrong key are innocuous (e.g., what is the harm if I encrypt something under a key that the adversary doesn't know?).

Implicit authentication might sound strange at first. Why is it a feature to not know whether your KE partner is who they claim? Here are two reasons why you might favor implicit authentication:

Implicit authentication protocols can use fewer rounds. Indeed, the AKE protocols in this section require only one message from each user, and these messages can be sent simultaneously, just like unauthenticated DHKE. The explicit-authentication protocols in the previous section required sequential rounds, because each user needed to sign their partner's DHKE message.
Imagine an application that uses an AKE implementation from a cryptographic library (here I mean library in the standard software-engineering sense). It's not hard to imagine that a careless calling application could misinterpret an error output as the all-zeros key. Imagine the harm if the application then proceeds to encrypt sensitive information under the all-zeros key, thinking that only the intended partner knows it! Within this scenario, it may be safer for the AKE protocol to never output an error and instead output a pseudorandom key that no one else knows.

18.3.1. Attempt: why communicate at all?

In this section, we assume Alice has published long-term key $A = g^a$ and Bob has published $B=g^b$ . An obvious question is, why don't they just take $g^{ab}$ to be their shared key? This would be an authenticated key exchange protocol that requires no communication!

Indeed, if we assume that only Alice knows $a$ and only Bob knows $b$ , then only Alice and Bob can know $g^{ab}$ . However, one notable problem with this trivial “protocol” is that whenever Alice and Bob run it, they clearly always obtain the same key. We would like multiple instances of AKE protocols to result in independent, pseudorandom keys.

More precisely, the AKE security definition allows an adversary to learn the output key from any session, and this should not make it any easier to predict or compute the key from another session, even between the same pair of users. If keys from one session are useful in guessing keys from another session, we say that the protocol suffers from a related-key attack.

18.3.2. Attempt: incorporate nonces

To avoid related-key/same-key attacks, the KE protocol must include some variability each time it is run. Consider the following proposal, in which Alice announces a uniformly chosen nonce $R$ :

In other words, the users terminate with $\ro( g^{ab}, R)$ as their shared key. Here we treat $\ro$ as a random oracle, so that every distinct $R$ leads to an independently uniform session key $\ro(g^{ab}, R)$ . A PRF would suffice for this example, but a random oracle is useful for the other protocols in this section.

This protocol avoids related-key attacks, but it does not provide forward secrecy. Suppose Alice and Bob complete a session of this protocol. If, at some later time, the adversary learns Alice's long-term secret key $a$ , then the adversary can recover the session key as $\ro( B^a, R )$ .

18.3.3. Attempt: incorporate ephemeral Diffie-Hellman

The previous protocol incorporated ephemeral variability, but not ephemeral secrets. Ephemeral secrets are necessary to provide forward secrecy; they are the only defense protecting session keys against leakage of the long-term secrets.

Below is an idea for an AKE protocol, in which the users perform an ephemeral Diffie-Hellman key exchange to complement the DHKE between their long-term keys.

In other words, the shared key is $\ro( g^{ab}, g^{xy})$ , where $g^{ab}$ is the long-term DH shared key and $g^{xy}$ is the ephemeral DH shared key. This protocol's design is motivated by the following security intuition, expressed from Alice's point of view:

Given my public key $g^a$ , only Bob (i.e., someone who knows $b$ ) can compute $g^{ab}$ .
Given my ephemeral Diffie-Hellman message $g^x$ , only the person who sent me $g^y$ can compute $g^{xy}$ .
In the random oracle model, only someone who knows both $g^{ab}$ and $g^{xy}$ can compute $\ro( g^{ab}, g^{xy})$ .

It is tempting to conclude that the only one who can learn the final output key is Bob, and only when he is Alice's partner. Unfortunately, this intuition is not completely accurate. Specifically, the first statement is incorrect and should be revised:

Given my public key $g^a$ , only Bob—or someone who has stolen my long-term secret $a$ !—can compute $g^{ab}$ .

To model forward secrecy, AKE security definitions allow the adversary to steal long-term secret keys. An adversary who steals Alice's long-term key will always gain the ability to impersonate Alice to others. However, in this protocol, such an adversary can also impersonate anyone to Alice! Here's how:

This kind of attack is called a key compromise impersonation (KCI) attack. Remember, the only inevitable consequence of leaking Alice's long-term secret is that the adversary can impersonate Alice to others. Anything beyond the inevitable, like the adversary impersonating others to Alice, is considered an attack by the AKE security definition.

18.3.4. Attempt: mix long-term and ephemeral secrets

Here is another approach at AKE that combines the long-term and ephemeral Diffie-Hellman messages in a different way:

In other words, the users terminate with $\ro( g^{xb}, g^{ay})$ as their shared key. Each of the terms $g^{xb}$ and $g^{ay}$ combines one user's long-term secret with the other user's ephemeral secret. In an exercise, you are asked to explain why this modification prevents the KCI attack from the previous example.

However, this protocol still fails to provide forward secrecy. Suppose Alice and Bob use this protocol to establish a key. Later, an adversary who steals both Alice and Bob's long-term secret keys ( $a$ and $b$ ) can compute the session key as

\ro( X^b, Y^a ).

In the AKE security definition, leaked long-term secrets, even those of both participants, should not help the adversary learn a session key! The adversary should be able to compute a session key only if it steals both the long-term and ephemeral secrets from a user.

18.3.5. Triple Diffie-Hellman

The triple Diffie-Hellman (3DH) protocol adds forward secrecy to the previous protocol, by including an entirely ephemeral Diffie-Hellman shared key into the random oracle's input:

In other words, the users terminate with $\ro( g^{xb}, g^{ay}, g^{xy} )$ as their shared key. Now both long term keys $a$ and $b$ are useless in helping an adversary predict $g^{xy}$ , so the protocol does not suffer from the same attack on forward secrecy as the previous example. The 3DH protocol can be proven secure with respect to the standard AKE security definition.

18.4. Authenticated key exchange in practice

TLS: Transport Layer Security (TLS) is the protocol that provides security for web connections online. It is the most widely used real-world application of cryptography. We illustrate the main ideas of TLS by imagining a client web browser making a hypothetical connection to the website joyofcryptography.com.

As we discussed in section 16.3.2, the website has a public key $\pk$ along with a certificate (or perhaps certificate chain). The certificate proves that some trusted CA believes that $\pk$ is indeed a public key owned by someone who controls this domain name. At the time of connection, the website presents $\pk$ and its certificate, which the browser then verifies.

Then, the browser and website run an AKE protocol, whose purpose is to authenticate the website with respect to $\pk$ . The goal of TLS is unilateral, or one-sided, authentication: Only the server's identity is authenticated. The TLS specification supports bilateral authentication, in which the client authenticates itself to the server, but this feature is not used in most everyday situations.

The latest version of TLS (1.3) uses an AKE based on the SIGMA protocol from section 18.2.4. SIGMA is a good fit for TLS because it authenticates with respect to signing keypairs, and the infrastructure for certificates is already built around signatures.

Signal: The Signal encrypted messaging protocol also uses an AKE to establish a key between users. However, encrypted messaging presents a very different set of constraints than web connections. A web connection is synchronous: The client and server are online simultaneously at the time of connection. But encrypted messaging is highly asynchronous. Users cannot be expected to be online at the same time, so messages between users are routed through a central server, which can temporarily store messages for a user until they come online again. It can take hours or days between sending a message and receiving a reply. An AKE protocol requiring many rounds would be rather inconvenient.

Thus, the Signal protocol uses a variant of the 3DH protocol (section 18.3.5), called Extended Triple Diffie-Hellman (X3DH), which requires only one asynchronous message from each user. Signal uses a centralized server to store and relay these protocol messages, as follows:

Beforehand, Bob generates a public key and a collection of ephemeral 3DH protocol messages, and privately remembers the corresponding ephemeral randomness. He gives these protocol messages to the server to be stored.
When Alice wants to start a new session with Bob and establish a shared key, she contacts the Signal server. It gives her one of Bob's pre-generated 3DH messages (and discards it).
Alice can generate her own ephemeral 3DH message. Since 3DH requires a single message from each user, she can immediately compute the resulting key and use it to start sending encrypted messages right away. 3DH is implicitly authenticated, so only Bob will be able to decrypt these ciphertexts. Alice can send her response and any encrypted messages to the Signal server to store until Bob is online.

As usual, we face the question of how to associate a person Bob to a public key. In the Signal protocol, each user must trust the server to relay the public key that Bob has generated. If the server relays a public key that it generated itself, then the server can become a person-in-the-middle and can read or tamper with the users' unencrypted messages. If Alice and Bob are victims of such an attack, then they will hold different AKE keys. Messaging applications provide a way for users to compare their AKE keys, and this is best done out-of-band of the application and its relay server (e.g., in person or over a different medium).

Forward Secrecy: In both of these real-world applications, it is impossible to overstate the importance of forward secrecy. Think about all the sensitive data currently being encrypted and transmitted on the web and using messaging applications. Now imagine a powerful government agency that collects all of this encrypted traffic with the intent to opportunistically decrypt it later. Forward secrecy protects this traffic, even if the secrets are later lost or stolen.

Exercises

Users in the protocol from section 18.2.3 sign the identifier of their intended session partner. Suppose instead that each user signs their own identifier. In other words, Alice will generate her signature as $S_A := \Sign(\sk_A, (A,B,\hl{\pk_A}))$ , and Bob will verify it accordingly. Does this modification also prevent the identity misbinding attack from section 18.2.2? Explain why or why not.
Users in the protocol from section 18.2.3 sign both Diffie-Hellman messages. Suppose instead that each user signs only their own Diffie-Hellman message, along with their partner's identifier. In other words, Alice will generate her signature as $S_A := \Sign(\sk_A, (\hl{A},\pk_B))$ , not including $B$ , and Bob will verify it accordingly. Describe an attack against this modified protocol.
In the SIGMA protocol (construction 18.2.1), the participants expand $g^{ab}$ into three keys: $\key_A \| \key_B \| \key_S$ . Then Alice sends MAC tag $F(\key_A, (\pk_A,\pk_B))$ and Bob sends MAC tag $F(\key_B, (\pk_A,\pk_B))$ .

Suppose instead that $g^{ab}$ is expanded into only two keys, and both users use the same MAC key. Alternatively, fix $\key_A = \key_B$ in the description of SIGMA. Show an attack against this protocol variant.
Suppose all users have a long-term public key $(\pk^{\text{sig}}, \pk^{\text{kem}})$ , where $(\sk^{\text{sig}}, \pk^{\text{sig}})$ is the keypair for a secure digital signature scheme and $(\sk^{\text{kem}}, \pk^{\text{kem}})$ is the keypair for a CCA-secure KEM. Find as many things wrong with the following AKE as you can.
Suppose all users have a long-term public key that is the verification key of a secure digital signature scheme. Suppose they also have access to a CCA-secure KEM. Find as many things wrong with the following AKE as you can.
Explain why the protocol in section 18.3.4 does not suffer from the same key compromise impersonation attack as the one in section 18.3.3.
Does the protocol in section 18.3.3 have forward secrecy?

Suppose Alice and Bob have long-term keys $g^a$ and $g^b$ , and they perform an ephemeral DHKE, exchanging $g^x$ and $g^y$ . There are four natural DH shared keys they could compute:

g^{ab}, g^{ay}, g^{xb}, g^{xy}.

We can obtain an implicitly authenticated AKE protocol by hashing (with a random oracle) three out of these four values. There are four ways to do so, leading to the following four AKE variants:

output key	security?
$\ro( g^{ab}, g^{ay}, g^{xb}\phantom{, g^{xy}} )$	??
$\ro( g^{ab}, g^{ay}, \phantom{g^{xb},} g^{xy} )$	??
$\ro( g^{ab}, \phantom{g^{ay},} g^{xb}, g^{xy} )$	??
$\ro( \phantom{g^{ab},} g^{ay}, g^{xb}, g^{xy} )$	3DH: secure $\checkmark$

The last variant is the 3DH protocol. What can you say about the security of the other three variants?

Consider the following idea for an implicitly authenticated key exchange protocol. Alice's public key is $A=g^a$ and Bob's is $B=g^b$ . They perform an ephemeral Diffie-Hellman with Alice sending $X =g^x$ and Bob sending $Y=g^y$ . The final session key is then:

$g^{(a+x)(b+y)} = \begin{cases} (BY)^{a+x}, & \text{ as computed by Alice;} \\ (AX)^{b+y}, & \text{ as computed by Bob.} \end{cases}$

Show how an adversary can impersonate Bob to Alice, without stealing Bob's long-term secret. In other words, the adversary can run the protocol, pretending to be Bob but not knowing $b$ (or $a$ for that matter), and successfully learn the key that Alice outputs.
Consider the following idea for an implicit-authentication AKE. Alice's public key is $A=g^a$ and Bob's is $B=g^b$ . They perform an ephemeral Diffie-Hellman with Alice sending $X =g^x$ and Bob sending $Y=g^y$ . The final session key is then:

$g^{ay + xb} = \begin{cases} Y^a \cdot B^x, & \text{ as computed by Alice;} \\ X^b \cdot A^y, & \text{ as computed by Bob.} \end{cases}$

Show how an adversary can impersonate Alice to herself, without stealing her long-term secret. This means we consider $A=B$ in the above description, although the adversary does not know $a$ .

Chapter Notes

The first formal security definitions for AKE were given by Bellare and Rogaway [27]. The current standard definition is called the SK security model, and is due to Canetti and Krawczyk [59,60]. Key-compromise integrity attacks (where leakage of Alice's long-term secret allows the adversary to impersonate others to her) were first observed by Just and Vaudenay [129]. Identity misbinding attacks were first observed by Diffie, van Oorschoot, and Wiener [85] but named by Krawczyk [141]. They are also called unknown key share (UKS) attacks.

The sequence of illustrative protocol examples in section 18.2 is inspired by Hugo Krawczyk's insightful lectures on AKE [142].

The protocol described in section 18.2.3 is due to Canetti and Krawczyk [59]. It is sometimes referred to as the “ISO-9798 key exchange,” although this ISO standard does not define any key exchange protocols [11]. More accurately, the protocol is Diffie-Hellman key exchange, augmented with the interactive authentication method of ISO-9798-3.

The SIGMA technique for AKE was proposed by Krawczyk [141].

The protocols from sections 18.3.3 and 18.3.4 are due to Blake-Wilson, Johnson, and Menezes [46], where they are named “protocol 3” and “protocol 4,” respectively. Kudla and Paterson [143] provided further security analysis of protocol 4 and also suggested the modification that results in 3DH (section 18.3.5). The NAXOS protocol of LaMacchia, Lauter, and Mityagin [145] also uses the same combination of three Diffie-Hellman secrets, although the ephemeral exponents are chosen in a slightly different way. A variant of 3DH, called X3DH [153], is the key exchange protocol used in the Signal messaging protocol, which is used by Facebook Messenger, WhatsApp, and Google's messaging application. The security of X3DH and the Signal protocol as a whole was studied by Cohn-Gordon, Cremers, Dowling, Garratt, and Stebila [69].

The protocol in exercise 18.10 is due to Matsumoto, Takashima, and Imai [154], and the self-impersonation attack against it was pointed out by Just and Vaudenay [129].

A comprehensive security analysis of the TLS 1.3 protocol was given by Dowling, Fischlin, Günther, and Stebila [88].