In this crypto bite, we'll explore an issue of authenticated key exchange protocols that we've overlooked so far: how do we protect the privacy of one or both communicating parties against a passive or an active attacker?

A Real World Scenario

Abderrahim Al Mansur is a fictitious Saudi scholar of theology. In the course of his advanced Quran studies, he needed a copy of the Bible to determine the origin and context of some Quranic verses. Unfortunatly, owning a Bible in his country is a crime, so his University's library didn't have a copy. But, being very persistant and determined to make a scientific contribution to his field, he decided to download bible.pdf from a foreign server using a file sharing app which implemented a variant of ISO-9796. Even though he quickly deleted this file soon after that, little did he know that his nightmare was just about to begin.

In the wee hours of the morning, a SWAT team of the religion police burst into his home, seized him, his books, notes, computers and his smartphone, and threw him in jail. A few days later, Al Mansur was facing a sharia court. This is an (americanized) transcript:

  • Judge: You've been charged with the crime of owning a Bible. How do you plead?
  • Al Mansur: I'm not guilty, your Honor. There's no Bible in my home.
  • Judge: The police can prove that you've downloaded a copy of the Bible from a foreign server.
  • Al Mansur: That's a lie!
  • Judge: Don't be silly. The police are using a US-made surveillance software that doesn't make mistakes.
  • Al Mansur: But, but...
  • Judge: Mr. Orwell, you're a specialist of Big Netbrother, Inc and our expert witness. Would you care to explain? I remind you that you're under oath.
  • Mr. Orwell: Yes, your Honor. We've captured the traffic of Mr. Al Mansur at the Riyadh CIX. The connection meta-data show that his smartphone connected to a file sharing server that hosts nothing else but copies of the Bible in various languages.
  • Al Mansur's lawyer: Anyone can spoof IP addresses! That's not a proof that my client connected to this server!
  • Mr. Orwell: True, but we've analyzed the key exchange protocol and in the trace, you can clearly see that Mr. Al Mansur sent his Identity to the server: \((\mathit{I_{}}, g^x)\).
  • Al Mansur's lawyer: This is no proof either! Maybe a colleague of him did this in order to get his beautiful air-conditioned office!
  • Mr. Orwell: Of course, that's a possibility. However, if you look further down the protocol trace, you'll see that Mr. Al Mansur's phone sent: \(\operatorname{sign_{}}(g^x, g^y, \mathit{I_{}})\).
  • Judge: I don't understand this technical mumbo jumbo. What does it mean, Mr. Orwell?
  • Mr. Orwell: Your Honor, it says that Mr. Al Mansur created a digital signature that he was communicating with at that time. Nobody else but him can create such a digital signature.
  • Judge: Why can't anybody else create such a signature? Isn't it all just ones and zeroes?
  • Mr. Orwell: To create such a signature, you need a so called private key in a file. Only the people who own this file can create this signature.
  • Judge: An that key file was found on Mr. Al Mansur's phone?
  • Mr. Orwell: Yes, it was.
  • Al Mansur's lawyer: Maybe it was my client's colleague who smuggled this key file into Mr. Al Mansur's phone?
  • Judge: Well, Mr. Orwell, is that likely?
  • Mr. Orwell: Unlikely, your Honor. By analyzing previous traces of Mr. Al Mansur's network activities, we can see that he used this key all the time to sign all kinds of communications, including to his University accounts, bank accounts, e-mail accounts and so on.
  • (Al Mansur's lawyer and his clients conferring in hushed voices)
  • Al Mansur's lawyer: your Honor, my client wishes to change his plea from non-guilty to guilty.
  • Judge: All right then. Mr. Al Mansur, would you please stand up. You've been convicted of illegally downloading and therefore of owning a copy of the Bible. This is a heinous crime, and you need to be severely punished. But, since you've pleaded guilty, and since you've been up to now a valuable member of our society, I'll show leniency. You're hereby sentenced to 200 whiplashes, and to the amputation of all fingers of your right hand, so you may never use them to download Bibles again. Session closed.

What's wrong with ISO-9796?

First of all, let's recall ISO-9796:

  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}})\)

