Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 12 down vote accepted

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, 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 would 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.

share|improve this answer
5  
You are a superhero. I love you. –  vergoglio Sep 6 '13 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 '13 at 21:20
1  
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. –  Thomas Pornin Sep 7 '13 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. –  Richard E. Silverman Mar 8 at 8:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.