Prime or Not Prime: That is the Question
2023-07-22
The SSH-Weak-DH tool checks whether a given SSH server supports weak Diffie-Hellman groups during the key exchange process in light of Logjam attacks.
Recently, I extended this tool to print the group's modulus and generator in hexadecimal and to show whether the modulus is a safe prime as expected. Moreover, the tool now checks whether the modulus is part of commonly used groups and prints its name if that's the case.
The following key exchange algorithms supported by OpenSSH (run ssh -Q kex to view all available algorithms) use a common Diffie-Hellman group, such as the "second Oakley group" from RFC 2409:
diffie-hellman-group1-sha1 diffie-hellman-group14-sha1 diffie-hellman-group14-sha256 diffie-hellman-group16-sha512 diffie-hellman-group18-sha512
These groups are hardcoded in dh.c in the OpenSSH source.
In addition to these fixed groups, OpenSSH supports the following group exchange algorithms where the server selects a group for the key exchange:
diffie-hellman-group-exchange-sha1 diffie-hellman-group-exchange-sha256
Specifically, the sshd(8) server parses the moduli(5) file (typically located at /etc/ssh/moduli or /etc/moduli) and picks a random group that meets the size requirements negotiated between the SSH client and server as part of the group exchange. For Portable OpenSSH 9.3, group sizes can range from 2048 bits to 8192 bits.
Validating whether groups specified in the moduli file are safe is resource-intensive. Therefore, SSH servers and clients perform only basic checks on the Diffie-Hellman public key during the key exchange without ensuring that the agreed upon groups are safe. These basic checks prevent a malicious client from choosing Diffie-Hellman public keys in an attempt to recover the server's private key as in CVE-2016-0701.
As OpenSSH uses the probabilistic Miller-Rabin primality test to check whether a generated modulus is a prime, there is a chance that the modulus is composite. Furthermore, attackers who gain write access to the moduli file (the file is only writable by root by default) can replace the validated safe primes by composite numbers or prime numbers with a trapdoor to subvert the Diffie-Hellman key exchange in a stealthy fashion.
An unsafe moduli file with a composite 2048-bit modulus configured on the server may look as follows:
$ cat /etc/ssh/moduli # DO NOT USE THIS UNSAFE CONFIGURATION!!! # Time Type Tests Tries Size Generator Modulus 20220722110357 2 6 100 2047 2 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF1
The SSH-Weak-DH tool now recognizes that this modulus offered by the server during the Diffie-Hellman key exchange is not a safe prime:
[!] BROKEN. FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF1 is not a safe prime.
Moduli that are not safe primes should be eliminated from the moduli file by generating a new file from scratch. To this end, the ssh-keygen(1) can be used with the -M generate and -M screen options to generate and validate moduli files, respectively. Systems offering broken moduli should undergo inspection to determine whether they have been compromised.