All previously shown authenticated key exchange protocols exposed the identity of the users \(\mathit{I_{Alice}}\) and \(\mathit{I_{Bob}}\) by sending them in the clear.

  • \((\mathit{I_{Alice}}, g^a, \operatorname{sign_{Alice}}(g^a))\) and \((\mathit{I_{Bob}}, g^b, \operatorname{sign_{Bob}}(g^b))\) in the AKE that was vulnerable to long-term impersonation of epheremal keys
  • \((\mathit{I_{Alice}}, g^a)\), \((\mathit{I_{Bob}}, g^b, \operatorname{sign_{Bob}}(g^a, g^b))\) in BADH
  • \((\mathit{I_{Alice}}, g^a)\), \((\mathit{I_{Bob}}, g^b, \operatorname{sign_{Bob}}(g^a, g^b, \mathit{I_{Alice}}))\) in the ISO-9796 fix.

Not only did this destroy Alice's and Bob's privacy w.r.t. any passive eavesdropper, it also left a trail of non-repudiable connection meta-data:

  • The AKE that was vulnerable to long-term impersonation of ephemeral keys leaked \(\operatorname{sign_{Alice}}(g^a)\) and \(\operatorname{sign_{Bob}}(g^b)\), so that Alice and Bob are confirming with their long-term private keys that they are indeed offering their epheremal keys \(g^a\) and \(g^b\) to some remote communication partner. They can't deny that they were the ones who generated those ephemeral keys.
  • Even worse, BADH leaked \(\operatorname{sign_{Bob}}(g^a, g^b)\) and \(\operatorname{sign_{Alice}}(g^a, g^b)\), so that Alice and Bob are confirming with their long-term private keys that they do participate in a key exchange with each other.
  • The ISO-9796 isn't any better, in fact it's even worse from a non-repudiability point of view: by leaking \(\operatorname{sign_{Bob}}(g^a, g^b,\mathit{I_{Alice}})\), Bob not only certified that he communicated with someone who offered \(g^a\), he also confirmed that he knew who offered \(g^a\), i.e. that is was \(\mathit{I_{Alice}}\). He can't say, for example: "I was communicating, but I thought it was with David". He can't deny that he knew and intended to communicate with Alice. Same for Alice, who confirmed by sending \(\operatorname{sign_{Alice}}(g^a, g^b, \mathit{I_{Bob}})\) that she knew and intended to communicate with the real McCoy Bob.

So what are the problems here?

  1. Privacy Breach: by sending the Identities in the clear, i.e. non-encrypted, privacy of the communicating peers w.r.t. a passive eavesdropper goes out of the window. We must therefore encrypt these Identities with a key known only to Alice and Bob. But to establish such a key is the goal of authenticated key exchange in the first place. Do we have a bootstrapping / chicken-and-egg problem here?
  2. Non-repudiability: By signing various privacy-sensitive data like Identities and ephemeral keys with their long-term private key, users are leaving behind a trail of non-repudiable connection meta-data. By encrypting those bits before signing them would go a long way towards mitigating non-repudiability. Using "private signatures" that are only usable by Alice and Bob, but by nobody else would be even better. But do such private signature schemes exist?

Let't try to fix each of these issues.

Initiator vs. Responder Privacy

Almost everywhere in the world before caller IDs became commonplace, when Bob's phone rings, he would pick it up and say something like: "Hello?" and the caller is expected to reply "hi, this is Alice", and then Bob would say "Hi Alice, this is Bob." Some people like Germans have it backwards: Bob will say: "Bob here." Alice will then reply: "Hey Bob, this is Alice."

In the general voice phone protocol, the initiator (Alice, the caller) will disclose her identity first, and only then will the responder (Bob, the callee) disclose his identity, if he agrees to talk to the caller. In the world of TLS, it's usually the other way around: the initiator won't disclose her identity before the responder disclosed his identity. Indeed, it's the server that would usually send its certificate to the client, and only then will the client (optionally, although that's rare) identify itself to the server.

