Diffie-Hellman Key Exchange

Tags Math

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}/p\mathbb{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*5\equiv 1\pmod 9, 8*4\equiv 5\pmod 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{g\odot g\odot\cdots\odot 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|G\right| 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 a\in 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 1\le x\le p-1 such that:

\[g^x\equiv b\pmod{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 private 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.

For comments, please send me an email.