If KCI allows MitM attacks, how are ephemeral exchanges an effective mitigation?

Question

Key Compromise Impersonation (KCI)^(0,1) is a failure mode in Authenticated Key Exchanges (AKE) where a client $A$ has their static Diffie-Hellman (DH) identity key pair $(K_{priv}^{A_{ID}}, \space K_{pub}^{A_{ID}})$ compromised by an adversary $V$. With $A$'s private identity key, $V$ is able to spoof authenticated connections, from $A$'s perspective, with another party $B$ with identity key pair $(K_{priv}^{B_{ID}}, \space K_{pub}^{B_{ID}})$ because $V$ can also calculate $K_{shared}^{AB} = K_{priv}^{A_{ID}} \circ K_{pub}^{B_{ID}}$.

This attack was applicable to protocols like TLS^(2,3) and Tox^(4,5). However, I don't understand how the advice to use ephemeral key exchanges⁽⁶⁾ as a means of mitigation can help in DH-only AKEs, since ephemeral DH doesn't prevent MitM attacks, which KCI allows. How does adding ephemeral DH mitigate KCI attacks in signatureless AKEs, and is ephemeral DH sufficient? If not, what are sufficient mitigations?

Answer 1

Let Alice's keypair be $(a, g^a)$ and Bob's be $(b, g^b)$. Now suppose the adversary steal's Alice's key $a$. Of course the adversary can now impersonate Alice to others. This question is asking about KCI attacks, where the adversary is able to impersonate others to Alice. Not all protocols protect against this.

Structure of implicitly authenticated protocols:

Suppose the parties also do an ephemeral DHKA with $g^x, g^y$. Alice knows $x$ and her actual partner knows $y$. Considering these ephemeral DHKA messages and their public keys, each party now has 2 DHKA messages, resulting in 4 possible combinations. For each combination, we can ask, from Alice's point of view, what kind of adversary could compute the DH secret:

• $g^{ab}$: Only Bob ($b$) or someone who stole Alice's key ($a$)
• $g^{ay}$: Only Alice's actual partner ($y$) or someone who stole Alice's key ($a$)
• $g^{xb}$: Only Bob ($b$)
• $g^{xy}$: Only Alice's actual partner ($y$)

A protocol vulnerable to KCI

In "protocol 3" of Blake-Wilson, Johnson, and Menezes [1] the parties use $H( g^{ab}, g^{xy})$ as their final secret. Besides Alice, who could compute this value?

(Bob OR someone who stole Alice's key) AND (Alice's actual partner)

Thus, this protocol is vulnerable to a KCI attack. Alice's actual partner could be an adversary who stole her key. This is the canonical example of a protocol vulnerable to KCI.

A protocol that protects against KCI

On the other hand, in Triple Diffie-Hellman (3DH) the parties use $H( g^{ay}, g^{xb}, g^{xy})$ as the final secret. Besides Alice, who could compute this value?

(Alice's actual partner OR someone who stole Alice's key) AND (Bob) AND (Alice's actual partner)

In other words, only Bob and only if he was Alice's actual partner. There is no KCI attack; the protocol achieves implicit authentication even in the presence of KCI adversaries.

---

[1] Blake-Wilson, Johnson, and Menezes: Key agreement protocols and their security analysis. 6th IMA International Conference on Cryptography and Coding, 1997.