OpenSSH moduli

While playing around with a small and customized Debian based system, I noticed that the following log message was seen every time a user logged on via SSH:

WARNING: /etc/ssh/moduli does not exist, using fixed modulus

So what is this moduli file and why should you keep one of those around?

 

As moduli(5) explains it: The /etc/ssh/moduli file contains prime numbers and generators for use by sshd(8) in the Diffie-Hellman Group Exchange key exchange method.

The Diffi-Hellman key exchange is used in the beginning of SSH sessions to generate a shared secret between the client and the server. Obviously, it would be quite important to get that step right.

Static modulus

But if my system was missing this file, which modulus was then used and sent to the connecting client? The log message said “using fixed modulus”. That sounds like something static. If you’d snoop around a bit in OpenSSH’s source code, you’d find a function called dh_new_group14() in dh.c:


DH *
dh_new_group14(void)
{
static char *gen = "2", *group14 =
"FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
"29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
"EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
"E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
"EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
"C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
"83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
"670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
"E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
"DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
"15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";

return (dh_new_group_asc(gen, group14));
}

 
That sure looks like a (6*10+4)*4*8 = 2048 bit value.

As the prime number is one of the non-secret values in the DH key exchange, meaning that the value is sent as plain text over the net, it should be simple to verify whether this is the value that is in use or not. Wireshark comes handy:

The “DH modulus (P)” value obviously looks the same as the characters in the code snippet above (prefixing null byte excluded). This was also fully confirmed by fetching the whole value as a text string and comparing both sources.

Should one be worried about this static built-in DH prime? Is it insecure? The ordinary moduli file is almost the same thing though, a static file provided by the OpenSSH project. These primes are known and most systems on the Internet are probably using the same set.

To perform a secure DH key exchange you’d need good primes, but not unique ones. The unique part of DH is within the random values generated by the two different parties (client/server), combined with the prime, this ends up as the shared secret.

Modulus length

The /etc/ssh/moduli file usually contains several different entries and sshd picks one randomly for each session. Does this increase security in some way?

The file also contains entries of different lengths in the range of 1024 to 8192 bits. I would probably not want to use the 1024 bit ones. Further investigation shows that the connecting SSH client specifies which minimum and maximum bit lengths it accepts, but also which bit length it prefers:

hex 400 = dec 1024, hex 1000 = 4096 dec, hex 2000 = dec 8192

You see that “DH GEX Numbers of Bits” set to 4096? That means that the ssh client I was using prefers 4096 bits. Hopefully, that was a well-thought-out decision made by some clever OpenSSH developer. Taking this into account, the static built-in prime, used if the /etc/ssh/moduli file is missing, ought to be considered too short.

BTW, this information is also seen by running ssh with the verbose flag:
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<4096<8192) sent

Generating the moduli file

Lets get hold of one of those moduli files with 4096 bit modulus then. Using the ssh-keygen tool you may generate it yourself.

First, "candidate primes" needs to be generated:
ssh-keygen -G /tmp/4096.1 -b 4096
It ends up as over 10000 candidates.

Secondly, these are tested and only the safe ones are kept; about 30 entries, at least in this run. The output file contains the ready-to-use moduli file.
ssh-keygen -T /tmp/4096.2 -f /tmp/4096.1

About four hours of CPU time was needed to complete this process on an Intel i7 processor. Generating 1024 bit ones instead only needed 1-2 minutes. As previously mentioned, the default moduli file contains varying sizes, even including 8192 bit entries. No wonder this file is pre-generated.

Trying it out

The new moduli file was installed and Wireshark was fired up once more:

Fetch the value off Wireshark and quickly process it in bash.
# p=00:da:11:08:47:31:4b:53:75:39:f2:a2:06:81:21:2a:0b:2e:.....

Strip all colons, erase first two characters (the null byte) and finally make the whole text string upper case:
# p=${p//:}; p=${p:2}; p=${p^^}

Finally find out if there's a matching entry in the moduli file:
# grep " $p$" /etc/ssh/moduli | sed -r 's/ [^ ]+$//'
20140208234044 2 6 100 4095 2
Yup. There sure is.

Giving it another try, another ssh and Wireshark session, shows that another modulus was used this time:
20140209012047 2 6 100 4095 2

Paranoia

Keep in mind that I am definitely not a mathematician nor a crypto expert. But should you really be using the default pre-generated moduli file that comes along with your Linux distribution?

  • You will find 1024 bit entries in there. Do you really want to allow that? Some broken (?) SSH client might have set its preferred bit length, or its max bit length to 1024 bit.

  • Is there any chance that these entries could have been tampered with? Have they been carefully chosen to make some sort of cracking easier? Checking out OpenSSH's CVS history of the moduli file, certainly shows that the file has been re-generated several times the last couple of years.

  • As almost everyone out there would be using the same set of DH primes, is it possible that an adversary could have built some sort of database that makes DH cracking easier, in case these specific primes are used in the DH key exchange?

  • There seems to be some sort of benefit of not always performing the DH key exchange using the same prime. Otherwise, why would sshd not just use the first entry in the moduli file all the time? If this is the case, would you really want to use the same primes as all the others do?

 

EDIT (2015-01-06):

Due to recent Edward Snowden leaks, this article was recently published.

The article is a walkthrough of the various encryption related settings provided by sshd, including recommendations on what to enable or not. Regarding the different key exchange algorithms, the article mentions:

"Bit size of the DH modulus: This eliminates 2 [diffie-hellman-group1-sha1: 1024 bit DH with SHA1] because the NSA has supercomputers and possibly unknown attacks. 1024 bits simply don’t offer sufficient security margin."

