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

Michael D'Errico <mike-list@pobox.com> Thu, 15 October 2020 16:16 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 49D943A08C5
for <cfrg@ietfa.amsl.com>; Thu, 15 Oct 2020 09:16:09 -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=jknK0hfI;
dkim=pass (2048-bit key)
header.d=messagingengine.com header.b=eDzXE2Tu

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 Q6sJ93_SXBTl for <cfrg@ietfa.amsl.com>;
Thu, 15 Oct 2020 09:16:06 -0700 (PDT)

Received: from wout2-smtp.messagingengine.com (wout2-smtp.messagingengine.com
[64.147.123.25])
(using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 3BC463A08C1
for <cfrg@irtf.org>; Thu, 15 Oct 2020 09:16:05 -0700 (PDT)

Received: from compute4.internal (compute4.nyi.internal [10.202.2.44])
by mailout.west.internal (Postfix) with ESMTP id 34EF6B4C
for <cfrg@irtf.org>; Thu, 15 Oct 2020 12:16:05 -0400 (EDT)

Received: from imap21 ([10.202.2.71])
by compute4.internal (MEProxy); Thu, 15 Oct 2020 12:16:05 -0400

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pobox.com; h=
mime-version:message-id:date:from:to:subject:content-type; s=
fm1; bh=aWk85OSPftEGGkQhe4BDXiOBmByfcTU1gc1RSYCOgqk=; b=jknK0hfI
eTgzDeS5kTefmJzK4e7XlPv7BWwkXRzY+FHm4eikAAZYHoRjpnYi7jiSNIbhAYNP
g0Ab3N9wSbeF89tiyWWw0I6YStvNtAXjFqYbB4j0qSbJ/R9etrkRFfgmgXlIt6zY
JThgiPjojbSoH8VR98jqbNFWrfxbKSU0/v9NX8GbEKjO6X/BjuS1aPJlP/4NdJL6
pszAATRM8z4XvnBlF4j/232FwQ2n5nIVIIo2MC6wsr5m01NblRvbHcULCHrKBKAp
Tl0X/AFwZUhOEMwvoc51zGn4ZLtMPpi71rJmDbTuyTlYP8It2dB61gAvLCiR4n+J
c9au8ZDFVGwyCA==

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=
messagingengine.com; h=content-type:date:from:message-id
:mime-version:subject:to:x-me-proxy:x-me-proxy:x-me-sender
:x-me-sender:x-sasl-enc; s=fm1; bh=aWk85OSPftEGGkQhe4BDXiOBmByfc
TU1gc1RSYCOgqk=; b=eDzXE2TujBqdvP+vxwjafX5aTHIYHpqa1plUegIvNy4AS
A5P9CyTuiOA38S0e9zt/h21pWuN/STJvAUUAH/TtUgO2pevwgqCwNkH66Z9YIJyA
Xk5C7kGq4MBab5RnmP4BAeRJ/JQmiBPQFW/oE4fBU0Liv+9jTJF9EMBMqwqyUdua
2Ugl36wPJKu7Syu1/3Of0uL54tkqaZEOvja6xYrRwoQuLCEXkLL7+bP9WSRnVL+/
pMGpTmis9cEK7sOYW99n2dNvkK+O0u66hOyp5IrDY/JLmv0FbHkjQwVJLK4XBi/o
059QLkjUP6I9QS6ET64vh056Ak0X/ir7SAhEqhVnA==

X-ME-Sender: <xms:xHWIX1cdCth67fzHWKjTX664eOgtW2rIa-_t03wo5034y3OniG3ifg>
<xme:xHWIXzPE1Nim9hX9JzcIhQjfijXj26BulK9kFkJBdO0EG9Mra387i9X9cermo-ju9
451SxOd3zufYDD-TQ>

X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrieefgdeljecutefuodetggdotefrodftvf
curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu
uegrihhlohhuthemuceftddtnecunecujfgurhepofgfggfkfffhvffutgesthdtredtre
ertdenucfhrhhomhepfdfoihgthhgrvghlucffkdfgrhhrihgtohdfuceomhhikhgvqdhl
ihhsthesphhosghogidrtghomheqnecuggftrfgrthhtvghrnheptefhgfdtvdeiteelhe
euveehudfhtdduueeuieekieehheeffedvgfduffekleeinecuvehluhhsthgvrhfuihii
vgeptdenucfrrghrrghmpehmrghilhhfrhhomhepmhhikhgvqdhlihhsthesphhosghogi
drtghomh

X-ME-Proxy: <xmx:xHWIX-izQYs72L5KvjAl_gRvKDReE2IB70DPBMUUdxWSv7RjFljwRg>
<xmx:xHWIX-91X6H7i6W85RQglIE7GEPOtH1T1T_IxzPqJJU4H-popWpTrg>
<xmx:xHWIXxu1MbD6-FxwMlFA-q6jswZD_a-ZRwlEYvxgkWjh6nNsSfjDPA>
<xmx:xHWIX_47avS9RPDMXVk2WOVjhSspOnEyZ1hbfaM97rTO1F_D646uXQ>

Received: by mailuser.nyi.internal (Postfix, from userid 501)
id 1B988660069; Thu, 15 Oct 2020 12:15:55 -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: <07090aa6-1bd1-4a37-810d-6cd95a6f1e7c@www.fastmail.com>

Date: Thu, 15 Oct 2020 12:15:43 -0400

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

To: cfrg@irtf.org

Content-Type: text/plain

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/HPOlwUE8ho-NJvooR-Ky4n2drEs>

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 16:16:09 -0000

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