When you want to encrypt your communications, you have the choice between two main families of algorithms:

1. Asymmetric encryption, they use two keys, one is public and allows encryption, the other remains private and allows decryption.
2. Symmetric encryption, they use the same key to encrypt and decrypt.

The advantage of the former lies in their public key, which can be publicly distributed and thus allow everyone to be able to send us messages.

But as soon as performance is an important criterion, they lose out to the latter, which are much more efficient but which require the correspondents to share a secret (the key).

The Diffie-Hellman key exchange protocol, named after its second inventors (those who filed the patent in 1977 because the first discoverers, working in the UK government communications services, were unable to publish their discovery), is a communication protocol to solve this problem: establish a shared secret by exchanging messages via a public communication channel.

Key exchange protocol

The goal is therefore to compute a common value without an indiscreet ear being able to guess it. Rather than repeating the metaphor based on paint, I offer you a more geographical version…

Basic principle

Establishing a secret key is a bit like establishing a rendez-vous point. The goal, for Alice and Bob who want to be able to talk quietly, is to meet in the same place without Eve, who is spying on their communications, knowing where they are.

To start Alice and Bob meet in a public place, this is the starting point. They secretly choose the trip they want to make and go their separate ways. Once at their point of arrival, they send each other their respective position, exchange places and redo the same movement. Hopefully, they end up in the same place, but not Eve.

For this protocol to work, there are a few small constraints to respect. It is considered that Eve is not able to follow the movements, she can only listen to the communications.

1. The order of the moves does not change the end point (they are commutative);
2. Eve cannot compute a move by observing a start and end point.

Moving by compass over short distances respects the first constraint (over very long distances, the curvature of the Earth no longer guarantees the associativity of these movements) but not the second. You will arrive at the same place, but for Eve, the computations are easy.

To respect the second constraint, we need a displacement that Eve cannot reverse. Let’s take, for example, a sequence of random movements (forward, backward, right, left) and let’s play there in a maze, even if it means bumping into the walls. By observing the point of departure and arrival, Eve cannot deduce the full sequence of movements. The problem this time is that there is no guarantee that Alice and Bob will arrive at the same place in the maze.

It therefore requires a space and an operation that is associative and difficult to reverse. Chance doing things well is precisely the characteristics of the discrete logarithm problem, subject of a previous article.

Formal definition

Alice and Bob will therefore use a finite group and a generator. The finite group is the space they will move through, the generator is their starting point, the exponentiation is how they move, and the secret exponents are Alice and Bob’s moves.

The key exchange protocol proceeds as follows:

1. Alice and Bob publicly agree on a group $(G, \times)$ and a generator $g$,
2. They each choose a random number (their secret key), $a$ for Alice and $b$ for Bob, this will be their move,
3. They compute their first destination (their public key) and send it to each other; Alice therefore sends $g^a$ to Bob and receives $g^b$ in return,
4. They calculate their final destination by applying their exponent again; Alice calculates $g^{b^a}$ and Bob calculates $g^{a^b}$.

First constraint. The equivalence of endpoints is due to the commutativity of the operation: $$g^{a^b} = g^{ab} = g^{ba} = g^{b^a}$$

Second constraint. The security of this algorithm is based on the fact that Eve, knowing $g$, $g^a$ and $g^b$, is not able to compute $g^{ab}$. This property is known as the Diffie-Hellman problem and, in the state of current knowledge, seems to be as difficult than that of the discrete logarithm.

We speak of a key exchange protocol because the pairs $(a, g^a)$ and $(b, g^b)$ are the pairs of private and public keys of Alice and Bob. These keys are used to computes the shared secret and if you go up to ElGamal, to encrypt messages.

Security

This protocol, used alone, has no use and is therefore used in conjunction with other protocols that fill its gaps (signature) and benefit from its strengths (persistent confidentiality).

Need of signatures

If Eve is able to intercept and modify communications, which is the case when using some communication channels, the security of the protocol falls.

If Eve steps between Alice and Bob, she too can choose a number $e$ and send $g^e$ to either side. Neither knowing that it is Eve, each communication half will be secured by a secret key: $g^{ae}$ between Alice and Eve and $g^{be}$ between Bob and Eve.

To avoid this risk, communications are therefore signed by Alice and Bob via public keys previously exchanged or certified by a trusted third party.

Persistent Privacy

We can then wonder the usefulness of this protocol… What is the point of using a key exchange protocol since it requires an asymmetric encryption/signature system? Why don’t we use a public key protocol directly!?

Yes, but what if Eve stored up all communications between Alice and Bob and took her time cracking Bob’s private key? Once the key is broken (or stolen, there’s no rule), all past and future communications would then be compromised.

Forward secrecy corresponds to this need to protect past communications and the Diffie-Hellman key exchange brings this property to the exchanges between Alice and Bob:

• They sign the communications during the key exchange;
• They use Diffie-Hellman to create a key;
• They use this shared key to encrypt the rest of the communication.

With this variant, even if Eve has the private key used to sign the communications, she still has to break the shared key to find out what they are talking about.

And if, in addition, Alice and Bob use different numbers at each session (we then speak of ephemeral keys), Eve will have to break each key individually.

Usage in SSL/TLS

When a client and a server set up a connection secured by SSL/TLS, this is encrypted using a symmetric algorithm and therefore requires that the client and the server agree on the key to be used.

Without going into the details of the messages exchanged (i.e. RFC-5246), the establishment of a connection follows the following steps:

1. Hello The client and the server agree on the algorithms they will use for cryptographic operations, the famous “cipher suites”.
2. Certificates The server sends its certificate and can ask the client to send one too. Each party verifies the authenticity of the certificates via their trusted third parties (the famous CA).
3. Key Exchange Messages The server sends the necessary data for the key exchange, the client will do the same afterwards.

Depending on the algorithms chosen in the Hello messages, the key exchange is done differently:

RSA In this mode, the client generates a shared key and sends it to the server, after having encrypted it with the server’s private key. Breaking the server key decrypts all communications it receive (past, present and future).

DH - fixed In this mode, the certificate (of the client and/or of the server) already contains the parameters and public keys. The key exchange messages are therefore empty (since the data is in the certificate), the parties compute the shared secret thanks to the content of the certificates. It is then necessary to break the shared key but once done, all subsequent communications will be readable.

DHE - ephemeral In this mode, the key exchange is replayed (with different numbers) at each session via Key exchange messages. It is therefore necessary to break each key individually for each session.

Although the communication is initiated by the client, it is the server which sends the first message for the key exchange (and therefore fixes the group and the generator). This is because, culturally, it is the company hosting the server that takes responsibility for communications security.

The ECDH and ECDHE algorithms for key exchange are also Diffie-Hellman key exchanges but use elliptic curves (hence the mention EC) as a group for their computations. The protocol is identical, only the elements and the operation change.

And after

One could almost speak of a dream protocol. It’s simple to implement, requires few operations, can run publicly while providing persistent privacy to all your sessions.

You now know how it works, the reasons for its security, its limitations and above all how it can be used to have secure communications.