OpenSSH Primes - can there be such a thing as "too few" primes available?

Question

The (old) Secure Secure Shell guide suggests (re)creating /etc/ssh/moduli so sshd has safe prime numbers to use for Diffie-Hellman key agreement.

I've generated a 4096-bit moduli file with ssh-keygen -G -b 4096, and then filtered them with ssh-keygen -T - which ended up with 31 safe numbers.

The stock file provided by my distro has 267, and it even has 218 after excluding those with less than 4000 bits (as stated by awk '$5 > 4000' /etc/ssh/moduli | wc -l).

I kind of get the general idea of what's this is for, but for sure am not expert on security - and an order of magnitude less of something sounds like a warning to me. What are the risks of having too few numbers left on the /etc/ssh/moduli? And, the big question - what amount of primes are considered too few? Are there any recommendations?

Answer 1

As a practical matter, assuming the primes are of sufficient size, a single set of parameters per size is sufficient. That's because a single set of parameters can be used multiple times, and in fact the named DH groups (diffie-hellman-group*) do exactly that. TLS similarly provides named groups of this kind where the parameters are used securely by implementations all over the world.

When you use the generic DH key exchanges, the client sends a size of parameters it's willing to use, and the server sends a suitable group. Because groups have virtually indefinite reuse, any set of parameters that meets the need is sufficient.

Now, if you use a small prime, like a 1024-bit prime, then it can be valuable to minimize the reuse of those primes. That's because we assume that major governments and large corporations can factor such numbers. Using a fixed, well-known value means that those organizations can precompute the data necessary to perform the attack and then use it on all instances of that prime. Changing parameters frequently dramatically increases computational effort to perform that attack.

However, if you're using an appropriate prime of at least 3072 bits, then you're providing at least 128-bit security, and those attacks don't apply. The only time you might have a problem is if you have a very old or very weak SSH client and can't avoid it, but most of the time that's not an issue and you can just use secure parameters.

It is helpful to have some parameters of different sizes, because different clients might prefer larger or smaller values for performance or security reasons, and you don't want to fail a connection needlessly. You should obviously not pick insecure sizes, but, say, 3072, 4096, 6144, and 7680 might provide sufficient sizes for most cases.