2
$\begingroup$

In PKCS#3 the generation for DH secrets mandates to generate them with a minimum size if length is specified:

The central authority may optionally select an integer $\ell$, the private-value length in bits, that satisfies $2^{\ell-1} \le p$.
[…]

An integer $x$, the private value, shall be generated privately and randomly. This integer shall satisfy $0 < x < p-1$, unless the central authority specifies a private-value length $\ell$, in which case the integer shall satisfy $2^{\ell-1} \le x < 2^\ell$.

(Math formulas re-typeset in LaTeX for readability; see comments.)

The normal way to do this would be generate a random number over the whole range and loop if it does not fit (pseudo Java):

do {
    x = new BigInteger(lSize, random);
} while(2^(lSize-1) > x || x > 2^lSize || x > p-1); // x.bitLength!=lSize || x > p-1

However this results in looping at least half of the time. Would it be safe to set the most significant bit by hand and generate the rest randomly. I think yes - as the bits are supposed to be independent:

do {
    x = new BigInteger(lSize-1, random);
    x = x.setBit(lSize);
} while (x > p-1);

Is this an acceptable optimization?

$\endgroup$
  • $\begingroup$ Ugh, don't use lowercase l as identifier please. Just use length or s for size. $\endgroup$ – Maarten Bodewes Aug 21 '16 at 14:25
  • $\begingroup$ l is the standards name for this (the original source of JDK uses lSize (which is confsing on its own, I would prefer xSize). $\endgroup$ – eckes Aug 21 '16 at 14:26
  • 1
    $\begingroup$ Using the names from the protocol is a good thing l suppose, but l'd still prefer something like lengthL or similar. I've just used the mathematical symbols (Unicode) but in that case you must be sure that UTF-8 is always supported - so CVS is out... $\endgroup$ – Maarten Bodewes Aug 21 '16 at 14:30
  • 1
    $\begingroup$ @MaartenBodewes: The lin the original text is perfectly readable (albeit somewhat similar to a 1), at least on my screen (obviously, it depends on which monospace font your browser uses). The problem is that, in the sans-serif font used here for plain question text, the lowercase L looks simply like a vertical bar (as does the capital I!). IMO, the solution is to either mark the quoted "monospace math" expressions as inline code (which renders them with a monospace font) or typeset them properly (preferably using a cursive $\ell$) at the cost of exact quote fidelity. $\endgroup$ – Ilmari Karonen Aug 21 '16 at 16:54
  • $\begingroup$ Thanks @IlmariKaronen for the typesetting. Looks great. Should be readable enough to discuss the question now. $\endgroup$ – eckes Aug 21 '16 at 17:42
3
$\begingroup$

Yes, the two code snippets in your question generate the exact same distribution of random outputs $x$ (assuming that the RNG you're using is indeed indistinguishable from a true source of uniformly random bits, anyway). Thus, it makes no difference to the outcome which of them you use.

BTW, it seems to me that neither of your programs correctly implements PKCS#3 section 7.1, and the difference could have potentially serious security implications. Specifically, the problem is that your code rejects any $x$ greater than $p-1$, even though PKCS#3 does not impose this limit when the length $\ell$ is defined by the central authority. As a consequence, you're not choosing $x$ randomly from the full range $2^{\ell-1} \le x < 2^\ell$, but rather from the reduced range $2^{\ell-1} \le x < \min(p, 2^\ell)$. This could be quite disastrous for security, if e.g. $p$ happens to be only slightly greater than $2^{\ell-1}$ (which the standard allows!).

Thus, AFAICT, a correct implementation of PKCS#3 section 7.1 would look something like this:

if (lSize == 0) {

    // no lSize defined: choose x uniformly from 0 < x < p-1
    do {
        x = new BigInteger(p.bitLength(), random);
    } while (x == 0 || x >= p-1);

} else {

    // lSize is defined: choose x uniformly from 2^(lSize-1) <= x < 2^lSize
    x = new BigInteger(lSize-1, random);
    x = x.setBit(lSize);

}

Note that, in the second case, it's quite possible that $x \ge p-1$. There is no mathematical problem with this, although obviously an implementation may wish to reduce such $x$ modulo $p-1$ before the exponentiation step for the sake of efficiency (but do beware of timing attacks possibly leaking up to a bit of the secret!).

It may also be desirable to reject $x = p-1$, as using this value would result in $y = 1$, which the other party should refuse to accept for obvious reasons (even though PKCS#3 does not appear to actually say so!). Of course, in practice, the case $x = p-1$ can only happen if $2^\ell > p-1$, and then only with probability $1/2^{\ell-1}$, which should be practically negligible if $p$ is large enough to be otherwise secure.

$\endgroup$
  • $\begingroup$ Yes there are two different restrictions on the upper secret length and OpenJDK (where the code is from) mixes them. It is not a big problem as l has to be smaller than |p| but well.... $\endgroup$ – eckes Aug 21 '16 at 20:52
3
$\begingroup$

Sure thing. You'd lose up to one bit of security, but that's generally acceptable.

$\endgroup$
  • 1
    $\begingroup$ A lot of these kind of definitions come from the fact that they are made by mathematicians (most theoretical cryptographers are mathematicians rather than developers). The problem is when these things creep up into actual protocols that need to be developed. Such a loop is completely unnecessary. $\endgroup$ – Maarten Bodewes Aug 21 '16 at 14:23
  • $\begingroup$ The problem is that "fixing bits" in this case seems safe, but in others not. For example to limit the range of random numbers nulling bits is not safe as the resulting intgers are not evenly distributed anymore. Thats why I am careful with the setting of 1 bit, but since it is on powr-of-two boundaries it looks fine. $\endgroup$ – eckes Aug 21 '16 at 14:28
  • $\begingroup$ Actually the PKCS3 definition is better than most, it does not prescribe looping. If you followa"Applied Cryptography" book receipt (where the original code comes from) then it is more strict on requiring a loop. (For "some" good reasons as my comment above) $\endgroup$ – eckes Aug 21 '16 at 14:30
  • 1
    $\begingroup$ Yes, it depends on the algorithm. Most of the time when the bits are converted to numbers in a range it's OK (you'd just use a sub-range), but when a completely random distribution of bits is required, it's certainly not. $\endgroup$ – Maarten Bodewes Aug 21 '16 at 14:34
  • 1
    $\begingroup$ @eckes: Ah, yes, you do lose some security when picking $x$ between $2^{\ell-1}$ and $2^\ell-1$, compared to just picking it uniformly between $1$ and $p-2$. I originally assumed that Maarten was referring to the difference between the two methods of picking $x$ between $2^{\ell-1}$ and $2^\ell-1$ shown in your question. $\endgroup$ – Ilmari Karonen Aug 21 '16 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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