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