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

Michael D'Errico <mike-list@pobox.com> Sat, 17 October 2020 18:34 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 AFEAA3A13C6
for <cfrg@ietfa.amsl.com>; Sat, 17 Oct 2020 11:34:28 -0700 (PDT)

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

X-Spam-Flag: NO

X-Spam-Score: -2.098

X-Spam-Level:

X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_MSPIKE_H4=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=P37j6QwE;
dkim=pass (2048-bit key)
header.d=messagingengine.com header.b=m9d9sIQh

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 nybnf9kW9Uvn for <cfrg@ietfa.amsl.com>;
Sat, 17 Oct 2020 11:34:26 -0700 (PDT)

Received: from wout1-smtp.messagingengine.com (wout1-smtp.messagingengine.com
[64.147.123.24])
(using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 377083A13C2
for <cfrg@irtf.org>; Sat, 17 Oct 2020 11:34:25 -0700 (PDT)

Received: from compute4.internal (compute4.nyi.internal [10.202.2.44])
by mailout.west.internal (Postfix) with ESMTP id C5A17ABD
for <cfrg@irtf.org>; Sat, 17 Oct 2020 14:34:23 -0400 (EDT)

Received: from imap21 ([10.202.2.71])
by compute4.internal (MEProxy); Sat, 17 Oct 2020 14:34:23 -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=sG9C/
9c+D81cQapBUu6mB89Rh/K/fswTo7f1WMXtTf8=; b=P37j6QwENjy7+uZbwrmrB
i90yqJQMjJeK/UEHK2QnOBMeGepGef4NPN22064O1wjECG4q/uYYx1/aTEMQA6Y5
+ANoZbTQNrWYlpM8cFuctfRs42G1aWRTeNWSW0r6OthifUx1uXUX3LU8q7lc9caw
TccIJKLX81WEEOwtvSDC8usu0RN5OE67XXupPkbjGeakH+hUiQFnsKEKxciMijU8
JuFogIvyf2fpll7qAA3ktxjkOumVAhi0Yj9iNy5aMMnGmKD7cii6yMz6ktw3NSBc
8qeNMEXPuFbkMIebsXB0OaOpM8nqRX1boEeoobm/es2VIQNNAqheIHR+adVBj03X
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=sG9C/9c+D81cQapBUu6mB89Rh/K/fswTo7f1WMXtT
f8=; b=m9d9sIQhBu7Tr5cJ4j0nfbZ7hEjVlNwJTfTib857GoeQLenFw9np49RuZ
b2/Xn/qPwZ4n4L6JYQJQgYwthbJlzkmFGqFhEGQyO90dor/V/joxXfB8LJ+VzoPV
LPnIwXxFKlDl8mIBHFAwiXLFaWn3yp1E/6+D3Uw/F6FDpYLCKs8C/V1PPsLb4Rby
9NGncaoHFRKbG3txwuJGoWST2ZqFriN8WGrTjgbgGTCwlJZwv8Vr8SRsnXWxm047
ACATmUbl1LUmqcAh5BsVg2CSnIADYNKFaYaJTVOb2aR5OfxYsvy7w4UsbGnLUqN4
ZHIPQN+960eONBvtme3HWOT46sg8Q==

X-ME-Sender: <xms:LjmLX6mklrE78xIAfumagoah5md0iO6L11vbbeXUhtN3oVXJbbfNnw>
<xme:LjmLXx0O1pYwnoJpx1L0scEK4bADVBugc4aNqyGKGO6aIpFZr_ZMSV1KKwq2UYlMX
5eVmD6PsLvkr0_4Dw>

X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrieejgdduvdejucetufdoteggodetrfdotf
fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen
uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtgfesth
hqredtreerjeenucfhrhhomhepfdfoihgthhgrvghlucffkdfgrhhrihgtohdfuceomhhi
khgvqdhlihhsthesphhosghogidrtghomheqnecuggftrfgrthhtvghrnhepgeelteefie
eijeeugedvkefgjeeijeffveeijeekkeeklefhieehveejtdeugeeinecuffhomhgrihhn
pegrlhhpvghrthhrohhnrdgtohhmrdgrrhenucevlhhushhtvghrufhiiigvpedtnecurf
grrhgrmhepmhgrihhlfhhrohhmpehmihhkvgdqlhhishhtsehpohgsohigrdgtohhm

X-ME-Proxy: <xmx:LjmLX4po7qkE5HYVBgtlL9subGhmcmU2NL3Id1gsE7gDwOFyBeEs8Q>
<xmx:LjmLX-nqidyv6nuBoCpH--m7kx14Ibr4eIr2kV9c4W6uZCzdl3TGJQ>
<xmx:LjmLX40f1qh3rKGXo5JpOFt-4tmyIPc_Dr3Pi8rvFDfd8Ry5pdnx2Q>
<xmx:LzmLX5CbbcTezlkoflmrAi23fGTwjrwuggDNq90WCtSZKDH7WMaOjw>

Received: by mailuser.nyi.internal (Postfix, from userid 501)
id BD0DA660069; Sat, 17 Oct 2020 14:34:12 -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: <3c63be30-5c09-42b0-a0a4-18190ef5d548@www.fastmail.com>

In-Reply-To: <cc5b03ef-01d0-44a3-9030-1faa99107425@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>

Date: Sat, 17 Oct 2020 14:34:01 -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/23mi7C5wEJpmlXU29_q5fchuz0k>

Subject: Re: [Cfrg]
=?utf-8?q?Inadequate_Definition_of_=22Safe_Prime=22_=3F_?=
=?utf-8?q?=28was=3A_Weak_Diffie-Hellman_Primes=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: Sat, 17 Oct 2020 18:34:29 -0000

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