# 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 at 22:37

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.

-
Figured as much. In this case I'm trying to break the system rather than fix it (that's someone else's job!) so I guess this definitely counts as a vulnerability. –  Polynomial Mar 27 at 11:32
@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 at 11:36
@Thomas One would think so, but it's a surprising pain in the ass to attack in any practical way unless you have a decent number of samples. Every implementation after Java 1.4.2 uses a 48-bit seed based on the current microsecond-resolution timestamp and some difficult-to-predict system statistics. It's absolutely possible, given various prerequisites, but therein lies the catch. –  Polynomial Mar 27 at 11:40
@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 at 11:46