The take-away from this is that there are two kinds of privacy protection in authenticated key exchange protocols: either the initiator's or the responder's identity will be withheld, at least in the beginning.

Can both initiator's and responder's identities be protected at the same time? It is indeed possible[BCDG87] though in practice, it rarely happens. It's usually either initiator or responder identity protection.

What can be protected?

Against a passive attacker, encrypting the identities is sufficiant to protect both initiator's and responder's identity. Unfortunatly, only one of the identities can be hidden against an active attacker. So the question is, which side's identity do we wish to protect? It depends on the use-case:

  • Roaming users need initiator protection: when you wander around with your smartphone in a city, you don't want your phone to constantly advertize its identity to a myriad of access points that it wouldn't want to connect to anyway. Therefore, wifi, GSM, LTE, ... key exchange protocols would typically protect the identity of the initiator. It's the responder that is supposed to advertize its identity first. It may spoof legitimate equipment as IMSI catchers do, but that's another issue. The point is that the initiator can decide to engage in key exchange protocol based on the advertized identity of the responder. Note that web clients connecting to web servers using TLS also fall into this category.
  • Electronic passports, NFC credit cards, etc. need responder protection: you don't want your ePassport to identify itself by responding to unindentified RFID readers being carried in some hackers' backpack in the subway who happen to be in your close vicinity. You also don't want your NFC-enabled credit or debit card to send its identity to some hacker's smartphone mimicking as a point of sale terminal. In both cases, we need responder protection: it's the initiator (RFID reader, NFC point of sale terminal) that is supposed to identify itself and the responder has a chance to check his peer's identity before engaging in key exchange protocol.

In other words, we have three distinct classes of key exchange protocols: those who protect the identity of the initiator against active attackers, those who protect the identity of the responder against active attackers, and those who don't care at all and offer no identity protection against active attackers.

On the Path Towards SIGMA

We will now try to modify AKEs until we get a usable authenticated key exchange protocol with initiator or responder protection. Instead of showing the end result right away, it is instructive to experiment with various designs that failed.

Can ISO-9796 be fixed?

Unfortunatly, ISO-9796 can't be fixed to provide identity protection against active attackers: on one side, Bob need the identity of Alice so he can authenticate himself to Alice: \(\operatorname{sign_{Bob}}(g^a, g^b, \mathit{I_{Alice}})\), therefore no initiator protection. On the other side Alice needs the identity of Bob before she can authenticate herself to Bob: \(\operatorname{sign_{Alice}}(g^a, g^b, \mathit{I_{Bob}})\), therefore no responder protection.

We've already seen that signing their own identity instead of the peer's identity results in a bad case of UKS. Furthermore, there's the issue of visibly signing the identity of the peer, which can have negative consequences on one's health, as the real world scenario illustrates.

What about SKEME?

Remember SKEME [K96]?

  1. \(A \rightarrow B \colon (A, \{k_a\}_{\mathit{pk}_B})\)
  2. \(A \leftarrow B \colon (B, g^b, \operatorname{MAC}(k_a, g^b, A), \{k_b\}_{\mathit{pk}_A})\)
  3. \(A \rightarrow B \colon (A, g^a, \operatorname{MAC}(k_b, g^a, B))\)

where \(\{m\}_k := \operatorname{Enc}(k, m)\), \(k_a\) and \(k_b\) are ephemeral random keys generated by \(A\) and \(B\) respectively, and \(A\) and \(B\) are a shortcut for the identity of \(A\) and of \(B\) respectively, i.e. \(A := \mathit{I_A}, B := \mathit{I_B}\).

We could first try to protect the identity of the initiator \(A\) by moving it inside the encrypted blob (\(B\) would do the same with his identity):

  1. \(A \rightarrow B \colon \{A, k_a\}_{\mathit{pk}_B}\)
  2. \(A \leftarrow B \colon (g^b, \operatorname{MAC}(k_a, g^b, A), \{B, k_b\}_{\mathit{pk}_A})\)
  3. \(A \rightarrow B \colon (A, g^a, \operatorname{MAC}(k_b, g^a, B))\)

