The SIGMA Protocols

In the previous episode, we've explored the STS protocol, which aims to protect the privacy of Alice and Bob. Unfortunatly, like so many other authenticated key exchange protocols, STS too is vulnerable to an identity misbinding attack. The reason for this was that proving knowledge of the shared key wasn't the point: we need to bind that key to the identities of Alice and Bob. This is exactly the aim of the SIGMA protocols.

The SIGMA-Protocols Family

The main problem with STS was that we didn't bind the identities \(A\) and \(B\) to the session key \(g^{ab}\). That was the reason for the devastating identity misbinding attack. Indeed: we signed \(g^a\) and \(g^b\) as in \(\operatorname{sign_A}(g^a, g^b)\) or \(\operatorname{sign_B}(g^a, g^b)\), and we either encrypted (STS-ENC) or MACed (STS-MAC) that signature with \(g^{ab}\). But we failed to protect \(A\) and \(B\) against modification. Even putting those identities in the encypted blob wasn't sufficient.

What we would like is something like ISO-9796, where \(A\) and \(B\) are protected by being included in the signatures: \(\operatorname{sign_A}(g^a, g^b, B)\) and \(\operatorname{sign_B}(g^a, g^b, A)\). Unfortunately, this approach had two fatal flaws:

  • Neither initiator nor responder privacy protection: both \(A\) and \(B\) needed the indentity of the peer before being able to proceed with the protocol
  • Non-repudiability: by signing the identity of the peer, one leaves a non-deniable proof of communication with that peer

So how can we resolve both issues? First of all, we stick to the idea of signing the pair \((g^a, g^b)\). That's a sensible thing to do, since it thwarts man in the middle attacks. But, obviously, we also need a mechanism to protect the identities \(A\) and \(B\) from being silently modified. Furthermore, this mechanism must be separate from signing, since we want to avoid non-repudiability.

Fortunately, such a mechanism exists: it's our good old MAC. What if we MACed our identity with a key known only by \(A\) and \(B\), in addition to the signing of \((g^a, g^b)\)? This SIGn-and-MAC idea[K03] leads to the basic version of the SIGMA protocol.

The Basic Version

Separately signing \((g^a, g^b)\) and MACing our own identity \(A\) or \(B\) is the basic SIGMA protocol:

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

where \(k_m\) is a MACing key derived from \(g^{ab}\) via a key derivation function: \(k_m := \operatorname{KDF}(g^{ab})\)

As we can see, our identity is now protected by the MAC: when \(B\) sends, among others, \(\operatorname{MAC}(k_m, B)\) back, \(A\) will use her copy of \(k_m\) to confirm that \(B\) hasn't been silently replaced by, say, \(E\). Intuitively, this should thwart the identity misbinding attack. Furthermore, by not signing our nor the peer's identity, we've defused the non-repudiability liability.

Unlike ISO-9796, Basic SIGMA doesn't require knowledge of the peer's identity as a prerequisite for generating and sending an authenticated version of our own identity. This makes SIGMA the protocol of choice for designing variants that provide initiator or responder indentity protection.

SIGMA-I: Protecting Initiators' Identity

Now is time to protect the identities of \(A\) and \(B\) against passive attackers. How do we do this? Well, by encrypting them, of course. This leads to the following variant of the SIGMA protocol:

The SIGMA-I Protocol:

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

where \(k_e\) is an encryption key and \(k_m\) is a MACing key, both derived from \(g^{ab}\) with a pseudo random function:

  • \(k_e \leftarrow \operatorname{PRF}(g^{ab})\)
  • \(k_m \leftarrow \operatorname{PRF}(g^{ab})\)

and, as usual, \(\{m\}_k = \operatorname{Enc}(k, m)\) is the encryption of message \(m\) with the key \(k\).

A pseudo random function \(f\) seeded with a seed \(s\) will generate a sequence \((f(s))_{i \in \mathbb N}\) that is indistinguishable from a random sequence \((x_i)_{i \in \mathbb N}\). In practice, such a function can be e.g. AES in GCM mode.

What have we gained here?

  • Since both identities \(A\) and \(B\) are encrypted, we have identity protection of both initiator and responder against passive attackers.
  • Since \(A\) has the opportunity of verifying the identity of \(B\) before disclosing her own identity, we have identity protection of the initiator against active attackers.
  • By signing, we've prevented man in the middle attacks
  • By MACing our own identity, we've prevented identity misbinding attacks

Note that SIGMA-I is also used in the upcoming TLS 1.3 standard.

SIGMA-R: Protecting Responder's Identity

You may now be wondering how to protect the responder's identity against active attackers. Basically, all we need to do is revert the roles of \(A\) and \(B\), and have \(A\) send her authenticated identity first. This leads to

