Key-Exchange

In Introduction to Cryptography, we explained one of the biggest issues with "traditional" cryptography (more appropriately called Symmetric-Key Cryptography). If two or more parties wish to communicate in a secure manner (without anyone being able to eavesdrop on or modify their messages), the will need to somehow exchange the agreed upon secret key with which they will encrypt their messages (you can read Symmetric-Key Cryptography for more in-depth explanation on symmetric key cryptography). This exchange requires a secure channel through which the key can be sent, as if someone was able to get access to their key, they will be able to decrypt all future messages. Back in the day people would meet secretly to exchange their keys. But in the modern age, where the volume of communication is too great, it is impractical to have to go through all these hoops to be able to send securely messages with someone else. This is where the revolutionary paper by Whitfield Diffie and Martin Hellman comes in all the way back in 1976 [1]. It was the first publicly available paper, which described a protocol through which two parties can agree on the same secret key through an unsecure channel, without anyone else being able to get ahold of their keys.

Nowadays with the development of Asymmetric-Key Cryptography, which doesn't necessitate the two parties to use the same key, key-exchange protocols may seem obsolete. However, they still find uses in End-to-End encryption protocols as they provide "forward secrecy" - if one of your messages gets decrypted by a third party, they may not be able to always decrypt following ones. As such it is important to be familiar with these protocols as well, in order to understand current more advanced concepts and algorithms. Additionally, if one doesn't want to bother with some of the complexity that comes with public key distributions and deletions, key-exchange protocols allow for a simple alternative.

The Key-Exchange Problem

Let us focus on the key-exchange problem through a simple story about our favourite trio - Alice, Bob, and Eve. Eve is the reallllyyyy jealous ex-wife of Bob and wants to sabotage all future relationships of his. Fortunately for her, she works at the post office, so she can read and modify all of Bob's messages. Bob has recently met a girl, with whom he regularly exchanges letters. Bob is aware of his ex-wife's intentions, hence why he wants to encrypt his communication with Alice.

If Bob and Alice met beforehand somewhere, they could have agreed on a secret key between them and continue to send their letters, without a worry. However, they are rather forgetful (and in love) so they spaced out that they need to do that during their last date. Bob thinks about sending the secret key to Alice in his next letter. However, Eve will surely read it, write down the key, and continue to monitor their conversation. Thus this simple solution would not work.

While thinking about this at his art studio, Bob has an idea how to agree on a key with Alice, without Eve being able to find out what it is. Bob quickly takes out a pen and paper and begins writing his plan. First, they will both buy some paint colour that they can both agree on (the specific colour doesn't matter too much and it is fine if Eve knows it too). Then, each of them, will buy another paint colour without telling the other one what it is. At home they will mix their own paint colour with the agreed upon one and send it in a letter to the other. Then, when they receive each other's letters, they will mix the received paint with their own paint. Whatever the colour of the result is will be their secret key. This hinges on three properties of paint. Most important one of them is that figuring out what the two paints used to create this colour is decently hard (anyone who has had to repaint a wall can understand the struggle). This means that Eve, while being able to see the resultng colour, as well as the originally agreed upon one, she will need a lot of time to figure out which specific paint colour each one used in secret. Second property of paint is that the order of mixing doesn't matter - whether Bob mixes yellow, green, blue or blue, green, yellow, doesn't matter - the result will be the same. Third - mixing the same colours will always produce the same result (there is no randomness in the process). Below you can find an illustration of this process from [2]:

Diffie-Hellman Key-Exchange

The previous analogy explains the Diffie-Hellman Key-Exchange protocol. Naturally, in the world of cryptography we don't use paint, but rely on prime fields (as seen below) or elliptic curves. The operations in either rely on the fact that currently, we have no efficient way of computing the discrete logarithm problem (inverting the paints in the analogy). Below are the steps of the Diffie-Hellman protocol:

Bob and Alice agree on a very large prime (p) - for example one send to the other in a public channel
Bob and Alice agree on a number 1p. This means that as we raise g to powers 1, 2, 3... modulo p, we will see each number 1≤g≤p-1 at most ones, i.e. g^a mod p = g for no other 1≤a≤p-1 other than 1.
Bob chooses a secret sB and Alice chooses a secret sA. Both sB and sA are greater than 1 and less than p
Bob calculates g^sB mod p = mB and sends it to Alice
Alice calculates g^sA mod p = mA and sends it to Bob
Bob receives Alice's message and calculates mA^sB mod p = k, where k is their common secret
Alice receives Bob's message and calculates mB^sA mod p = k, where k is their common secret
This holds because (g^sB mod p)^sA mod p = (g^sA mod p)^sB mod p = g^sA*sB mod p

Bob and Alice can now continue their communication using some form of Symmetric-Key Cryptography and Eve will not be able to read their messages, as she:

Has g, p, mB (g^sB mod p), and mA (g^sA mod p)
She cannot realistically obtain sB from mB
She cannot realistically obtain sA from mA
She cannot compute g^sA*sB mod p = k from the information she has

Below you can find an interactive example (obviously for the sake of understanding we work with small numbers here. Normally they would be really really large):

Bob	Alice	Eve
Chooses p =	Chooses p =	Sees p =
Chooses g =	Chooses g =	Sees g =
Chooses sB =	Chooses sA =
g^sB mod p =	g^sA mod p =
Sends	Receives	Sees
Receives	Sends	Sees
Calculates mA^sB =	Calculates mA^sB =
Continues secret communication	Continues secret communication	Can't do a thing

Drawback of Diffie-Hellman

The protocol described above works great if the attacker can only listen to messages. If they can also modify messages, well the protocol fails. Suppose Eve listens on the shared g and p, and chooses her own secret - sE. Then to Bob and Alice she sends g^sE mod p, pretending she is the other intended party. Bob and Alice continue the protocol with Eve, thinking their doing it with each other instead. At the end of it, Eve will have two secret keys - one for communication wiht Bob and the other for communication with Alice. Whenever she receives an encrypted message from Bob, she decrypts it, reads its contents, and encrypts with the key for Alice before sending it to her. The two lovers remain none the wiser.

This problem can be remedied if Bob and Alice have some way to prove their identity to each other, for example via Digital Signatures.