Only in the third step would \(A\) disclose her identity, after having verified \(B\)'s identity. That the identity \(A\) is sent in the clear an can be read by a passive attacker can easily be remedied: just send \(\{A\}_{\mathit{pk_B}}\) or even \(\{A\}_{g^{ab}}\) instead of \(A\)). The bigger issue here is that in step 1 \(A\) needs \(\mathit{pk}_B\), the public key of \(B\) beforehand, even before initiating the key exchange (\(A\) could always send her public key \(\mathit{pk}_A\) in step 1, so that \(B\) can use it in step 2). This will be fixed by the SIGMA protocol below.

The STS Protocol

An alternative authenticated key exchange protocol that tries to protect identities is STS[DVW92], the Station-to-Station protocol used in ISDN.It comes in some variants. We'll discuss STS-ENC and STS-MAC below[K03].

The STS-ENC protocol

We start with good ole BADH:

  1. \(A \rightarrow B \colon (A, g^a)\)
  2. \(A \leftarrow B \colon (B, g^b, \operatorname{sign_B}(g^a, g^b))\)
  3. \(A \rightarrow B \colon \operatorname{sign_A}(g^a, g^b)\)

which is, of course, vulnerable to an indentity misbinding attack. To mitigate UKS, both parties prove knowledge of their shared key \(g^{ab}\) which is unknown to any attacker, by encrypting their signatures with that key. BADH becomes:

  1. \(A \rightarrow B \colon (A, g^a)\)
  2. \(A \leftarrow B \colon (B, g^b, \{\operatorname{sign_B}(g^a, g^b)\}_{g^{ab}})\)
  3. \(A \rightarrow B \colon \{\operatorname{sign_A}(g^a, g^b)\}_{g^{ab}}\)

But, we can do better! \(B\) can protect his identity in step 2 by encrypting \(B\) as well:

  1. \(A \rightarrow B \colon (A, g^a)\)
  2. \(A \leftarrow B \colon (g^b, \{B, \operatorname{sign_B}(g^a, g^b)\}_{g^{ab}})\)
  3. \(A \rightarrow B \colon \{\operatorname{sign_A}(g^a, g^b)\}_{g^{ab}}\)

Can \(A\) also protect her identity by encrypting \(A\)? Sure thing! But not in step 1, since at this point in time, she doesn't yet have \(g^b\), and thus can't compute \(g^{ab}\). However, \(B\) doesn't need \(A\) yet in step 2, so \(A\) could send her (encrypted) \(A\) later in step 3. The result is the

STS-ENC protocol with identity protection:

  1. \(A \rightarrow B \colon g^a\)
  2. \(A \leftarrow B \colon (g^b, \{B, \operatorname{sign_B}(g^a, g^b)\}_{g^{ab}})\)
  3. \(A \rightarrow B \colon \{A, \operatorname{sign_A}(g^a, g^b)\}_{g^{ab}}\)

Interesting, isn't it? Now, the identities are indeed protected.

UKS with an Online Registration Attack, or: STS-ENC isn't secure!

But is STS-ENC secure? The answer is no[BwM99]: STS-ENC is (unsurprisingly?) vulnerable to... you've guessed it by now... our old friend, the KE protocol killer: an identity misbinding attack, with a twist. Here's how it works in the simple case of STS-ENC which doesn't include the identities in the encrypted blob. Without meddling by \(E\), \(A\) and \(B\) perform this variant of STS-ENC:

Basis STS-ENC:

  1. \(A \rightarrow B \colon g^a\)
  2. \(A \leftarrow B \colon (B, g^b, \{\operatorname{sign_B}(g^a, g^b)\}_{g^{ab}})\)
  3. \(A \rightarrow B \colon (A, \{\operatorname{sign_A}(g^a, g^b)\}_{g^{ab}})\)