The SIGMA-R Protocol:

  1. \(A \rightarrow B \colon g^a\)
  2. \(A \leftarrow B \colon g^b\)
  3. \(A \rightarrow B \colon \{A, \operatorname{sign_A}(g^a, g^b), \operatorname{MAC}(k_m, A)\}_{k_e}\)
  4. \(A \leftarrow B \colon (g^b, \{B, \operatorname{sign_B}(g^a, g^b), \operatorname{MAC}(k'_m, B)\}_{k'_e})\)

As we can see, it's the initiator \(A\) who discloses her identity first to \(B\), and responder \(B\) has a chance of verifying that identity before deciding to disclose his identity in turn. As with SIGMA-I, SIGMA-R has the following properties:

  • Since both identities \(A\) and \(B\) are encrypted, we have identity protection of both initiator and responder against passive attackers.
  • Since \(B\) has the opportunity of verifying the identity of \(A\) before disclosing his own identity, we have identity protection of the responder against active attackers.
  • By signing, we've prevented man in the middle attacks.
  • By MACing our own identity, we've prevented identity misbinding attacks.

If you've paid attention, you've noticed that \(A\) used keys \((k_e, k_m)\) while \(B\) used a different pair of keys \((k'_e, k'_m)\). The reason for this is to prevent reflection attacks. In other words:

  • \(k_e \leftarrow \operatorname{PRF}(g^{ab})\)
  • \(k'_e \leftarrow \operatorname{PRF}(g^{ab})\)
  • \(k_m \leftarrow \operatorname{PRF}(g^{ab})\)
  • \(k'_m \leftarrow \operatorname{PRF}(g^{ab})\)

IKE

A variant of the SIGMA protocols deployed in IPSec is IKEv1. Instead of separatly signing and MACing, we sign a MAC of \(g^a\), \(g^b\), and our own identity (the mac-then-sign construction):

The IKEv1 Protocol (aggressive mode):

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

Note that while this mac-then-sign construction can be proven secure, we've already seen that a variation such as sign-then-mac (which is nothing else than STS-MAC) isn't secure against an identity misbinding attack. This shows how even slight variations of a protocol can totally break security assurances. Just looking at a key exchange protocol isn't enough: since intuition has proven us wrong so many times, we need a rigorous formal proof that an AKE is actually doing what its designer intended it to do.

Of course, we need to protect the identities \(A\) and \(B\) from passive attackers by moving them inside an encrypted blob. This leads to

IKEv1 with Identity Protection (IKE Main Mode):

  1. \(A \rightarrow B \colon g^a\)
  2. \(A \leftarrow B \colon g^b\)
  3. \(A \rightarrow B \colon \{A, \operatorname{sign_A}(\operatorname{MAC}(k_m, A, g^a, g^b))\}_{k_e}\)
  4. \(A \leftarrow B \colon \{B, \operatorname{sign_B}(\operatorname{MAC}(k'_m, B, g^a, g^b))\}_{k'_e}\)

where \(k_e\) and \(k'_e\) are again encryption keys and \(k_m\) and \(k'_m\) are MACing keys drawn from a pseudo-random function seeded by \(g^{ab}\).

Exercise: IKEv1 main mode protects initiator's and responder's identities against a passive attacker. Whose identity is protected against an active attacker here?

Another variation of SIGMA (and IKEv1) is IKEv2, the current authenticated key exchange protocol of IPSec.

Reflection Attacks

Exercise: Show a reflection attack against the 4 message SIGMA-R and 4 message IKE Main Mode protocols, when \(k_e = k'_e\) and \(k_m = k'_m\).

On Full-fledged SIGMA Protocols

A real-world protocol is more complicated that the simplified versions we've seen above and in previous articles. A full-fledged SIGMA protocol includes additional fields like session IDs, nonces against replay attacks, certificates, counters, and so on. With added complexity comes more degrees of liberty in protocol design. For example: what additional fields should we include in the signature, in the MAC, in the encrypted blob? And with great flexibility comes great responsibility... and potential for bugs and outright mistakes that would break protocols.

To illustrate this point: while it makes sense to put more than less additional fields inside a signature, putting too many in there is bad. For example, add certificates (identities) inside signatures, and non-repudiability raises its ugly head again. There's an obvious tension between various choices, and it is not always clear which choice is sensible.

Another issue in real-world full-fledged protocols is the reuse (or rather misuse) of certain fields for totally different purposes. Hugo mentions nonces as a typical example. In the examples shown above, the ephemeral keys \(g^a\) and \(g^b\) had a dual-use as keys and as nonces, since they were generated afresh from a huge space for each run of the protocol. That's why replay attacks were unlikely. But even if the designers of the simplified core protocol knew what they were doing, sooner or later, someone would want to reuse \(g^a\) and \(g^b\) for some other purpose in a real-world version of that protocol... thus violating the nonce-ness use, and therefore totally breaking the protocol. That's why protocol designers are strongly advised to use distinct fields for each distinct purpose (e.g. use an explicit nonce field instead of relying on ephemeral keys' nonceness), even at the cost of more protocol bloat.

Due to the increasing complexity and brittleness of real-world protocols, hand-written proofs with paper and pencil are needed for each and every variant, before we can deploy some protocol in the wild with any confidence. Those proofs are tedious, slow, and human provers are prone to errors. An emerging reseach field deals with automated protocol verification, using programs like ProVerif, CryptoVerif, Tamarin etc. to ferret out obvious design mistakes. These verifiers can catch mistakes that even experts could miss. However, when they remain silent, it doesn't mean that the protocols are free of bugs. Furthermore these verifiers can't catch all subtleties, and some of them need manual guidance to steer their proofs: they are merely helpers in the capable hands of experts. But this is an interesting topic for another series of crypto bites.

But before diving into the interesting world of automated verification and code generation, let's look at implicitly authenticated Diffie-Hellman.

Source

This article is my transcript and understanding of the first 22:30 minutes of Hugo Krawczyk's talk "STS, Sigma and IKE (IPSec's Key Exchange)" 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 75 and ends at slide 86.

Literature

  • [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 (link.springer.com, technion.ac.il (full version)).