Obviously, that doesn't really prove anything, but it is interesting that the modulus length is mentioned, and that it is recommended to remove the 1024 bit primes from the moduli file.

12 Replies to “OpenSSH moduli”

  1. You were the last link on the first page of google search results, but you were certainly the most helpful. Thank you so much.

    1. Aaron – records aren’t always published. I don’t use RSA that is any lower than 4096 bits. Yes, this is overly paranoid – so what? I generate it once, and it should be fine for the rest of my life.

  2. My impression of the public crypto community is its mainly made up of very savvy individuals with a good knowledge of math and crypto. Since snowden my opinion has fallen. Instead of tightly, well reasoned opinions, I am now getting “Oh don’t do that, the NSA possess magic devices based on unfathomable technology” Its this the modern equivalent of “here lies dragons.”

    BTW thank you for this informative blog entry and the useful replies.

  3. @Aaron Toponce

    Not exactly. Computing a discrete logarithm is considerably faster for specially crafted moduli, i.e. composite numbers, or non-safe primes ((p-1)/2 is composite). Ssh-keygen’s primality tests are statistical tests and can lead to false positives.

    For instance, one could submit bad moduli (such as p*q where p and q are 512 bit-primes) to ssh-keygen -T until such a bad modulus passes the tests. Then, they can break crypto using this 1024-bits modulus with 2^512 complexity only.

    Hence the whole point:
    -if you suspect some of your distrib’s moduli have been specially crafted, then regenerate them
    -as there is no noticable overhead for 2048+ bits moduli, remove 1024 bits ones
    I would add:
    -if you fear the default primality tests are not sufficient and some bad moduli went through, then increase the number of tests (-a option)
    -if you suspect ssh-keygen has been tampered with to only generate crafted moduli or to weaken its primality tests, then audit the code or use another tool you trust more

  4. @Evariste

    OpenBSD changes the moduli on every release, and the file is part of a cryptographically signed package provided by your distribution. If you suspect that the moduli file has been “specially crafted”, then it was the OpenBSD devs, or your OpenSSH package maintainer. It didn’t happen in transit from the repository server to your computer.

    The 1024-bit primes don’t offer a large enough security margin, agreed, and they can be “specially crafted”, but I doubt that is the case here.

    Regardless, the moduli file is only used when using the Diffie-Hellman Group Exchange method, which isn’t the default key exchange. As of OpenSSH 7.1, the default key exchange order is:

    1. curve25519-sha256@libssh.org
    2. ecdh-sha2-nistp256
    3. ecdh-sha2-nistp384
    4. ecdh-sha2-nistp521
    5. diffie-hellman-group-exchange-sha256
    6. diffie-hellman-group-exchange-sha1
    7. diffie-hellman-group14-sha1

    There are 4 higher priority key exchange algorithms that will be negotiated before the Diffie-Hellman Group Exchange algorithms. This doesn’t address older clients that don’t support these algorithms, of course, nor clients that have manually selected to use DHGE instead of auto-negotiation.

    So, if it will make you sleep better at night, feel free to remove the 1024-bit primes. In reality, they’re still safe.

  5. As estimated by the authors behind the Logjam attack, the much more difficult precomputation needed to solve the discrete log problem for a 1024-bit prime would cost on the order of $100 million, well within the budget of large national intelligence agency such as the U.S. National Security Agency (NSA). The Logjam authors speculate that precomputation against widely reused 1024-bit DH primes is behind claims in leaked NSA documents that NSA is able to break much of current cryptography.
    https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf
    https://en.wikipedia.org/wiki/Diffie-Hellman_key_exchange#Practical_attacks_on_Internet_traffic

    Please stop defending 1024 bit key sizes, when your dealing with agencies that can throw around billions of dollars, you can’t rely on the best _known_ “record breaking” results of academic institutions, their results are not directly useful.

  6. Convenient Brittney responded 3 years after I did, and I’m responding 2 years after her, and 5 years after my last reply. According to https://www.keylength.com/en/compare/ in 2010, the recommended minimum DH GEX primes were:

    * Lenstra / Verheul: 1613 bits
    * Lenstra Updated: 1245 bits
    * ECRYPT: 1024 bits
    * NIST: N/A bits
    * ANSSI: 2048 bits
    * NSA: N/A
    * RFC3766: N/A
    * BSI: N/A bits

    It’s now 2020, and the recommended minimum key lengths are:

    * Lenstra / Verheul: 1881 bits
    * Lenstra Updated: 1387 bits
    * ECRYPT: 3072 bits
    * NIST: 2048 bits
    * ANSSI: 2048 bits
    * NSA: N/A
    * RFC3766: N/A
    * BSI: 2000 bits

    Take it for what you will, but those are papers published by actual cryptographers, security experts, and those “in the field”. It’s one thing to discuss the possibility of a nation state threat, it’s entirely another to actually see it in practice. We should stay on the conservative side of the line, I agree, but there is no need for FUD.

    Also, the command for generating the DH GEX primes has changed. It’s now:

    $ ssh-keygen -M generate -O bits=2048 moduli-2048.candidates
    $ ssh-keygen -M screen -f moduli-2048.candidates moduli-2048

    Writing a Bash for-loop, starting with 2048 bits and incrementing every 1024 bits until 8196 bits yielded about 200 primes and took about two days. The default /etc/ssh/moduli file that ships with my Debian unstable system gives about 400 primes with the the sizes of 2047, 3071, 4095, 6143 ,7679, and 8191 bits. Curious that 5120 bits was skipped over and 7680 bits was chosen in favor of 7168 bits. Whatever.

    So either run through that Bash loop twice, or increment every 512 bits instead of every 1024 bits, to yield a new /etc/ssh/moduli of roughly 400 DH GEX primes.

Comments are closed.