# 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 < 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?

-
Using java.util.Random for any cryptographic purpose is bad, no matter what is done with the output. There is the SecureRandom subclass for this reason. – Paŭlo Ebermann Mar 28 '13 at 22:37

• The public modulus $p$, which may be presumed to be known already, and
@Polynomial Doesn't "using Java's Random" count as a colossal vulnerability already? I think anything else short of handing over the secret nonce is moot in comparison. Good question nonetheless, timing attacks are very relevant currently. – Thomas Mar 27 '13 at 11:36
@Polynomial: if the default Java Random object is used (which may or may not be the case when Random is used), and if you can detect using timing analysis that the $\bar a \geq p$ condition has been triggered, then you can rule out some states or/and initial values of the RNG, and speed-up an attack; in fact, you could conceivably recover the state of the RNG by timing analysis only. That has nothing to do with DH. – fgrieu Mar 27 '13 at 11:46