[Cfrg] Weak Diffie-Hellman Primes

Michael D'Errico <mike-list@pobox.com> Sat, 10 October 2020 22:01 UTC

Return-Path: <mike-list@pobox.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 68BF83A09A8 for <cfrg@ietfa.amsl.com>; Sat, 10 Oct 2020 15:01:35 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.101
X-Spam-Status: No, score=-2.101 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_H2=-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=OEdKQqLH; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=rIBJELsY
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id mhWFX-kYqtHB for <cfrg@ietfa.amsl.com>; Sat, 10 Oct 2020 15:01:34 -0700 (PDT)
Received: from wout5-smtp.messagingengine.com (wout5-smtp.messagingengine.com []) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 01E983A09A3 for <cfrg@irtf.org>; Sat, 10 Oct 2020 15:01:33 -0700 (PDT)
Received: from compute4.internal (compute4.nyi.internal []) by mailout.west.internal (Postfix) with ESMTP id 3BA04466 for <cfrg@irtf.org>; Sat, 10 Oct 2020 18:01:32 -0400 (EDT)
Received: from imap21 ([]) by compute4.internal (MEProxy); Sat, 10 Oct 2020 18:01:32 -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=HJP+3mFnwWv75fHexGxhQI6lfE2rUbVlvZKp7v45CTw=; b=OEdKQqLH KQmTMYLF7D85gNEN44YVL626V3L0Wy6FqFCx2MiJdg7zVYTeDH/zv7qDMt1O3U8s kCAIMRjrn4+RpZK3t3t1tG5zvCQjWHkQZjn4QM0rku8n0Q0o2UeElrXbFZ7EVsYJ a4nwd4cUsO6Ohlxz2vp283/yYDkegCkAC7QTmPFOYwYH2DOEsPrU8z2XAkP1R17q N6S09h6xohKjP49+Gqagr3pJWkb84PaLJEzdKtXW+Y+gItOtIZZ9K1rFw7Jd2VP2 BljYe7kgAzM/pwIgX9NVIP3ab1xq0lUdXA7mg9wB3ykEsleILsGEcoNZ8i9GuSmR mv+yw07wG8O+pw==
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=HJP+3mFnwWv75fHexGxhQI6lfE2rU bVlvZKp7v45CTw=; b=rIBJELsYHM5IHpgj6O1xIG8OfHgLzWqJO3csfVY2ffubK BLCo4oGO8zuVHtrPJB8oedTXlTM7vc/C7qjG0FewbiV10rGVeb+W6pArEul5AGhe p/uC0n2xTV1y1uk+gZprIpSGtt0VXDBicSEFiP+bR3GFrpRwELwhyvPX3ZIyZzDo NR8Ipkjp9a/vKER0RKs8/FWu8OnyUfrVUamA32267O3+BtJZQNN9z4cdmsp+3NcK DNwgFcJQDUQbXgB6CPvUZqBAP3RBGTbbHgdbBOIODYlt85QlZuZX/4zCeFtfrtFd 72LF7HYV5ZEfj/LzPnXU7xCaF551cRU6s3TpmpTLg==
X-ME-Sender: <xms:Oy-CX7mx37iFL6JoG9Tas56sqhWmKMeUFniEOk3BC_FsYyTzyFcUVw> <xme:Oy-CX-39bD2b-_V-jBw2yKBDJLOvc7Ocuyxd4lYdHIlL8eKRBh68IGXQVqGylCKE8 c7-v-74Dxztxxq-TQ>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrheefgdduieekucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfffhffvufgtsehttdertd erredtnecuhfhrohhmpedfofhitghhrggvlhcuffdkgfhrrhhitghofdcuoehmihhkvgdq lhhishhtsehpohgsohigrdgtohhmqeenucggtffrrghtthgvrhhnpeethffgtddvieetle ehueevheduhfdtudeuueeikeeiheehfeefvdfgudffkeelieenucevlhhushhtvghrufhi iigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehmihhkvgdqlhhishhtsehpohgsoh igrdgtohhm
X-ME-Proxy: <xmx:Oy-CXxpkZ6dRnXLw7UAwbo2AC9jCITXGfDxtX7o7Dl0gkD0hiZcBBg> <xmx:Oy-CXzln0EMmr2gnJmCO2mN6TpGfpBytwf6MVbEbv1WTRuca5ufiiw> <xmx:Oy-CX53tSO9xcyMPsM7VjD6BwwMg6uIK94vrfn7BFQ3iS5RuL4k8Nw> <xmx:Oy-CX6A6RedCO1cXPkUh0GayqUoY3muAFxib9Y5y-0CiueO99pO-dA>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 75ADA660069; Sat, 10 Oct 2020 18:01:22 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.3.0-407-g461656c-fm-20201004.001-g461656c6
Mime-Version: 1.0
Message-Id: <0a24076e-3227-405c-84d4-26d82b5ff783@www.fastmail.com>
Date: Sat, 10 Oct 2020 18:01:11 -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/uFBQhngHLde2X5Q7viWvXhbkyuc>
Subject: [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: Sat, 10 Oct 2020 22:01:35 -0000


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.