Are there security issues with discrete logarithm keys not being uniformly distributed?

Question

Generally, algorithms based on discrete logarithm specify that private keys are chosen as scalars between 1 and the order of the group (denoted $q$ here). For instance IEEE P1363 and FIPS 186-3 both specify this range for DL private keys. Is it a problem if the key is not uniformly chosen from this range?

One possibility would be choosing a random integer of $k=\log_2(q)$ bits and reduce it mod $q$. In this case, the private key would be more likely to be in the range $[1,2^k-q]$ than otherwise. Another situation where this would occur is if the implementation fixes a top bit, for instance repeatedly generating $k$-bit integers until one less than $q$ is generated). So the attacker knows the key is not in the range $[1...2^{k-1}]$.

How much of an advantage do attackers gain when key generation techniques like these are used? Obviously the total key space is reduced, but is there a reduction in security beyond that? For instance is a DSA key with 160 bit $q$ and $x$ fixed to being 159 bits easier to break than a DSA key with 159 bit $q$ and $x$ fully random?

Answer 1

The discrete logarithm problem can be attacked with either a specific or a generic algorithm. A specific algorithm is one that tries to exploit structural weaknesses of the specific group in which discrete logarithm is used; e.g. Index Calculus when we are talking about exponentiation modulo a big prime. Generic algorithms only use the group law and thus work on "any" group. For normal elliptic curves (excluding those which allow for an efficient pairing), no specific algorithm is known.

For a group with $N$ elements, where the private key is chosen uniformly, the best generic algorithms work with cost $O(\sqrt{N})$; so with a 160-bit group you have security $2^{80}$. If the private key is not chosen uniformly, then the generic algorithm can be adjusted to take that into account: ultimately, this is equivalent to reducing $N$. In your examples, the "equivalent" $N$ is no smaller than $q/2$, so you reduce your security by no more than a $\sqrt{2}$ factor: not really worth worrying.

However, in (EC)DSA signature generation, a new value (called $k$ in FIPS 186-3) must be generated modulo $q$ for each signature; it is sometimes called a "transient private key". Contrary to the private key $x$, the value $k$ MUST be generated uniformly. For instance, if $k$ is chosen by selecting a sequence of random bits of length one less than the length of $q$, or if $k$ is selected by taking a sequence of random bits of the same length than $q$ and reducing it modulo $q$, then the private key $x$ can be reconstructed by observing many signatures and total cost $2^{63}$, which, while still big, is substantially lower than the expected $2^{80}$. This was found by Bleichenbacher in 2001; I am not sure it was formally published anywhere (Vaudenay talks of it as a "private communication"). The problem here is not in the discrete logarithm per se, but in how $k$ and $x$ are used in the computation of $s$ (the second half of an (EC)DSA signature).

The current FIPS 186 (FIPS 186-3) fixes that issue by generating a bit sequence at least 64 bits longer than $q$, then reducing it modulo $q$ (this makes the bias small enough to be unimportant). In X9.62-2005 (the ECDSA standard), they simply generate bit sequences of the length of $k$ and start again if this yields a value which does not lie between $1$ and $q-1$.

Either way, for a properly secure (EC)DSA signature generation, you must have a way to generate reasonably unbiased $k$ values; hence, you can use the same generator for producing the private key $x$.