Diving too deeply into DH Moduli and OpenSSH

tl;dr:

• Debian/Ubuntu use the /etc/ssh/moduli file as distributed by the OpenSSH project at the time of the distribution’s release
• This file is only used for diffie-hellman-group-* KexAlgorithms
• The default KEX algorithm on my setup is the post-quantum sntrup761x25519-sha512@openssh.com instead
• Therefore, you can generate your own moduli, but it is increasingly irrelevant
• Having more moduli listed means that sshd will do more processing during every connection attempt that uses the file

There is also a “fallback” behavior if the server can’t read the moduli file or find a match, which I don’t fully understand.

Intro

There’s a lot on the internet about Diffie-Hellman, primes, and groups.  I will be skipping over most of this, and looking more closely at how OpenSSH in particular handles the Diffie-Hellman group exchange (all diffie-hellman-group-exchange-* KEX algorithms.)

References to the source code and “current behavior” of OpenSSH specifically refer to Portable OpenSSH version 9.3p1.  This upstream version was chosen for inclusion in Ubuntu 23.10, Mantic Minotaur, which happens to be my current desktop.

The Fallback

My curiosity was initially stoked by ssh-audit mentioning the “OpenSSH DH GEX fallback mechanism.” ⚠️ It turns out that if OpenSSH cannot read /etc/ssh/moduli or find an acceptable group in there (between min and max preferences from the client), then it falls back to one of groups 14/16/18 (2048/4096/8192 bits), defined in RFC 3526.

Curiously, fallback function is passed the client’s max preference, but rounds that (possibly upwards) to the closest eligible group.  Thus, if the mechanism is activated with a client that accepted "2048–7168" bits, OpenSSH would choose the 8192-bit fallback.  This happens even though the server is otherwise willing to use the 4096-bit group.

(This code appears in dh.c, functions choose_dh() and dh_new_group_fallback().)

Either I don’t understand correctly, or it is only a theoretical problem, and not a practical one.

The Client’s Preferred Size

There is—probably wisely—no configuration for the length of moduli in the request sent by the client.  OpenSSH chooses the lengths to send by hard-coded settings for min and max (currently 2048 and 8192, respectively), and determines its preferred setting by calling a dh_estimate() function.

That function, in turn, converts a “symmetric bit length” to a DH length.  This appears to take into account the cipher key size, cipher block length, cipher IV length (except those are mostly defined to 0), and MAC length (except that only UMAC has a non-zero value.)

This yields 3072 for 128-bit, 7680 for 192-bit, and 8192 for 256-bit.  The first two numbers correspond to the list of equivalent strengths listed in NIST SP 800-57 Part 1 (currently in Rev. 5, published in 2020.) The last is obviously limited by the maximum length that OpenSSH is willing to use, as the publication suggests a 15360-bit length instead.

It may be possible to get a preferred size of 2048 when using 3des-cbc🛑, which is only 112 bits of security.  But don’t do that!

Rereading Moduli

OpenSSH appears to read through the /etc/ssh/moduli file twice on every request: once to find candidates, and once more to rediscover the candidate that was chosen.  Internally, it parses every line (first pass) and every line up to the chosen candidate (second pass), including allocating the generator and prime, and converting them from hex to binary.  If the candidate disappears from the file between passes, then the fallback mechanism is activated.

I know I am worried about the performance of a once-per-connection thing here, but it appears that the moduli file should be as short as is practical, while providing enough moduli/lengths to offer suitable coverage.  Likewise, it should contain only lengths that clients are actually willing to use.

Moduli File Contents

OpenSSH regularly distributes updated versions of their moduli file.  Debian and Ubuntu pull that version of the file into their own release process.  This limits the usefulness of precomputing anything based on the moduli; after some time, those moduli are phased out by new OS releases.

OpenSSH provides moduli with lengths of 2048, 3072, 4096, 6144, 7680, and 8192.  But from what we learned earlier, it will only really request 3072, 7680, and 8192 itself.  The other three sizes are for the benefit of other clients.  But I wanted to wrap up my research, so I did not study any of them.

The 2048-bit Moduli

SSH hardening guides recommend removing entries from /etc/ssh/moduli that are less than 3072 bits with commands like:

awk '$5 >= 3071' /etc/ssh/moduli > /etc/ssh/moduli.safe
mv /etc/ssh/moduli.safe /etc/ssh/moduli

(This file lists N-bit primes as N-1 bits, because technically the first bit is always 1.  IDK that it really makes a difference, but to keep the 3072-bit primes, the command has to match 3071 instead.)

Aside from the fallback mechanism, this guarantees that the server won’t be able to find any smaller primes to use, even if the client sends a request like “min 1024, prefer 1024” that would normally select smaller primes.

The Anticlimatic Conclusion

After all that, I realized that this was theoretical in my case.  Since OpenSSH 8.5 (March 2021), the package has supported the post-quantum sntrup761x25519-sha512@openssh.com KEX algorithm, which does not use classic Diffie-Hellman… and therefore, doesn’t use the moduli file.  This appears to have been made the default in OpenSSH 8.9 (February 2022), which was included with Ubuntu 22.04 LTS.

I ended up limiting my SSH client via adding to ~/.ssh/config:

Host *
    KexAlgorithms sntrup761x25519-sha512@openssh.com
    Ciphers aes256-gcm@openssh.com

I have AES-NI on both ends.  I’ll add chacha20-poly1305 and/or per-host exceptions, if circumstances change.