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

From: Dan Brown <[email-masked]>
Date: Wed, 5 Apr 2017 19:39:04 +0000

Hi All,

Is the prime p=630*(427!+1)+1 vulnerable to the SNFS, or some variant of SNFS?  I think not, but I could easily be very wrong.

If not, then the prime p=630*(427!+1)+1 seems to have some potential advantages (listed below) for use in finite field (classic) Diffie-Hellman key agreement.  I am not sure of these, so please let me know if you agree or not.

1. Its given expression uses 14 just characters, with standard math notation, so it has a relatively compact representation, ensuring (arguably) it was NOT the result of an exhaustive search of random primes for some obscure weaknesses (as in Gordon's attack), since presumably such a search would result in a more complicated expression.

2. Its given expression is not just a simple polynomial evaluation, due to the factorial, thereby avoiding a known class of primes to which SNFS is known to apply.  (Most expressions (that I can think of) for large DH primes that use fewer than 14 characters, such as Mersenne primes, are already known to be relatively weak under the SNFS, as I understand it.)

3. It seems (heuristically) that, in general, factorials (see *) are not easily expressed as polynomials, which weakly and conjecturally suggests that the known forms of SNFS might not apply to p.  Of course, vulnerability to SNFS should nonetheless be tested, just like for any other DH prime.  (* a heuristic reason: a generic ability to find modularly-efficient polynomial expressions for factorials would lead to an efficient factoring algorithm, though, of course, 427 factorial may be an exception to this conjectured rule.)

4. The cofactor 630 is small.  Though not 2, as in a "safe" prime, 630 is still small enough (either to use as a cofactor exponent, or to let a few fixed bits out of a 3000 to leak.) 

5. The cofactor 630 is small as possible, for the choice 427!+1 of large prime factor of p-1. (Again, a choice aimed to rule out any tricks.)  Also, 630 is a slightly smaller than what one would expect on average.

6. The bit length of p is at least 3072 bits, corresponding to 128-bit security, with modest margin for error (against improvements in GNFS, etc.)  (Varying this conditions, allows for other similar expressions for primes, but not too many.)

7. The large prime order subgroup has order q = 427!+1, with the property that q-1 is very smooth (compared to average).  This property of q-1 should make den Boer's reduction between the DHP and DLP nearly optimal.  

8. Questionably: the special form of p might enable mild speed-ups (compared to random primes) in modular reduction. 

9. Beyond just its compact expression, as measured in its 14-character count, there _seem_ to be very few primes that share all of the benefits above (e.g. near-optimal den Boer reductions), so its specialness is even greater than its compactness suggests.  This specialness further ensures resistance to malicious-search attacks (like Gordon's).  (This advantage overlaps with advantages 2 and 5).

I'm not saying that classic DH is preferable to alternatives ECDH (or QR crypto), it is not.  But classic DH has a role in a high-end systems that can afford to apply multiple layers of security (in an effort to protect against a major catastrophe of one algorithm failing).  

Some IETF protocols currently allow several classic DH primes. Some are derived from pi, or e, which is an example of a strategy often called nothing-up-my-sleeve (NUMS).  These extant NUMS DH primes resist known attacks, but I'm wondering if p=630*(427!+1)+1 seems to have some mild advantages over these, mainly stronger security arguments (including an arguably better NUMS-type argument), as listed above.  

Again, my main proviso for p=630*(427!+1)+1 is that I have not tried to run some kind of SNFS on p.  I truly have very limited understanding of the NFS, so maybe I am missing something obvious, such as the factorial enabling the SNFS (or some new of variant of SNFS). Despite this risk, I still thought special prime was at least worth further consideration.
 
Best regards,

Dan Brown 
Certicom, BlackBerry

PS The situation for ECDH is a little different from FFDH, because of Gordon's attack, which involves a hidden weakness of known kind, i.e. a trapdoor.  Therefore, in FFDH the imperative to use some form of NUMS to exclude a trapdoor is a greater than in ECDH.   For ECDH, the main risk seems to be a totally new attack, which, in my opinion, increases the relative imperative to choose a pseudorandom curve (as I've argued previously on the CFRG list).  Obviously p=630*(427!+1)+1 is not pseudorandom.  (Choosing a pseudorandom classic DH prime weakens the NUMS-type arguments against trapdoors (because the prime would be less compact), and likely weakens the effectiveness of the den Boer reduction.)

---

From: Greg Rose <[email-masked]>
Date: Wed, 5 Apr 2017 13:32:25 -0700

> On Apr 5, 2017, at 12:39 , Dan Brown <[email-masked]> wrote:
> [snip]... for the choice 427!+1 of large prime factor of p-1. [snip]
> 

Since a surprisingly large number of people think that N!+1 must be prime (referring back to the proof that there are an infinite number of primes) I checked. It is. Not that I ever doubted you, Dan...

Greg.

---

From: Greg Rose <[email-masked]>
Date: Wed, 5 Apr 2017 16:20:26 -0700

> Since a surprisingly large number of people think that N!+1 must be prime (referring back to the proof that there are an infinite number of primes) I checked. It is. Not that I ever doubted you, Da…

A number of people responded off-list asking why I said this, and/or how I checked primality.

Quoting: https://primes.utm.edu/notes/proofs/infinite/euclids.html
> Theorem.
> There are infinitely many primes.
> Proof.
> Suppose that p1=2 < p2 = 3 < ... < pr are all of the primes. Let P = p1p2...pr+1 and let p be a prime dividing P; then p can not be any of p1, p2, ..., pr, otherwise p would divide the difference P-p1p2...pr=1, which is impossible. So this prime p is still another prime, and p1, p2, ..., pr would not be all of the primes.
> It is a common mistake to think that this proof says the product p1p2...pr+1 is prime.  The proof actually only uses the fact that there is a prime dividing this product.

I calculated 427!+1 using bc, edited it to remove continuation lines, and pasted the result into https://www.alpertron.com.ar/ECM.HTM. If it had been composite, it might have taken a long time when asked to factor it, but it takes very little time to come back and say that it's prime (that is, it is its only non-trivial factor).

However, I then proceeded with the obvious experiment to check the original number: (quoting Dan's original mail)
> Is the prime p=630*(427!+1)+1 vulnerable to the SNFS, or some variant of SNFS?  I think not, but I could easily be very wrong.

Somewhat to my dismay, it did NOT immediately pronounce the number to be prime. 20 minutes later it's still trying to factor it. I don't have anything to hand that will just check primality... perhaps someone else should check it. (Or I will try harder when I have something better than my laptop, which will be a while). It's also possible I made some sort of transcription error, and if so I apologize. Someone who has Mathematica or Maple lying around?

Greg.

---

From: Greg Rose <[email-masked]>
Date: Wed, 5 Apr 2017 16:25:38 -0700

OK, I apologize... the program (which I didn't write) kept stale state lying around. When I restarted it, it said:

1 830998 721485 262949 894836 702451 036961 346345 183758 057314 969605 832210 766165 484702 660527 749681 669753 293173 634175 291671 053884 438775 722488 816078 101720 141886 540180 229728 708756 676904 267800 678375 988109 211903 639383 849998 133815 812655 789179 917782 318753 560669 025779 190769 237162 496508 423323 724885 434846 784602 021522 663931 265719 264163 422908 174749 084948 418025 158073 086974 407112 952072 014257 210539 064732 122044 449074 000638 203336 247808 232800 652739 257418 300964 286406 604674 828535 227832 036133 240428 107251 355410 159614 879003 579690 248976 997943 069280 372792 089146 955523 612918 267331 616675 492696 740809 033257 982724 038666 839691 447355 159466 625504 307450 674480 068371 423101 067410 940809 499585 043794 510375 720619 282353 170149 104988 150297 750261 797134 258461 975343 104442 292481 380023 690803 048872 074527 925875 984122 186106 029245 281730 797546 168103 284672 654245 481350 717852 877532 157706 240000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000631 (943 digits) is prime

... back to your normally scheduled program.

Greg.

Phone/Signal:  +1 619 890 8236 
GPG/PGP:  1081A37C  232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C

> On Apr 5, 2017, at 16:20 , Greg Rose <[email-masked]> wrote:
>

---

From: Travis Finkenauer <[email-masked]>
Date: Thu, 6 Apr 2017 01:33:56 +0000

I verified the primality of q = 427!+1 and p = 630*(427!+1)+1 in a python shell:

>>> import math, sympy
>>> q = math.factorial(427) + 1
>>> q
2906347176960734841102915400715931684676738386917551293602548940017089151563020096075793145507544909799419325859795323626093294797601295362066222447438952667031315410724883975028255045041250967003021649815634917672723512152046317329813204370731220675839985347995496026203846545595056245788546987335750260208358284546291147473293252515791139722473131884086360496749320657551127839785289082610236625397838417994044140052064528157551457620578232391435991791325758463549417841949376589453031999388696831078873411074599909633778369511252614215116845902011637486786496344033030211520607498474074348716583103427724802387789604245206457732417620741922128269046960386975413294794633781512968490642838333805952796503387711844405306514987765843460355064766744241388139564882514479660485760706796398091343123973467734371818224366218814091320885248000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001L
>>> p = 630 * q + 1
>>> p
1830998721485262949894836702451036961346345183758057314969605832210766165484702660527749681669753293173634175291671053884438775722488816078101720141886540180229728708756676904267800678375988109211903639383849998133815812655789179917782318753560669025779190769237162496508423323724885434846784602021522663931265719264163422908174749084948418025158073086974407112952072014257210539064732122044449074000638203336247808232800652739257418300964286406604674828535227832036133240428107251355410159614879003579690248976997943069280372792089146955523612918267331616675492696740809033257982724038666839691447355159466625504307450674480068371423101067410940809499585043794510375720619282353170149104988150297750261797134258461975343104442292481380023690803048872074527925875984122186106029245281730797546168103284672654245481350717852877532157706240000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000631L
>>> sympy.ntheory.isprime(q)
True
>>> sympy.ntheory.isprime(p)
True

-Travis

> On Apr 5, 2017, at 4:20 PM, Greg Rose <[email-masked]> wrote:
> 
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Travis Finkenauer <[email-masked]>
Date: Thu, 6 Apr 2017 01:54:18 +0000

I just realized the '>>>' of the python shell might be rendered as a triple blockquote; here is the python session with '>>>' replaced with '%':

% import math, sympy
% q = math.factorial(427) + 1
% q
2906347176960734841102915400715931684676738386917551293602548940017089151563020096075793145507544909799419325859795323626093294797601295362066222447438952667031315410724883975028255045041250967003021649815634917672723512152046317329813204370731220675839985347995496026203846545595056245788546987335750260208358284546291147473293252515791139722473131884086360496749320657551127839785289082610236625397838417994044140052064528157551457620578232391435991791325758463549417841949376589453031999388696831078873411074599909633778369511252614215116845902011637486786496344033030211520607498474074348716583103427724802387789604245206457732417620741922128269046960386975413294794633781512968490642838333805952796503387711844405306514987765843460355064766744241388139564882514479660485760706796398091343123973467734371818224366218814091320885248000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001L
% p = 630 * q + 1
% p
1830998721485262949894836702451036961346345183758057314969605832210766165484702660527749681669753293173634175291671053884438775722488816078101720141886540180229728708756676904267800678375988109211903639383849998133815812655789179917782318753560669025779190769237162496508423323724885434846784602021522663931265719264163422908174749084948418025158073086974407112952072014257210539064732122044449074000638203336247808232800652739257418300964286406604674828535227832036133240428107251355410159614879003579690248976997943069280372792089146955523612918267331616675492696740809033257982724038666839691447355159466625504307450674480068371423101067410940809499585043794510375720619282353170149104988150297750261797134258461975343104442292481380023690803048872074527925875984122186106029245281730797546168103284672654245481350717852877532157706240000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000631L
% sympy.ntheory.isprime(q)
True
% sympy.ntheory.isprime(p)
True

-Travis

On 4/5/17, 6:33 PM, "Cfrg on behalf of Travis Finkenauer" <[email-masked] on behalf of [email-masked]> wrote:

    True
    True
    
    -Travis

---

From: "Anna (Amy) Johnston" <[email-masked]>
Date: Wed, 5 Apr 2017 20:37:11 -0700

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.

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.

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. 

Pocklington's theorem is not only an efficient test for this prime, but is a way to efficiently (if q is at least 1/2 the bits, then 2 exponentiations) test primality, but also quickly verify primality AND produces an element of order q (the same two exponentiations).
 
A. Johnston
Sent from my iPad

> On Apr 5, 2017, at 18:54, Travis Finkenauer <[email-masked]> wrote:
> 
> sympy.ntheory.isprime

---

From: Dan Brown <[email-masked]>
Date: Thu, 6 Apr 2017 14:26:28 +0000

Good points!  Responses inline below (between <<< >>> sorry if that's awkward.)

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Anna (Amy) Johnston

<<<
Sounds right.  Primality proofs are good checks before deployment.  I felt they were not needed to tentatively discuss the merits.

<<< 
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. 

<<< 
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.

---

From: "Anna (Amy) Johnston" <[email-masked]>
Date: Thu, 6 Apr 2017 19:29:21 -0700

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 <[email-masked]> wrote:
>

---

From: Watson Ladd <[email-masked]>
Date: Thu, 6 Apr 2017 20:13:24 -0700

> 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…

Smart attackers tune the relative complexities of the two stages to
optimize for attack cost.  If you can sieve faster, you can sieve
harder to save time in the linear algebra step. This depends crucially
on interconnect speed, resources, etc. They also balance the
precomputation time against the time to find a particular discrete
logarithm. The gains from cheapening an already cheap step depend on
the new tradeoffs that enables.

> 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…

The GNFS parallelizes across primes as well.  Furthermore, using
supplied primes by each side has lead to security vulnerabilities in
TLS. These were avoidable, but show that there is no panacea. However,
no attacker will ever conduct a calculation of size 2^256. The way to
avoid them computing every key is to make sure that they cannot even
compute 1 key.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.