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

Dan Brown <danibrown@blackberry.com> Wed, 05 April 2017 19:39 UTC

Return-Path: <danibrown@blackberry.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C5D8712948B for <cfrg@ietfa.amsl.com>; Wed, 5 Apr 2017 12:39:10 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.608
X-Spam-Level:
X-Spam-Status: No, score=-1.608 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, PLING_QUERY=0.994, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id RQg_7MHHVXl1 for <cfrg@ietfa.amsl.com>; Wed, 5 Apr 2017 12:39:08 -0700 (PDT)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) (using TLSv1.2 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 42B9D1242F5 for <cfrg@irtf.org>; Wed, 5 Apr 2017 12:39:08 -0700 (PDT)
Received: from xct106cnc.rim.net ([10.65.161.206]) by mhs211cnc.rim.net with ESMTP/TLS/DHE-RSA-AES256-SHA; 05 Apr 2017 15:39:06 -0400
Received: from XCT115CNC.rim.net (10.65.161.215) by XCT106CNC.rim.net (10.65.161.206) with Microsoft SMTP Server (TLS) id 14.3.319.2; Wed, 5 Apr 2017 15:39:06 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT115CNC.rim.net ([::1]) with mapi id 14.03.0319.002; Wed, 5 Apr 2017 15:39:05 -0400
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
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.248]
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?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 05 Apr 2017 19:39:11 -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.)