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

"Anna (Amy) Johnston" <> Fri, 07 April 2017 02:29 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 14F83128E19 for <>; Thu, 6 Apr 2017 19:29:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.005
X-Spam-Status: No, score=-1.005 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, PLING_QUERY=0.994, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 6sn-ByfuQeyC for <>; Thu, 6 Apr 2017 19:29:25 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:400e:c05::230]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 72B2E12708C for <>; Thu, 6 Apr 2017 19:29:23 -0700 (PDT)
Received: by with SMTP id g2so51453319pge.3 for <>; Thu, 06 Apr 2017 19:29:23 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=am2EbZPqRAi04ZaRQXMjS1P7eSIEkMdu6RlpeNPNtlM=; b=NzdUq+OMWB5VuHnpQp6tvCkmW9M/5Ll9pelFOmcijOVtD7QzYQdi4sONJ4H0HVuih1 gvokV/wAZ4LhbYOonmJtdA+uKuX2rf82MPp90vNhz4M527sg8RfrUGY5ehqyHw+H4Tee iU/PBFiFp40ItSyXX/ul8hhGUcSpV1y7/9lntUlmhjcMpGBSzRCzPOnRW0PIMNTFpiQ7 ObxB9haYHO10Ht4iOQHjYXrjVRIT2LhAxqMr/4cw+nQy+CELP8z1KDk9Mzlg9CjYyGgj d5Quc5iV7Jxkp7/TEl1/nIAsFF7qBfL1CTpVS1qlhWMRHqrFL1SFJv37Y7rTcJF3GSlO h1Xg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=am2EbZPqRAi04ZaRQXMjS1P7eSIEkMdu6RlpeNPNtlM=; b=JI1obBuIcoCy1prEa1iPLrYJEytqtF0pC6x7ZDx2QB9Ap+DPC83SobyFrdio7xzIgf YdCC0/CvaGS+zaBVrn/xCxYoK7qJirZStRsV0fX5vtRpw2Vy00tKMhw3JhJHyfg1fhNW BO2E4HZP1xyy8TVX2ZG4faSEJizGN2X/lodrY5751U0gr46TiUJCtM2aQWxGGN3W2wkR 9wFyYZEVG7udAofkJj2245r140vad6wEWfVuPgWpVoZS8+CjKazwAB8BGEnvcLyitAZs OS8F2jnKsA7N2INIgFCtxd69eAQv8rdx89hextFo9smguqXSozzRi5tUV06fh2aW0d91 xnNQ==
X-Gm-Message-State: AFeK/H21s+IQx7loogcw+P7vesffDCD5X9JDLH6UAeDDeVKN8Z1W0DHno5nwI8EGhvB/CA==
X-Received: by with SMTP id r4mr38771658pfg.185.1491532162912; Thu, 06 Apr 2017 19:29:22 -0700 (PDT)
Received: from ?IPv6:2601:1c2:4f03:b950:7472:1d95:ea1f:52e3? ([2601:1c2:4f03:b950:7472:1d95:ea1f:52e3]) by with ESMTPSA id u69sm5949654pfg.121.2017. (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 06 Apr 2017 19:29:22 -0700 (PDT)
Content-Type: text/plain; charset="us-ascii"
Mime-Version: 1.0 (1.0)
From: "Anna (Amy) Johnston" <>
X-Mailer: iPad Mail (14E304)
In-Reply-To: <>
Date: Thu, 06 Apr 2017 19:29:21 -0700
Cc: "" <>
Content-Transfer-Encoding: quoted-printable
Message-Id: <>
References: <> <> <> <> <> <> <>
To: Dan Brown <>
Archived-At: <>
Subject: Re: [Cfrg] Prime 630*(427!+1)+1 for classic DH?
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 07 Apr 2017 02:29:27 -0000

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 <> wrote:
> Good points!  Responses inline below (between <<< >>> sorry if that's awkward.)
> -----Original Message-----
> From: Cfrg [] 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., 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.