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 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 Bs are Alice’s and Bob’s public keys, while bs 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 the
generator 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.