Consequences of tampered /etc/ssh/moduli

Question

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

Answer 1

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 p^k = 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.