Re: [Cfrg] Prime 630*(427!+1)+1 for classic DH?

["Anna (Amy) Johnston" <[e-mail]>]

Quick review, just so we're on the same page: Backdoored primes have hidden properties that allow discrete logarithms to be more easily computed.  This generally implies a polynomial structure to the prime which enables a more efficient sieve -- the special number field sieve (SNFS).  All primes can be linked to a special number field sieve, but finding the correct relation is very difficult (computationally infeasible) and some may not reduce computation as well as others.  In other words no prime is guaranteed to be safe against the SNFS, intentionally backdoored or not.

Number field sieves -- general, special or otherwise -- have three stages: sieve, solve (huge system of equations), and index calculus (find discrete log).  Once the sieve/solve steps have been completed, individual discrete logarithms are fairly fast and anywhere the prime is being used is vulnerable.

The SNFS only improves the sieve, it does not improve the linear algebra stage.  So if the linear algebra is becoming the time consumer (calendar wise, as the massive parallelism in the sieve means it spends a lot of compute time but not as much calendar time), the SNFS will not be as large a concern.

Anyone concerned about the SNFS, or any index calculus style attack, should be treating primes as cryptographic parameters with a fixed life time.  Single primes used across an entire network would be worth the expense of the sieves.  Never changing the prime gives an attacker all the time in the world to break it, and once broken, they own it and everything protected with it.

This is why I recommend against static primes of any kind.

A. Johnston

Sent from my iPad

> On Apr 6, 2017, at 07:26, Dan Brown <[e-mail]> wrote:
> 
> Good points!  Responses inline below (between <<< >>> sorry if that's awkward.)
> 
> -----Original Message-----
> From: Cfrg [mailto:[e-mail]] On Behalf Of Anna (Amy) Johnston
> 
> With a prime like this (and with the knowledge that q is prime), a better way (non-probabilistic) is to use Pocklington's theorem.  Two exponentiations with the right base and you've proved primality.  q can also be checked for primality with Pocklington's, but it takes a larger number of much smaller exponentiations.
> 
> <<<
> Sounds right.  Primality proofs are good checks before deployment.  I felt they were not needed to tentatively discuss the merits.
>>>> 
> 
> The SNFS reduces the computation cost of the sieve, but as larger base fields become the norm (at least 2048 bits), the linear algebra, not the sieve will be the problem (see iacr e-print 2017/067, page 8, as well as other discrete logarithm records in the past -- all shift work away from the linear algebra to the sieve).  This means that back doors are not as big a concern.
> 
> <<< 
> I was extrapolating (too much?) from Fried et al. ia.cr/2016/961, especially this from the Section 6.3 Lessons:
> 
> "Both from this perspective, and from our more modern one, dismissing
> the risk of trapdoored primes in real usage appears to have been a mistake, as
> the apparent difficulties encountered by the trapdoor designer in 1992 turn out
> to be easily circumvented."
> 
> My extrapolation is that for even for very large keysizes, let's not dismiss the possibility of a trapdoor, so let's use some kind of additional countermeasure.  I'm not alone in this, since other fixed DH prime in IETF RFCs are derived from pi, etc. I agree that it may, in the end, be overly cautious, but it seems to have little cost. 
>>>> 
> 
> If sieving attacks are the main concern, then regularly changing  the primes used would be a bigger boost to security.  Fixed primes, uses everywhere, mean that the huge cost of the sieve and solving the system of equations have an even bigger payoff.  Changing primes regularly minimizes an attackers gain from any possible sieve attack -- SNFS, more general, or other index calculus attacks which may be developed. 
> 
> <<< 
> Yes, you're essentially right about variable primes. I totally forgot to compare to them.  Prime 630*(427!+1)+1 should only be compared to other fixed DH primes. At the moment, I don't remember the usual tradeoffs between fixed and variable classic DH primes ..., but I recall that some like fixed DH primes. 
> 
> Hmm, I think variable DH primes compare less favorably to 630*(427!+1)+1 on the issue of the den Boer reduction.  I rather like the original den Boer reduction between DHP and DLP, and nearly optimizing it forces one to a special prime, which might as well (???) be fixed.  I do realize that there are reasonable alternatives to den Boer.  Most simply, just assume that DHP hard.  Use a Maurer-Wolf reduction, or rely on Boneh-Lipton's results about the conjectural existence of such reductions.  I just see the den Boer reduction as simpler, but maybe that's being too sentimental.
> 
> Side joke: for those that really like to see vitanums pi and e in their primes (not to mention sqrt(2)), look up Stirling's formula to find them in 630*(427!+1)+1.
>>>>