0
$\begingroup$

When picking an ephemeral Diffie-Hellman private key (little a or little b), can I reasonably just pick 32 random bytes? I am specifically interested in use within SRPv6.

RFC5054 says that these ephemeral keys are "a random number that SHOULD be at least 256 bits in length."

RFC2631 says

X9.42 requires that requires that the private key x be in the interval [2, (q - 2)]. x should be randomly generated in this interval.

(where q is (N-1)/2.)

Goals and concerns

It would be nice to just get a bunch of random bytes and make those into a big integer than to have to uniformly pick a big integer within a specific range.

Question updates following comments

When rfc2631 was first published (1999) DH groups were very small my todays (2017) standards. I am using the 4096-bit group from Appendix A of rfc5054, which means that q is a 4095-bit number. So if I shorten the range to a whole number of bytes, I would need to get 511 random bytes (4088 bits). That is an enormous amount of entropy to be asking.

As noted in a comment, picking a number uniformly in a range (that isn't a whole number of bytes) means addressing the modulo bias. I would much prefer to not try to deal with the modulo bias and so just pick a whole number of bytes.

Related questions (and answers)

My question is related to – but distinct from – Diffie-Hellman secret key choices, which is asking about some very specific values of generated keys.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Note that DH and SRP is distinct protocols, which differ in subtle ways. I don't believe they differ significantly as far as your question goes; however, I would go with the SRP-specific RFC... $\endgroup$
    – poncho
    Commented Sep 30, 2017 at 19:59
  • 3
    $\begingroup$ I think for SRP you need to pick uniformly from the subgroup (i.e. a random key between 0 and q multiplied by the co-factor to project into the subgroup). Otherwise you'll lose some theoretical security guarantees (perfectly hiding, computationally binding, IIRC). $\endgroup$
    – CodesInChaos
    Commented Sep 30, 2017 at 20:34
  • $\begingroup$ I should point out then when using a 4096 bit group, following the fuller standard requires getting (at least) 511 bytes of randomness for something that may not even provide 256 bit security. Seems like overkill. $\endgroup$
    – Jeffrey Goldberg
    Commented Oct 1, 2017 at 21:44
  • 1
    $\begingroup$ @JeffreyGoldberg You need to distinguish between different security goals. One goal is preventing an attacker from learning any information about the password (beyond validating a single password guess) and AFAIK SRP provides security against computationally unbounded attackers with respect to that goal, which requires choosing a truly random element from the group. If you're willing to sacrifice that guarantee, a secret of twice the security level is probably still computationally secure. $\endgroup$
    – CodesInChaos
    Commented Oct 2, 2017 at 8:53
  • 1
    $\begingroup$ @JeffreyGoldberg I'm not an expert on SRP, so my comments are just a mix of speculation and vague recollections. I'd prefer leaving answering this to somebody who really understands SRP and its security assumptions. $\endgroup$
    – CodesInChaos
    Commented Oct 3, 2017 at 13:36

2 Answers 2

Reset to default
1
$\begingroup$

It would be nice to just get a bunch of random bytes and make those into a big integer than to have to uniformly pick a big integer within a specific range.

If you pick a uniformly random value from a bigger set and throw away everything that is not in your range until you find something you will get a uniformly random value in that range.

If however you do something like taking a random big integer and reducing it modulo $q-2$ to put it into your range you will skew the distribution and you will lose some security.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I’m aware of the modulo bias, and for smaller ranges of integers work to get a truly uniform distribution within the range. But that is more expensive with when dealing with cases where q is 4095 bits. This is why I am asking if I can use a smaller range than all of [2, q-1]. $\endgroup$
    – Jeffrey Goldberg
    Commented Oct 2, 2017 at 15:38
1
$\begingroup$

I am going to answer my own question based on CodesInChaos's earlier comment and the content of Section 8 of RFC 3526: More Modular Exponential (MODP) Diffie-Hellman groups for Internet Key Exchange.

It states that the exponent size should be twice the strength estimate for the group, and it gives low and high estimates for the strength of groups of different sizes.

+----------+---------------------+---------------------+
| Modulus  | Low Estimate        | High Estimate       |
|          +----------+----------+----------+----------+
|          |          | exponent |          | exponent |
|          | in bits  | size     | in bits  | size     |
+----------+----------+----------+----------+----------+
| 1536-bit |       90 |     180- |      120 |     240- |
| 2048-bit |      110 |     220- |      160 |     320- |
| 3072-bit |      130 |     260- |      210 |     420- |
| 4096-bit |      150 |     300- |      240 |     480- |
| 6144-bit |      170 |     340- |      270 |     540- |
| 8192-bit |      190 |     380- |      310 |     620- |
+----------+---------------------+---------------------+

The moduli in the SRPv6 RFC (5054) are the same as in this (though they use different generators, g), so we can use these estimates (to the extent that they are still considered valid today) to find the most appropriate exponent size for each group.

Personally, I am rounding up from the low estimate to the nearest multiple of 8, except for the 3072 group, where I round down to exactly 256 bits for simple convenience (and the fact that this what what the code base I'm looking at already uses.)

So using that rounding scheme (with my exception) I have

  • 3072 bit group – 32 byte exponent
  • 4096 bit group – 38 byte exponent
  • 6144 bit group – 43 byte exponent
  • 8192 bit group – 48 byte exponent

(I'm not planning on supporting groups smaller than the 3072 group).

Note that my choice of rounding and of working from the low estimate are somewhat arbitrary judgement calls. I'm prioritizing for implementation and run time ease, while still staying within reasonable choices.

I'm not ignoring the fact that there are definable (though abstract) security advantages to picking an exponent uniformly within the range [2, q - 2]. Other things being equal, I would seek those advantages. But having a server request many hundreds of bytes of randomness during every authentication event is definitely not a case of "other things being equal."

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.