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

Michael D'Errico <mike-list@pobox.com> Fri, 16 October 2020 02:23 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 27A253A0E98
for <cfrg@ietfa.amsl.com>; Thu, 15 Oct 2020 19:23:07 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -2.097

X-Spam-Level:

X-Spam-Status: No, score=-2.097 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_DNSWL_BLOCKED=0.001,
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=ZHkmtR6M;
dkim=pass (2048-bit key)
header.d=messagingengine.com header.b=MbKk59+x

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 RhVtjFR67QLk for <cfrg@ietfa.amsl.com>;
Thu, 15 Oct 2020 19:23:05 -0700 (PDT)

Received: from out4-smtp.messagingengine.com (out4-smtp.messagingengine.com
[66.111.4.28])
(using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id ED7273A0E93
for <cfrg@irtf.org>; Thu, 15 Oct 2020 19:23:04 -0700 (PDT)

Received: from compute4.internal (compute4.nyi.internal [10.202.2.44])
by mailout.nyi.internal (Postfix) with ESMTP id B11A15C00F4;
Thu, 15 Oct 2020 22:23:03 -0400 (EDT)

Received: from imap21 ([10.202.2.71])
by compute4.internal (MEProxy); Thu, 15 Oct 2020 22:23:03 -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:cc
:subject:content-type; s=fm1; bh=a6U90KpFVyM0pxNbbPHcQ7K3dxtaiqD
0apDlTo1ccWY=; b=ZHkmtR6MinCa7TyF4A+C9ywba8S8A5VE1hoSINP5HzvUaEG
vqizDyu7RvDrLKdYKvsk0NLhxqNSuNsGMYuXrRnY+Qs938Oo0aUfn0jWsuQsP0hR
JvF/AZ/IcbutzI9cxdTjd9Nb2gAwZopfOvPQTHwTXTSXR19AZjRjczHxi2hoFet5
aF0bP0LzmBsNKFrQeGIMg1SPNrSbOm69Hqe7W6uNYYpUJR64j2GZWP/7oh/oC5Dh
jvDfzUkt9LMlEr870DLRPVprWPbzmgtmdKh80YfsUdQkkT5UxPSSgfKJVoOoThGq
QHO+aWakW0wfQwMMK2e2YVmGc4cQdY4frZch+1Q==

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=
messagingengine.com; h=cc: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=a6U90K
pFVyM0pxNbbPHcQ7K3dxtaiqD0apDlTo1ccWY=; b=MbKk59+xLbSR41cSm6+n5Y
G6lkH/aQYl0CwV3MrwIWCL+PfcbEy5L3ztICKiwyAktKh1PR87y4InyPvtvfQK6e
vMcrEZEuAxh3TCV4IfolI8THL/6CDZx13uvLJD/Dhyo7E0fSfc2ix1pNnxrU3Rl4
OJ+ZvNAjs8PPRg1rA3vMX5Dbl8rmXRgqZx+TxfTgLmzaB7Mrrdx1fJUCjObTimzf
cAD1nD0hiQawULqHrTlCdOzRhlkaYfOXTFbSYdtwG1QFk3e7sTAv2YnukrsNxPq3
SPIRxIdPpZpR7dCh9hYVek4uU3d9qUIYR8QPw2a5UoWr9wXZcENVy0mf60rcqRDg
==

X-ME-Sender: <xms:BwSJX8euPVKK9FBQOf_Id9UtUeiBj9raydy1K-bhUs2unPq1xpi_qw>
<xme:BwSJX-NQtGgeZZgNypX5kjItbnTjU4tkFp9YwI1Mgq2nT2AE58LqD5_rmEJlzw81f
QG4vieOvM1Uhh4uag>

X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrieeggdehlecutefuodetggdotefrodftvf
curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu
uegrihhlohhuthemuceftddtnecunecujfgurhepofgfggfkjghffffhvffutgesthdtre
dtreertdenucfhrhhomhepfdfoihgthhgrvghlucffkdfgrhhrihgtohdfuceomhhikhgv
qdhlihhsthesphhosghogidrtghomheqnecuggftrfgrthhtvghrnhepteetueeuudefle
duuedtgfdtvdeivdetheeuueegtddulefgjedvgfefffeltedtnecuffhomhgrihhnpehi
rhhtfhdrohhrghenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfh
hrohhmpehmihhkvgdqlhhishhtsehpohgsohigrdgtohhm

X-ME-Proxy: <xmx:BwSJX9i6Fvh74hiAss2vwjJHGqx2F1_3HSGocifO_Bu0NB_yUMAG9w>
<xmx:BwSJXx8Kj-EbRbypEx9GpuGVBVqbk-GdzcFGzswe0BujXeb0E8mYJw>
<xmx:BwSJX4vt1v-tqsVbYxOctdYKJzfx-MI9Ir6n_ECpOdAm-bB3ydRU5Q>
<xmx:BwSJXx6dDpu6Hsn-aXf97OJjR8RGyUA8yNcUGSYLzEzKhach7mdKHw>

Received: by mailuser.nyi.internal (Postfix, from userid 501)
id 040B8660069; Thu, 15 Oct 2020 22:22:53 -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: <19672d78-77de-4744-b9d8-470a18dc3ac0@www.fastmail.com>

In-Reply-To: <ACF3D521-99D7-4A46-A3E6-2865FE53A816@gmail.com>

References: <07090aa6-1bd1-4a37-810d-6cd95a6f1e7c@www.fastmail.com>
<ACF3D521-99D7-4A46-A3E6-2865FE53A816@gmail.com>

Date: Thu, 15 Oct 2020 22:22:42 -0400

From: "Michael D'Errico" <mike-list@pobox.com>

To: "Anna Johnston" <jannaston@gmail.com>

Cc: cfrg@irtf.org

Content-Type: text/plain

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/qF1zsjiCHkn0JKRSobAKzLXwZAk>

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: Fri, 16 Oct 2020 02:23:07 -0000

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