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

Watson Ladd <watsonbladd@gmail.com> Fri, 07 April 2017 03:13 UTC

Return-Path: <watsonbladd@gmail.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 34A99129495 for <cfrg@ietfa.amsl.com>; Thu, 6 Apr 2017 20:13:28 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.005
X-Spam-Level:
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: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 MZcKzeniL6KY for <cfrg@ietfa.amsl.com>; Thu, 6 Apr 2017 20:13:26 -0700 (PDT)
Received: from mail-pg0-x22d.google.com (mail-pg0-x22d.google.com [IPv6:2607:f8b0:400e:c05::22d]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EAD6B129446 for <cfrg@irtf.org>; Thu, 6 Apr 2017 20:13:25 -0700 (PDT)
Received: by mail-pg0-x22d.google.com with SMTP id x125so53217436pgb.0 for <cfrg@irtf.org>; Thu, 06 Apr 2017 20:13:25 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=3e/pQyxrwNDwzlP1/pH9Wnpx5Lv92jva2hHNol6BT7Y=; b=lqvqXya7ndDlMoQ9gwT0qwxa1dQ4d90g5mklXCkrXkA2uKKNvBqTQh/HTWuX6e4NOv /KUd0g04LHMDg+Nc700/uNEc+vItqxjg9YdRPlkYkjUS/SSXN0hGTiRCZdPDjrhLmJcG io8OB+cS74BZbBbeCOg29yic0LKshTsZphI1rImbtKLpz4bMb0mulQQ3w5WgrQMDWdGP R1t3kIx7yzMdMMl66Qb8WBQz/2ibiwvG5pRNCvh9iSrSZXwHMC8SvnzavaAME6CMlec3 B1VFWHtkwqvLhMxDBtd6Ullf5VphfCsFHwfrrYBsYNXTfTcd3Hg0tiix4Fdvf0Z219vU aWAg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=3e/pQyxrwNDwzlP1/pH9Wnpx5Lv92jva2hHNol6BT7Y=; b=f6Ly4HF84ARVjHLZGy3/bKZGMxJROa5p1h93P4TrGNMnhDjxkd4vZbUDnp9/saIUGv uQVDPYcAVaH6VYN/GHrgFiwlKbg4/c2KNQl5eQXPVsrEwl5oZD2fsz0xrLNbjEbOIKWE nlFvHSZp91PFD2YA49jbfPGKzEMnr0cC5S1+DjsUMNmLP0kskFMQUJfWkTNfHneQ9QfL v55PdQ6d6Hiq9xxO7Vq28jVoqfJ5DfuqGaAZzk0DHVRcthgnEmZHyImU/qyobEbPgozO ycYSP+0nCilG1haQ8ZMitUaJFa46i4XbhtPMXWoOEHuVpClyyzm3sBnFxcFFTf8yjDdi CB7A==
X-Gm-Message-State: AFeK/H0h/Tzh+J4zqPQaR+Zh07ShbARaE0XKdJLtxGdulQEd+IVbgecKPItMhmBlXD4GaUvQmftYIFJmx3WWjA==
X-Received: by 10.98.17.20 with SMTP id z20mr39344167pfi.67.1491534805323; Thu, 06 Apr 2017 20:13:25 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.100.160.194 with HTTP; Thu, 6 Apr 2017 20:13:24 -0700 (PDT)
In-Reply-To: <CD786F91-3C6B-4E85-88B6-FE09514E8913@gmail.com>
References: <810C31990B57ED40B2062BA10D43FBF501B0A7E2@XMB116CNC.rim.net> <B237EB39-C25F-48D7-9B51-81653A380F5F@seer-grog.net> <88898D32-CFF0-4043-BA88-9849031069E2@seer-grog.net> <7626A54F-BE87-4E68-B0F9-54CD878B4A87@juniper.net> <91D64FF1-D997-42FB-90CE-3B1422584974@juniper.net> <C5082BB6-EE29-4E64-A1FA-80E6BE482C60@gmail.com> <810C31990B57ED40B2062BA10D43FBF501B0AC3A@XMB116CNC.rim.net> <CD786F91-3C6B-4E85-88B6-FE09514E8913@gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
Date: Thu, 06 Apr 2017 20:13:24 -0700
Message-ID: <CACsn0cnBkOGJ2zYpavY7tHURL3i1QWcfHA=WfWKCXBALLGudFQ@mail.gmail.com>
To: "Anna (Amy) Johnston" <jannaston@gmail.com>
Cc: Dan Brown <danibrown@blackberry.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/AAZ4OlsNFpV4BLoAqnIbTkG1Q5g>
Subject: Re: [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: Fri, 07 Apr 2017 03:13:28 -0000

On Thu, Apr 6, 2017 at 7:29 PM, Anna (Amy) Johnston <jannaston@gmail.com> wrote:
> 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.

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

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.

>
> 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 <danibrown@blackberry.com> wrote:
>>
>> Good points!  Responses inline below (between <<< >>> sorry if that's awkward.)
>>
>> -----Original Message-----
>> From: Cfrg [mailto:cfrg-bounces@irtf.org] 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.
>>>>>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg



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