How Diffie-Hellman Key Exchange can Cause Availability Issues

The Diffie-Hellman key exchange is a cryptographic protocol that allows parties to establish a shared secret over an insecure channel. The security of this key exchange is based on the difficulty of the Discrete Logarithm Problem (DLP) in a given group, such as the multiplicative group of integers modulo a prime number $p$ .

The Diffie-Hellman key exchange is computationally expensive due to the nature of the mathematical operations it involves, particularly the explained modular exponentiation with very large numbers Even with optimized algorithms like square-and-multiply or Montgomery multiplication, which can lead to significant computational effort. The arithmetic operations involved require high-precision arithmetic to handle large numbers, however, standard processors are not designed to handle such large integers directly, so multiple-precision arithmetic libraries are used,

Exploiting the computationally expensive nature of the Diffie-Hellman key exchange protocol an attacker can perform a denial-of-service (DoS) attack by sending arbitrary numbers as public keys to a target server forcing it to generate its public key, validate the peer's one, and compute the shared secret. All three operations require the computationally complex modular exponentiation which creates an asymmetric resource usage situation, which is the basis for overloading the server's CPU and rendering it unavailable. The attack is carried out with such a methodology called D(HE)at attack (CVE-2002-20001).

Mathematical Background

Basic Concepts

The Diffie-Hellman key exchange is based on the following key mathematical concepts:

• Modular Arithmetic: This involves operations on numbers modulo some integer $p$ .
• Primitive Root and Generator: For a prime number $p$ , a number $g$ is called a primitive root modulo $p$ (or generator) if every number between 1 and $p-1$ can be expressed as $g^k \pmod p$ for some integer $k$ . In other words, the powers of $g$ modulo $p$ generate all numbers from 1 to $p-1$ .
• Discrete Logarithm Problem (DLP): Given $g$ , $p$ , and $g^a \pmod p$ , it is computationally hard to determine $a$ . This problem forms the basis of security for the Diffie-Hellman key exchange.

Public Key and Shared Secret Computation

Let's assume two parties -- Alice and Bob -- want to establish a shared secret. The followings explain how it can be
done using the Diffie-Hellman key exchange:

1. Public Parameters:

   • Alice and Bob publicly agree on a large (usually 2048-8192 bit) prime number $p$ and a primitive root (generator) $g$ . These values are not secret and can be known to everyone.

2. Private Exponents:

   • Alice chooses a private key $a$ , which is a random integer between 1 and $p-1$ .
   • Bob chooses a private key $b$ , which is also a random integer between 1 and $p-1$ .

3. Compute Public Keys:

   • Alice computes her public key $A = g^a \pmod p$ using her private key $a$
   • Bob computes his public key $B = g^b \pmod p$ using his private key $b$
   • Both $A$ and $B$ are shared over the insecure communication channel.

4. Compute Shared Secret:

   • Alice computes the shared secret $s = B^a \pmod p$ using Bob's public key $B$ .
   • Bob computes the shared secret $s = A^b \pmod p$ using Alice's public key $A$ .
   • Both computations result in the same value, $s = g^{ab} \pmod p$ , which is the shared secret key.

Issues Cause the Performance Degradation

The situation is aggravated by the fact that to maintain security, the size of the prime $p$ and the private keys $a$ and $b$ must be large enough to prevent attacks, such as the discrete logarithm attack. The larger these numbers, the more secure the protocol, but also the more computationally demanding it becomes. In environments with limited computational resources (like IoT devices, embedded systems, or mobile devices), performing modular exponentiation with large numbers can lead to noticeable delays, higher power consumption, and increased resource usage.

Long Exponent (CVE-2022-40735)

The number of operations grows with the size of the private exponent. The time complexity of modular exponentiation is about $O(\log e)$ , where $e$ is the exponent. It means that the long exponent issue in the Diffie-Hellman key exchange relates to the length of the private exponent (the secret number chosen by each party). If the exponent is particularly long (e.g., 8192 bits), then performing this exponentiation operation can be computationally expensive and time-consuming, and may cause availability issues (CVE-2022-40735).

* estimated value

According to the technical paper of the D(HE)at attack (Table 2) there have been different recommendations for short private exponent sizes for various prime number sizes for decades. The exponent sizes were determined by considering both security and performance, but there were cryptographic libraries, such as OpenSSL, and OpenJDK, that used long exponents (Table 4) considering only security, but not the performance risking damage to availability, being that the larger the exponent the more effective a D(HE)at attack. As the paper states:

