### Re: [TLS] DH generator 2 problem?

Michael D'Errico <mike-list@pobox.com> Fri, 09 October 2020 12:36 UTC

Return-Path: <mike-list@pobox.com>

X-Original-To: tls@ietfa.amsl.com

Delivered-To: tls@ietfa.amsl.com

Received: from localhost (localhost [127.0.0.1])
by ietfa.amsl.com (Postfix) with ESMTP id 4999A3A0EF4
for <tls@ietfa.amsl.com>; Fri, 9 Oct 2020 05:36:42 -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=jOg0VAKf;
dkim=pass (2048-bit key)
header.d=messagingengine.com header.b=H7YxCy1T

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 uPwc0_ZOt42z for <tls@ietfa.amsl.com>;
Fri, 9 Oct 2020 05:36:40 -0700 (PDT)

Received: from wout4-smtp.messagingengine.com (wout4-smtp.messagingengine.com
[64.147.123.20])
(using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 694F93A0EF3
for <tls@ietf.org>; Fri, 9 Oct 2020 05:36:39 -0700 (PDT)

Received: from compute4.internal (compute4.nyi.internal [10.202.2.44])
by mailout.west.internal (Postfix) with ESMTP id 949709E2
for <tls@ietf.org>; Fri, 9 Oct 2020 08:36:38 -0400 (EDT)

Received: from imap21 ([10.202.2.71])
by compute4.internal (MEProxy); Fri, 09 Oct 2020 08:36:38 -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
:subject:content-type; s=fm1; bh=p7bPXduSoBmv6/EQt+LpGR/gMs0jpR9
BFHetGT3uNtk=; b=jOg0VAKf8srD4Mx9Ig72sNCP74961v/uAuS1j9S5LMf6sS8
kikCOLsguWZ/kXdBAecW2CgiTs+TgyBvkQY5nZen1/WIHOsuvC4n3w12wgB18JnV
ZF19KKa4lYJmEz5LmvYNHdl7xOMxm4+JB0NBtPmEWX/bguj5Ut6Hm/1OhFA3Tl1E
knA3fW4Hh6JxD3YOGzkOayr2Bb0czJ7ogIuvj1ltTAiV1PnDzLfrpF9Ctv0/hAp0
DNWTK7hAbSy3Ol6U4xrbk3ksYdv0MUH4C5CehD5K4hcwuOG9l9lSEi0dCKXT1s3F
wvr2dN10NZE1dv05IH++03VwoyDV/lyWdfjwhug==

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=
messagingengine.com; h=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=p7bPXd
uSoBmv6/EQt+LpGR/gMs0jpR9BFHetGT3uNtk=; b=H7YxCy1T8Os37OlgTH7n9V
as0yxABRDinkvvQJhXXtl7whGZIZ7dZS3zz7YKBomvQJcyoeZGXgbJ5TQDn46v/N
i2NBBIAOeO0MVObQW1b2EKp9ynDa0w3ZwaE89OK6a1KHz7FAVWt+H2jNhiREMNL6
uFLYs5Quyc5LGIiH80T10FW2PYrnrLnNh+saUtgOG9UxPWzJqU80ir+mqqA1dj+y
1d4oZMHjxRDx5LY0flHectD3DpviGVRdPzDVMf3PEJR4uDc3oWRkf7y62ys0SHYP
+SGAv0A7E3GOer35kb2BknfJFqyo1EfvJlteJpKknOy8SvZ0/iSjP+0py2FUJqfg
==

X-ME-Sender: <xms:VVmAXyT-qZGjh5JvSPr3rrcZEfduHFnE4hcs72o9vNebYwPBPbiXPg>
<xme:VVmAX3yp24hxbZlVQie0-a4xFOxWXX-j9tKUHej2OWReTLhHTBgOUnFfdqe4hjNy3
aa7NSLGUfGLhyC3pQ>

X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrhedugdehhecutefuodetggdotefrodftvf
curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu
uegrihhlohhuthemuceftddtnecunecujfgurhepofgfggfkjghffffhvffutgesthdtre
dtreertdenucfhrhhomhepfdfoihgthhgrvghlucffkdfgrhhrihgtohdfuceomhhikhgv
qdhlihhsthesphhosghogidrtghomheqnecuggftrfgrthhtvghrnhepieejueegheelgf
ehtddvueetteefuefgffdvkeehteeutdekffejtedtiefggfdtnecuvehluhhsthgvrhfu
ihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepmhhikhgvqdhlihhsthesphhosg
hogidrtghomh

X-ME-Proxy: <xmx:VVmAX_3pfF2s1AVc4W-4p42Rg-2lVhsgQqg_A0ygQT5RYBbJQBmieQ>
<xmx:VVmAX-BaiGh9dXAid8XpJ0yrBJV6QVpuR9zq4I1yStuwCNJD2QBPCQ>
<xmx:VVmAX7i1d0ajqomy7KyMRv6O4v-8R5fgRrg5C41kaoMKzsFBq0p84Q>
<xmx:VlmAX2uJRv8UkODi8EBEtmRUAhaoCD6XCErpnDJevkKIr5GaEsRk8A>

Received: by mailuser.nyi.internal (Postfix, from userid 501)
id 172AC66006F; Fri, 9 Oct 2020 08:36:29 -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: <dd15bfa7-f5d7-47c3-9ce8-caf6a445fdce@www.fastmail.com>

In-Reply-To: <d876f953-2d5a-40a4-5738-b2bc24705f2c@pobox.com>

References: <d876f953-2d5a-40a4-5738-b2bc24705f2c@pobox.com>

Date: Fri, 09 Oct 2020 08:35:45 -0400

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

To: "TLS List" <tls@ietf.org>

Content-Type: text/plain

Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/k2_7aOPoqK8u0jWpgDx6YOqNtMc>

Subject: Re: [TLS] DH generator 2 problem?

X-BeenThere: tls@ietf.org

X-Mailman-Version: 2.1.29

Precedence: list

List-Id: "This is the mailing list for the Transport Layer Security working
group of the IETF." <tls.ietf.org>

List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>,
<mailto:tls-request@ietf.org?subject=unsubscribe>

List-Archive: <https://mailarchive.ietf.org/arch/browse/tls/>

List-Post: <mailto:tls@ietf.org>

List-Help: <mailto:tls-request@ietf.org?subject=help>

List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>,
<mailto:tls-request@ietf.org?subject=subscribe>

X-List-Received-Date: Fri, 09 Oct 2020 12:36:42 -0000

I have not written any code, but have just been thinking about what is going on and I am pretty sure that the bottom 64 bits of 2^X mod P tell you information which can help you determine X. The top bits are also suspect but I haven't worried about those yet. My original message below explains which primes I'm talking about. They all have a solid block of 64 bits with value one in both the uppermost and bottom-most bit positions. This construction seems to make the primes a very bad choice for use with a Diffie-Hellman key exchange. If you think about how a modulo operation takes place (the long way, one bit position at a time), you compare the operand to (a shifted version of) P and if it's bigger you subtract P and shift P one bit to the right. If the operand is not bigger than P, you just shift P one bit to the right without doing a subtraction. Due to the construction of all of the primes in the RFCs cited below, you will get a trace of this in the bottom 64 bits. There will be a one whenever a subtraction occurred and a zero otherwise. This is because if you calculate the two's complement of the prime (followed by a bunch of zeros), there will be a lone 1 preceded by at least 63 zeros. Instead of subtracting, you can add this two's complement number, so a 1 will be placed wherever a subtraction happened or a 0 if there was no subtraction. I've not worked out how to use these 64 bits to then reconstruct X, but this seems like it was purposeful so I'm fairly certain it reduces the complexity of determining X from 2^X mod P. (In fact, there may be a use for more than just 64 of the bottom bits.) A private discussion I had seems to indicate that these particular primes would be bad even with a different generator (because number theory). I am hopeful that it's possible to construct better primes which are more secure than these (even using a generator of 2) for use with Diffie-Hellman. Mike On Thu, Oct 8, 2020, at 13:54, I wrote: > Using finite-field Diffie-Hellman with a generator > of 2 is probably not the best choice. Unfortunately > all of the published primes (RFCs 2409, 3526, and > 7919) use 2 for the generator. Any other generator > would likely be (not sure how much?) more secure. > > The problem is that 2^X consists of a single bit of > value 1 followed by a huge string of zeros. When > you then reduce this modulo a large prime number, > there will be a pattern in the bits which may help > an attacker discern the value of X. This is further > helped by the fact that all of the published primes > have 64 bits of 1 in the topmost and bottom-most bits. > In addition, the larger published primes are very > similar to the shorter ones, the shorter ones closely > matching truncated versions of the larger primes. > > If you were to manually perform the modulo-P operation > yourself, you would add enough zeros to the end of P > until the topmost bit is just to the right of the 1 > bit from 2^X, and then you'd subtract. This bit > pattern will always be the same, no matter the value > of X. In particular, the top 64 bits disappear since > they're all one. Continuing the mod-P operation, you > adjust the number of zeros after the prime P and then > subtract again, reducing the size of the operand. The > pattern of bits again will be the same, regardless of > the value of X, the only difference being the number > of trailing zeros. > > I have not looked at the cyclic patterns which happen > as you do this, but I wouldn't be surprised to find > that the "new" primes based on e (RFC 7919) have > easier-to-spot bit patterns than those based on pi. > > This is speculation of course. > > Should we define some new DH parameters which use a > different generator? Maybe the primes are fine.... > > Mike

- [TLS] DH generator 2 problem? Michael D'Errico
- Re: [TLS] DH generator 2 problem? Salz, Rich
- Re: [TLS] DH generator 2 problem? Scott Fluhrer (sfluhrer)
- Re: [TLS] DH generator 2 problem? Michael D'Errico
- Re: [TLS] DH generator 2 problem? Michael D'Errico
- Re: [TLS] DH generator 2 problem? Watson Ladd
- Re: [TLS] DH generator 2 problem? Michael D'Errico
- Re: [TLS] DH generator 2 problem? Christopher Wood
- Re: [TLS] DH generator 2 problem? Dan Brown
- Re: [TLS] DH generator 2 problem? Michael D'Errico
- [TLS] Weak Diffie-Hellman Primes (was: DH generatâ€¦ Michael D'Errico