Re: [TLS] DH generator 2 problem?

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Thu, 08 October 2020 19:08 UTC

Return-Path: <sfluhrer@cisco.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 350A23A0C45 for <tls@ietfa.amsl.com>; Thu, 8 Oct 2020 12:08:58 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -9.598
X-Spam-Level:
X-Spam-Status: No, score=-9.598 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, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cisco.com header.b=Atw75lQV; dkim=pass (1024-bit key) header.d=cisco.onmicrosoft.com header.b=imL0M7IH
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 hPYowJjm5CfJ for <tls@ietfa.amsl.com>; Thu, 8 Oct 2020 12:08:56 -0700 (PDT)
Received: from alln-iport-7.cisco.com (alln-iport-7.cisco.com [173.37.142.94]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 21FBB3A0C2D for <tls@ietf.org>; Thu, 8 Oct 2020 12:08:56 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=3420; q=dns/txt; s=iport; t=1602184136; x=1603393736; h=from:to:subject:date:message-id:references:in-reply-to: content-transfer-encoding:mime-version; bh=eoDy580PpghzV5Wtd59F/ckKk0xFbpyZE01ooAOFjoc=; b=Atw75lQVY2e0i3XMIuWiGbeN/MsnQGUWbhy7za6fyKumGgBCHAHZvCkB P9nBvmQuJFCC4jAkV+GnP/AFNjlALVeS0Ar4P4CQcJMXnUmxRLHQX/q0R gAD6tngqKcU5U37KhS26Dcs7AWYOaU5gsszNQoP7JlasncWX7Mn49ws6O c=;
IronPort-PHdr: =?us-ascii?q?9a23=3AbCVPpRUthZEDuoa4LLCd5mLF3nvV8LGuZFwc94?= =?us-ascii?q?YnhrRSc6+q45XlOgnF6O5wiEPSBNyHuepDge3G9avnXD9I7ZWAtSUEd5pBH1?= =?us-ascii?q?8AhN4NlgMtSMiCFQXgLfHsYiB7eaYKVFJs83yhd0QAHsH4ag7KpXe1/XgZHR?= =?us-ascii?q?CsfQZwL/7+T4jVicn/3uuu+prVNgNPgjf1Yb57IBis6wvLscxDiop5IaF3wR?= =?us-ascii?q?zM8XY=3D?=
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0D8CACMYn9f/5ldJa1gHgE8DAILFYF?= =?us-ascii?q?PgVJRB4FJLywKh3kDjVKYe4JTA1ULAQEBDQEBLQIEAQGESgKCCgIlNwYOAgM?= =?us-ascii?q?BAQsBAQUBAQECAQYEbYVcDIVyAQEBAQIBEigGAQE4CwQCAQgRBAEBHxAyHQg?= =?us-ascii?q?CBAESCBqFUAMOIAGeJAKBOYhhdIE0gwEBAQWFHxiCEAmBOIJyhjGEEhuBQT+?= =?us-ascii?q?BVIJNPoQ/g0iCLbddCoJomwmhMJMboB0CBAIEBQIOAQEFgWokgVdwFTuCaVA?= =?us-ascii?q?XAg2SEIpWdDcCBgoBAQMJfIw7AYEQAQE?=
X-IronPort-AV: E=Sophos;i="5.77,351,1596499200"; d="scan'208";a="557548825"
Received: from rcdn-core-2.cisco.com ([173.37.93.153]) by alln-iport-7.cisco.com with ESMTP/TLS/DHE-RSA-SEED-SHA; 08 Oct 2020 19:08:55 +0000
Received: from XCH-ALN-001.cisco.com (xch-aln-001.cisco.com [173.36.7.11]) by rcdn-core-2.cisco.com (8.15.2/8.15.2) with ESMTPS id 098J8sPT009698 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=FAIL); Thu, 8 Oct 2020 19:08:54 GMT
Received: from xhs-aln-003.cisco.com (173.37.135.120) by XCH-ALN-001.cisco.com (173.36.7.11) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Thu, 8 Oct 2020 14:08:54 -0500
Received: from xhs-aln-002.cisco.com (173.37.135.119) by xhs-aln-003.cisco.com (173.37.135.120) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Thu, 8 Oct 2020 14:08:54 -0500
Received: from NAM04-SN1-obe.outbound.protection.outlook.com (173.37.151.57) by xhs-aln-002.cisco.com (173.37.135.119) with Microsoft SMTP Server (TLS) id 15.0.1497.2 via Frontend Transport; Thu, 8 Oct 2020 14:08:54 -0500
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=oRcmPMcd1WJVbwKxdoeOblMLtb5ZNGJlbJkR2+GqjCGrGcva9UPNE54I5Ie4Gtdzr+DybnFahM8fGMgB437C5C5Hpfop5csKM16SRlnEhUrU9e8TS+jKuJ1cex/IfcHbagnG6xz1cMQAo8hAzMrjp3ZVvYfW75WCEbJwimMd5VFV6Hgbc9pDhSBa8uT0HmDqfneLYhV5XaJSGk6GK+btb/l1ARuTARwNRcCQYyzaERWwKWTktdEIvqsujh8s3YEumgre5Vz3Q5PV35ZmuHKmoud7obi5/v9kPQBFDPnIHVhqQZxwJ2gumpimHp4ImehGqltaUkZzt9ZO4d8NUigrmQ==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=DBdJZCVS/ZaZCjvmJ6UQGjPEcmsRrbeDag+sewYaYZY=; b=I7KnkQr0EAmceEEMUAhTU0gJkyKLMeUeYTX/DGpbql2dbArY4yTPEHlgqnWkegNmuh89zOjhMsSaqjjADSXkkCTVhSfqbYg0f4QV8syZLxPirA2Unc3s291Oe6X7NDFV2cGlmTOQqr8duAlpMjZ7f48wbQ8+YYjvwurptaub2A9N6BUicYgACRoNkP1f9bC0weTACecIT3T9l/r8pL0Pg00DQHDavGSr9ByxLKAy7zPxwNJoEWALQqg4u/QsZJB22UN0OjOUOgcyf35iY4swVuJEGZWVDtF38p6vodmpWsZbEGn+BA3BrcfBcjeBgempWM5IFNSAEJQRFpQx0u0HBg==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=cisco.com; dmarc=pass action=none header.from=cisco.com; dkim=pass header.d=cisco.com; arc=none
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cisco.onmicrosoft.com; s=selector2-cisco-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=DBdJZCVS/ZaZCjvmJ6UQGjPEcmsRrbeDag+sewYaYZY=; b=imL0M7IHSQ0VuSTFyhLxIpEUi9sYpzAESjauuxQ4T8WD9q0Q5WZH78aLChsQSPCXPlrr41ET9rDSHcd6HuWr+AUNB40zeWeSmP425STZdNGEW9ZwB79aeFiwfBvVP5YxGppkFRd704k/LknEjTpagxEHcTXyWX21gF1ugobNc48=
Received: from BN7PR11MB2641.namprd11.prod.outlook.com (2603:10b6:406:b1::25) by BN6PR1101MB2274.namprd11.prod.outlook.com (2603:10b6:405:4d::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3433.38; Thu, 8 Oct 2020 19:08:53 +0000
Received: from BN7PR11MB2641.namprd11.prod.outlook.com ([fe80::8d1c:3090:bf65:2372]) by BN7PR11MB2641.namprd11.prod.outlook.com ([fe80::8d1c:3090:bf65:2372%7]) with mapi id 15.20.3455.022; Thu, 8 Oct 2020 19:08:53 +0000
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: "Michael D'Errico" <mike-list@pobox.com>, TLS List <tls@ietf.org>
Thread-Topic: [TLS] DH generator 2 problem?
Thread-Index: AQHWnZwY6NYWk8rhvU+q9JqNqZTbsqmODBlg
Date: Thu, 8 Oct 2020 19:08:52 +0000
Message-ID: <BN7PR11MB2641389E2A613A5B1DFBB176C10B0@BN7PR11MB2641.namprd11.prod.outlook.com>
References: <d876f953-2d5a-40a4-5738-b2bc24705f2c@pobox.com>
In-Reply-To: <d876f953-2d5a-40a4-5738-b2bc24705f2c@pobox.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: pobox.com; dkim=none (message not signed) header.d=none;pobox.com; dmarc=none action=none header.from=cisco.com;
x-originating-ip: [173.38.117.82]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 81b8e8a6-edb7-4d0c-c028-08d86bbd98db
x-ms-traffictypediagnostic: BN6PR1101MB2274:
x-microsoft-antispam-prvs: <BN6PR1101MB227431E4C3B813C16A2C436BC10B0@BN6PR1101MB2274.namprd11.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: f/48PR6qrX6OALf/lmMoyggWC1cV0ZTP7PVxC75OkKDxwaygEvjS/QmJH9nc3gaH7MZ/qIO14qsGd3dkDgj/qDwca5ShLPWdnaT0D1weMYKcAh41CIo9db184lenUw1SIQJZddIrqxjJ/L5ac+zU0K3uT4fVNlK8qPD84AN9mh3wjHhXkNI6OzY/dBHc0EC5OWbqptm1NbkHucCH/9flvEb+0tWjqgDenbnLR0bCAlq8bTDjwePTIjMgsCrhivTwbTW58186Ctn6GeTe/GifHMFkQmxXO8H7aH0qBLNOTQR7CljVn3eLn2784RuyP7UQ0tdSSHOM67xWq+9JGg65GA==
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:BN7PR11MB2641.namprd11.prod.outlook.com; PTR:; CAT:NONE; SFS:(136003)(366004)(39860400002)(346002)(396003)(376002)(55016002)(110136005)(186003)(64756008)(83380400001)(66476007)(26005)(53546011)(9686003)(8676002)(2906002)(71200400001)(66446008)(86362001)(66946007)(66556008)(8936002)(7696005)(478600001)(316002)(52536014)(76116006)(6506007)(5660300002)(33656002); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: hRojN4AHch5SYNfU8j+B7guBqv6g1pDyZFzC7n07vBQP3IQdL3kxDW7DGSQGNkoWAiQAg7rUmUyb9fgDbN6ytN7E1DQRNmTtnp9R1Tr/kmLdF6rBPMaVevMInCa4gvyIr5u2h1vfMiNYTabXsomUvsPAla3SQdyyLCJ+MXjg+o1lCX7MRhMXvWh6iFdb0BBYFw7NnY6bddfC6cNvs7GONz29wkd6SBmdVD2Z08ritsNbNDqmScG/alPiVw6DZwOQQDdHqn34+EJ0Ze2i9WW32I+wIbSgN8i6IN1xRU3mbhSAqKVsN4qRwqaSGJ5u/9mrZKhjRqhsXydWNHYbVFBB5TwjtLfDm/cSn0m2Jsv+dDabz4C9q3bGXUffsIfrzwAWv+x0sFGW2UArm4fL9wn33KT4IiEQjsvGDgHqsxRsK3VvXurKzp9nCm7ycaaJIX1Ge83w5bCC6HBbIl88XenFRTQw7IWX01lMLBND6pUMGwLwLWCiuwQXpTRmpHmghZBRUUhTJWy5WGBBKLB1/2Hwa+/ufQWCKujc1tDb/hAMj2mWzl8VB4uYk1PIUrvjDla0+uYAWgEXVLuIBb1UebuQiyNDq2IumgPl0ZaAhr3nB9wXXv1H9n5jAlUjxfo84bgI+KRgQGv06jE4//N3XuHSdQ==
x-ms-exchange-transport-forked: True
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: BN7PR11MB2641.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 81b8e8a6-edb7-4d0c-c028-08d86bbd98db
X-MS-Exchange-CrossTenant-originalarrivaltime: 08 Oct 2020 19:08:52.8585 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 5ae1af62-9505-4097-a69a-c1553ef7840e
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: 7QIE9+tnUxQDYG38wb8Z7054tgS8+/uHRTZDnjuwywqrOOSF6NyQ3MdTEUcfylcNhdTZVXx/QSbqKAMhfqUfAg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN6PR1101MB2274
X-OriginatorOrg: cisco.com
X-Outbound-SMTP-Client: 173.36.7.11, xch-aln-001.cisco.com
X-Outbound-Node: rcdn-core-2.cisco.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/QhFN0zJd7ylTrrcKVZufbrhYH9k>
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: Thu, 08 Oct 2020 19:08:58 -0000

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