What should be the size of a Diffie-Hellman private key?

Question

I'm implementing the SRP-6 protocol, which relies on discrete logarithms for it's security (essentially Diffie-Hellman).

The RFC documents state:

The private values $a$ and $b$ SHOULD be at least 256-bit random numbers, to give approximately 128 bits of security against certain methods of calculating discrete logarithms.

I can't seem to find any info on this – is it still valid advice?

Is the reason for this simply that the best known method for calculating discrete logs of $n$-bit numbers requires $2^{n/2}$ steps?

Answer 1

Well, yes, that is generally good advice about DH.

Here is some background on this: support you were given a value $g^x \bmod p$, and you were also told that $1 \le x \le A$ for some value $A$. If so, then there are several known attacks (such as Big Step/Little Step and Pollard's Rho) that can recover $x$ in about $\sqrt A$ steps. If we have as our security goal that it should take at least $2^{128}$ steps, then means that $\sqrt A \ge 2^{128}$, or $A \ge 2^{256}$, that is, we take our private exponent $x$ to be a random 256 bit number (note: in this context, we count it as a 256 bit number even if the msbit happens to be zero).

Now, there are a few other notes I want to leave you with:

• There isn't much point in making the private exponent much larger than that; there is another avenue (Number Field Sieve) which also can solve the Discrete Log problem in time which is independent of the size of the exponent, but only depends on the size of the modulus. For realistic modulus sizes, this will also be around (or, at least, not significantly more than) $O(2^{128})$ steps, so making the private exponent significantly bigger will just make your computations more expensive, without making the system any more secure in any real sense.

• One minor point about SRP (as opposed to straight DH); the protocol does leak the LSbit of the initiator's private exponent (by leak, I mean that someone listening to the messages being exchanged can deduce that bit value). I don't believe that that's a big deal (as it's only 1 bit, and nothing else is leaked). If you want to be pedantic, I suppose you could have the initiator pick a 257 big private exponent (so there will still be 256 unknown bits).

Answer 2

Oh, and while you did not specifically ask about this, there is another point I believe that is important to highlight; DH and SRP are different protocols, and have different requirements on the generator they use. In particular, taking a generator that is designed to be used securely within DH can void the security properties of SRP.

Here's what's going on: it's all about the order of the generator; that is, the smallest value $q>0$ such that $g^q \equiv 1 \mod p$.

For DH, we generally pick a generator that has a prime order; that is, one for which $g^x \bmod p$ has a prime number of distinct values. Here's why: if we picked a generator with a composite order (and particular, one with small prime factors), then that leaks some small amount of information about the private exponent we picked. That is, if $r$ is a small factor of $q$ (the order of $g$), then someone who just sees $g^x \bmod p$ can determine the value of $x \bmod r$. Now, if there's only a couple of small prime factors, this amount of leakage need not be worrisome; however, when given a choice of whether to leak any information or not, we generally choose not to; picking a generator with a prime order does just that.

For SRP, we must pick a generator for the entire group (that is, has order $p-1$); such a $g$ is also known as a primitive root or primitive element. This is mentioned in the SRP specification, but it's easy to overlook. However, here are the consequences of picking a generator that does not generate the entire multiplicative group:

• One of the fundamental security guarantees that SRP tries to provide is if someone is passively listening to an SRP exchange, they learn nothing, and in particular, they will not be able to eliminate any possible likely passwords from consideration.

• Now, if we look at the second SRP message (from server to client), we see that it is the value $B = kv + g^b$. Now, our passive listener does not know the values of $v$ (a value derived from the shared secret), or $b$. However, what he can do is take a guess at the shared secret, compute the corresponding $v'$ value, and look at $B - kv' = g^b$, and check whether, for the value $B - kv'$, is there such a value $b$. Now, determining the value of $b$ is a hard problem; what is easy determining whether such a value exists. If there is no such value $b$, then our passive listener can then deduce that his guess at the shared secret is impossible, and can scratch it off his list.

• In practice, this allows a listener who evesdrops to 20 SRP exchanges to cut down a dictionary of one million possible passwords down to the correct one (and possible one or so false entries); obviously, this is a huge violation of the SRP security goals.

So, by having $g$ having order $p-1$ (so that $g^x \bmod p$ can take on all possible values between $1$ and $p-1$, the above tells the attacker nothing; when he checks whether $B - kv' = g^b$ had a possible solution for $b$, the answer will always be "yes" (unless $B - kv' = 0$, which is extremely unlikely), and so the above doesn't allow the attacker to eliminate any possibilities from his list; he learns nothing.

Now, when I give advise on DH groups, I normally point people at the IKE groups; those work very well for DH, however they fail for SRP (because they all have $q = (p-1)/2$).

So, how do you pick a value $g$ which is a primitive element? Well, if someone else hasn't already defined that for you, one easy way to make sure that your group is safe with SRP is to make sure that:

• $p$ and $(p-1)/2$ are both prime (note that these are listed as requirements in SRP anyways)
• $p \equiv 3 \mod 8$
• $g = 2$

The first ensures that the orders that group members can have are: $1$, $2$, $(p-1)/2$ and $p-1$. We already know that the order of the element $2$ is not $1$ or $2$; the second ensures there is no $x$ with $x^2 = 2 \mod p$, which means that $2$ does not have order $(p-1)/2$, and hence the order must be $p-1$.

The example they give in the Python implementation satisifies the above; if your number theory is not up-to-snuff, you could do worse than to just use that.

Answer 3

The size of the modulus for ssh implementations of Diffie-Hellman (according to RFC4419 from 2006) should be between 1024 and 8192 bits.

This seems to be a bit off from what @poncho recommended (128 bits) in 2012.