In the last episode, we've seen that the Basic Authenticated Diffie-Hellman Key Exchange (BADH) was vulnerable to an Unknown Key Share Attack. We'll discuss a fix that takes care of Identity Misbinding Attacks, at least in this case, so we'll finally do have a more robust authenticated Key Exchange protocol.

What happened so far?

Let's recall what we've seen so far. The BADH protocol looks like this:

1. Alice \(\rightarrow\) Bob: \((\mathit{I_{Alice}}, g^a)\)
2. Alice \(\leftarrow\) Bob: \((\mathit{I_{Bob}}, g^b, \operatorname{sign_{Bob}}(g^a, g^b))\)
3. Alice \(\rightarrow\) Bob: \(\operatorname{sign_{Alice}}(g^a, g^b)\)

And the identity-misbinding attack allowed Eve to create two conflicting perceptions:

• Alice's perception: I am sharing a key \(g^{ab}\) with Bob
• Bob's perception: I am sharing a key \(g^{ab}\) with Eve

Eve managed to confuse Bob to share a key with her that was actually co-created by Alice. How did she manage to accomplish this feat? By simply forwarding Alice's \(g^a\) offer under her identity \(\mathit{I_{Eve}}\) to Bob (that's the part where Bob started to get confused), then forwarding Bob's reply back to Alice, and finally by throwing Alice's signature away, and replacing it with her own signature (which completed Bob's confusion). We can resume it like this:

• Alice \(\rightarrow\) Bob: \((\mathit{I_{Eve}}, g^a)\)
• Alice \(\leftarrow\) Bob: \(\mathit{(I_{Bob}}, g^b, \operatorname{sign_{Bob}}(g^a, g^b))\)
• Alice \(\rightarrow\) Bob: \(\operatorname{sign_{Eve}}(g^a, g^b)\)

This couple of changes was more than enough to trigger UKS on Bob's side.

The ISO-9796 Fix

Of course, the fix is to add the identity of the peer to the signatures:

1. Alice \(\rightarrow\) Bob: \((\mathit{I_{Alice}}, g^a)\)
2. Alice \(\leftarrow\) Bob: \((\mathit{I_{Bob}}, g^b, \operatorname{sign_{Bob}}(g^a, g^b, \mathit{I_{Alice}}))\)
3. Alice \(\rightarrow\) Bob: \(\operatorname{sign_{Alice}}(g^a, g^b, \mathit{I_{Bob}})\)

Be careful here: adding our own's identity to the signature is useless. It's the expected peer's identity (the one we'd like to talk to, not the interloper) that needs to be "sealed" inside the signature.

Here, we use the signing function like this:

\[ \operatorname{sign_{Id}}(k_1, k_2, \mathit{Id_{peer}}) \leftarrow \operatorname{sign}(\mathit{Id}, k_1 || k_2 || \mathit{Id_{peer}}) \]

In other words, we simply append \(\mathit{Id_{peer}}\) to both short-term public keys.

Why is that a fix?

Let's see what happens when Eve tries her UKS trick again on this protocol:

1. Alice \(\rightarrow\) Eve: \((\mathit{I_{Alice}}, g^a)\)
2. Eve \(\rightarrow\) Bob: \((\mathit{I_{Eve}}, g^a)\)
3. Eve \(\leftarrow\) Bob: \((\mathit{I_{Bob}}, g^a, g^b, \operatorname{sign_{Bob}}(g^a, g^b, \mathit{I_{Eve}}))\)
4. Alice \(\leftarrow\) Eve: \((\mathit{I_{Bob}}, g^a, g^b, \operatorname{sign_{Bob}}(g^a, g^b, \mathit{I_{Eve}}))\)
5. Alice computes \(\operatorname{verify}(\mathit{I_{Bob}}, g^a || g^b || \mathit{I_{Alice}}, \operatorname{sign_{Bob}}(g^a, g^b, \mathit{I_{Eve}}))\), gets false, Stop.

Of course, Alice expects the signature provided by Bob (Eve) to match her Identity, i.e. to match \(g^a || g^b || \mathit{I_{Alice}}\). But since Eve tried to fool Bob into believing that he's interacting with her, Bob signed \(g^a || g^b || \mathit{I_{Eve}}\) instead. And since Eve doesn't have access to Bob's long-term private key, she can't forge a signature like \(\operatorname{sign_{Bob}}(g^a, g^b, \mathit{I_{Alice}})\).

The Canetti-Krawczyk Security Model

Argumenting like this makes it intuitive to understand what's going on on a very high level. Unfortunately, it's merely hand-waving. Since secure protocol design can be brittle it's way too easy to come up with a construction that may seem secure, yet is fundamentally broken. As UKS has taught us, intuition only goes so far. We should never rely (exclusively) on it. What we need at this point is a real proof that this protocol is secure.

Any security proof worth its salt requires a security model. Key Exchange protocols are nowadays proven with the help of the Canetti-Krawczyk Security Model[CK01]. Explaining this very useful model is way too involved for a small article that needs to be bite-sized and that can be read on the go.

Source

This crypto bite is merely my understanding of Hugo's talk "Overview of Security Definitions" at the of the 8th BIU Winter School on Cryptography, starting at 10:45. Slides are in [K18, pages 22-27].

The actual proof of the security of ISO uses Authenticators, which I cover in the next crypto bite.

Suggested further reading: [LMM05, FG09].

 Literature

• [CK01] Ran Canetti, Hugo Krawczyk: Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels. In: Pfitzmann B. (eds) Advances in Cryptology — EUROCRYPT 2001. Lecture Notes in Computer Science, vol 2045. Springer, Berlin, Heidelberg  (doi, available on iacr.org, acm.org)
• [LMM05] Xinhua Li, Jianfeng Ma, SangJae Moon (2005) On the security of the canetti-krawczyk model. In: Proceeding CIS'05 Proceedings of the 2005 international conference on Computational Intelligence and Security - Volume Part II Pages 356-363. (doi, acm.org (paywalled))
• [FG09] Dario Fiore and Rosario Gennaro (2009): Making the Diffie-Hellman Protocol Identity-Based (iacr.org)