Key Exchange Protocols

Key exchange protocols form a crucially important family of cryptographic protocols. Without key exchange (KE), Alice and Bob can't even establish a secure channel which provides confidentiality and integrity. In this mini-series, we'll explore a couple of key exchange protocols and discuss their properties.

We start with and closely track Hugo Krawczyk's presentation at the 8th BIU Winter School on Cryptography on Secure Key Exchange, February 11-15th 2018, as well as his paper on the SIGn-and-MAc Approach[K03]. Following a beginners' level introduction to unauthenticated Diffie-Hellman, we'll try to thwart man in the middle attacks with various modifications to the DH protocol. Almost everyone will assume a public key infrastructure (PKI) and will start by signing Alice's and Bob's ephemeral public keys. But there's one problem with that: both participants leak ephemeral signatures that lack freshness and that are vulnerable to replay attacks. The next step is to add freshness, by including the other side's ephemeral public key into the signature. The resulting 3-way handshake protocol (BADH) may look good to the untrained protocol designer, but now, we're wide open to an unknown key share attack. UKS, also known as identity misbinding attack, is the killer of countless authenticated key exchange protocol designs that have been proposed in the past. To prevent UKS, we show the ISO fix, in which each participant signs the peer's identity. Is this fix secure? To prove this, we need the Canetti-Krawczyk model, which we won't explain in this mini-series. Instead, Hugo sketches a fascinating proof using authenticators.

Up to here, we didn't address privacy a.k.a. identity protection issues. With the ISO protocol, Alice and Bob are sending their identities in the clear, for every attacker to collect. Even worse, by signing information that went over the wire and sending those signatures out, they are offering a trail of non-repudiable (!) connection logs to eavesdroppers. Clearly, this isn't acceptable. Many protocols have been proposed to resolve these issues. Unfortunatly, most of them are vulnerable to UKS. To learn what to avoid, we discuss a flawed real-world example: the STS protocol. From the lessons learned there, we'll move on to the very important family of SIGMA protocols that are at the heart of IPSec (IKE) and TLS 1.3 (SIGMA-I), and which provide, in addition to deniability, privacy protection of initiator and responder against passive attackers, and privacy protection of either initiator or responder (but not both) against active attackers.

Protocols like STS, SIGMA etc. aren't cheap: they require 3 or 4 messages for the handshake, and make use of expensive cryptographic operations like more bignum exponentiations than unauthenticated Diffie-Hellman, encryptions, public key signatures, MACs and so on. Striving for minimalism, we would like AKEs that are more efficient than that, both in terms of communication overhead and required computational power (think smart cards, IoT devices, ...). One class of minimalistic AKEs is that of implicitly authenticated DH, which include protocols like HMQV that are based upon the cryptographic primitive of designated verifier signatures, which are only verifiable by a verifier chosen by the signer (e.g. by her peer).

Of course, even though this mini-series currently ends here (I may extend it later), it is not the end of the KE design saga. Analyzing the security of these simplified KE schemes as well as their full-blown real-world counterparts is tedious and error-prone. This raises the question of automated protocol verification, and of verified protocol implementations (libraries), which is covered by Karthikeyan Bhargavan in the third part of the 8th Winter School (covered in the Verified Crypto series).

Happy watching and reading.

Covered Topics

Relevant Topics in the Verified Crypto series

Let's have a party!

After learning a lot about Alice and Bob's key exchanges in this series, it is time to let other participants join the fun. Mark Zhandry, back then a PhD candidate at Stanford University and now assistant professor at Princeton University, presents in the following video Multiparty NIKE (non-interactive key exchange)[MZ17], a key exchange protocol that doesn't require the parties to be online all the time (i.e. it is asynchroneous, non-interactive) for more than just two parties (group keys). This protocol leverages multilinear pairings. Slides.

Source

This complete series is my own transcript of the 8th BIU Winter School on Cryptography, Secure Key Exchange, February 11-15 2018,  that is organized by the Center for Research and Applied Cryptography of the Bar-Ilan University, Israel. This transcript wouldn't exist without the slides and videos of the talks that were graciously provided to the general public.

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)).
  • [MZ17] Fermi Ma, Mark Zhandry: Encryptor Combiners: A Unified Approach to Multiparty NIKE, (H)IBE, and Broadcast Encryption. (iacr.org, full pdf)