"Only expanding the size of the private keys without proportionally increasing the modulus p does not yield stronger security, but causes significant performance degradation."

Unnecessary Public Key Validation (CVE-2024-41996)

Parties can agree on any public parameters (prime number $p$ and generator $g$ ) during the cryptographic handshake. However, certain combinations of these parameters may risk the small subgroup confinement attack. Parties can avoid the attack by validating the peer's public key according to NIST SP 800-56A Rev 3.. The validation requires modular exponentiation ( $1 \equiv A^{(p-1)/2} \bmod p$ ) whose resource requirement is similar to the public key generation when long exponent was used, as both sizes of the base ( $A$ ) and the exponent ( $(p-1)/2$ ) is the same as the size of the prime ( $p$ ).

According to the special publication of NIST (Section 5.6.2.3.2) under certain conditions the validation can be skipped, without risking a small subgroup confinement attack. The conditions are met when parties use parameters defined in the related standards (RFC 7919, RFC 8268) as the prime parameters are always safe-primes, which is the case in TLS 1.3, SSH 2.0, and IKEv2. Cryptographic libraries, such as OpenSSL, perform the validation independently from the fact that the cryptographic protocol guarantees the use of safe primes, risking damage to availability (CVE-2024-41996), similarly to the long exponent attack.

"This routine shall only be used with ephemeral FFC public keys generated using the approved safe-prime groups when assurance of the partial validity of such keys is to be obtained ..."

Large key sizes by default

Parties can agree on any public key sizes (prime number $p$ ) during the cryptographic handshake. It means that a malicious client can force the server to use the largest key size enabled by acting as if it supports only the largest enabled one. As larger key sizes require more resources when computing and validating the public key than the smaller ones the default of the enabled Diffie-Hellman parameters in the case of cryptographic libraries becomes particularly important. When larger parameter sizes (e.g., 6144, or 8192 bit) are enabled by default an attack can be more important than only the smaller ones would be enabled as in many cases maintainers use the library default assuming that the defaults were selected with due care.

According to NIST SP 800-57 Part 1, Rev. 5 256 bits of security would require a 15360-bit key size, which is practically unfeasible for the majority of cryptographic libraries stated by the paper about D(HE)at attack (Table 12). It is also considerable that both 256 and 384 bits of security can be achieved with much better performance using elliptic-curve-based Diffie-Hellman key exchange (Table 14). It means that neither security nor performance considerations can justify enabling algorithms by default which may cause availability issues. However, the majority of the cryptographic libraries -- including OpenSSL -- enable the largest key size (8192-bit) during parameter negotiation (RFC 7919) according to D(HE)at the technical paper (Table 10).

Summary

There are three operations during the Diffie-Hellman key exchange that require resource-intensive modular exponentiation:

1. public key generation
2. public key validation
3. shared secret calculation

A malicious client can trigger all three operations without any privileges or considerable resource requirement (D(HE)at attack -- CVE-2002-20001) due to the nature of the protocol, even though the effectiveness highly depends on implementation issues.

In the case of public key generation and shared secret calculation the resource requirement increases strongly when a long exponent is used, meaning that the potential of a successful attack also increases (CVE-2022-40735). This implementation issue becomes problematic, when the cryptographic protocol supports the parameter negotiation (e.g., TLS, SSH), meaning that a larger key size can be forced as presented in the technical paper about the D(HE)at attack (Table 7, Figure 11). System administrators can hardly reduce the impact of this implementation issue. The only exception is the Diffie-Hellman parameter file in the case of TLS, where exponent size can be declared.

The resource requirement of the public key validation is necessarily as high as the other two operations as the base, the exponent and the modules (prime) have the same large (2048-8192 bits) size. However, the validation is not needed if an appropriate modulus is used, but implementations may not take this fact into account (CVE-2024-41996), thus increasing the cost of the key exchange. A system administrator cannot mitigate the issue since the validation is done independently from the Diffie-Hellman parameters.

The default setting of the supported Diffie-Hellman parameter sizes is significant in the case of a cryptographic protocol where the parameters are negotiable. In several cases, default values are not overwritten in the application server configuration. Practically it means that the larger a cryptographic library enables the key size by default the more effective an attack can be. This is especially true when the library is affected by the mentioned issues, however, larger key sizes can be disabled in a server configuration.