Re: [TLS] DH generator 2 problem?

Dan Brown <danibrown@blackberry.com> Fri, 09 October 2020 17:11 UTC

Return-Path: <danibrown@blackberry.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 E4E9D3A0D1E; Fri, 9 Oct 2020 10:11:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.299
X-Spam-Level:
X-Spam-Status: No, score=-3.299 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-1.2, 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 (2048-bit key) header.d=blackberry.com
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 FODsxz9v9IEC; Fri, 9 Oct 2020 10:11:29 -0700 (PDT)
Received: from smtp-pc11.blackberry.com (smtp-pc11.blackberry.com [74.82.81.43]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6B57B3A0D21; Fri, 9 Oct 2020 10:11:27 -0700 (PDT)
Received: from pps.filterd (mhs401cnc.rim.net [127.0.0.1]) by mhs401cnc.rim.net (8.16.0.42/8.16.0.42) with SMTP id 099H9I0P061532; Fri, 9 Oct 2020 13:11:24 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blackberry.com; h=from : to : subject : date : message-id : references : in-reply-to : content-type : mime-version; s=corp19; bh=A96v2ZOysHJB0HGEi8LlwPkt+QFDRFiua27+HsQlSAg=; b=sHYYLzFyt9r1JcIkKM0bFah4TXnOa23vBzvhKd6OjVLCy8kMqv1lF4HrvIJMWYnHBHhC G9haaYxtRGaGZE+Aq035/Hjvb7ZylaB1Wuf40dlUewduKte4O20P+tf3RbuQ8iYBIg/4 BC0HabHOjB+0CGGBfulTBE8JKhC843nZ+NE7/qDXo1L520Tq7zkUCoppeMV4V7QGEoRL wvrxeHGbWLROPswhYdIjpG6rpW89YHeMYmGNjHIJ/KUwx8u/pc93wBMgQlGArtADV7ax b/4ZJRqdB45IZHTWokFY6GjVGwfHbSUIfe4Odk+xDbxc8iL8j/SKWrfl+WIbykfS5pCY QA==
Received: from xch212ykf.rim.net (xch212ykf.rim.net [10.2.27.112]) by mhs401cnc.rim.net with ESMTP id 3429jhhuq0-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT); Fri, 09 Oct 2020 13:11:24 -0400
Received: from XCH210YKF.rim.net (10.2.27.110) by XCH212YKF.rim.net (10.2.27.112) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2044.4; Fri, 9 Oct 2020 13:11:23 -0400
Received: from XCH210YKF.rim.net ([fe80::ac8d:3541:704c:478a]) by XCH210YKF.rim.net ([fe80::ac8d:3541:704c:478a%5]) with mapi id 15.01.2044.006; Fri, 9 Oct 2020 13:11:23 -0400
From: Dan Brown <danibrown@blackberry.com>
To: "Scott Fluhrer (sfluhrer)" <sfluhrer=40cisco.com@dmarc.ietf.org>, "Michael D'Errico" <mike-list@pobox.com>, TLS List <tls@ietf.org>
Thread-Topic: [TLS] DH generator 2 problem?
Thread-Index: AQHWnZwZhaKJlgLOrU+o5xOQwr3ljKmOVMEAgAElhkA=
Date: Fri, 9 Oct 2020 17:11:23 +0000
Message-ID: <3e7d6e2eccb149f592b49f39b135952d@blackberry.com>
References: <d876f953-2d5a-40a4-5738-b2bc24705f2c@pobox.com> <BN7PR11MB2641389E2A613A5B1DFBB176C10B0@BN7PR11MB2641.namprd11.prod.outlook.com>
In-Reply-To: <BN7PR11MB2641389E2A613A5B1DFBB176C10B0@BN7PR11MB2641.namprd11.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [100.64.197.184]
Content-Type: multipart/signed; micalg=2.16.840.1.101.3.4.2.1; protocol="application/x-pkcs7-signature"; boundary="----=_NextPart_000_00B6_01D69E3D.AEBBDF70"
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.235, 18.0.687 definitions=2020-10-09_09:2020-10-09, 2020-10-09 signatures=0
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/2hmVgw_brisBs_ZQncK7PHgN2TI>
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 17:11:32 -0000

Dear Michael,

Your concern that special primes in Diffie--Hellman might be weaker has some
truth: the famous and ingenious special number field sieve (SNFS) works
against primes with special structure.  See 
https://eprint.iacr.org/2016/961 
for a recent application (which, as an extra wrinkle, is also able to hide
the special structure). 

Therefore, applied cryptography like TLS already uses vetted primes in
Diffie--Hellman, with careful guidance from cryptographers such as those in
CFRG, which specialize in such fundamentals.  (Full disclosure: I proposed
some primes for DH to the CFRG list (for reductionist security), but never
followed through with an I-D.)

Scott explains below very well, as one'd expect, why the generator choice
should generally not matter (random self-reducibility).

Best regards,

Dan

> -----Original Message-----
> From: TLS <tls-bounces@ietf.org> On Behalf Of Scott Fluhrer (sfluhrer)
> Sent: Thursday, October 8, 2020 3:09 PM
> To: Michael D'Errico <mike-list@pobox.com>om>; TLS List <tls@ietf.org>
> Subject: Re: [TLS] DH generator 2 problem?
> 
> > -----Original Message-----
> > From: TLS <tls-bounces@ietf.org> On Behalf Of Michael D'Errico
> > Sent: Thursday, October 08, 2020 1:54 PM
> > To: TLS List <tls@ietf.org>
> > Subject: [TLS] DH generator 2 problem?
> >
> > 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.
> 
> No, that is known to be not true.
> 
> In particular, if you can compute discrete logs to the base 2, you can
compute
> discrete logs to any base (except in the cases where 2 generates an
> anomalously small subgroup, which is not the case in the above groups).
> 
> Here's how it works; suppose you were given the problem of solving the
> discrete log problem g^x = h, for some g, h.  Then, if you can solve
discrete logs
> to base 2, you would solve these two problems:
> 
> 2^y = g
> 2^z = h
> 
> Once you have solved those two problems, then you have x = y z^-1 mod p-1.
> 
> It's a little more complex if g, h is not in the subgroup that 2
generates, but not
> that much more (unless, as above, the size of that subgroup is far smaller
than
> p-1).
> 
> >
> > 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.
> 
> Actually, for these group, the value of 2^x mod p can take on (p-1)/2
different
> values; there is no chance that the bit pattern will be trapped in some
cul-de-
> sac, as you appear to be suggesting...
> 
> >
> > 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.
> 
> I would be surprised; do you have some reason that would suggest why bits
> derived from the binary expansion of 'e' would be somehow qualitatively
> different from bits derived from the binary expansion of 'pi'?
> 
> >
> > This is speculation of course.
> 
> Might I suggest you learn a bit of number theory to go along with your
> speculation?
> 
> >
> > Should we define some new DH parameters which use a different
> > generator?  Maybe the primes are fine....
> 
> If the prime is fine, so is the generator...

----------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.