[TLS] DH generator 2 problem?

Michael D'Errico <mike-list@pobox.com> Thu, 08 October 2020 17:54 UTC

Return-Path: <mike-list@pobox.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id D8C543A0B97 for <tls@ietfa.amsl.com>; Thu, 8 Oct 2020 10:54:18 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Status: No, score=-2.099 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, 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 (1024-bit key) header.d=pobox.com; domainkeys=pass (1024-bit key) header.from=mike-list@pobox.com header.d=pobox.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id bj4B5gn4GTiW for <tls@ietfa.amsl.com>; Thu, 8 Oct 2020 10:54:17 -0700 (PDT)
Received: from pb-smtp20.pobox.com (pb-smtp20.pobox.com []) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C767B3A0B96 for <tls@ietf.org>; Thu, 8 Oct 2020 10:54:17 -0700 (PDT)
Received: from pb-smtp20.pobox.com (unknown []) by pb-smtp20.pobox.com (Postfix) with ESMTP id 58624F6FC4 for <tls@ietf.org>; Thu, 8 Oct 2020 13:54:16 -0400 (EDT) (envelope-from mike-list@pobox.com)
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=to:from :subject:message-id:date:mime-version:content-type :content-transfer-encoding; s=sasl; bh=xAOb0Nszpu68/gzd0KiLaAtqt hc=; b=Peb8WGtWBVsilNh54zo+zp1ynTRrMWWcqJvkrUX4IOodP8ANhNzOherCM SiYrI11qk/IjTWcp3Q0Cw1NhNU0ACnoaRt4wgrzKmMUIc+j9Bwnx7aR/kGtWfmD3 G91sWoGBMxjjxnq6Y+tYH3eJloGV33KbvFxqxnMPs6L7XsuOOQ=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=to:from:subject :message-id:date:mime-version:content-type :content-transfer-encoding; q=dns; s=sasl; b=Dn6B1didpL3ezUoDy6z 0XHGMDnV6nUMWvmIa04yFxER2OV+rB9r5SyEVTMYz2N2D2ax620/sCooRDU8RGIp YEEA68FAtGGgri704ESxVsXmEbY+zWMv2sINR2fIGMeInwqjxuCGsdjY/MYspsUb CJeFz84bTL1FftD7MZDK2s6E=
Received: from pb-smtp20.sea.icgroup.com (unknown []) by pb-smtp20.pobox.com (Postfix) with ESMTP id 52175F6FC3 for <tls@ietf.org>; Thu, 8 Oct 2020 13:54:16 -0400 (EDT) (envelope-from mike-list@pobox.com)
Received: from MacBookPro.local (unknown []) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by pb-smtp20.pobox.com (Postfix) with ESMTPSA id 50609F6FBF for <tls@ietf.org>; Thu, 8 Oct 2020 13:54:13 -0400 (EDT) (envelope-from mike-list@pobox.com)
To: TLS List <tls@ietf.org>
From: Michael D'Errico <mike-list@pobox.com>
Message-ID: <d876f953-2d5a-40a4-5738-b2bc24705f2c@pobox.com>
Date: Thu, 08 Oct 2020 13:54:10 -0400
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.13; rv:68.0) Gecko/20100101 Thunderbird/68.12.1
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"; format="flowed"
Content-Language: en-US
Content-Transfer-Encoding: 7bit
X-Pobox-Relay-ID: 469908CE-098F-11EB-BC8A-E43E2BB96649-38729857!pb-smtp20.pobox.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/euFTrTCRY5Hki1N4DIXe_165QqQ>
Subject: [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: Thu, 08 Oct 2020 17:54:19 -0000

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