I haven't read through the references but am grateful for them. Indeed, I haven't actually followed this mail-thread in detail but I was struck by a strange sense of déjà-vu. There was a similar discussion over 10 years ago;
http://marc.info/?t=107058742900001&r=1&w=2 :-) Talk about feeling old... Cheers, Geoff On Tue, May 27, 2014 at 8:47 PM, mancha <[email protected]> wrote: > On Tue, May 27, 2014 at 08:23:29AM +0200, Otto Moerbeek wrote: > > On Tue, May 27, 2014 at 05:23:45AM +0000, mancha wrote: > > > > > On Mon, May 26, 2014 at 09:01:53PM +0000, 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 > > > > > > This is probably more wonkish than Ben intended with his question > > > but for those interested, the Poisson result I alluded to is due to > > > Gallagher [1]. > > > > > > [1] Gallagher, On the distribution of primes in short intervals, > > > Mathematika, 1976 > > > > Would this work: if you are worried the algorithm will never pick the > > highest of a prime pair, just make it search backward half of the > > time? > > > > But I understand it has no real security implications. > > > > -Otto > > The issue is not limited to twin primes though that extreme drives the > point home. In the twin case {p,p+2}, OpenSSL only finds p+2 if p+1 or > p+2 happens to be the randomly selected start point. So, the proportion > of primes OpenSSL finds that are twins will be significantly lower than > theory predicts. With OpenSSL's incremental search, the probability a > particular probable prime p is selected is proportional to the length of > the gap of composites which immediately precedes it. > > Brandt and Damgard [1], from what I can tell the fathers of the > incremental search OpenSSL uses, share Viktor Dukhovni's view and use an > entropy argument to conclude little or no additional risk exists with > incremental searches relative to uniformly distributed prime generation. > > Mihailescu (of Catalan Conjecture fame) establishes a complexity > equivalence class to argue improved attacks against an incremental > search can be converted to attacks against uniformly distributed prime > generation with comparable runtimes [2]. For Mihailescu, incremental > search bias is "tolerable", especially in light of the lower entropy > costs and efficiency gains relative to naive discard & repeat. The > improvements he models are, in essence, improvements in the > state-of-the-art not the result of leveraging bias. > > Fouque and Tibouchi [3] offer the differing view that it's preferable to > minimize bias and generate primes that are almost uniform "even if it is > not immediately clear how such biases can help an adversary". They > suggest a few algorithms that improve on naive discard & repeat by > discarding only the top N bits of a candidate at each iteration, among > other innovations. > > --- > [1] Brandt and Damgard, On Generation of Probable Primes by Incremental > Search, 1988 > ]2] Mihailescu, Measuring the Cryptographic Relevance of Biased Public > Key Distributions, 1998 > [3] Fouque and Tibouchi, Close to Uniform Prime Number Generation With > Fewer Random Bits, 2011 > >
