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

Michael D'Errico <mike-list@pobox.com> Fri, 16 October 2020 19:55 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 316573A0AA4
for <cfrg@ietfa.amsl.com>; Fri, 16 Oct 2020 12:55:20 -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_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=U83UvgY+;
dkim=pass (2048-bit key)
header.d=messagingengine.com header.b=iJGWT0fd

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 GeNJG8c8L2Zm for <cfrg@ietfa.amsl.com>;
Fri, 16 Oct 2020 12:55:18 -0700 (PDT)

Received: from wout3-smtp.messagingengine.com (wout3-smtp.messagingengine.com
[64.147.123.19])
(using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 291203A0AA3
for <cfrg@irtf.org>; Fri, 16 Oct 2020 12:55:18 -0700 (PDT)

Received: from compute4.internal (compute4.nyi.internal [10.202.2.44])
by mailout.west.internal (Postfix) with ESMTP id 37D7AF83
for <cfrg@irtf.org>; Fri, 16 Oct 2020 15:55:17 -0400 (EDT)

Received: from imap21 ([10.202.2.71])
by compute4.internal (MEProxy); Fri, 16 Oct 2020 15:55:17 -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=gGfv1
lEioBGJx3sO0nWju4wwYuF52OZJLwv/O6r7+bU=; b=U83UvgY+ioCSivKXC0n8t
gNPL9OqHBz+BpyNH5zCEHjnAbveNfTeBRo5ftTTfb6aa7xp1wx+fiTAtUaATKwru
MUpK7tMvS0ZBvoIxxjacDPGz81TPg0h6fo4gs4ungaT5fIRZroRCu54cD7v/vN0D
iew6YYGhTNg2WDGt4OlVvNQv5Tf8giQBdsv+tzR4S5pFoC9XUZBHndIrtYBc9xyG
HPkMCrRMqsYzlXavB67299fnhvujP4utIAwjWjSchXd7cXnoBYzymD9zLALLBXWJ
c6dzU2qRcVWWzdcTCR1a3IqKI8e8f9pkhXRQCSPW3fdtvk1MFLKJ2XhYCAYQfYcW
g==

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=gGfv1lEioBGJx3sO0nWju4wwYuF52OZJLwv/O6r7+
bU=; b=iJGWT0fdzhevx4syeDkRfoYhXzvIb7BPv5Hzr8cV3aFkK9SB2BYs5ImZZ
QHLLGZC+ZhLs+K0wTTBCul9+AwoPljFI+lwVlajRwYxM4iRgI/yqRfgHdeHKy1NC
TFyRrNykFxavfNBICv/nHrVxRyKrGSauwTNMtkL5O6I6nMkmiFlaQMKjzPY+14sz
nQUiPZ8bhjmAcBhkjoo7xb4WghO4Cj0QpYUOUvTF92smQvVu/H9px3IIiuc7yLxa
L79nHNqw/ZCVsnHLG8cJoXCmYoQDT0Mths/GOBjFtX7FB8GYylUqIJKFBIX42CCk
cGVje2p/4Y/b1MQQLh11RA9TCXzbg==

X-ME-Sender: <xms:pPqJX-LtCQh8gnGQ-Pj0OBqa-BwNj77Obt36M9OGCPm8rTxVWsq40g>
<xme:pPqJX2JxQejker_g0xeXczrtzUGS5BGnGFvc3FvKh2Ug4Uyj_jKkOlcD-ZCuiyyMz
SfaRR371XCdE04t1A>

X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrieehgddugeefucetufdoteggodetrfdotf
fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen
uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtgfesth
hqredtreerjeenucfhrhhomhepfdfoihgthhgrvghlucffkdfgrhhrihgtohdfuceomhhi
khgvqdhlihhsthesphhosghogidrtghomheqnecuggftrfgrthhtvghrnhepfeefiedule
fhteeifeehieffudehteektdetteejkeeukedutdfgveehgeevffetnecuffhomhgrihhn
pehirhhtfhdrohhrghenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrih
hlfhhrohhmpehmihhkvgdqlhhishhtsehpohgsohigrdgtohhm

X-ME-Proxy: <xmx:pPqJX-uqcyk_Bv9wxCawc7eFzGwYwvxZRXy9mPIJ7N5XGeBvPh3flg>
<xmx:pPqJXzZUVjHezoGD8px3-Zt69g27IlmgJEwp5QGqxWj4tMKXl_tOgQ>
<xmx:pPqJX1YjdkMDfV9kKHb8HleK7GU7q5fwz_CheLKBswbTp8lrxUc7zA>
<xmx:pPqJX-lyAYDyvQFg1u4wLYyZhbxEqCyqLdpXBAZ-EwIbiUMOeNOp9w>

Received: by mailuser.nyi.internal (Postfix, from userid 501)
id 255C7660069; Fri, 16 Oct 2020 15:55:07 -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: <cc5b03ef-01d0-44a3-9030-1faa99107425@www.fastmail.com>

In-Reply-To: <770E332F-B404-45C8-898B-BAD69A9B75A0@shiftleft.org>

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>

Date: Fri, 16 Oct 2020 15:53:36 -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/PSKR9CeDiQkanBfL6zKYxceEtGU>

Subject: [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: Fri, 16 Oct 2020 19:55:20 -0000

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, > > > > Thank you for your message! > > > > 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 Thu, Oct 15, 2020, at 16:00, Anna Johnston wrote: > >> Hi Michael, > >> The attack you mentioned is logical. If I am not mistaken, the attack > >> is recovering, bit by bit, the quotient (v) in the equation: 2^X = vP + > >> r, where r = 2^X mod P. The fly in the attack is size. > >> (1) The smallest P in this list is over 700 bits: P > 2^{700}. > >> (2) X is on the order of P, as 2 has order q where P=2q+1. > >> (3) so, 2^X, in its unreduced form, is greater than 2^{2^{700}} > >> (4) That means that v (the quotient) is greater than > >> 2^{2^{700}}/2^{700}=2^{2^{700}-700} which is still about 2^{2^{700}}, > >> or 2^{700} bits long. > >> > >> This size means that only a minuscule fraction of the quotient bits > >> could be computed/stored (not enough seconds in time or atoms in the > >> known universe). > >> > >> Hope this helps, > >> > >> Anna > >> > >>> 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 mailing list > >>> Cfrg@irtf.org > >>> https://www.irtf.org/mailman/listinfo/cfrg > >> > >> > > > > _______________________________________________ > > Cfrg mailing list > > Cfrg@irtf.org > > https://www.irtf.org/mailman/listinfo/cfrg > >

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