From: Dan Brown <danibrown@blackberry.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: Prime 630*(427!+1)+1 for classic DH?
Thread-Index: AdKuRDlyn/lIDT1CSziTnc33dxF2iA==
Date: Wed, 5 Apr 2017 19:39:04 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF501B0A7E2@XMB116CNC.rim.net>
Accept-Language: en-US, en-CA
Content-Language: en-US
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/3xXApon0jo-eSLrcqVAftMzVzIs>
Subject: [Cfrg] Prime 630*(427!+1)+1 for classic DH?
Precedence: list

Hi All,

Is the prime p=3D630*(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=3D630*(427!+1)+1 seems to have some potential adva=
ntages (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 n=
ot.

1. Its given expression uses 14 just characters, with standard math notatio=
n, so it has a relatively compact representation, ensuring (arguably) it wa=
s 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 re=
sult 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 kn=
own 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 kno=
wn to be relatively weak under the SNFS, as I understand it.)

3. It seems (heuristically) that, in general, factorials (see *) are not ea=
sily 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 r=
ule.)

4. The cofactor 630 is small.  Though not 2, as in a "safe" prime, 630 is s=
till small enough (either to use as a cofactor exponent, or to let a few fi=
xed bits out of a 3000 to leak.)=20

5. The cofactor 630 is small as possible, for the choice 427!+1 of large pr=
ime factor of p-1. (Again, a choice aimed to rule out any tricks.)  Also, 6=
30 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 secu=
rity, with modest margin for error (against improvements in GNFS, etc.)  (V=
arying this conditions, allows for other similar expressions for primes, bu=
t not too many.)

7. The large prime order subgroup has order q =3D 427!+1, with the property=
 that q-1 is very smooth (compared to average).  This property of q-1 shoul=
d make den Boer's reduction between the DHP and DLP nearly optimal. =20

8. Questionably: the special form of p might enable mild speed-ups (compare=
d to random primes) in modular reduction.=20

9. Beyond just its compact expression, as measured in its 14-character coun=
t, 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 resistanc=
e to malicious-search attacks (like Gordon's).  (This advantage overlaps wi=
th advantages 2 and 5).

I'm not saying that classic DH is preferable to alternatives ECDH (or QR cr=
ypto), 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 again=
st a major catastrophe of one algorithm failing). =20

Some IETF protocols currently allow several classic DH primes. Some are der=
ived 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=3D630*(427!+1)+1 seems to have some mild advantages ove=
r these, mainly stronger security arguments (including an arguably better N=
UMS-type argument), as listed above. =20

Again, my main proviso for p=3D630*(427!+1)+1 is that I have not tried to r=
un 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 enablin=
g the SNFS (or some new of variant of SNFS). Despite this risk, I still tho=
ught special prime was at least worth further consideration.
=20
Best regards,

Dan Brown=20
Certicom, BlackBerry

PS The situation for ECDH is a little different from FFDH, because of Gordo=
n'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 imperativ=
e to choose a pseudorandom curve (as I've argued previously on the CFRG lis=
t).  Obviously p=3D630*(427!+1)+1 is not pseudorandom.  (Choosing a pseudor=
andom classic DH prime weakens the NUMS-type arguments against trapdoors (b=
ecause the prime would be less compact), and likely weakens the effectivene=
ss of the den Boer reduction.)