Potential vulnerability in DH key selection - am I understanding this right? I'm reading through a DH implementation, and I think I found a potential hole.


Public $p$ and $g$ values are properly selected.
A candidate secret value $\bar a$ is pseudo-randomly selected such that $0 \leq \bar a &lt; 2^{|p|}$, where $|p|$ is the number of bits required to store $p$.
If $\bar a \geq p$, discard it and repeat the previous step. Otherwise select it as the secret value $a$.


This already leaks some information about the output of the PRNG, since measuring the number of repeated selections via timing tells us how many $\bar a$ values were chosen such that $\bar a \geq p$. Whilst the PRNG is poor (it's Java's inbuilt Random class), this doesn't constitute a feasible timing attack.

An interesting case is when $p$ is close to $2^{|p|}$, since there will be cases where the $\bar a \geq p$ condition will only be met when certain bits are set. For example:

$p = 0xFE4041FB$, or 11111110010000000100000111111011 in binary.
$|p| = 32$, therefore the maximum selected $\bar a$ value will be $2^{|p|}-1 = 0xFFFFFFFF$.
For every iteration in the loop, we know that $\bar a \geq p$, so the first 7 bits of $\bar a$ must have been 1.

Am I correct here, or have I missed something? Are there any other holes?
If an implementation uses a poor PRNG, there will always be vulnerabilities in that implementation. However, if you replace Random for a cryptographically secure PRNG, the method you describe for generating private exponents is fine. In such case the timings will only reveal information about:


The public modulus $p$, which may be presumed to be known already, and
The discarded values.


A CSPRNG will output values that are indistinguishable from uniform and therefore computationally unrelated. Hence, learning information about the values that are discarded, will not reveal any information about the value that is eventually selected.