Re: [CFRG] [Cfrg] Using Diffie-Hellman With a Non-prime Modulus

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Thu, 29 October 2020 22:16 UTC

Return-Path: <sfluhrer@cisco.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id DC5E13A0930 for <cfrg@ietfa.amsl.com>; Thu, 29 Oct 2020 15:16:29 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -9.601
X-Spam-Level:
X-Spam-Status: No, score=-9.601 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, 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=kVhgg26J; dkim=pass (1024-bit key) header.d=cisco.onmicrosoft.com header.b=M51mYq6Q
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 7HQ_99b_kx5x for <cfrg@ietfa.amsl.com>; Thu, 29 Oct 2020 15:16:28 -0700 (PDT)
Received: from alln-iport-8.cisco.com (alln-iport-8.cisco.com [173.37.142.95]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 1795C3A08AF for <cfrg@irtf.org>; Thu, 29 Oct 2020 15:16:28 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=5494; q=dns/txt; s=iport; t=1604009788; x=1605219388; h=from:to:subject:date:message-id:references:in-reply-to: content-transfer-encoding:mime-version; bh=rYaDxIDnuOzA60HX1EN/tA+APcGzIEHC0fp3Wwt13HY=; b=kVhgg26Joo3YkerazVZ+mJfRSqzDuC0KMinKuEaG3r5N41M2ORAN2HHE BwSnDcsJHHCVWpajp3XDGBb+Z9GpWlcyFatRAeNFuDSS0GHX2dExEwnQx 9j5aXL+HpW9KyBQUAxpqIoCj3UQDMga7n+NA9ar8Gw+P9A/O6QXInY6Pe E=;
IronPort-PHdr: =?us-ascii?q?9a23=3AXbS+lxW5UhP2/9TfRDR9AS6LTfLV8LGuZFwc94?= =?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?A0DfCQDyPZtf/4cNJK1iHgEBCxIMQIM?= =?us-ascii?q?hUQdwWS8uCoQzg0kDjUmYe4JTA1QLAQEBDQEBGAsKAgQBAYRKAheBcAIlOBM?= =?us-ascii?q?CAwEBCwEBBQEBAQIBBgRxhWEMhXIBAQECAQEBARAREQwBASwMCwQCAQgRBAE?= =?us-ascii?q?BAQICJgICAiULFQgIAgQBEggXA4MFgksDDiABAgyjPgKBO4hodoEygwQBAQW?= =?us-ascii?q?BMwGDXxiCEAMGgQ4qgnKCYU5ChRSBQxuBQT+BEUOBT1AuPoJFFwECgUAgFYM?= =?us-ascii?q?AM4IskBkogx6jMoEMCoJsiQiPDoMOgxeKEJQ+k0SKd5EWboNCAgQCBAUCDgE?= =?us-ascii?q?BBYFrI4FXcBU7gmlQFwINjh+DcYUUhUR0AjYCBgEJAQEDCXyMOwGBEAEB?=
X-IronPort-AV: E=Sophos;i="5.77,430,1596499200"; d="scan'208";a="594112684"
Received: from alln-core-2.cisco.com ([173.36.13.135]) by alln-iport-8.cisco.com with ESMTP/TLS/DHE-RSA-SEED-SHA; 29 Oct 2020 22:16:27 +0000
Received: from XCH-ALN-001.cisco.com (xch-aln-001.cisco.com [173.36.7.11]) by alln-core-2.cisco.com (8.15.2/8.15.2) with ESMTPS id 09TMGRd3027101 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=FAIL); Thu, 29 Oct 2020 22:16:27 GMT
Received: from xhs-rtp-003.cisco.com (64.101.210.230) by XCH-ALN-001.cisco.com (173.36.7.11) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Thu, 29 Oct 2020 17:16:26 -0500
Received: from xhs-aln-002.cisco.com (173.37.135.119) by xhs-rtp-003.cisco.com (64.101.210.230) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Thu, 29 Oct 2020 18:16:25 -0400
Received: from NAM11-CO1-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, 29 Oct 2020 17:16:25 -0500
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=MNDCd5vhwS0R2aRI4z9HCEgLzYxd/kim24sZxr0+dRIopchfzKbh4/d17Yo6seF0IDRxo/ug0SnVJQbdNmrYrEkDccbJ4M+AiiwWNB+VxPRcYW2jzBW25BKAUxuttcJFWUDzpSMeyueWph6pAQZTmqRyDDUbT9Su2a/GleSfix0O/RYzPjtt+cgDHw7EsfWwqkLavR9AeJAu/qnenaEJHPpXnL14WaPNTEc1E/NoOaVTexulSZTanpDIhDzVt9Ugm/m8KxWP3otOYD2cAr1WiV3IWPlLFDC4THNqcG9EeTgoCS/pnYF8k0aTYfiicOXlAKr0vTIDrx/dQdjSLRKUKg==
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=rYaDxIDnuOzA60HX1EN/tA+APcGzIEHC0fp3Wwt13HY=; b=mgWl5G6Eii11mPOJ1ZExxYMvf9JKvY5bgaNOdEL2gxKE8ucCCuQn9ql6YAvtg391wxWFDbPyM6OH9juYHiEpeCl9X7ABVEE7+h96UE3oA3bbJVa/Ox1TyAwmFvgA0MAj2nmmi8ne+P/SmuXj0d5WrlF5Zq30E/f5M1cT07LBsBnFS4N5VPa1W3W5vxmVWqn+AnNM4saw6cqw6XhXNqmsKYztIZ3RPyDjTsOydBSVExe5tjT3eUyPXiCQme/43rQBVjXEygvN7o5AuB/kW2QJJN05Ah536TFOTJCAe+EGbSr82DdkP9PhV0MU0dZcs2kuibnxMq1q9NmrZhkvKfvYeg==
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=rYaDxIDnuOzA60HX1EN/tA+APcGzIEHC0fp3Wwt13HY=; b=M51mYq6QiHs9TELkFLU54+KZIPAIpXRohf47ycMDa/xql/EjLWrjSvP6H73bK1eribRwyc/s5UBdz4E3DKPcGvb5JwBi0/IvwydWY/TGCFFzH7A+agr1P8lJ89TLr6H2uXzB7TXgSWJoIoCK5mX0qzjvJyjBKKsY8llu8jArTbY=
Received: from BN7PR11MB2641.namprd11.prod.outlook.com (52.135.244.153) by BN7PR11MB2706.namprd11.prod.outlook.com (52.135.245.146) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3477.21; Thu, 29 Oct 2020 22:16:23 +0000
Received: from BN7PR11MB2641.namprd11.prod.outlook.com ([fe80::c044:416b:51fe:be5b]) by BN7PR11MB2641.namprd11.prod.outlook.com ([fe80::c044:416b:51fe:be5b%3]) with mapi id 15.20.3477.034; Thu, 29 Oct 2020 22:16:23 +0000
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: "Michael D'Errico" <mike-list@pobox.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [CFRG] [Cfrg] Using Diffie-Hellman With a Non-prime Modulus
Thread-Index: AQHWrWJao/ZFvZ+o7kyF5AyD2SLB4amtdAOAgAGiSYCAAAbYUA==
Date: Thu, 29 Oct 2020 22:16:23 +0000
Message-ID: <BN7PR11MB2641B00395B31AA668B8CB7EC1140@BN7PR11MB2641.namprd11.prod.outlook.com>
References: <6f5bddd5-04c8-45bf-87b1-7bb1e852666f@www.fastmail.com> <817BB671-266A-41F1-89E8-4BB740B61B93@shiftleft.org> <7b0d0e0c-bb1d-46e3-b513-2a9327d21bd2@www.fastmail.com>
In-Reply-To: <7b0d0e0c-bb1d-46e3-b513-2a9327d21bd2@www.fastmail.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.79]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 5c9df466-1404-40ab-a6de-08d87c58458d
x-ms-traffictypediagnostic: BN7PR11MB2706:
x-microsoft-antispam-prvs: <BN7PR11MB2706BEA5F3BFDBCC85CE3212C1140@BN7PR11MB2706.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: LYU4Dhp7Py2wQCfGM0tj9PGBWYt0FyHmn/m+I72nypb499DLyYnut45Ve7dHs1GgBJj9ZNbTf0DxD1oJcaeoYZKLO6fSoyFbg04NQ4gNi+HFfOgzfTB3/ItDwKqNEUE8Ul2IfdMMbj248JjPo6X1dCrhM1bjPHxoZfm2vf6cT7bFk22B6h7QP5Xo+lTFr6QwCfyksn4mPfEYUW2OgfMx1ccCt5iVJOMwYNmoJjH7xnyboGfsGJumEeFAodnr8zg+KB5R+wFqqWu9mVRdd8BG6xLOkoFGn+Xuv6r+YrJotiEAsUynO42Vk1s7jsQbS1aI3rsayMv5looGMI7typ4RkbH0F4DoDXEZZ9dZzFSCnVexkiLOaFpCGCthee+xNSnp0QfKqqWzXoCYiDekRrC+JQ==
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:(366004)(136003)(39860400002)(376002)(396003)(346002)(33656002)(76116006)(66556008)(26005)(52536014)(66476007)(64756008)(66446008)(66946007)(55016002)(8676002)(110136005)(6506007)(186003)(8936002)(86362001)(5660300002)(478600001)(966005)(53546011)(316002)(2906002)(71200400001)(9686003)(7696005)(83380400001); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: XeIee1IIcM+km3ZAm66KM3SJVZeclkfL15T8aQrGAzhpfGJdv2PKJQKR3ElFBxQvPsoQKQnpY4IClUu2QqlUdT9jcGBYU5P74Vd9VBNHbJAe+Qs9zdoZXw5C5og1btgENZwZNbJzbt4PHajevofGVnZVe7MoEYs//LrTKpxJ0+ym7Va7K4ZykwOi6U6gBk1vCmmOS37TKeDD+T+Y7Q02omauc6RVJ3IRcSguq00iZs2QiQJWsTJz3BRxS1QkVTyvL5R3ameajYFFAoS/MXUWpM8/ThE0Ep9z/fept7kR0i/PdHtTti5vwQLmu+RfK8qxiRFIUpcHj6K7wEyxNYxCg53RDlaio3t6zJ3yFSgaRrWg+Gs9rQAOwEiQnJzN2KrR1KSV6f8hifxnzLqmOHunzbFb/JE5W2hmzI1AiL0nK0RnmhqOxg137eplV4cOOoUg5Qgy4ux4goDDoCp2z/MMNS8tWMgnRg6I1Oc9sdHKrxd513y1uTcengSyf+wqFqhp9QXomwM5iG79FytbVXesb0mSnJ8QKnF4A8mGuZi/bHB9/Ls5f8QwjqzkPZOMAyEkr47hoVUKyaEOGJhJpy8M0CKwwKWvkvIH7Uk5UtGvO4RNDZ/5LUuVrDlrBWwIfWXr5FVaD8eu2bwZmaNCN8UUUQ==
x-ms-exchange-transport-forked: True
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
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: 5c9df466-1404-40ab-a6de-08d87c58458d
X-MS-Exchange-CrossTenant-originalarrivaltime: 29 Oct 2020 22:16:23.8113 (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: omKAc9mLwp0RyaRlz+GtarbFQvPTV3uh2re4mzvhaD3kFiAmriQaPCNJL+mjkd0SgqtizEXlKBH8yJlLvaJciw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN7PR11MB2706
X-OriginatorOrg: cisco.com
X-Outbound-SMTP-Client: 173.36.7.11, xch-aln-001.cisco.com
X-Outbound-Node: alln-core-2.cisco.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/ubOSgUXgyat0_RuHoggkyHuqPao>
Subject: Re: [CFRG] [Cfrg] Using Diffie-Hellman With a Non-prime Modulus
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: Thu, 29 Oct 2020 22:16:30 -0000

> -----Original Message-----
> From: CFRG <cfrg-bounces@irtf.org> On Behalf Of Michael D'Errico
> Sent: Thursday, October 29, 2020 5:15 PM
> To: cfrg@irtf.org
> Subject: Re: [CFRG] [Cfrg] Using Diffie-Hellman With a Non-prime Modulus
> 
> Hi Mike,
> 
> Thanks for providing your insight into this problem and your conclusions.
> 
> I'm trying to answer the question: "How do we pick the best modulus M for
> use with Diffie-Hellman?"  So my interest in this is more academic; I'm not
> necessarily concerned with speed of computation, at least not now.
> 
> It may be true that M+1 is more important than M itself.
> 
> This conjecture comes about because of the previous thread I started here,
> and the fact that while addition modulo M is cyclic with period M,
> exponentiation modulo M is cyclic with period M-1 (Fermat's little theorem),
> so maybe we've introduced an off-by-one error in our use of DH.

It's not true in general that exponentiation modulo M is cyclic with period M-1.  It is true if M is prime; however you are considering composite M, hence Fermat does not apply.

> 
> The idea I presented below is to have M+1 be prime instead of M, and then
> figure out how to choose M such that Diffie-Hellman still works, and is not
> easy to mess up.  M-1 also seems important, so finding an M sandwiched
> between a pair of twin primes might be a good idea.
> 
> So I'd still appreciate a pointer to a reference which explains the procedure
> and caveats associated with using a composite modulus in Diffie-Hellman, if
> you know of any.

Mike Hamburg already outlined the issues for M with public factorization. For M with a secret factorization, there are a number of ways for us to hide a backdoor in the DH operation, for example, https://eprint.iacr.org/2016/644.pdf (not the best, IMHO, just the first reference I found) - hence, good luck in getting anyone to trust that you didn't...

> 
> Thank you,
> 
> Mike
> 
> 
> On Wed, Oct 28, 2020, at 16:17, Mike Hamburg wrote:
> > Hello Mike,
> >
> > If you do DH mod p*q, then this can be attacked by solving discrete
> > log mod p and mod q, and then using the Chinese Remainder Theorem.
> > Mod p^n isn’t any better, and GF(p^n) kinda works but is much weaker
> > due to Joux et al’s recent work.  So you won’t get extra security this
> > way.
> >
> > So overall, there’s no reason to do the math mod pq unless it's
> > somehow faster than mod p, and even then you would use mod p as the
> > wire format, not mod pq.  In particular, it’s strictly better to do DH
> > mod p instead of mod p^n.
> >
> > I’ve looked into using pq for the purposes of faster arithmetic for
> > elliptic curves or postquantum crypto, but I didn’t find a case where
> > it was clearly worthwhile. It’s also generally not great for DH,
> > because the kinds of p that would be fast enough for this to be
> > plausibly worthwhile are the same types where the special number field
> > sieve poses a risk.
> >
> > You could also use math mod pq where p and q are secret, but I’m not
> > sure why you’d do that for DH.
> >
> > Cheers,
> > — Mike
> >
> >> On Oct 28, 2020, at 7:38 PM, Michael D'Errico wrote:
> >>
> >> Hi,
> >>
> >> Can someone please point me to a reference showing how to use
> >> Diffie-Hellman where the modulus is not a prime number?  Preferably
> >> one readable by laymen.
> >>
> >> The reason for this is I'm considering looking for a modulus M which
> >> is not prime, but where M is the number between some pair of Twin
> >> Primes, and also maybe where M is a prime times a power of two.
> >>
> >> I found at least one of these: 786431,786433 is a twin prime pair
> >> with midpoint 3*2^18.
> >>
> >> I'd hope to find an M whose odd prime factor is very large.
> >>
> >> Thanks,
> >>
> >> Mike
> 
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg