Understanding and verifying security of Diffie-Hellman parameters

When we use machines to communicate over the internet, we often want those exchanges to be secure: protected against modification in transit, scrambled in a way that only we and the intended recipient can read it, and linked with a specific identity (a specific server or person) so that we know who we are communicating with. 

While there are multiple protocols that provide assurances about security, the good ones require that the parties agree on some shared secret before any user data can be encrypted and integrity protected. 

There are two methods commonly used to agree on shared secrets: have one party use some long-term asymmetric key to encrypt the secret and send it to the owner of the key (like in an RSA key exchange), or have both parties exchange messages that contribute to the computed shared secret (what we call Diffie-Hellman key exchange). 

The security of both methods depends on picking numbers that are just right. In one variant of the Diffie-Hellman key exchange one of the parameters needs to be a large prime number. Because the key exchange is vulnerable to attacks if the number is not prime, or not a special kind of prime, the Red Hat Crypto Team has developed a tool to provide mathematical proof that the numbers we distribute are indeed primes of that special type and thus aren’t the weakest link in the security of systems that depend on them. We’ve also published a set of primality certificates to allow for quicker verification of their primality.

At the end of this article you can find instructions on how to use this tool, called ecpp-verifier, to verify the primality certificates or how to check that all the primes used by OpenSSH have matching certificates.

Diffie-Hellman: Mixing the color of security

The problem we are facing with key exchange is of two parties agreeing on a shared secret over an insecure channel that can be observed by an attacker (for simplicity, let’s not consider an attacker that is also able to modify exchanged messages, this is solved by authentication).

From a high level perspective, key exchange algorithms work similar to mixing paint, relying on the property that it is easy to mix them, but very hard to separate them back. Both parties start with a publicly known “base color.” They mix it with a secret color and exchange the result with the other party. 

The other party adds their secret color to the received mix and they both end up with the same result. An attacker is not able to do the same as they are not able to separate the secret colors from the mix and combining exchanged mixes would result in a different color.

Mathematically speaking, we need a function f that (1.) is hard to reverse and (2.) for any combination of arguments, it holds that f(f(x, a), b) = f(f(x, b), a). 

Going back to the paint example, x is the publicly known color and a, b are secret colors of respective parties.

The whole scheme is called Diffie-Hellman key exchange. There are two functions with the required properties commonly used in cryptography: exponentiation modulo prime (forming Finite Field Diffie-Hellman, or FFDH) and point multiplication over elliptic curve, forming Elliptic Curve Diffie-Hellman (ECDH). 

In Red Hat Enterprise Linux (RHEL) we support ECDH over only a select set of well-known curves that have been extensively examined by the cryptographic community, there is nothing more we need to do to show their security. At the same time, some protocols, like SSH and TLS before TLS 1.3, allow the server to pick arbitrary numbers as the basis of the FFDH key exchange. 

In particular, in the OpenSSH package, we distribute the /etc/ssh/moduli file that includes tens of prime numbers of different sizes. Those primes will be used for diffie-hellman-group-exchange-sha1, diffie-hellman-group-exchange-sha256, or gss-gex-sha1-* key exchanges. With the security of SSH depending on the choice of these numbers, how do we make sure they’re a good fit? Let’s first take a look at what FFDH uses them for.

Finite Field Diffie-Hellman

As I wrote previously, finite field Diffie-Hellman uses exponentiation modulo prime to agree on a shared secret. The parameters we need are a prime number p (more about it later), the number which we will be exponentiating g (called the base or generator) and two exponents, let’s call them a and b. The exponents are secret and aren’t shared with the other party. 

The key exchange will look something like this:

• Party A will select a random number a between 1 and p, calculate the value of base g to the power a modulo p, let’s call it x, and send it to party B.

• Party B will do similar steps: select a random number b between 1 and p, calculate the value of base g to the power b modulo p, let’s call it y, and send the result to party A.

• Upon receiving the value from B, party A will take that number y and raise it to power a modulo p. Similarly party B will take the number x and raise it to power b modulo p.

Since x^b=g^ab=g^a·b=g^b·a=g^ba=y^a mod p, both A and B get the same result without exchanging either a or b explicitly or a value that allows easy calculation of either a or b.

You may wonder why guessing a or b is hard, given that we have logarithms. 

The reason is that we need to calculate discrete logarithms, for which there is no efficient general algorithm. For example, consider g = 4, x = 256 and y = 1048576. 

Then even if we don't know how to calculate logarithms, we can guess the value of a or b. For y we can start with a guess of 2. That gives a value of 4² = 16, which is too little. Then we can guess 14, which gives a value of 4¹⁴ = 268435456, which is too much. Then we can pick a number between 2 and 14, say 8, as a new guess. That will give us another value: 65536. That tells us that the value we're looking for is between 8 and 14. Then we can guess 10, which will give the value we look for: 1048576. 

We can use a similar process to search for the exponent of x to arrive at the value of a = 4. But if we use those exponents modulo 13 instead, then we’ll get x = 9 and y = 9. 

Let's try to use the same algorithm to find the a and b. With the first guess of 2 we get 3. Since the highest meaningful exponent is p-1 (so 12 in this example, more on this later in the article), let's try a smaller one, a 7. That gives a value of 4. But if we try a 6, we'll get 1. If we try 5, we'll get 10. 

If you don’t see the pattern, don’t be too hard on yourself: there isn’t a simple one. Or even a not-so-simple one. In fact, this is known as the discrete logarithm problem. It’s not as simple as zeroing in on the value of the right size, and much closer to poking around in the dark. Taking that modulo 13 does a good job at hindering the ability to reverse the operation, and it gets even better with larger and more carefully selected numbers.

While using many sufficiently large numbers as p will give us a secure key exchange if we perform additional checks on shared values, there is a class of prime numbers we can use for p that allows us to skip the computationally intensive checks, and use the smallest possible number for the expected level of security, those are the so-called safe primes.

Safe primes

While we’ve briefly looked at g = 4 mod 13 in the previous section, let’s see what values we get when we keep exponentiating a few values to higher powers (starting from 0).

For 1 we get just repeating 1.

For 2 we get: 1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, and then it repeats forever.

For 3 we get: 1, 3, 9, and then starts repeating.

For 4 we get: 1, 4, 3, 12, 9, 10, and then starts repeating.

For 5 we get: 1, 5, 12, 8, and then starts repeating.

For 12 we get 1, 12, and then starts repeating.

There is a relationship between the length of the repeating pattern and the prime number we’re using for the modulus: the lengths of those patterns can only be equal to divisors of p-1. Since 13 - 1 = 12, and 12 has 1, 2, 3, 4, 6, and 12 as divisors, those are the only lengths that we will find. 

The second observation we can make is that if we take the result of exponentiation of a given number, and start exponentiating it further (for example for 4 we take 4² = 3 mod 13) the only numbers we will get in the new repeating pattern will be the numbers we already saw in the repeating pattern of 4 (in the example with 3, all of 1, 3, and 9 are present in the repeating pattern of 4). Because of that, we call those repeating patterns “groups”, and for values that generate smaller repeating patterns “subgroups”. See Fermat’s little theorem for a proof of this.

An attacker is actually interested in such small subgroups, as if they know that the key share is part of the small subgroup, the shared secret will be too. Then instead of guessing the shared secret among all the numbers between 1 and p-1, they need to look through just the subgroup.

While it doesn’t look like much of a difference for the example with 13, as the subgroup of 3 is only 4 times smaller than the prime, for numbers we commonly use in cryptography, the full group will be at least as large as 2²⁰⁴⁸ (or 10⁶¹⁶) while the subgroup can be small, for example, comparable to 2⁶⁴ (or 10¹⁹), in other words, many orders of magnitude smaller.

Now, since for any odd prime p, p-1 will be even (and each prime other than 2 is an odd number), there will always be a subgroup of size 2, so that’s unavoidable. But we can keep factoring p-1. In fact, (p-1)/2 doesn’t have to be composite, it can be a prime number. That’s actually helpful for avoiding small subgroups. 

If we consider a prime number p = 2q + 1, where q is also prime, then the only subgroups (pattern lengths) possible are: 1, 2, q, and p-1, as those are the only divisors of p-1. That means that if we eliminate the results of the exponentiation of 1 (which creates a group of size 1) and p-1 (which creates a group of size 2), the only possible group sizes that remain are q and p-1. 

Both are similar in size to the prime p we use and therefore safe. With groups of large size, attacks that attempt to force the shared key into one of them don’t give any advantage to the attacker. Forcing the connection to use one of the small subgroups is not possible, the parties always check that the key share or shared secret is not equal to 0, 1, or p-1 otherwise the operation is failed.

Closely related to the safe prime are the Sophie Germain primes, named after the 18th-century French mathematician that first worked with them. For a safe prime p, where p = 2q + 1, the q is the Sophie Germain prime.

Composite modulus

If the number used as the modulus, the p in this example, is not prime, then calculating the discrete logarithm is easier.

Calculating the discrete logarithm of a composite modulus can be done by finding the discrete logarithms of its individual prime factors. This has two consequences. First, that while performing DH using composite modulus can be safe, it requires knowing the factorisation of the modulus to show its safety. 

Secondly, if the factorisation is not known, the attacker might have chosen primes for which calculating discrete logarithm is much easier than for more typical primes of comparable size. Given that factorisation of numbers with large factors is still a hard problem, we can’t quickly check that an arbitrary composite modulus is safe or not.

As such, the standards require prime moduli.

Special Number Field Sieve

The fastest algorithm for calculating discrete logarithms uses the general number field sieve as one of its steps. But for some numbers faster algorithms are available. In particular, if the prime lies near a power of a small integer (i.e., if p = r^e ± s where r and s are small) then the special number field sieve can be used instead of the slower general number field sieve. In practice it allows attacking primes 50% larger than with the general sieve, so attacking a 1536 bit SNFS-vulnerable prime requires similar computational resources as attacking a 1024 bit non-vulnerable prime.

Since the r and s we’re looking for are small, it’s easy to iterate over likely values and check for all the small values of r what’s the smallest distance between a power of it and the p in question.

Primality testing

We talked a lot about prime numbers, but how do we know that a number is prime?

For small numbers n, like 13, we can just iterate over all numbers smaller than n and check that they don’t divide it. But that’s not really doable for the kind of numbers we use in cryptography, which are comparable to 2²⁰⁴⁸ or 10⁶¹⁶. The most commonly used algorithm for testing primality for such large numbers is the Miller–Rabin primality test.

The problem is that this test is probabilistic in nature. For any specific “base” for which the test is executed there are composite numbers that pass the test, these are called strong pseudoprimes. While there are no pseudoprimes that pass the test for all bases, there are pseudoprimes that test as “prime” for many bases. In fact, there are ways of constructing them so that they pass the tests for an arbitrary number of bases.

In other words, if the supposed prime could have been constructed by an attacker to be vulnerable (either by not being prime or not being a safe prime) we can’t use Miller–Rabin test to say with high degree of certainty that the number is indeed prime.

Thankfully, there are algorithms that can prove the primality of a number, the downside is that the tests are much slower than Miller–Rabin’s and can’t be done on the fly, but it doesn’t matter much when the prime numbers are used for a long time. One of them, based on elliptic curves, produces primality certificates that can be independently verified and allows for (relatively) fast verification of the results.

Primality certificates

The elliptic curve primality proving is a set of techniques that allow to prove mathematically the primality of a number. It can also output a primality certificate to speed up subsequent re-verification. While the algorithms themselves are complex and require a bit of heuristics to operate quickly, the resulting primality certificates are not complex and can be verified by evaluating just a few equations. Finding good values to show the primality of the number requires a lot of work, verifying that work is simple in comparison.

The basic idea behind the primality certificates is that they build a sort of a ladder that allows us to prove primality of a big number by proving the primality of progressively smaller numbers. With the primality of the smallest number in the ladder shown by either trial division, or by using the Miller–Rabin test (which has been shown to have no false positives for numbers smaller than 2⁶⁴ when a few specific bases are used).

Primo

The fastest implementation of ECPP that we know of is the Primo application. Unfortunately, while it is free and runs on Linux, it’s not open source software. This means we can’t completely trust the validity of the certificates it produces. Thankfully, it uses only three different kinds of primality certificates which can be verified using relatively simple code (excluding the elliptic curve arithmetic implementation) in about 120 lines of Python code.

The three certificates are the Pocklington primality test (for numbers for which partial factorization of p-1 is known), Brillhart, Lehmer, Selfridge certificate (for numbers for which partial factorization of p+1 is known), and finally the Atkin-Goldwasser-Kilian-Morain Certificate for primes that do not have a special form.

The tool that implements the verifiers for these certificates is called ecpp-verifier and it’s available under the terms of the LGPLv2.1 license.

Running ecpp-verifier

The ecpp-verifier package is available on GitHub. It depends on the Python ECDSA and six packages. It can optionally use the General MultiPrecision arithmetic for Python bindings (gmpy or gmpy2) to the GNU MP library. We'll explain how to install the latter (as it’s slightly faster) in a bit. 

Note: You don’t have to install this tool on the machine from which you want to check the /etc/ssh/moduli file, you can copy that file to some different system and check it there.

Installing dependencies on RHEL 8

To install the package and dependencies you will need pip. Install it with:

dnf install python3-pip

Optionally, you can install Python bindings to the GNU Multiple Precision Arithmetic Library to significantly speed up the verification of primality certificates.

First you will need to enable CodeReady Linux Builder repository. After that, install the development packages:

dnf install gcc make libmpc-devel gmp-devel mpfr-devel python3-devel

And finally install the bindings:

pip3 install gmpy2

Installing dependencies on RHEL 7

To install the package and dependencies you will need pip. Install it with:

yum install python3-pip

Optionally, you can install python bindings to the GNU Multiple Precision Arithmetic Library to significantly speed up the verification of primality certificates.

Install the development packages:

yum install gcc make libmpc-devel gmp-devel mpfr-devel python3-devel

And finally install the bindings:

pip3 install gmpy2

Installing dependencies on Fedora

You can also do this on Fedora, if you prefer Fedora as a desktop. All the Python dependencies are already packaged in Fedora, making installation a bit easier:

dnf install python3-pip python3-gmpy2 python3-ecdsa

Installing the ecpp package

Download .whl file from the latest release on github.

Install it using the following command:

pip3 install ecpp-*.whl

On RHEL, it should automatically download and install the ecdsa dependency.

Checking for primality certificates of the OpenSSH moduli file

To check if the primes in the /etc/ssh/moduli file are included in the ecpp tool, run the following command:

ecpp --moduli /etc/ssh/moduli

After half a minute to a few minutes (depending on CPU speed) it will print a list of internal paths to the primality certificates needed to verify the parameters.

On RHEL 8.4 the output will look like this:

[+] line 3: cert: certificates/ssh-certs-rhel8.1/primo-B410F0222526B-239.out, cert: certificates/ssh-certs-rhel8.1/primo-B410F0222526B-203.out
[+] line 4: cert: certificates/ssh-certs-rhel8.1/primo-B410F0222526B-174.out, cert: certificates/ssh-certs-rhel8.1/primo-B410E028AC87D-029.out
...
[+] line 451: cert: certificates/ssh-certs-rhel8.1/primo-B410F0222526B-26B.out, cert: certificates/ssh-certs-rhel8.1/primo-B410F0222526B-07E.out
[+] line 452: cert: certificates/ssh-certs-rhel8.1/primo-B410E028AC87D-086.out, cert: certificates/ssh-certs-rhel8.1/primo-B410F0222526B-0D8.out

Where “line” refers to the line in /etc/ssh/moduli file, while the two cert paths are respectively for the p and the q primes.

Verifying a primality certificate

You can verify a single primality certificate. Let’s use the p prime of the ffdhe2048 parameters from RFC7919 as an example. You can download the primality certificate directly from the git repository:

wget https://raw.githubusercontent.com/tomato42/ecpp-verifier/499443405f84d1f89f988aeb80a9e07227e8515f/certificates/ffdhe-dkg/ffdhe2048_p-updated-f4-1.out

Then you can verify it like this:

ecpp --in ffdhe2048_p-updated-f4-1.out

After few tens of seconds to few minutes (depending on the size of the verified prime and CPU speed) it will print the following, if the primality certificate is valid:

certificate is a prime number
prime in certificate is not vulnerable to SNFS

Verifying all certificates in the moduli file

It is also possible to both check for the presence of primality certificates and at the same time checks if the primality certificates of the primes in the file are valid, that they are safe primes and that the primes are not vulnerable to SNFS. 

To do that, run the ecpp like this:

​ecpp --verify --moduli /etc/ssh/moduli

Though note that for the moduli file in RHEL 8 and Fedora, because there are more than 800 certificates to verify, the process will take a lot of time (multiple hours) even with a fast modern CPU.

The output of the command will look like this:

[+] line 3: cert: certificates/ssh-certs-rhel8.1/primo-B410F0222526B-239.out - is a prime number, is not vulnerable to SNFS attacks, cert: certificates/ssh-certs-rhel8
.1/primo-B410F0222526B-203.out - is a prime number
[+] line 4: cert: certificates/ssh-certs-rhel8.1/primo-B410F0222526B-174.out - is a prime number, is not vulnerable to SNFS attacks, cert: certificates/ssh-certs-rhel8
.1/primo-B410E028AC87D-029.out - is a prime number
[+] line 5: cert: certificates/ssh-certs-rhel8.1/primo-B410F0222526B-0D3.out - is a prime number, is not vulnerable to SNFS attacks, cert: certificates/ssh-certs-rhel8
.1/primo-B410F0222526B-230.out - is a prime number
…

Conclusion

This is how you check numbers to ensure they’re a good fit for use with Finite Field Diffie-Hellman: verify that they’re safe primes located far away from powers of small integers. 

While explaining the rationale and nitty-gritty details behind that, we’ve also introduced the concept of primality certificates and the tool we’re using to verify them. If you’re running Red Hat Enterprise Linux, you’re already benefiting from ecpp-verifier for quite a while, as it’s integrated into our QA process to verify the OpenSSH moduli we ship. 

We’re sharing it with a wider audience in the hope that it may prove itself useful in other places too, and also to show our work and to allow others to review it.