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

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.