# Consequences of tampered /etc/ssh/moduli

What are the consequences if an attacker is able to modify the `/etc/ssh/moduli` file?

The `/etc/ssh/moduli` contains pre-generated group parameters for Diffie-Hellman. A DH key exchange occurs in the early steps of the SSH connection and generates the secret shared key which will be used for encrypting the data. DH works in a given group; technically, a modulus p (a big prime integer) and a generator g: the generator is in the 1..p-1 range, and it should be such that its order is a multiple of a "big enough" prime q. The order k is the smallest non-zero integer such that pk = 1 mod p. Discrete logarithm, and therefore DH, can be broken through with an effort which depends on both p and the largest prime factor of k (which we will call q):

• There is a variant of the Number Field Sieve which breaks discrete logarithm if p is not big enough; current record is for a 530-bit prime and it is assumed that 1024-bit primes are still safe [Ed. Not anymore, see various blog posts about Diffie-Hellman dated 2015-10-15.], and 2048-bit primes will be safe for the foreseeable future.

• Generic discrete logarithm algorithms apply with cost proportional to the square root of the biggest prime factor of k; so it is important (and sufficient) that k admits a prime factor of at least 200 bits if "100-bit security" is to be achieved.

An attacker who can modify `/etc/ssh/moduli` could try to replace the nice DH group parameters with other group parameters who look fine but make DH-breaking easier (or even easy) for him. There are mostly two ways to do that:

1. Choose a prime p and a generator g such that the order k of g is a product of only small prime integers. This can easily be done; for instance, begin by generating a bunch of small primes (say 80 bits each at most); then try random products of such primes: for each product r, compute p = 2r+1 and see if that yields a prime. If it does, then p is such that any generator g modulo that prime will imply weak Diffie-Hellman.

2. Generate a special prime p such that NFS is faster for that specific p. See this article for some theoretical background.

The `/etc/ssh/moduli` file does not contain the order of the suggested generator, so you cannot simply verify if that order is prime and matches g. However, you could take p-1 and apply the Elliptic-Curve factorization method on it: this will find all the small prime factors in p-1, and thus allow you to check that the order of g has not been weakened (k is necessarily a divisor or p-1). Thus, weakening of the first kind can be detected (albeit not in a matter of a few seconds). Correspondingly, attackers who do not like risk of exposure (in particular spy agencies) will refrain from using that method.

The second kind of weakening, however, is hard to detect. So one has to assume that an attacker who could somehow corrupt your `/etc/ssh/moduli` file (e.g. by altering the file as distributed with OpenSSH, through some bribery of OpenSSH developers) could, potentially, have introduced a backdoor allowing him to decrypt your SSH connections at will (SSH connections to your server, since the group parameters are chosen by the server). Since the involved mathematics are not simple, that attacker would, at least, be a competent attacker.

The only good countermeasure is to replace the `/etc/ssh/moduli` contents with values which you know to be correct and not malicious, by virtue of having generated them yourselves. `ssh-keygen` can do that (see the man page). You could also do that with some custom code (e.g. with Java's `BigInteger` class, this is a matter of 50 lines of code at most).

Alternatively, use DSA group parameters (they also work) which were generated as described in Annex A of FIPS 186-4: these are nothing-up-my-sleeve numbers because the candidate values for p are obtained through a deterministic, fully-specified PRNG, which, presumably, cannot be coerced into making a "special prime" which makes NFS easy. It would have been better if OpenSSH developers had used such a verifiable generation method to begin with.

• You are a superhero. I love you. Sep 6, 2013 at 18:04
• Is SSH's /etc/ssh/moduli analogous to OpenSSL's dh{512,1024,2048}.pem file? I always thought those contained a fixed (non-ephemeral) secret DH value. If they are the same thing, can they also be world-readable and even shared between servers?
– lxgr
Sep 6, 2013 at 21:20
• The `dh512.pem`, `dh1024.pem` and `dh2048.pem` are part of OpenSSL's source code, as distributed, so everybody as them -- therefore, they cannot be secret. Each of them contains the ASN.1+PEM encoding of a `SEQUENCE` of two `INTEGER` values, which are, respectively, a big prime p and a generator g. So yes, they are very similar in concept to OpenSSH's `/etc/ssh/moduli` file. Sep 7, 2013 at 14:16
• Note that the “moduli” file is relevant only if you enable the “group exchange” variants of the SSH-2 key exchange algorithms, e.g. diffie-hellman-group-exchange-sha1. The diffie-hellman-group{1,14}-sha1 methods and others use fixed D-H groups defined in the standard. Mar 8, 2014 at 8:00
• @Florian there is good reason to believe that the NSA has performed precomputations allowing NFS to attack specific 1024-bit groups, inc. one used by OpenSSH. weakdh.org has a PDF on it. It is presumed that custom 1024-bit groups properly generated on your server are probably safe. You do not need math/crypto background if you trust the OpenSSH code: - To generate: `ssh-keygen -G moduli-2048.candidates -b 2048` - To test: `ssh-keygen -T moduli-2048 -f moduli-2048.candidates` The resulting file has results that passed the testing, and you can replace the stock moduli file with that one. Sep 12, 2015 at 8:45