Original post

This post presents the Diffie-Hellman Key Exchange (DHKE) – an important part

of today’s practical cryptography. Whenever you’re accessing an HTTPS website,

it’s very likely that your browser and the server negotiated a shared secret

key using the DHKE under the hood.

## Mathematical prerequisites

The understand the math behind DHKE, you should be familiar with basic *group
theory*. A group is a set with a binary operation, such that any two items in

the set combined with the operation produce another item in the set, the

operation is associative, the set has an identity element w.r.t the operation

and each set element has an inverse.

The group we’re most interested in for the sake of understanding Diffie Hellman

is mathbb{Z}_{p}^{*} – the positive integers that are relatively prime

to *p*, with the “multiplication modulo *p*” operation (another common notation

for this group is (mathbb{Z}/pmathbb{Z})^*). This is a finite group.

By definition, its cardinality is phi(p), where phi is

Euler’s totient function.

As an example, mathbb{Z}_{9}^{*}={1,2,4,5,7,8}. The cardinality of

this group is phi(9)=6. We can multiply members of the group modulo

9 to get other elements of the group: 2*5equiv 1pmod 9,

8*4equiv 5pmod 9 etc.

For a prime *p*, the group contains all the integers from 1 to *p-1*

and its cardinality is *p-1*.

### Cyclic groups

Given a group *G* with the operator odot, we define the **order**

of an element *g* in the group – *ord(g)* – as the smallest positive integer

*k* such that:

[g^k=underbrace{godot godotcdotsodot g}_{k times}=1]

Where 1 is the identity element of *G*. Note that we use the exponent notation

g^k for convenience, even though odot is not necessarily a

multiplication – this would work for any group. For example, in the group

mathbb{Z}_{9}^{*} shown above, *ord(8)* is 2, and *ord(2)* is 6.

A group *G* which contains an element *a* with the maximal order

ord(a)=left|Gright| is called a **cyclic group**. Elements in a

cyclic group that have maximal orders are called *generators* or *primitive
elements*.

These elements can generate all the other elements of the group by repeated

application of the group operation. In other words, given a generator *g*,

every ain G can be expressed as g^k for some *k*.

For example, mathbb{Z}_{9}^{*} is cyclic and its primitive elements

are 2, 5 and 8.

It can be shown that for a prime *p*, the group mathbb{Z}_{p}^{*} is

always cyclic and has phi(p-1) primitive elements, though there’s

no easy way to find them – we just have to test them one by one. The proof of

this theorem is quite technical, so I’ll leave it for another time.

## The Discrete Logarithm Problem

The mathematical problem at the heart of the DHKE is the Discrete Logarithm

Problem (DLP). In this discussion I’m going to focus on the DLP in the

multiplicative group of integers modulo a prime – mathbb{Z}^{*}_{p},

and will mention the general DLP later on.

Given a finite cyclic group mathbb{Z}^{*}_{p} with a prime *p*,

a primitive element g in mathbb{Z}^{*}_{p} and another element

b in mathbb{Z}^{*}_{p}, the DLP problem is finding an integer

1le xle p-1 such that:

[g^xequiv bpmod{p}]

We’ve seen earlier that such an integer must exist because *g* is a primitive

element of the group.

The DLP is hard – no one knows how to solve it efficiently. This doesn’t mean

that such a solution doesn’t exist – it wasn’t proven to not exist. In this, DLP

is similar to factoring, which is essential for the security of RSA.

## Diffie-Hellman Key Exchange (DHKE)

The protocol starts with a *setup stage*, where the two parties agree on the

parameters *p* and *g* to be used in the rest of the protocol. These parameters

can be entirely public, and are specified in RFCs, such as RFC 7919.

For the main key exchange protocol, let’s assume that Alice and Bob want to

compute a shared secret they could later use to send encrypted messages to one

another. They know *p* and *g* already.

**Stage 1**

Alice does:

- Choose a random b_{alice}in{{2,dots,p-2}}
- compute B_{alice}equiv g^{b_{alice}} mod p

Bob does:

- Choose a random b_{bob}in{{2,dots,p-2}}
- compute B_{bob}equiv g^{b_{bob}} mod p

These *B*s are Alice’s and Bob’s public keys, while *b*s are their private

keys. Note that due to the DLP, it’s hard to compute *b* from *B*.

**Stage 2**

Alice sends B_{alice} to Bob, while Bob sends B_{bob} to Alice.

**Stage 3**

Now, Bob can compute B_{alice}^{b_{bob}}equiv (g^{b_{alice}})^{b_{bob}}equiv g^{b_{alice}b_{bob}}mod p.

Alice can compute B_{bob}^{b_{alice}}equiv (g^{b_{bob}})^{b_{alice}}equiv g^{b_{bob}b_{alice}}mod p.

These are equal, and serve as a shared key between Alice and Bob. They can now

use it to encrypt a strong symmetric cipher key (say, AES-256) and use that

to communicate in complete privacy.

## Authenticated DHKE

The basic DHKE protocol, as descibed above, is easily vulnerable to a

man-in-the-middle (MITM) attack. When Alice and Bob exchange their public keys

in stage 2, nothing guarantees to Alice that the key she received comes from

Bob. Eve could place herself between Alice and Bob and set up an exchange with

each one of them separately, while making them beleive they are talking to

each other. Then she could read all the traffic, while Alice and Bob suspect

nothing.

The solution to this problem is to use *authenticated DHKE* instead. The core

protocol remains the same, but when Alice and Bob exchange messages, these

are signed with a strong signature algorithm. For example, Alice and Bob can

use their RSA public keys to sign these messages. Then the MITM attack is

impossible because Eve can’t send a message to Bob pretending she’s Alice,

without access to Alice’s private RSA key.

## Forward secrecy

In the RSA post we’ve

seen how the RSA algorithm can be used to create a shared secret between two

parties and thus for secret communication. RSA has a serious flaw when used

like that, though. There’s a lot of traffic using a single key, which may help

breaking it. Once broken, this key can be used to read *all past* communications

that used the same key.

DHKE, on the other hand, has *forward secrecy*. A new DHKE shared secret is

generated for every session. Breaking this key will expose the secrets of this

session, but won’t enable the attacker to read all past correspondence. Such

keys are called *ephemeral*.

You may ask – can’t RSA be made ephemeral? Can’t we use a “master” RSA key to

authenticate the key exchange, and generate a fresh public/private key pair

for each communication? Yes, that’s absolutely possible, but DHKE is still

preferred because it’s more efficient. While generating an RSA key pair requires

finding two large primes with certain characteristics, generating a new DHKE

public key is simply choosing a random integer and computing a single modular

exponent – this is much faster.

## Choosing “safe” primes

We’ve seen before that the *p* and *g* parameters for DHKE are public. How are

these chosen? Can we choose any *p* and *g* and have strong security?

Turns out that the answer is no, due to some interesting math. Algorithms like

Index Calculus can

be used to crack the DLP in sub-exponential time. It’s so powerful that we’ll

need primes of 1024 bits to have 80-bit security (meaning the equivalent of

brute-forcing a 80-bit symmetric key).

When coupled with the Pohlig-Hellman attack, we may get in

trouble. This attack uses the CRT to break

the DLP in time proportional to the *factors* of *|G|* [1]. Note that when *p*

is a prime, *p-1* is composite, so it will end up having some factors. Which

factors? Hard to say, but we want to maximize them. The best way to maximize

them is to pick primes of the form *2q+1*, where *q* is a prime. Then

|G|=p-1=2q, and its factors are 2 and *q*. *g* is chosen such that it

generates a sub-group of size *q*, which ensures we have a large prime *|G|*.

Primes of the form *2q+1* are called *safe primes*.

For example, RFC 7919 recommends several parameters,

presenting them thus:

```
The hexadecimal representation of p is:
FFFFFFFF FFFFFFFF ADF85458 A2BB4A9A AFDC5620 273D3CF1
D8B9C583 CE2D3695 A9E13641 146433FB CC939DCE 249B3EF9
7D2FE363 630C75D8 F681B202 AEC4617A D3DF1ED5 D5FD6561
2433F51F 5F066ED0 85636555 3DED1AF3 B557135E 7F57C935
984F0C70 E0E68B77 E2A689DA F3EFE872 1DF158A1 36ADE735
30ACCA4F 483A797A BC0AB182 B324FB61 D108A94B B2C8E3FB
B96ADAB7 60D7F468 1D4F42A3 DE394DF4 AE56EDE7 6372BB19
0B07A7C8 EE0A6D70 9E02FCE1 CDF7E2EC C03404CD 28342F61
9172FE9C E98583FF 8E4F1232 EEF28183 C3FE3B1B 4C6FAD73
3BB5FCBC 2EC22005 C58EF183 7D1683B2 C6F34A26 C1B2EFFA
886B4238 611FCFDC DE355B3B 6519035B BC34F4DE F99C0238
61B46FC9 D6E6C907 7AD91D26 91F7F7EE 598CB0FA C186D91C
AEFE1309 85139270 B4130C93 BC437944 F4FD4452 E2D74DD3
64F2E21E 71F54BFF 5CAE82AB 9C9DF69E E86D2BC5 22363A0D
ABC52197 9B0DEADA 1DBF9A42 D5C4484E 0ABCD06B FA53DDEF
3C1B20EE 3FD59D7C 25E41D2B 66C62E37 FFFFFFFF FFFFFFFF
The generator is: g = 2
The group size is: q = (p-1)/2
```

The parameters in this RFC are the only ones approved for the newest TLS

standard – version 1.3, which also removes the support for custom groups.

The safety of the primes used for DHKE is not a purely theoretical concern!

Real attacks have been (and are probably still being) mounted against unsafe

choices. See CVE-2016-0701

for example, and the paper Measuring small subgroup attacks against

Diffie-Hellman for more

technical details.

## A word on elliptic curves

Elliptic curves are all the rage in cryptography in the past couple of decades, and for a good reason. They provide

similar security to the “classical” multiplicative modular groups with much

smaller keys. If you’re using TLS 1.3, the key exchange protocol will most

likely be ECDHE – Elliptic Curve Diffie-Hellman Exchange.

Explaining elliptic curves is a huge topic of its own, so I’ll just briefly

mention them w.r.t. the material presented in this post.

The beauty of abstract algebra is that you can develop mathematics that will

apply in the same way to very different groups. We’ve seen the DLP defined for

multiplicative modular groups, but it can also be defined for different groups.

Elliptic curves are pairs of points which fullfill certain polynomial equations

[2], and when set up properly these points can form cyclic groups under certain

operations. A DLP can be defined for these groups, and it’s as hard to solve as

the classical DLP. Much of the math remains the same – generators, subgroups,

and so on. DHKE looks the same as well – Alice and Bob both pick a random group

member, and compute an “exponent” (repeated application of the group operation),

sending it on the wire. They combine their exponents to get a shared secret key,

while Eve cannot reconstruct their private exponents from the transmitted

information because of the infeasibility of the DLP.

Elliptic curve groups are great because – compared to classical multiplicative

modular groups – they are less susceptible to sub-exponential attacks.

Therefore, to gain ~128 bits of security (i.e. make attacks equivalent to

brute-forcing 128-bit values) we can use a key of size 256 bits (as opposed to

3072 bits for classical DH). This makes cryptographic protocols much faster.

[1] | Specifically, it’s proportional to the sizes of the subgroup which thegenerator generates. The size of subgroups are related to the factors of |G|, per Lagrange’s Theorem. |

[2] | y^2=x^3+ax+b, which should look familiar from analytic geometry in middle school. |