We now assume that \(E\) can register \(A\)'s public key with an online CA under her name in a time shorter that it takes to complete the STS protocol (think a couple of seconds at the most). This is not so unrealistic, since many online CAs can deliver certificates almost instantly, and don't require from the registrant \(E\) of the public key to prove that she owns the corresponding private key before signing the submitted public key with CA's super-secret private key. The UKS attack on STS-ENC looks like this on the \(E \leftrightarrow B\) side:

  1. \(E \rightarrow B \colon g^a\)
  2. \(E \leftarrow B \colon (B, g^b, \{\operatorname{sign_B}(g^a, g^b)\}_{g^{ab}})\)
  3. \(E\) connects to CA, and registers \(A\)'s public key under her name \(E\).
  4. \(E \rightarrow B \colon (E, \{\operatorname{sign_A}(g^a, g^b)\}_{g^{ab}})\)
  5. \(B\) decrypts the signature, and seeing identity \(E\), calls \(\operatorname{verify}(E, \operatorname{sign_A}(g^a, g^b))\)

The point here is that the verification in step 5 succeeds! But why is that so? Let's look at this more closely. To understand what's going on, we need to be more explicit in the protocol spec, by explicitly adding the certificates of the public keys that are being sent along. The STS-ENC between \(A\) and \(B\) with explicit certs would look like this:

Basis STS-ENC with Certificates:

  1. \(A \rightarrow B \colon g^a\)
  2. \(A \leftarrow B \colon (\mathit{cert_B}, g^b, \{\operatorname{sign_B}(g^a, g^b)\}_{g^{ab}})\)
  3. \(A \rightarrow B \colon (\mathit{cert_A}, \{\operatorname{sign_A}(g^a, g^b)\}_{g^{ab}})\)

As usual, the certificates are signed by the CA with its super-secret key \(\mathit{sk_{CA}}\) and contain, among others, a pair of identity and public key:

  • \(\mathit{cert_A} = (A, \mathit{pk_A}, \operatorname{sign}(\mathit{sk_{CA}}, A || \mathit{pk_A}))\)
  • \(\mathit{cert_B} = (B, \mathit{pk_B}, \operatorname{sign}(\mathit{sk_{CA}}, B || \mathit{pk_B}))\)

That's why we don't need to send the identities \(A\) and \(B\) in addition to \(\mathit{cert_A}\) and \(\mathit{cert_B}\), since they are already included in the certs. The certificates are now playing the role of the identities, and they carry along public keys (plus, they are CA-certified).

What \(E\) does in step 3. of the UKS attack is to extract \(pk_A\) from \(\mathit{cert_A}\), and have the CA sign \(\mathit{pk_A}\), but using her own identity \(E\):

  • \(\mathit{cert_E} = (E, \mathit{pk_A}, \operatorname{sign}(\mathit{sk_{CA}}, E || \mathit{pk_A}))\)

This is the certificate that \(E\) sends with her identity to Bob, and this certificate is valid. The whole \(E \leftrightarrow B\) interaction, including certs becomes:

  1. \(E \rightarrow B \colon g^a\)
  2. \(E \leftarrow B \colon (\mathit{cert_B}, g^b, \{\operatorname{sign_B}(g^a, g^b)\}_{g^{ab}})\)
  3. \(E \rightarrow \mathit{CA} \colon (E, \mathit{pk_A})\)
  4. \(E \leftarrow \mathit{CA} \colon \mathit{cert_E}\)
  5. \(E \rightarrow B \colon (\mathit{cert_E}, \{\operatorname{sign_A}(g^a, g^b)\}_{g^{ab}})\)
  6. \(B\) decrypts the signature, and using the provided \(\mathit{cert_E}\), calls \(\operatorname{verify}(\mathit{cert_E}, \operatorname{sign_A}(g^a, g^b))\)

