# Diffie Hellman - how large should the random number be?

When using the Diffie Hellman exchange with the second Oakley group 1024 bit Prime per RFC 2409 (*), how large should the random numbers generated by both sides be?

In RFC 2631 this is called the private key, and I'm quoting:

X9.42 requires that the private key x be in the interval [2, (q -
2)]. x should be randomly generated in this interval. y is then
computed by calculating g^x mod p. To comply with this memo, m MUST
be >=160 bits in length, (consequently, q MUST be at least 160 bits
long). When symmetric ciphers stronger than DES are to be used, a

I'm going to be using AES-256 for the content encryption.

I don't know what q is for the second Oakley group.

Is 160 bits enough? Do I need to go as high as 1024 bits?

Needless to say I have a noise-generation capacity problem and I'm hurting already, so I need the least amount of noise that still keeps the system secure (at a roughly 112 bit equivalent bits of security which is approximately the level of security provided by the DH with a 1024 bit prime).

(*) I know this prime is not great, is being deprecated and all that. This is a legacy system for which I cannot enlarge the prime.

EDIT - clarification on my motivation: I'm using a good physical real random number generator (no "pseudo" magic). Yet to maintain statistical independence of the output there is a max sample rate. There is a scenario in the system which requires a fast setup of thousands of secure connections. I would rather not store the noise on disk in preparation for this scenario (lots of pitfalls down that path, let alone certification requirements) nor "expand" the noise using one of many techniques.

• Your desire to avoid crypto-quality pseudorandom expansion (from a crypto-quality seed) is understandable but, in my opinion, unfounded in this instance. One simple and secure solution is going to be using a crypto-strength PRNG (seeded by your physical real random number generator, say, seeded by 128 true-random bits) to generate a full 1024-bit exponent. – D.W. Mar 25 '12 at 23:01

Short answer. Yes, I think it is fine to choose x as a random 160-bit number. (I would not bet my life on it, but I'm pretty sure it is fine.)

Technical details. There are (at least) two ways to attack Diffie-Hellman.

1. One way is to use fancy algorithms for computing the discrete logarithm, e.g., based upon the number field sieve or the like. The running time of these algorithms is dependent upon the prime modulus p, and you need p to be large (certainly at least 1024 bits) to resist these attacks.

2. Another way is to use more basic algorithms, such as the baby-step giant-step algorithm or Pollard's algorithm. The running time of these algorithms is dependent upon the smaller of the size of q or the size of the exponent x. You need q to be large (at least 160 bits) to resist these attacks. You need the exponent to be chosen from a large space (i.e., at least 160 bits of entropy) to resist these attacks.

Since there are two different attacks, you'll need to choose your parameters to defeat both. That's why you need your exponent to be at least 160 bits.

Now the most conservative thing to do is to choose x uniformly at random in the interval [0,q-1] (or [2,q-2] if you prefer, it doesn't really matter). This will surely be secure, as long as p and q are big enough. The quote you pulled out seems to be saying that X9.42 recommends you use this conservative approach.

However in many cases you can get away with an optimization, sometimes known as the short-exponent optimization. The idea is you choose x uniformly at random from some smaller interval, say [0, 2160 - 1]. This is usually secure, if the protocol is designed right, though there have been some exceptions. The benefit is that if q is large, choosing a shorter x like this can significantly improve performance.

For the group you mention, q = (p-1)/2. (*) In other words, q is around 1023 bits long. This means the most conservative thing to do is to choose your x to be from the full range [0,q-1], but I believe you can probably get away with using the short-exponent optimization. I tried to read the IKE documents, and I didn't immediately find an explicit statement of whether the short-exponent optimization is always guaranteed to be safe for IKE, though I did find some passing remarks which seem to indicate that the developers did anticipate it might be OK to use.

Footnote (*): You can infer this as follows. RFC 2409 says that the "properties of these groups are described in [RFC2412]". Section E.2 of RFC 2412 lists the corresponding group, and lists the largest prime factor of the group order. The largest prime factor can be verified to be (p-1)/2. From this, it follows that q = (p-1)/2.

Edit 3/24: I just noticed, thanks to @CodeinChaos's answer, that you mentioned your reason for using a short exponent is not performance but rather the limited entropy in your PRNG. I find this a bit odd. What PRNG are you using? Are you sure you have a crypto-strength PRNG? Most cryptographic PRNGs can be used to pull an arbitrary-length pseudorandom string. If yours doesn't, then you can always take the output of your PRNG and expand it to a 1024-bit pseudorandom string: e.g., generate a 128-bit AES key K, then use AES(K,0), AES(K,1), AES(K,2), AES(K,3), ..., AES(K,7) to generate a 1024-bit pseudorandom string. Once you have a 1024-bit pseudorandom string (as long as it is crypto-quality and the original RNG has enough entropy in it), you can use that as a full-length 1024-bit exponent.

Do check that your RNG/PRNG is crypto-strength. For example, `/dev/urandom` and `CryptGenRandom` are good, but `rand()`, `random()`, `drand48()` are all bad. (`/dev/random` is strong but unnecessary; use `/dev/urandom` instead, and you will be able to draw a full-length exponent with no problems.) Search on this site for more information about crypto-quality PRNGs.

• So let me get this straight : the standard says I need to choose from the 1023 bit range, in this case, yet you think I'm OK with a 160 bit random based on a knowledge of known attacks? – Tal Weiss Mar 24 '12 at 12:03
• @TalWeiss, yup. There are 2 different standards here. The RFC claims that X9.42 requires that you choose from the full 1023-bit range. (I'm not familiar with X9.42, and I don't know if it indeed says that, or why.) My belief is that choosing a 160-bit value is OK and that the quote from X9.42 does not need to be followed. I realize it sounds dubious, and I apologize that I have not been able to find an external source to support my claim. Feel free to use the full 1023-bit range if it makes you more comfortable. – D.W. Mar 24 '12 at 18:18
• See my edit per your edit. – Tal Weiss Mar 24 '12 at 19:19

Needless to say I have a noise-generation capacity problem and I'm hurting already, so I need the least amount of noise that still keeps the system secure (at a roughly 112 bit equivalent bits of security which is approximately the level of security provided by the DH with a 1024 bit prime).

I'd look into using a good crypto PRNG which you seed(and occasionally re-seed) with your actual entropy. That way you can easily create large amounts of random numbers. I believe fortuna is a popular choice for a PRNG.

Once generating random numbers is cheap, there is no reason use numbers smaller than the maximal range. But since I'm not too familiar with DH, I don't know what that range is.

160 bits is enough for 1024 bit DH, but that will be weaker than your 256 bit AES. See for example Table 2 in NIST SP 800-57, or this key length calculator. (For equivalence with 256-bit symmetric keys they recommend 15360-bit DH (with 512-bit random number), or, more practically, using a 512-bit elliptic curve.)

So if your legacy system stops you using a stronger key exchange, using a 256-bit key might be a waste of time.