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 <***@zoho.com> 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
>
>