The call to \(\operatorname{verify}(\mathit{cert_E}, \operatorname{sign_A}(g^a, g^b))\) succeeds, because \(\operatorname{verify}\) will first use the widely distributed public key of the CA \(\mathit{pk_{CA}}\) to verify that the provided certificate \(\mathit{cert_E}\) is valid (it is), and will then extract from \(\mathit{cert_E}\) the public key \(\mathit{pk_A}\). \(B\) is now convinced that \(\mathit{pk_A}\) is \(E\)'s public key: after all, the CA said so in \(\mathit{cert_E}\)! And since Alice signed \(g^a || g^b\) with her private key \(\mathit{sk_A}\) corresponding to \(\mathit{pk_A}\), this signature will indeed verify! From here onwards, \(B\) will think that he is intercating with \(E\) instead of with \(A\)... in other words: UKS successful!

Interestingly, but not unusual with UKS, to mount this attack, \(E\) didn't need to decrypt the encrypted signature \(\{\operatorname{sign_A}(g^a, g^b)\}_{g^{ab}}\) at all with the key \(g^{ab}\) that she doesn't have and that she can't derive anyway (under the DDH assumption). All she needed was:

  • online access to a fast CA,
  • a CA that doesn't require PoP (proof of possession of private key),
  • a peer \(B\) that tolerates little delays in the KE phase.

Such attacks can happen in the real world. Who said that AKE protocol design wasn't brittle?

We've cheated (a little) by showing UKS with an online registration attack only in the trivial case that the identities (certificates) weren't encrypted. But can \(E\) mount such an attack against STS-ENC with identity protection that we introduced above which moved the identities / certificates inside the encrypted blob? If that encryption is being done with a stream cipher, that attack is trivial too, because it is easy to substitute only the identity / the certificate in the ciphertext without touching the encryption of the signatures. In other words, it is trivial to replace \(A \rightarrow B \colon \{A, \operatorname{sign_A}(g^a, g^b)\}_{g^{ab}}\) with \(E \rightarrow B \colon \{E, \operatorname{sign_A}(g^a, g^b)\}_{g^{ab}}\), without having to decrypt and then re-encrypt \(\operatorname{sign_A}(g^a, g^b)\) (assuming a fixed format, where e.g. the identities \(A\) and \(E\) are of the same length). If a block cipher is used, mounting such an attack is less trivial.

The STS-MAC Protocol

The main problem with STS-ENC is that encryption is not enough to prove knowledge of \(g^{ab}\). MAC-ing with \(g^{ab}\) is much better suited for this purpose. STS-MAC, a variant of STS, does exactly this: it MACs the signatures instead, using the shared key:

Basis STS-MAC:

  1. \(A \rightarrow B \colon g^a\)
  2. \(A \leftarrow B \colon (B, g^b, \operatorname{sign_B}(g^a, g^b), \operatorname{MAC}(g^{ab}, \operatorname{sign_B}(g^a, g^b)))\)
  3. \(A \rightarrow B \colon (A, \operatorname{sign_A}(g^a, g^b), \operatorname{MAC}(g^{ab}, \operatorname{sign_A}(g^a, g^b)))\)

Here, \(\operatorname{MAC}(k, m)\) is the message authentication code of \(m\) under the key \(k\). In practice, something like \(\operatorname{HMAC}(\operatorname{KDF}(g^{ab}), m)\) is often used, with a suitable key derivation function \(\operatorname{KDF}\) that translate group elements \(g^{ab}\) into keys with the required number of bits... but that is irrelevant to our present discussion.

There's of course also a variant with certificates:

STS-MAC with Certificates:

  1. \(A \rightarrow B \colon g^a\)
  2. \(A \leftarrow B \colon (\mathit{cert_B}, g^b, \operatorname{sign_B}(g^a, g^b), \operatorname{MAC}(g^{ab}, \operatorname{sign_B}(g^a, g^b)))\)
  3. \(A \rightarrow B \colon (\mathit{cert_A}, \operatorname{sign_A}(g^a, g^b), \operatorname{MAC}(g^{ab}, \operatorname{sign_A}(g^a, g^b)))\)

