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

Anna Johnston <jannaston@gmail.com> Thu, 15 October 2020 20:00 UTC

Return-Path: <jannaston@gmail.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 35BFA3A0FD7
for <cfrg@ietfa.amsl.com>; Thu, 15 Oct 2020 13:00:13 -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, FREEMAIL_FROM=0.001,
SPF_HELO_NONE=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=gmail.com

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 Bad5Zsn4mtW8 for <cfrg@ietfa.amsl.com>;
Thu, 15 Oct 2020 13:00:11 -0700 (PDT)

Received: from mail-pl1-x632.google.com (mail-pl1-x632.google.com
[IPv6:2607:f8b0:4864:20::632])
(using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 78A823A0FD4
for <cfrg@irtf.org>; Thu, 15 Oct 2020 13:00:11 -0700 (PDT)

Received: by mail-pl1-x632.google.com with SMTP id b19so2222063pld.0
for <cfrg@irtf.org>; Thu, 15 Oct 2020 13:00:11 -0700 (PDT)

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:subject:from:in-reply-to:date:cc
:content-transfer-encoding:message-id:references:to;
bh=PVz4m56MM695kmwwMvn7cYVuB3LslzZpga5nHdL4/Nc=;
b=bWoR2TqVstxIx/ordBBbbwKovHb7C1pVbXaZtIHqJqCPYBzEXFm1N57QJ5b/6yBn7Z
5jTNnVFpIKdhL+GBYcDrOI2yPmkgd19yzXvVKK8BLXmUjah7deqGezIZ+78f3mqH+Zj2
zQGzoFB740J2vZjNGBWJUeK2qgEwf7yeWu3ggxFIkiXuoFAcLP1p7DQ+TVbzC1voQWan
YUQ7xgCs6yKG2tlmdSZ68+Th6I1ugl7cTpHi9nedlc6CojQC51jBF34ruJzDD1VwKU8l
TghPhiLSuNnZxGpH6ELspGeswYjvYAkAF+xd8exqmOpH4o34BwMTiVjKEVfervDhxXaB
0y2g==

X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc
:content-transfer-encoding:message-id:references:to;
bh=PVz4m56MM695kmwwMvn7cYVuB3LslzZpga5nHdL4/Nc=;
b=MelYkrCM8s8L8xYq6evT1tE4trbchvB4DNupGTTfM1C4ccAG057tVoJKCE3dafzSeK
hNyDIfPS7aTwPv2J/SZUgOi1b1S8scNdcVrkWP2EO/yZBk6xfa8qUZiRGCgPs6nK9HBD
z7XS+PiMZYMvYJt9po+u3oiseyLpgBNa5rdYIikgvB3GEp+WfZW3PINq6yxjTNCMK0Br
bvnI79Pbe2YE7RmOEig4+kJLO09c0WgJ7844W/uYIlwD4CKQDtGklpFvIhs9c23Gd0cG
RE4EPXW7nRPvk/mBIJUI7kW6e19mtYuHxPPLQ0K8SpUXzueAkx5kU8WrILu2p1cNk5ai
3V0A==

X-Gm-Message-State: AOAM530S3Hd9pDkwTsjKSNdpxvWK2z4aUmMoLUcUxW4C4S1GBCC4HHja
6L4rb0OZ3joR2rTsDhliwrE=

X-Google-Smtp-Source: ABdhPJzSoU1MJIR1ICD1q6J8hBz+LrKtjSzNsm15H5XElwmSv2XceTVCdDrRbCh7KgYsHuS/IulF0w==

X-Received: by 2002:a17:90a:d3d5:: with SMTP id
d21mr342746pjw.168.1602792010862;
Thu, 15 Oct 2020 13:00:10 -0700 (PDT)

Received: from amj-macbook-2.lan (c-73-180-23-16.hsd1.wa.comcast.net.
[73.180.23.16])
by smtp.gmail.com with ESMTPSA id kb15sm115562pjb.17.2020.10.15.13.00.09
(version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128);
Thu, 15 Oct 2020 13:00:09 -0700 (PDT)

Content-Type: text/plain;
charset=us-ascii

Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.120.23.2.4\))

From: Anna Johnston <jannaston@gmail.com>

In-Reply-To: <07090aa6-1bd1-4a37-810d-6cd95a6f1e7c@www.fastmail.com>

Date: Thu, 15 Oct 2020 13:00:09 -0700

Cc: cfrg@irtf.org

Content-Transfer-Encoding: quoted-printable

Message-Id: <ACF3D521-99D7-4A46-A3E6-2865FE53A816@gmail.com>

References: <07090aa6-1bd1-4a37-810d-6cd95a6f1e7c@www.fastmail.com>

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

X-Mailer: Apple Mail (2.3608.120.23.2.4)

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

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: Thu, 15 Oct 2020 20:00:13 -0000

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