Diffie-Hellman

Diffie–Hellman Key Exchange

Key Exchange

To encrypt communications, Alice can use AES. For this, Bob needs to know the same symmetric key so Alice can generate one and send it over to Bob. After that, they can simply use the key to encrypt their communications.

But what if an adversary is passively snooping in on their conversation? Now the adversary has the symmetric key and can decrypt all encrypted content that Alice and Bob are sending to each other! This is where using a key exchange can be interesting for Alice and Bob (and for ourselves in the future). By using a key exchange, they can obtain a symmetric key that a passive observer won’t be able to reproduce.

A key exchange starts with both Alice and Bob generating some keys. To do this, they both use a key generation algorithm, which generates a key pair: a private key (or secret key) and a public key. Alice and Bob then send their respective public keys to each other. Public here means that adversaries can observe those without consequences. Alice then uses Bob’s public key with her own private key to compute the shared secret. Bob can, similarly, use his private key with Alice’s public key to obtain the same shared secret. Pictorially:

A key exchange provides the following interface: it takes your peer’s public key and your private key to produce a shared secret. Your peer can obtain the same shared secret by using your public key and their private key.

An active MITM would have no problem intercepting the key exchange and impersonating both sides. In this attack, Alice and Bob would effectively perform a key exchange with the MITM, both thinking that they agreed on a key with each other. The reason this is possible is that none of our characters have a way to verify who the public key they receive really belongs to.

The key exchange is unauthenticated!

Pictorially:

An unauthenticated key exchange is vulnerable to an active MITM attacker. Indeed, the attacker can simply impersonate both sides of the connection and perform two separate key exchanges.

While key exchanges are useful, they do not scale well in all scenarios without their sister primitive—the digital signature. Key exchanges are rarely used directly in practice, however. They are often just building blocks of a more complex protocol.

Group

A group contains:

• A set of elements

• A special binary operation (like + or ×) defined on these elements

Note that Diffie-Hellman works in a multiplicative group: a group where the multiplication is used as the defined binary operation.

A (multiplicative) group has the following properties:

• Closure: Operating on two elements results in another element of the same set. For example, for two elements of the group a and b, $a \cdot b$ results in another group element.

• Associativity: Operating on several elements at a time can be done in any order. For example, for three elements of the group $a$, $b$, and $c$, then $a(bc)$ and $(ab)c$ result in the same group element.

• Identity element: Operating with this element does not change the result of the other operand. For example, we can define the identity element as $1$ in our multiplicative group. For any group element a, we have $a \cdot 1 = a$.

• Inverse element: Existing as an inverse to all group elements. For example, for any group element a, there’s an inverse element $a^{-1}$ (also written as $\frac{1}{a}$) such that $a \cdot a^{–1} = 1$ (also written as $a \cdot \frac{1}{a} = 1$).

Diffie-Hellman works over $\mathbb{Z}/p\mathbb{Z} = \{1, 2, 3, ... , p-1\}$, where $p$ is a large prime.

$\mathbb{Z}/p\mathbb{Z}$ has two additional properties:

• Commutative: The order of operations doesn't matter. For example, given two group elements a and b, then ab = ba. A group that has this property is often called an Abelian group.

• A finite field: A Galois group that has more properties, as well as an additional operation (in our example, we can also add numbers together).

Due to the last point, DH defined over this type of group is sometimes called Finite Field Diffie-Hellman (FFDH).

Subgroup

A subgroup is just a group contained inside your original group. That is, it’s a subset of the group elements. Operating on elements of the subgroup results in another subgroup element, and every subgroup element has an inverse in the subgroup, etc.

A cyclic subgroup is a subgroup that can be generated from a single generator (or base). A generator generates a cyclic subgroup by multiplying itself over and over. It happens that when our modulus is prime, every element of our group is a generator of a subgroup. These different subgroups can have different sizes, which we call orders. Here is an example:

The different subgroups of the multiplicative group modulo 5. These all include the number 1 (called the identity element) and have different orders (number of elements).

Ring and Field

The set of integers modulo $n$, together with the operations of both addition and multiplication is a ring. This means that adding or multiplying any two elements in the set returns another element in the set.

When the modulus is prime: $n = p$, we are guaranteed an inverse of every element in the set, and so the ring is promoted to a field. We refer to this field as a finite field $F_p$.

The Diffie-Hellman protocol works with elements of some finite field $F_p$ , where the prime modulus is typically a large prime.

Generator

Every element of a finite field $F_p$ can be used to make a subgroup $H$ under repeated action of multiplication. In other words, for an element $g$: $H = \{g, g^2, g^3, ...\}$

A primitive element of $F_p$ is an element whose subgroup $H = F_p$ , i.e., every element of $F_p$ can be written as $g^n \mod p$ for some integer $n$. Because of this, primitive elements are sometimes called generators of the finite field.

Discrete Logarithm Problem (DLP)

The security of the Diffie-Hellman key exchange relies on the Discrete Logarithm Problem (DLP) in a group, a problem believed to be hard to solve.

Diffie-Hellman key generation:

1. All the participants must agree on a large prime $p$ and a generator $g$.

2. Each participant generates a random number $x$, which becomes their private key.

3. Each participant derives their public key as $g^x \mod p$.

The fact that the discrete logarithm problem is hard means that no one should be able to recover the private key from the public key. For example:

Choosing a private key in Diffie-Hellman is like choosing an index in a list of numbers produced by a generator g. The discrete logarithm problem is to find the index from the number alone.

Lab

CryptoHack – Diffie-Hellman challengesCryptoHack

Diffie-Hellman - CryptoHack

Reference

Real-World CryptographyManning Publications

Real-World Cryptography