and even one which encrypts the certificates and signatures, then MACs the resulting ciphertext (remember that encrypt-then-mac is better than mac-then-encrypt and mac-and-encrypt[K01]):

STS-MAC with Certificates and Identity Protection:

  1. \(A \rightarrow B \colon g^a\)
  2. \(A \leftarrow B \colon (g^b, \{\mathit{cert_B}, \operatorname{sign_B}(g^a, g^b)\}_{g^{ab}}, \operatorname{MAC}(g^{ab}, \{\operatorname{cert_B}, \operatorname{sign_B}(g^a, g^b)\}_{g^{ab}}))\)
  3. \(A \rightarrow B \colon (\{\mathit{cert_A}, \operatorname{sign_A}(g^a, g^b)\}_{g^{ab}}, \operatorname{MAC}(g^{ab}, \{\mathit{cert_A}, \operatorname{sign_A}(g^a, g^b)\}_{g^{ab}}))\)

Unfortunately, STS-MAC is also vulnerable to UKS[BwM99], and we didn't even exploit the fact that both encryption and MAC keys aren't independently chosen as they should've been (in fact, they're the same \(g^{ab}\) here). Even worse than STS-ENC, the UKS with Online Registration on STS-MAC works even with PoP CAs, i.e with CAs that require proof of possession of the corresponding private key. Putting the signer's certificate under the signature as in \(\operatorname{sign_A}(\mathit{cert_A}, g^a, g^b)\) and \(\operatorname{sign_B}(\mathit{cert_B}, g^a, g^b)\) also doesn't help.

So What's Wrong with STS?

It turns out that proving knowledge of the shared key \(g^{ab}\) isn't the point. The problem is that this key can be bound to a wrong identity, leading to the identity misbinding attack. We need to bind this key to the identity of the participants... something that ISO-9796 did but without privacy protection. The SIGMA protocols that we'll explore in the next crypto bite aim to tackle this issue.


This article is my transcript and understanding of Hugo Krawczyk's talk "Diffie-Hellman Protocols and Authenticators", starting at minute 29:00, at the 8th BIU Winter School on Cryptography on Secure Key Exchange, February 11-15 2018 (all videos). The presentation described here starts at slide 60.

The Real World Scenario at the top of this crypto bite is my own dramaturgic rendering of the very real dangers that privacy breaches and non-repudiability of authenticated key exchange protocols can incur in real life.


  • [BCDG87] Ernest F. Brickell, David Chaum, Ivan B. Damgård, Jeroen van de Graaf: Gradual and Verifiable Release of a Secret (Extended Abstract). In: Pomerance C. (eds) Advances in Cryptology — CRYPTO ’87. Lecture Notes in Computer Science, vol 293. Springer, Berlin, Heidelberg. (, pdf available)
  • [K96] Hugo Krawczyk: SKEME: a versatile secure key exchange mechanism for Internet. In: Proceedings of Internet Society Symposium on Network and Distributed Systems Security, 22-23 Feb. 1996 (IEEE paywalled;, paywalled, full pdf)
  • [DVW92] Whitfield Diffie, Paul C. van Oorschot, Michael J. Wiener: Authentication and Authenticated Key Exchanges. In: Designs, Codes and Cryptography, 2, pages 107-125 (1992) (DOI, full pdf)
  • [BwM99] Simon Blake-Wilson, Alfred Menezes: Unknown Key-Share Attacks on the Station-to-Station (STS) Protocol (1999).
  • [K01] Hugo Krawczyk: The order of encryption and authentication for protecting communications (Or: how secure is SSL?) ( 2001/045, postscript)
  • [K03] Hugo Krawczyk: SIGMA: The ‘SIGn-and-MAc’ Approach to Authenticated Diffie-Hellman and Its Use in the IKE Protocols. In: Boneh D. (eds) Advances in Cryptology - CRYPTO 2003. Lecture Notes in Computer Science, vol 2729. Springer, Berlin, Heidelberg (, (full version)).