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