Not quite correct, the prime rands shouldn't come from a DRBG, they should come from an NRBG (NIST terminology).
There's a considerable difference between the performance of an entropy source and a DRBG.
The output of a DRBG not being non-deterministic being the important point.
/dev/random V /dev/urandom performance. (1-2 bytes/second V 100k+/second)
/dev/random V /dev/urandom performance. (1-2 bytes/second V 100k+/second)
I did change the RNG sources for some of the OpenSSL code in our hacked version to help with the performance problems using the wrong source causes, for example RSA blinding data can safely come from a DRBG (pseudo_rand_bytes()).
Peter
-----owner-openssl-...@openssl.org wrote: -----
To: openssl-dev@openssl.org
From: David Jacobson
Sent by: owner-openssl-...@openssl.org
Date: 05/27/2014 05:16PM
Subject: Re: Prime generation
From: David Jacobson
Sent by: owner-openssl-...@openssl.org
Date: 05/27/2014 05:16PM
Subject: Re: Prime generation
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
> 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
