Unknown Key Share Attack

In the last episode of the authenticated Diffie-Hellman Key Exchange series, we've thwarted Susan's plot to long-term impersonate Alice in case of the leakage of Alice's ephemeral key \(a\) by adding an element of freshness to \(\operatorname{sig_{Alice}}(g^a)\). We've ended up with the Basic Authenticated Diffie-Hellman Key Exchange (BADH) protocol:

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

Unfortunately, BADH is vulnerable to another class of attack: Unknown Key Share Attack (UKS), a.k.a Identity Misbinding Attack[DVW92, K18].

The Identity Misbinding Attack

 Alice has a cheking account with Bob, a big bank. She wants to deposit $1000 to her account. This is what happens most of the time:

  1. Alice \(\rightarrow\) Bob: \((\mathit{I_{Alice}}, g^a)\)
  2. Alice \(\leftarrow\) Bob: \((\mathit{I_{Bob}}, g^b, \operatorname{sig_{Bob}}(g^a, g^b))\)
  3. Alice \(\rightarrow\) Bob: \(\operatorname{sig_{Alice}}(g^a, g^b)\)
  4. Alice \(\rightarrow\) Bob: \(\operatorname{Enc}(k_{g^{ab}}, \textrm{Deposit 1000})\)

Bob deduces from the session key \(k_{g^{ab}}\) that the $1000 are to be deposited to Alice's account.

Enters Eve. Eve also has an account with Bob, but next time Alice makes a deposit to her account, Eve wants to divert the funds to her own account. So she intercepts the next Alice-Bob session like this:

  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^b, \operatorname{sig_{Bob}}(g^a, g^b))\)
  4. Alice \(\leftarrow\) Eve:  \((\mathit{I_{Bob}}, g^b, \operatorname{sig_{Bob}}(g^a, g^b))\)
  5. Alice \(\rightarrow\) Eve: \(\operatorname{sig_{Alice}}(g^a, g^b)\)
  6. Eve \(\rightarrow\) Bob: \(\operatorname{sig_{Eve}}(g^a, g^b)\)
  7. Alice \(\rightarrow\) Eve: \(\operatorname{Enc}(k_{g^{ab}}, \textrm{Deposit 1000})\)
  8. Eve \(\rightarrow\) Bob: \(\operatorname{Enc}(k_{g^{ab}}, \textrm{Deposit 1000})\)

