On 5/26/14 2:01 PM, mancha wrote:
On Mon, May 26, 2014 at 08:49:03PM +0000, Viktor Dukhovni wrote:
On Mon, May 26, 2014 at 08:20:43PM +0000, mancha wrote:
For our purposes, the operative question is whether the distribution
bias created can be leveraged in any way to attack factoring (RSA)
or dlog (DH).
The maximum gap between primes of size $n$ is conjectured to be around
$log(n)^2$. If $n$ is $2^k$, the gap is at most $k^2$, with an
average value of $k$. Thus the most probable primes are most $k$
times more probable than is typical, and we lose at most $log(k)$ bits
of entropy. This is not a problem.
One consequence of the k-tuple conjecture (generally believed to be
true) is that the size of gaps between primes is distributed poisson.
You're right when you say the entropy loss between a uniform
distribution to OpenSSL's biased one is small. In that sense there is
not much to be gained entropy-wise from using a process that gives
uniformly distributed primes over what OpenSSL does.
However, if a way exists to exploit the OpenSSL distribution bias, it
can be modified to be used against uniformly distributed primes with
only minimal algorithmic complexity increases. In other words, the gold
standard here isn't a uniform distribution.
--mancha
I doubt the claim (in one of the messages of this thread, but not above)
that generating a fresh random value for each prime check adds
considerable expense. If we include a CTR-DRBG generator (from NIST SP
800-90A) in the implementation, then the cost for 2048 bit RSA or DH is
18 AES block encryption operations (and it could be lowered to very
close to 16). Years ago, AES was said to take 18 cycles per byte on a
Pentium Pro (according to Wikipedia article). That comes to 2304
cycles. That's got to be peanuts relative to prime testing. On modern
processors the case is even stronger. According to the white paper at
https://software.intel.com/sites/default/files/m/d/4/1/d/8/10TB24_Breakthrough_AES_Performance_with_Intel_AES_New_Instructions.final.secure.pdf,
an Intel Core i7 Processor Extreme Edition, i7-980X can achieve 1.3
cycles per byte on AES, which would be 375 cycles. (There are a lot of
assumptions here. For one thing the paper was reporting CBC mode
decryption. If the hardware is specific to CBC mode, so it can can't
get parallelism with encryption, then it would be quite a bit slower.)
If it doesn't cost much to generate a new random value for each trial,
why not just do it?
--David
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-dev@openssl.org
Automated List Manager majord...@openssl.org
