### Re: [Cfrg] Weak Diffie-Hellman Primes

Michael D'Errico <mike-list@pobox.com> Mon, 12 October 2020 18:43 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 4BC583A160F
for <cfrg@ietfa.amsl.com>; Mon, 12 Oct 2020 11:43:47 -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=ZZiZ5Y+U;
dkim=pass (2048-bit key)
header.d=messagingengine.com header.b=eqbTpVE4

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 tRPNGGUKNHay for <cfrg@ietfa.amsl.com>;
Mon, 12 Oct 2020 11:43:45 -0700 (PDT)

Received: from out3-smtp.messagingengine.com (out3-smtp.messagingengine.com
[66.111.4.27])
(using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 6744D3A160E
for <cfrg@irtf.org>; Mon, 12 Oct 2020 11:43:45 -0700 (PDT)

Received: from compute4.internal (compute4.nyi.internal [10.202.2.44])
by mailout.nyi.internal (Postfix) with ESMTP id 0FE0F5C015B
for <cfrg@irtf.org>; Mon, 12 Oct 2020 14:43:44 -0400 (EDT)

Received: from imap21 ([10.202.2.71])
by compute4.internal (MEProxy); Mon, 12 Oct 2020 14:43:44 -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=rZRuU
ORLzxt8PjX6tolLVTWgNgvH9DSExRI9r6jSejE=; b=ZZiZ5Y+UpyZi15qSeMGuo
iSOqzX2PS9Z3FXKK51JOhOEDV4NQEONl1YiVt8IF53Y3tRFZk5bFi/MUeGrr3trd
vkC6Q+gUxYyA9mB1CPPSCqYpKdI4V2pRXBvkyNX8wyijzQger1wJXTKNU1rfwziX
juqJpboJpy0S9IX9WJ/kGeyiAHYr2dWJ40rAKl7drWksx+ORQ55RmiT64jt+p1Z5
THulALNCkTdFRZLZcNJdSQrbvvbdaY3eTz8HkzqP8OUhygLlwnW3NBqu7ir3idpm
M21WEGK+yotz8Ol/pMvArSapzr1np4E2JgpbNENFLOAjyjNMYH1vwNAINcMclKi5
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=rZRuUORLzxt8PjX6tolLVTWgNgvH9DSExRI9r6jSe
jE=; b=eqbTpVE447mM1MfRMP4Suz+vbpijVip0G8MSVLy32NrgMqgKWgAtNjCea
5xT5PgZH7E1x8Sf1ufWffWxUQzUbHd0XjpJ5FjnpOunyX/cAcNkOd7kD5583lw7c
SoJdZT9iDPnPQjp5PpmhD54HWYCOTpd/bRqSWJXWOZOQg+hsy0/p6y27Hyyw+C2a
74WHwwbNHS+Et+bYD+SKC1dfb1/SfKNSCkaL2gp9UymnyYZ30ZtVFJjwN4hUc94n
SOStrljq70Y/O1SNE8YZ9wJvNOVZNjm0vphRfOU0OYRfCeiVqVd4tKQp+VG3lWe3
i9yipWGkvu5FHnVZBIVhBH54LmAIA==

X-ME-Sender: <xms:36OEXwkPnFbI7Xnd88waiIekW-ypcFlWzQuAyVTAXUOmr2a5AcaScQ>
<xme:36OEX_2YNgjjACw2NJiQ1DDDxaiqhFLqcBmSC2EM7qTFjW1VUr-gwIw6VF_eNZOlJ
X73lzi8MB2QL68tTg>

X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrheejgddufedtucetufdoteggodetrfdotf
fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen
uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtgfesth
hqredtreerjeenucfhrhhomhepfdfoihgthhgrvghlucffkdfgrhhrihgtohdfuceomhhi
khgvqdhlihhsthesphhosghogidrtghomheqnecuggftrfgrthhtvghrnhepjeehgeeute
fggfdvfeetgeeghfeitdekgedtieekvdekleeuteffuddvffekgeeunecuffhomhgrihhn
pegslhgrtghksggvrhhrhidrtghomhdpphhrohhofhhpohhinhhtrdgtohhmnecuvehluh
hsthgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepmhhikhgvqdhlihhs
thesphhosghogidrtghomh

X-ME-Proxy: <xmx:36OEX-rJTvMN75TsX7b_6j0oAuvFhA_udXNJk5nrMsdMD3x1zGcLBQ>
<xmx:36OEX8mgj7Zkt1dIGAPQsw799kr4jCYR004tbgp6RTb1gmsNrM7BCA>
<xmx:36OEX-3PK4nqcxtAC7ifw-gqddlmFsplN8pmbbIWWHgwzs6mQyRHXg>
<xmx:4KOEX_DxEWfo6Oy578P8LwaN-wA0flj8G5g8T2sOif7YenWeDTfYyw>

Received: by mailuser.nyi.internal (Postfix, from userid 501)
id F3D0A660069; Mon, 12 Oct 2020 14:43:34 -0400 (EDT)

X-Mailer: MessagingEngine.com Webmail Interface

User-Agent: Cyrus-JMAP/3.3.0-407-g461656c-fm-20201004.001-g461656c6

Mime-Version: 1.0

Message-Id: <29deaa6e-dc17-4fb9-976d-23ae8b34494f@www.fastmail.com>

In-Reply-To: <da998077e86749298c5e158c322c06fa@blackberry.com>

References: <0a24076e-3227-405c-84d4-26d82b5ff783@www.fastmail.com>
<da998077e86749298c5e158c322c06fa@blackberry.com>

Date: Mon, 12 Oct 2020 14:42:12 -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/st3WZ1BazGSmrCCf305nRraaisA>

Subject: Re: [Cfrg] Weak Diffie-Hellman Primes

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: Mon, 12 Oct 2020 18:43:47 -0000

Hi again, [My bigger concern is other long-term parameters in other places with longer runs of 1's or 0's.] If you take the lowest 64 bits of the public value: r = (uint64) (2^X mod P); because of the special format of the published prime numbers as detailed in my original message below, you know that the modulo P operation touched this much larger number: (2^X mod P) + rP I haven't worked out what advantage this gives you in determining X, and likely don't know the required math to do so. I am HOPEFUL that this is a false alarm, but I don't know how to prove that to myself. Thank you for the consideration, Mike On Mon, Oct 12, 2020, at 14:22, Dan Brown wrote: > > Hi Mike and CFRG list, > > Not sure where to draw line between false alarms and well-intentioned > concerns, since these can intersect, so I tried to understand Mike's > DLP attack strategy ... > > Somehow he aims to find bits, the 2^j, in the quotient of 2^X over P. > But there are nearly X/2 such bits, so finding them all would cost as > much as exhaustive search. > > (C.f. Polar rho method, taking sqrt(X) steps.) > > Likely misunderstood the proposed method, but am at least trying. > > > Sent with BlackBerry Work (www.blackberry.com) > *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://urldefense.proofpoint.com/v2/url?u=https-3A__www.irtf.org_mailman_listinfo_cfrg&d=DwICAg&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql-UonsW647lYqnsrbXizKI6MgkEw&m=tZVPiwvPHNhVOmq07mAv6dmVDQlZzwq_f8amSXXto_E&s=NyJBFGx6gbKbkDE1W9v4dZEZXff-kNCuzGyswktikEk&e= > This transmission (including any attachments) may contain confidential > information, privileged material (including material protected by the > solicitor-client or other applicable privileges), or constitute > non-public information. Any use of this information by anyone other > than the intended recipient is prohibited. If you have received this > transmission in error, please immediately reply to the sender and > delete this information from your system. Use, dissemination, > distribution, or reproduction of this transmission by unintended > recipients is not authorized and may be unlawful.

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