Here is what happens in plain terms:

  1. Alice initiates the BADH handshake with Bob, but Eve intercepts the message.
  2. Eve forwards Alice's handshake message to Bob, but replaces \(\mathit{I_{Alice}}\) with her ID \(\mathit{I_{Eve}}\). She also keeps a copy of \(g^a\) for later.
  3. Bob thinks that Eve wants to BADH-handshake (because of the \(\mathit{I_{Eve}}\) in the handshake message), so he replies accordingly. Note though that the public key that Eve offered is Alice's \(g^a\) and not her own \(g^e\).
  4. Eve forwards Bob's reply to Alice, unchanged.
  5. Alice completes the BADH handshake, but Eve intercept that message again.
  6. Eve replaces once again \(\mathit{I_{Alice}}\) with her identity \(\mathit{I_{Eve}}\) in the final handshake message of Alice, and then forwards that to Bob. Note that Eve has all the ingredients to create \(\operatorname{sig_{Eve}}(g^a, g^b)\) from scratch: she got \(g^a\) in step 1, and \(g^b\) in step 3. On the other hand, she dropped Alice's signature which is not needed anymore.
  7. Alice, oblivious of Eve's machinations, encrypts a deposit order for $1000 with the key \(k_{g^{ab}}\) which she shares with Bob, and sends that order to Eve
  8. Eve forwards that encrypted message (which she can't read nor modify) unchanged to Bob.

At this point, Bob decrypts the message, and deduces from the key \(k_{g^{ab}}\) and his previous interaction with Eve, that he has to deposit those $1000 to Eve's account. Alice's $1000 were successfully diverted to Eve's account.

The interesting point is that there are 2 sessions in this exchange, one between Alice and Eve:

  • Alice \(\rightarrow\) Eve: \((\mathit{I_{Alice}}, g^a)\)
  • Alice \(\leftarrow\) Eve:  \((\mathit{I_{Bob}}, g^b, \operatorname{sig_{Bob}}(g^a, g^b))\)
  • Alice \(\rightarrow\) Eve: \(\operatorname{sig_{Alice}}(g^a, g^b)\)
  • Alice \(\rightarrow\) Eve: \(\operatorname{Enc}(k_{g^{ab}}, \textrm{Deposit 1000})\)

and one between Eve and Bob:

  • Eve \(\rightarrow\) Bob: \((\mathit{I_{Eve}}, g^a)\)
  • Eve \(\leftarrow\) Bob: \((\mathit{I_{Bob}}, g^b, \operatorname{sig_{Bob}}(g^a, g^b))\)
  • Eve \(\rightarrow\) Bob: \(\operatorname{sig_{Eve}}(g^a, g^b)\)
  • Eve \(\rightarrow\) Bob: \(\operatorname{Enc}(k_{g^{ab}}, \textrm{Deposit 1000})\)

As you can see, both sessions follow the BADH to the letter. Yet, still, bad things happened.

What's the actual problem?

It is a matter of inconsistant perceptions:

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

Everything that Alice sends to Bob, Bob thinks comes from Eve. This is particularly troubling, if Alice's messages to Bob are actually legitimate commands.

In the other direction, everything Bob sends back to Eve, Eve can blindly relay back to Alice.

Interestingly, the virtual connection between Alice and Bob, with Eve in the middle, is encrypted, even end-to-end: Eve can't see what Alice and Bob are talking about. Because of this encryption, Eve can't change the content of this conversation (short of dropping or replicating replies). Her only, but decisive advantage is that Bob thinks that he's talking with her, and not with Alice.

In the case of Bob being an Bank, this scenario is, of course, a little unrealistic. In the real world, the e-banking program would define a layer-7 protocol on top of the encryption stuff. For example, Alice would neet to send an encrypted JSON or XML string, specifying not only the amount, but also her bank account number and an access code for the $1000 so that Bob knows where to withdraw them from before depositing them into Alice's account... and possibly other data fields. Almost always, Alice's account number will be needed and provided. Can Eve use an Identity-Misbinding attack in this case to steal Alice's money as we've seen before? The answer is no, because, since Alice's deposit order to Bob is encrypted, Eve has no means to change the destination account number in the (encrypted) JSON or XML string. Bob would immediately detect Eve's plot and refuse to execute that order (and will also report Eve to the cops). Adding this kind of application-level additional measure of safety shouldn't be necessary, were the key exchange protocol provably secure (at least against UKS). But does such a protocol exist at all? Hang on.

UKS: The "differential cryptanalysis of KE protocols"

According to Hugo Krawczyk, Unknown Key Share attacks are to the world of Key Exchange protocols the equivalent of differential cryptanalysis to the world of symmetric block ciphers. Both class of attacks are extremely powerful and managed to break a lot of established protocols that were deemed secure.

A cure against UKS?

So how do we fix BADH? Is there a cure against UKS? Hang on til the next article.

Sources and further reading

The original paper describing UKS is [DVW92]. Very frequently cited is also [BwM99].

Many current protocols seem to be vulnerable to UKS. One recent example is DTLS-SRTP which is used in WebRTC[TR18].

I'm merely explaining Hugo Krawczyk's talk "What are Key Exchange Protocols?", of the 8th BIU Winter School on Cryptography, starting at 50:00. Slides in [K18, pages 22-27].

and the first 10:45 minutes from his next talk "Overview of Security Definitions":

Literature