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.