Re: [Cfrg] Weak Diffie-Hellman Primes

Michael D'Errico <> Mon, 12 October 2020 18:43 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 4BC583A160F for <>; Mon, 12 Oct 2020 11:43:47 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.098
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: (amavisd-new); dkim=pass (2048-bit key) header.b=ZZiZ5Y+U; dkim=pass (2048-bit key) header.b=eqbTpVE4
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id tRPNGGUKNHay for <>; Mon, 12 Oct 2020 11:43:45 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 6744D3A160E for <>; Mon, 12 Oct 2020 11:43:45 -0700 (PDT)
Received: from compute4.internal (compute4.nyi.internal []) by mailout.nyi.internal (Postfix) with ESMTP id 0FE0F5C015B for <>; Mon, 12 Oct 2020 14:43:44 -0400 (EDT)
Received: from imap21 ([]) by compute4.internal (MEProxy); Mon, 12 Oct 2020 14:43:44 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; 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=; 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: Webmail Interface
User-Agent: Cyrus-JMAP/3.3.0-407-g461656c-fm-20201004.001-g461656c6
Mime-Version: 1.0
Message-Id: <>
In-Reply-To: <>
References: <> <>
Date: Mon, 12 Oct 2020 14:42:12 -0400
From: "Michael D'Errico" <>
Content-Type: text/plain;charset=utf-8
Content-Transfer-Encoding: quoted-printable
Archived-At: <>
Subject: Re: [Cfrg] Weak Diffie-Hellman Primes
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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,


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 (
> *From: *Michael D'Errico <>
> *Sent: *Oct 10, 2020 6:01 PM
> *To: *
> *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
> 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.