The Diffie Hellman key exchange

Modern cryptography allows for the communication of secret messages over a public network.

So far this series has only covered symmetric cryptography, which requires the sender and receiver to have communicated some kind of secret before using the network. 

In our first blog post on cryptography basics, we introduced symmetric ciphers, a basic encryption scheme using a one-time pad. Then, in our second post, we introduced cryptographic hash functions, which help to uphold message integrity. 

In this blog post, we’ll introduce asymmetric cryptography, which allows for secure communication without needing to exchange any secrets ahead of time. Specifically, we’ll examine the Diffie-Hellman (DH) exchange, a method which allows a sender and receiver to arrive at a shared secret even if all of their communication is observed. This shared secret can then be This shared secret can then be used to encrypt communication using the more efficient symmetric algorithms covered in prior posts.

‍

Diffie–Hellman

Named after its inventors Whitfield Diffie and Martin Hellman, the Diffie–Hellman (DH) key exchange is a way to exchange a secret key over a public network. First introduced in 1976, it’s one of the first examples of asymmetric cryptography and remains widely used today. Web browsers frequently use DH to secure communication with web servers over the internet as one part of TLS protocol.

The security of DH is based on the asymmetric difficulty of certain mathematical operations. For example, it’s easier to multiply two numbers compared to factoring their product. Consider these two questions:  “What are the factors of 1679?” and “What is 23*73?“. Multiplication can be done with a straightforward algorithm, but factoring requires a trial-and-error approach. DH uses this type of mathematical asymmetry to allow Alice and Bob to arrive at the same value without an observer able to do so, even when the observer has access to every message Alice and Bob have exchanged.

A common metaphor used to illustrate DH is mixing paint. First Alice and Bob agree on a common colour to use as their base. They then each choose a secret colour paint to mix into it. The mixtures can be shared without revealing the colours or quantity added to anyone who may obtain a sample. Alice and Bob then mix the same proportion of their secret colour with the received colour to both end up with the same colour.

The paint analogy assumes that unmixing the observed paint is difficult, such that Eve is unable to determine what colour Alice and Bob both end up with as a final product, even though she knows the starting colour and sees it mixed with both Alice and Bob’s secret colours. Mixing paint captures the asymmetric difficulty between calculating exponents, and is a good visualization to gain an intuition for an otherwise abstract concept. However, computers operate on numbers, so some advanced mathematics is used to provide a mechanism that operates like the paint-mixing analogy.

To begin, Alice and Bob will first agree on parameters to use for their calculations – the “shared colour” in the paint mixing analogy. These shared parameters don’t need to be kept secret and are only used as a starting point. For DH, Alice and Bob first agree on two values, a large prime number and a smaller number known as a generator. These numbers define a modulo group that Alice and Bob will use for calculations. The prime is often referred to as p, and the generator as g in equations.

Mathematically speaking a group is a set of numbers along with an operation, such that every element has an inverse and there exists an identity element with respect to the operation. Some examples would be the set of integers with addition. “+ 0” is effectively no operation, so it is the identity element of that group. For multiplication, the identity element is 1. The inverse means any operation with one element can be reversed by applying the same operation with another element, such as +3 being cancelled by +(-3). Note 0 needs to be excluded from the multiplicative group since it lacks an inverse. 

For DH, the operation is exponentiation, e.g. (2^x), and the set will be the numbers 1,2,3…p. All operations will “wrap” around at p. The modulo group should be based on a prime number for a number of reasons. Generally, the hard problem asymmetric cryptography relies on is that factoring numbers is difficult. Non-prime modulus can have easy-to-find factors that make the challenge easier. Also, prime modulo groups have elements that can serve as good generators. Ideally, generators are able to produce any element in the set by raising the initial number to an arbitrary power.

For example, given the prime modulo 5, a good generator element is 2.
2¹ mod 5 = 2
2² mod 5 = 4
2³ mod 5 = 3
2⁴ mod 5 = 1

To be safe in the era of modern computers, these numbers should be much larger than the examples given. In fact, they should be so large that a modern computer cannot brute force all of the possible numbers. There is nuance to parameter selection and the literature should be checked for exact details.

Once Alice and Bob agree on a group (defined by p and g), they will each select a random number to keep secret. Alice and Bob will both raise the generator point by the power of their random number. They then exchange their product values over the network. Again, these product values do not need to be kept secret. The assumption is that undoing exponentiation is impractical for Eve so she can not determine the secret value that was mixed in, just as she was unable to unmix the paint in the analogy.

Upon receiving each other's mixed numbers, Alice and Bob each raise the received value with the same secret number they used in the previous step. Alice will have calculated (g^x)^y mod p, and Bob will have calculated (g^y)^x mod p. The commutative property ensures (g^x)^y = (g^y)^x. This means Alice and Bob should have the same number after this process that Eve is unable to determine. Since Alice and Bob have a shared number that only they know, they can then use this as a basis for a key used in a symmetric cipher.  

It’s important to note that although this number is a shared secret, it shouldn’t be used as a key directly. Instead, it should be used as input to a key derivation function (KDF), like Argon2, which will deterministically produce a value that is suitable to be used as a secret. Even though the shared number is secret, it likely lacks the random distribution that symmetric algorithms require. A KDF provides a way for Alice and Bob to derive a well-distributed value from their shared number.

During the exchange, Eve may learn what g, p, g^x and g^y represent, yet she is unable to determine the secret values Alice and Bob denoted by x and y. The difficulty of reversing exponentiation compared to calculating it allows Alice and Bob to each create commutative one-way functions, allowing them to arrive at the same value. This is referred to as the discrete logarithm and forms the basis of security for many cryptographic algorithms.

Although DH may have allowed Alice and Bob to exchange secrets over a public network, it does have a vulnerability when used alone. If Eve was able to intercept the communications, she could perform a “man in the middle” (MITM) attack by impersonating Alice and Bob. If Eve performed two DH handshakes, one with Alice and one with Bob. She could then decrypt each message, read and edit it, then re-encrypt it with the other key. DH allows for secrets to be communicated over a public network, but by itself, it lacks a mechanism to authenticate each party.‍

It's possible for Alice and Bob to have agreed on some kind of secret beforehand and use a symmetric message authentication scheme, but this would mitigate many of the benefits asymmetric cryptography brings. Alice and Bob would still need to exchange some kind of password in advance to ensure they really are communicating with one another. 

That said, there are still some benefits to DH with symmetric authentication. If Alice and Bob use DH every time they wish to communicate, they can ensure each session is encrypted with a unique key. As long as they both delete the secrets used, even if their password is later compromised, prior communications remain undecryptable. This method is referred to as “Diffie Hellman ephemeral” or the abbreviated DHE. The cryptographic property this provides is known as forward secrecy.

As mentioned earlier, web browsers frequently perform DH as part of TLS. In order to ensure the server belongs to the owner of the domain name, certificate authorities generate public/private key signatures.

‍

The next installment by Polymesh developer Eric Richardson will cover these public/private key signatures, which will introduce RSA.