### [Cfrg] Ideal Diffie-Hellman Primes (was: Inadequate Definition of "Safe Prime" ?)

Michael D'Errico <mike-list@pobox.com> Sun, 18 October 2020 14:06 UTC

Return-Path: <mike-list@pobox.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 DFE653A03F4
for <cfrg@ietfa.amsl.com>; Sun, 18 Oct 2020 07:06:12 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -0.198

X-Spam-Level:

X-Spam-Status: No, score=-0.198 tagged_above=-999 required=5
tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1,
DKIM_VALID_EF=-0.1, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001,
SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no

Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key)
header.d=pobox.com header.b=JMEXMKSu;
dkim=pass (2048-bit key)
header.d=messagingengine.com header.b=GdxcpHDd

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 Y73E0hbZq8DA for <cfrg@ietfa.amsl.com>;
Sun, 18 Oct 2020 07:06:10 -0700 (PDT)

Received: from wout4-smtp.messagingengine.com (wout4-smtp.messagingengine.com
[64.147.123.20])
(using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id B134E3A03F2
for <cfrg@irtf.org>; Sun, 18 Oct 2020 07:06:10 -0700 (PDT)

Received: from compute4.internal (compute4.nyi.internal [10.202.2.44])
by mailout.west.internal (Postfix) with ESMTP id CD19DC3C
for <cfrg@irtf.org>; Sun, 18 Oct 2020 10:06:09 -0400 (EDT)

Received: from imap21 ([10.202.2.71])
by compute4.internal (MEProxy); Sun, 18 Oct 2020 10:06:09 -0400

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pobox.com; h=
mime-version:message-id:in-reply-to:references:date:from:to
:subject:content-type:content-transfer-encoding; s=fm1; bh=1cFMC
bLELK7ShCe4iK+ksLvtAtvuXuteTOWcfZfEjSE=; b=JMEXMKSupAXztJCv4TNyw
hd3wd7LEPiKOoBIcz9/y/yL5WJ7XhRu1IuiEhio0vjpSzSOeK+s8e/sSehO8y6a0
giddcFRRk026zvICfehx3SoxhBD++D5Z6qzMfAZ8UewC601Q6OnBu3Rne1ROUDu3
5TWCjs0cmk/9Yrblr+Lc5prvHEWqJia+Gj7KHd0pyc7Ga265zmLc3AB/vg667fiE
g0htsbR6bQV1nGvYXwLbo3gSTDHL3ospelzW0UdUL68FoSITCwHrncTk5YVES4mq
p9dyKMv2MKrMFbIoyNU+5CUGYhN5BbZZ8+GfK4HkVBherg2QkMfBQR7M0GhqwQl4
w==

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=
messagingengine.com; h=content-transfer-encoding:content-type
:date:from:in-reply-to:message-id:mime-version:references
:subject:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender
:x-sasl-enc; s=fm1; bh=1cFMCbLELK7ShCe4iK+ksLvtAtvuXuteTOWcfZfEj
SE=; b=GdxcpHDdB7g5/qTz+kWw65AMWSAz29CVbOmUeT6ZTr/keXPML02eAmcdN
jldHTaNV8jlo+RTw90rv9zB8lCgi6y9u+nqJmNo26PLUPn7RAGl739G3CS8IVT9D
ht7fBi2hmK2MccuHkeobs9XXTodqlD+NHiENYAv0DYXoqzoyzP+88wWcdTmnCdiO
uHJrARKviElf6aLzK/RIq3uSVQplh+tqKY0BhGXx3Tv1/AMcpIEtBm+DKwkxwsIg
JM7rxvaGsYpO9wH5+R2mlXkV0BKWlszO5Wgfz1t0qCbDXuqlo5R3ttcU8eL6yIsI
MbsXh3CFxEBj8+CRUrxY7uNv1LoeA==

X-ME-Sender: <xms:0UuMX9cI70_XFYq8ZCanQGSeSh2vmRYRShaORmnJE316_SKcA3nrBA>
<xme:0UuMX7MJ4qp3LxcQJmqdtc3lhMx3KscHaVvFZGpQgP9LPBcDgkCdmddKfKCAqIVrM
DLJ0FdAuqaDj2DqtA>

X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrieelgdejvdcutefuodetggdotefrodftvf
curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu
uegrihhlohhuthemuceftddtnecunecujfgurhepofgfggfkjghffffhvffutgfgsehtqh
ertderreejnecuhfhrohhmpedfofhitghhrggvlhcuffdkgfhrrhhitghofdcuoehmihhk
vgdqlhhishhtsehpohgsohigrdgtohhmqeenucggtffrrghtthgvrhhnpeegleetfeeiie
ejueegvdekgfejieejffevieejkeekkeelhfeiheevjedtueegieenucffohhmrghinhep
rghlphgvrhhtrhhonhdrtghomhdrrghrnecuvehluhhsthgvrhfuihiivgeptdenucfrrg
hrrghmpehmrghilhhfrhhomhepmhhikhgvqdhlihhsthesphhosghogidrtghomh

X-ME-Proxy: <xmx:0UuMX2hLWfkH4D0BIkokpPngZL22o64do3qyq5JNgXilu-emWVcSOg>
<xmx:0UuMX2_3h11WMZulX11gCmvk4n7FYvxz7EYVpELutoV4Ol8BrVt89Q>
<xmx:0UuMX5vYyZPEyn_USZPH9uLBQg4KVoc2mtsJq8N51WuThEfBLmd8BA>
<xmx:0UuMX34XsSDfvJBR1Qoa5MDPl5w08iPtoomoz35IYqUC_0ee9ppMow>

Received: by mailuser.nyi.internal (Postfix, from userid 501)
id BF9D266006F; Sun, 18 Oct 2020 10:05:59 -0400 (EDT)

X-Mailer: MessagingEngine.com Webmail Interface

User-Agent: Cyrus-JMAP/3.3.0-489-gf39678d-fm-20201011.001-gf39678d0

Mime-Version: 1.0

Message-Id: <bc77f256-2fc6-48c1-9a7a-60ec6caaa55d@www.fastmail.com>

In-Reply-To: <3c63be30-5c09-42b0-a0a4-18190ef5d548@www.fastmail.com>

References: <07090aa6-1bd1-4a37-810d-6cd95a6f1e7c@www.fastmail.com>
<ACF3D521-99D7-4A46-A3E6-2865FE53A816@gmail.com>
<19672d78-77de-4744-b9d8-470a18dc3ac0@www.fastmail.com>
<770E332F-B404-45C8-898B-BAD69A9B75A0@shiftleft.org>
<cc5b03ef-01d0-44a3-9030-1faa99107425@www.fastmail.com>
<3c63be30-5c09-42b0-a0a4-18190ef5d548@www.fastmail.com>

Date: Sun, 18 Oct 2020 10:04:39 -0400

From: "Michael D'Errico" <mike-list@pobox.com>

To: cfrg@irtf.org

Content-Type: text/plain;charset=utf-8

Content-Transfer-Encoding: quoted-printable

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/8GCzkGW8cUTW8IhMBEN2li_WF1c>

Subject: [Cfrg] =?utf-8?q?Ideal_Diffie-Hellman_Primes_=28was=3A_Inadequat?=
=?utf-8?q?e_Definition_of_=22Safe_Prime=22_=3F=29?=

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.29

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: Sun, 18 Oct 2020 14:06:13 -0000

Good morning, Perhaps there is an "ideal" Diffie-Hellman prime with the following characteristics: [1] P is prime [2] (P-1)/2 is prime [3] (P+1)/4 is prime Is it possible to generate such a number (in a reasonable amount of time)? (You'd be able to skip any numbers where P mod 8 isn't 3.) In addition, I notice that all of the published Diffie-Hellman primes in [MODP] and [FFDHE] have their 64 most significant bits set to 1. Is this to make it unlikely for the secret X to be randomly chosen greater than P (when calculating 2^X mod P)? Does Diffie-Hellman fail if you choose a secret X larger than P? Do clients and servers check? Mike [MODP]: RFC 2409 and RFC 3526 [FFDHE]: RFC 7919 On Sat, Oct 17, 2020, at 14:34, I wrote: > Hi, > > I went to the trouble of computing the factors [*] > of (P+1)/2^64 for all of the "MODP" primes in RFCs > 2409 and 3526, and the "FFDHE" primes in RFC 7919, > so I thought it would be good to share the results. > > The final factor(s) are not shown but are assumed > to be prime or very large since the factoring > program never finished: > > > modp-0768: 3 * 5 * 58502243 * {183-digits} > > modp-1024: 2 * 3^3 * 7 * 61 * 755333 * > 903210511397 * {267} > > modp-1536: 2^3 * 3^2 * 5 * 7 * 59 * 773 * > 10111 * 713941 * 116114161 * {418} > > modp-2048: 3 * 5 * {597} > ffdhe-2048: 2^3 * 3^3 * 5 * 101 * 46559 * > 95651 * {583} > > modp-3072: 3 * 13 * 2129 * 5572027361377 * {888} > ffdhe-3072: 2^3 * 3 * 173 * {902} > > modp-4096: 2 * 3 * 3067 * {1210} > ffdhe-4096: 3^3 * 5^2 * 5683 * 853854997 * {1199} > > modp-6144: 3 * 19 * 137 * 211 * {1825} > ffdhe-6144: 2 × 3 × 41 × 9533 × 2417897 * {1818} > > modp-8192: 2^5 * 3^3 * 5 * 7^2 * 17 * 277 * {2438} > ffdhe-8192: 3 * 937 * 140611 * {2439} > > > Are there any conclusions to be drawn from this? > > Maybe that modp-2048 is "better" than ffdhe-2048, > but ffdhe-8192 is better than modp-8192? > > Is modp-1536 a really bad choice for a prime? > > Mike > > > [*] I used: https://www.alpertron.com.ar/ECM.HTM > (hopefully I didn't make any mistakes....) > > >> Hello, >> >> I think that the current definition of a "safe prime" >> for use in Diffie-Hellman may be inadequate and >> could require more than just: >> >> [1] P is prime >> [2] (P-1)/2 is also prime >> >> Maybe you also want: >> >> [3] (P+1) is square-free >> >> This postulate follows from the discussion quoted >> below. I've found that all of the Diffie-Helman primes >> published in RFC's 2409, 3526, and 7919 allow you >> to brute-force compute a secret 32 times faster than >> you would expect just looking at the number of bits. >> >> The prime numbers all have the property that (P+1) >> is divisible by 2^64. This follows from the fact that >> the lower sixty-four bits are all ones. I don't know >> if any additional problem arises by having the top >> 64 bits also equal to 1. >> >> These primes are (assumedly) safe according to the >> current definition ([1] and [2] above), but perhaps >> effectively 64 or more bits shorter than advertised. >> >> This could mean that the number field sieve would >> also be faster (the 2048-bit primes could act like >> 1984-bit primes), but I have not tried to determine >> this myself. >> >> It may be really difficult to find primes satisfying [1], >> [2], and [3], so there'd maybe be a trade-off where >> you'd allow a few square factors.... >> >> This is not my field of expertise, so I apologize if >> anyone feels I'm wasting their time. >> >> Mike >> >> >> On Fri, Oct 16, 2020, at 09:07, Mike Hamburg wrote: >>> Hello Mike, >>> >>> The limiting factor for DH security (and also RSA security) is a very complex >>> attack algorithm called the Number Field Sieve. So attacks on 2048-bit DH >>> safe prime would take time: >>> >>> * ~ 2^2048 using straightforward brute force >>> * ~ 2^1024 using collision-based brute force such as Pollard’s Rho >>> * ~ 2^112 using NFS. >>> >>> For DSA and sometimes for DH, people use primes p with a generator g >>> of smaller prime order q, eg q ~ 2^256 here. This speeds up the operation >>> at the cost of lower brute-force resistance. This would reduce the brute >>> force costs to >>> >>> * ~ 2^256 using straightforward brute force >>> * ~ 2^128 using collision-based brute force >>> * but still ~ 2^112 using NFS >>> >>> This is generally seen as acceptable, because the cost estimates for rho >>> attacks are much more certain than for NFS, and are still at an acceptable >>> level. Since the security is determined mainly by the best attack, this >>> doesn’t lower the security. (Unless NFS at that scale is harder than >>> projected, but in that case the security is still fine.) >>> >>> Likewise, your attack slightly speeds up straightforward brute force, but >>> not (as far as you’ve shown) collision-based brute force or NFS. So it >>> doesn’t affect the overall security of DH / DSA. >>> >>> However, primes of a special form *can* reduce security against the NFS. >>> But these aren’t primes that specifically begin or end with a lot of 1s, but >>> rather primes that can be expressed as a low or medium-degree polynomial >>> with small coefficients. For example, p = 2^2048 - 1557 would be a poor >>> choice, because it can be written as a small polynomial, eg >>> >>> p = x^32 - 1557 with x = 2^64. >>> >>> I’m not an expert on NFS, so I’m not sure exactly how much security this >>> knocks off. Asymptotically you lose about 20% of the bits, (eg 2^112 -> >>> 2^89, which is still out of reach of academics but maybe not large / govt >>> organizations, especially because most of the work can be amortized >>> across many discrete logs) but concretely this might be quite different. >>> >>> Cheers, >>> — Another Mike >>> >>>> On Oct 16, 2020, at 3:22 AM, Michael D'Errico <mike-list@pobox.com> wrote: >>>> >>>> Hello, >>>> >>>> [...] >>>> >>>> The algorithm I showed should run about 32 times faster >>>> than brute force, even though it's doing a brute force >>>> search. >>>> >>>> According to Wikipedia, a 2048-bit Diffie-Hellman prime >>>> is equivalent to 112 bits for a symmetric key, so perhaps >>>> the special structure of both 2048-bit published primes >>>> makes them equivalent to only 107 bits. >>>> >>>> Mike >>>> >>>>>> On Oct 15, 2020, at 09:15, Michael D'Errico <mike-list@pobox.com> wrote: >>>>>> >>>>>> Hi, >>>>>> >>>>>> I've figured out just a bit more. I'm actually trying >>>>>> not to work on this problem, but my brain keeps >>>>>> thinking about it anyway. The special format of >>>>>> the prime numbers in RFC's 2409, 3526, and >>>>>> 7919 allow you to create an interesting device to >>>>>> calculate the private value from a Diffie-Hellman >>>>>> public value using on the order of N bits (size of >>>>>> prime P). >>>>>> >>>>>> The lowest 64 bits of the Diffie-Hellman public >>>>>> value Y = (2^X mod P) contain a record of when >>>>>> the mod operation performed a subtraction of a >>>>>> shifted version of P (see my original message >>>>>> quoted below). You can reconstruct a larger value >>>>>> the modulo operation was working on by adding >>>>>> back: >>>>>> >>>>>> uint64 y = Y; // low 64 bits of public value >>>>>> >>>>>> Y += y * P; // mod P touched this number >>>>>> >>>>>> This updated version of Y contains the number >>>>>> that the mod P operation was working on 64 steps >>>>>> prior to finishing. But since the generator was 2 >>>>>> (and 2^X is a solitary 1 followed by a huge string >>>>>> of zeros), this new larger value of Y will have 64 >>>>>> zeros at the end which can be removed: >>>>>> >>>>>> Y>>= 64; // remove 64 zero bits >>>>>> >>>>>> This process can now repeat using the lowest 64 >>>>>> bits of Y again: >>>>>> >>>>>> repeat { >>>>>> >>>>>> uint64 y = Y; >>>>>> >>>>>> Y += y * P; >>>>>> >>>>>> Y>>= 64; >>>>>> >>>>>> } until (???); >>>>>> >>>>>> This process unwinds the modulo P operation all >>>>>> the way back to 2^X in steps of size 64. The only >>>>>> thing missing is the terminating condition, which >>>>>> I'm pretty sure would be: Y contains a single bit >>>>>> with value 1 (somewhere in the top 64 bits). If >>>>>> so, then the value of y would be zero a few times >>>>>> in a row and then contain a single one bit. >>>>>> >>>>>> If you can reliably determine when the algorithm >>>>>> has finished, you could build a device which >>>>>> computes X from Y using roughly N bits. It would >>>>>> be really slow, but it would be guaranteed to find >>>>>> the answer (32 times faster than brute force >>>>>> reversing the mod P operation one bit at a time >>>>>> on average?). >>>>>> >>>>>> Perhaps there is a way to make this algorithm >>>>>> (much) faster? >>>>>> >>>>>> Even if there isn't, it is very interesting to me that >>>>>> these primes exhibit such a strange feature. >>>>>> >>>>>> Mike >>>>>> >>>>>> >>>>>>> From: Michael D'Errico <mike-list@pobox.com> >>>>>>> Sent: Oct 10, 2020 6:01 PM >>>>>>> To: cfrg@irtf.org >>>>>>> Subject: [Cfrg] Weak Diffie-Hellman Primes >>>>>>> >>>>>>> Hi, >>>>>>> >>>>>>> I'm not a member of this list, but was encouraged to >>>>>>> start a discussion here about a discovery I made >>>>>>> w.r.t. the published Diffie-Hellman prime numbers in >>>>>>> RFC's 2409, 3526, and 7919. These primes all have >>>>>>> a very interesting property where you get 64 or more >>>>>>> bits (the least significant bits of 2^X mod P for some >>>>>>> secret X and prime P) detailing how the modulo >>>>>>> operation was done. These 64 bits probably reduce >>>>>>> the security of Diffie-Hellman key exchanges though >>>>>>> I have not tried to figure out how. >>>>>>> >>>>>>> The number 2^X is going to be a single bit with value >>>>>>> 1 followed by a lot of zeros. All of the primes in the >>>>>>> above mentioned RFC's have 64 bits of 1 in the most >>>>>>> and least significant positions. The 2's complement >>>>>>> of these primes will have a one in the least significant >>>>>>> bit and at least 63 zeros to the left. >>>>>>> >>>>>>> When you think about how a modulo operation is done >>>>>>> manually, you compare a shifted version of P against >>>>>>> the current value of the operand (which is initially 2^X) >>>>>>> and if it's larger than the (shifted) P, you subtract P at >>>>>>> that position and shift P to the right, or if the operand >>>>>>> is smaller than (the shifted) P, you just shift P to the >>>>>>> right without subtracting. >>>>>>> >>>>>>> Instead of subtracting, you can add the 2's complement >>>>>>> I mentioned above. Because of the fact that there are >>>>>>> 63 zeros followed by a 1 in the lowest position, you will >>>>>>> see a record of when the modulo operation performed >>>>>>> a subtraction (there's a one) and when it didn't (there's >>>>>>> a zero). >>>>>>> >>>>>>> You can use the value of the result you were given by >>>>>>> your peer (which is 2^X mod P) and then add back the >>>>>>> various 2^j * P's detailed wherever the lowest 64 bits >>>>>>> had a value of 1 to find the state of the mod P operation >>>>>>> when it wasn't yet finished. This intermediate result is >>>>>>> likely going to make it easier to determine X than just a >>>>>>> brute force search. >>>>>>> >>>>>>> I don't plan to join this list, though I am flattered to >>>>>>> have been asked to do so. I'm not a cryptographer. >>>>>>> >>>>>>> Mike

- [Cfrg] Weak Diffie-Hellman Primes Michael D'Errico
- Re: [Cfrg] Weak Diffie-Hellman Primes Dan Brown
- Re: [Cfrg] Weak Diffie-Hellman Primes Michael D'Errico
- Re: [Cfrg] Weak Diffie-Hellman Primes Michael D'Errico
- Re: [Cfrg] Weak Diffie-Hellman Primes Anna Johnston
- Re: [Cfrg] Weak Diffie-Hellman Primes Michael D'Errico
- Re: [Cfrg] Weak Diffie-Hellman Primes Mike Hamburg
- [Cfrg] Inadequate Definition of "Safe Prime" ? (w… Michael D'Errico
- Re: [Cfrg] Inadequate Definition of "Safe Prime" … Michael D'Errico
- [Cfrg] Ideal Diffie-Hellman Primes (was: Inadequa… Michael D'Errico
- [Cfrg] Is Diffie-Hellman Better Than We Think? (w… Michael D'Errico
- Re: [Cfrg] Is Diffie-Hellman Better Than We Think… Christopher Patton
- [Cfrg] Your Secret is Too Short (was: Is Diffie-H… Michael D'Errico
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Mike Hamburg
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Dan Brown
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Andrey Jivsov
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Ian Goldberg
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Dan Brown
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Andrey Jivsov
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Andrey Jivsov
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Ian Goldberg
- [Cfrg] New Type of Math Object Discovered? (was: … Michael D'Errico