Why is this authenticated Diffie–Hellman key exchange insecure?

Question

I was searching for the information on authenticated Diffie–Hellman key exchange and found these slides. The author says, “Remember $$A\to B: (A, g^x, \operatorname{SIG}_a((g^x, B)))$$ $$B\to A: (B, g^y, \operatorname{SIG}_b((g^y, A)))$$ insecurity”. I fixed the mistake with $A\to B$, replaced public keys with secret ones in the signature function and added sender identifiers. I do not understand why this protocol is insecure, and I can't find anything about this protocol. I understand it as follows. Upon receiving the first message $(C, X, s)$, Bob aborts if $s$ is not a signature of $(X, B)$ by $C$, otherwise generates $y$, sends $(B, g^y, \operatorname{SIG}_b((g^y, A)))$ and associates the session key $X^y$ with $C$. Upon receiving the second message $(C, Y, s)$, Alice aborts if $s$ is not a signature of $(Y, A)$ by $C$ or $C\neq B$, otherwise associates $Y^x$ with $C$ (Bob).

I have been unsuccessfully trying to implement the attack described in “3.1 BADH and the identity-misbinding attack: A motivating example” in “SIGMA: the ‘SIGn-and-MAc’ Approach to Authenticated Diffie-Hellman and its Use in the IKE Protocols” by Hugo Krawczyk. This and related papers are the only material on the subject I could find. Suppose that Darth posesses a secret key $d$ and the corresponding public key $D$. Since Alice initiates the session, Alice will think that she is talking to Bob anyway. If Darth replaces the first message with $(D, g^x, \operatorname{SIG}_d((g^x, B)))$, Bob will send $(B, g^y, \operatorname{SIG}_b((g^y, D)))$. I do not see how Darth can persuade Alice to start the session using $g^y$ since Darth does not have $\operatorname{SIG}_b((g^y, A))$.

Answer 1

The attack described is an identity misbinding attack; it is an authentication vulnerability where two protocol participants have divergent views of who is involved in the conversation. In a nutshell, Alice and Bob complete the key exchange protocol (and optionally continue sending messages to each other). Still, Alice may think she is talking to Charlie, while Bob believes he is talking to Alice. I'll give some more motivation for the attack at the end. But let's first look at the case of BADH (AKA: Badly Authenticated Diffie-Hellman).

Insecurity of BADH

Consider the first protocol message $$A \to B: (A, g^x, \operatorname{SIG}_b((g^x, B)))$$.

Assume that Charlie replaces the first message message with $$(C, g^x, \operatorname{SIG}_c((g^x, B)))$$ That is: Charlie replaces the initiator's identity, computes a signature under its public key, forwards this new message to Bob, and forwards the next protocol message unchanged.

Observe that from Bob's perspective, the first message can be verified as coming from Charlie. Later, Alice concludes the key exchange as she happily verifies a signature from Bob. In the end, Bob thinks he is talking to Charlie, and Alice thinks she is talking to Bob.

A few remarks are in order:

1. This is not an attack on the secrecy of the key: Charlie doesn't know the key Alice and Bob are using in their subsequent session!
2. The attack works because Bob doesn't know who will want to talk to them beforehand. This is not an unrealistic scenario, as I expand on below.
3. The attack works even if a malicious Charlie uses a legitimately (understand, randomly) generated signing key. This is important in the adversarial model; I'll expand below.
4. Replays are another issue with this protocol. Charlie can leverage a replay to break authentication as well. Arguably, in a different sense.

How to prevent this: The basic prevention strategy is: first, use a better AKE. Second, include the identities of both peers in the key derivation. For instance, $K = \mathrm{KDF}(g^{xy}, g^x, g^y, A, B)$. And in general, the session key should really depend on the entire communication transcript.

Misbinding attacks

This attack looks strange and unmotivated, but let's see where it makes sense to care about this. The scenario is quite relevant in AKEs that allow post-specified peers: Bob (wlog) may not know beforehand that it wants to talk to Alice. For instance, Bob may be a server with mandatory client authentication. Bob cannot know in advance which of the many clients is trying to establish a connection. But, it is desirable for an authenticated key exchange protocol (AKE) to guarantee that the identity claims are indeed valid. Consider this example where an identity misbinding attack would be bad: Alice uses BADH to log into an online store where she wishes to redeem a voucher that tops up a balance on her account. The online store uses BADH with mandatory client authentication, allowing users to log into their accounts directly. Meanwhile, Charlie mounts a misbinding attack; the unsuspecting Alice goes directly to the top-up page and enters the voucher code. Consequently, the online stores thinking that they authenticated Charlie will end up topping Charlie's account up.

Attacker model:

As discussed, this attack can be mounted even if the attacker uses honestly generated keys. Which sort of approximates a real-life scenario where users in the systems somehow have to prove knowledge of a secret key to a Certificate Authority before receiving a signed certificate. This assumption can be argued as non-realistic, and the paper ASICS: Authenticated Key Exchange Security Incorporating Certification Systems proposes models considering issues with Certification Systems.

And, once you give the attacker more liberties, you can have stronger attacks where for example, Charlie only changes the identity bit but nothing else.

Answer 2

My guess is that when it is written approximately

Can we really have a non-replayable 2-msg protocol?
□ Remember (the question's protocol) insecurity

the author is thinking about an attacker capturing the first message of the exchange $(A, g^x, \operatorname{SIG}_a((g^x, B)))$ and using a replay of that to impersonate Alice.

There are two variants:

• Declaring victory just because Bob thinks (and the logs of its machine show) that Alice connected again, when she did not.
• Further, if Alice leaked the $x$ she used in the past, that allows the attacker to get the new shared secret by doing just as Alice normally does, and fully impersonate Alice.