Re: [Cfrg] One question about MODP: the structure of DLP prime in a finite field

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Tue, 19 November 2019 04:03 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 3EEEA12081A for <cfrg@ietfa.amsl.com>; Mon, 18 Nov 2019 20:03:54 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -14.5
X-Spam-Level:
X-Spam-Status: No, score=-14.5 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_HI=-5, 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=dachkUJd; dkim=pass (1024-bit key) header.d=cisco.onmicrosoft.com header.b=vP1NaOC9
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 Q8GvnRCvm4Sg for <cfrg@ietfa.amsl.com>; Mon, 18 Nov 2019 20:03:49 -0800 (PST)
Received: from rcdn-iport-3.cisco.com (rcdn-iport-3.cisco.com [173.37.86.74]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 39CB112025D for <cfrg@irtf.org>; Mon, 18 Nov 2019 20:03:49 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=3835; q=dns/txt; s=iport; t=1574136229; x=1575345829; h=from:to:subject:date:message-id:references:in-reply-to: content-transfer-encoding:mime-version; bh=9rNo0Nx8nfJ01RKz45cIcnybICys1E9FGR82VxfayQs=; b=dachkUJdnl/m+iThCnZPXm9tc6Z260OIk8pLs0v4PfUaRe+cWmq026EQ jj2X7UQWrQaBMCeQiWNTUn5othV8IeZ0DWZvt3TXpeO0GkDi1M72apoDX vlbT32xGGkNGl8TT0AqM26qTDhUHS92yj47Y8pgayoKrNh8ikIu+ORoKt U=;
IronPort-PHdr: =?us-ascii?q?9a23=3AZRwIsRyTqaLDmbDXCy+N+z0EezQntrPoPwUc9p?= =?us-ascii?q?sgjfdUf7+++4j5YhWN/u1j2VnOW4iTq+lJjebbqejBYSQB+t7A1RJKa5lQT1?= =?us-ascii?q?kAgMQSkRYnBZueB0nmLOTndQQxHd9JUxlu+HToeUU=3D?=
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0BNAADOaNNd/4UNJK1lGgEBAQEBAQE?= =?us-ascii?q?BAQMBAQEBEQEBAQICAQEBAYFtAgEBAQELAYFKUAVsWCAECyqHcAOKdU6CEJg?= =?us-ascii?q?AgUKBEANUCQEBAQwBARgLCgIBAYRAAoIjJDcGDgIDCwEBBAEBAQIBBQRthTc?= =?us-ascii?q?MhVEBAQEBAgEBARAoBgEBLAwEBwQCAQgRBAEBHgEQJwsdCAEBBAESCBqDAYJ?= =?us-ascii?q?GAw4gAQIMpWYCgTiIYIIngn4BAQWFBRiCFwMGgTYBiUuCSRiBQD+BEUaCTD6?= =?us-ascii?q?CYgEBA4EmIhgFgzuCLK4tCoIqhxqFJokqmhGOSIg4kVACBAIEBQIOAQEFgWg?= =?us-ascii?q?jgVhwFTuCbFARFJEag3OFFIU/dIEojTUBAQ?=
X-IronPort-AV: E=Sophos;i="5.68,322,1569283200"; d="scan'208";a="653615887"
Received: from alln-core-11.cisco.com ([173.36.13.133]) by rcdn-iport-3.cisco.com with ESMTP/TLS/DHE-RSA-SEED-SHA; 19 Nov 2019 04:03:47 +0000
Received: from XCH-ALN-012.cisco.com (xch-aln-012.cisco.com [173.36.7.22]) by alln-core-11.cisco.com (8.15.2/8.15.2) with ESMTPS id xAJ43lZc010501 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=FAIL); Tue, 19 Nov 2019 04:03:48 GMT
Received: from xhs-rtp-003.cisco.com (64.101.210.230) by XCH-ALN-012.cisco.com (173.36.7.22) with Microsoft SMTP Server (TLS) id 15.0.1473.3; Mon, 18 Nov 2019 22:03:47 -0600
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.1473.3; Mon, 18 Nov 2019 23:03:46 -0500
Received: from NAM01-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.1473.3 via Frontend Transport; Mon, 18 Nov 2019 22:03:46 -0600
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=DXgVZOHBd0ZPtdy7QktCcUXYGQbTdxAz9v0iD5Imz8MrQr0MzWqgjvsHmiivylvv3zQQsasc4y9ucojwPdS7Ywa05Y4osJ4dENhRDsl7foeAROw/or36q1sYPxWr54Wzo79fQ+r3aYk4hT+Ppnak0Xk8IFyJ71a7HvbUBJ94Bbk7DG2R3IxJvluIb+g8zdjvfHD8QO7YfaY49UINk+zu3AxXwmN6WahPH7XmxLlDGUnGL2nFenbsBmqrDvzsZEipOYKZ5ncmm5QWvHxgD6iVSODwXCWu3nwWQjnpGvQq823NilXqGt3UGcyKdRY+yhuPGE1qUNDhb31yMr5yymRHRg==
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=WIx+X2nyVmHPdTqJ70Zyrs7D0jWKTw0eplg4P7gIXjg=; b=aBVu4dPndFc06Lc5Bx7yweSEQ1+Xm/Eav6PCi1kECp4xGZFGvrTyZjeMOyMy5gfyluvNlGCgLDimo8rh7N2y1w1kc4g687SNcQNHkVqHa0QyhepJ0qRNJ09QKsXaBIu3VU55vJg5SsBtFgKioU2rDRVReJ5wxtt1RBe2ifaea+FUuO9cHiIv7F4wFlg7Jdiw8ijJG1WRqavufGeyp96x2A0DE/W6BqmkDoen74jPnypcIrdaio4cqhlSV/JA7Q+u71S3GrZ5LkTktWceSHcaWmgIX0KAcWcc8ZDMSqAQcx0b45I6AVITPP0mtSLfw9UlFFUkExP5NkwObQUbACLxcg==
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=WIx+X2nyVmHPdTqJ70Zyrs7D0jWKTw0eplg4P7gIXjg=; b=vP1NaOC9NjxhgONIjM5Az4rYCYfSK8lOXy5vPxEEhTvabYPCTu00fIpkwqoVfGYLhRJbnctCOL95YzzR0JiuAPXLJ66IvXpfg4UyyX5wN6WpTWDwrWpjZ9ybyR0gnklvJj3Td2DpYoKLgXD3HcKADev7mZbPYrLaJc18DhpcFvA=
Received: from BN8PR11MB3666.namprd11.prod.outlook.com (20.178.221.19) by BN8PR11MB3538.namprd11.prod.outlook.com (20.178.218.214) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2451.23; Tue, 19 Nov 2019 04:03:45 +0000
Received: from BN8PR11MB3666.namprd11.prod.outlook.com ([fe80::815c:974a:5eab:868b]) by BN8PR11MB3666.namprd11.prod.outlook.com ([fe80::815c:974a:5eab:868b%7]) with mapi id 15.20.2451.029; Tue, 19 Nov 2019 04:03:45 +0000
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: Wang Guilin <Wang.Guilin@huawei.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: One question about MODP: the structure of DLP prime in a finite field
Thread-Index: AdWegtVJxKWRMLE+TymcwM5ykoxhwQACbuuw
Date: Tue, 19 Nov 2019 04:03:45 +0000
Message-ID: <BN8PR11MB3666349CA819D2B251FCCAC8C14C0@BN8PR11MB3666.namprd11.prod.outlook.com>
References: <0d62d07932d44b53ab30b1cdb47db8ee@huawei.com>
In-Reply-To: <0d62d07932d44b53ab30b1cdb47db8ee@huawei.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: spf=none (sender IP is ) smtp.mailfrom=sfluhrer@cisco.com;
x-originating-ip: [2001:420:c0c8:1005::641]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 5c1d64d5-cb44-4584-f14e-08d76ca57930
x-ms-traffictypediagnostic: BN8PR11MB3538:
x-microsoft-antispam-prvs: <BN8PR11MB353890FFFBFB71536A0C3169C14C0@BN8PR11MB3538.namprd11.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-forefront-prvs: 022649CC2C
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(4636009)(39860400002)(366004)(346002)(396003)(376002)(136003)(189003)(199004)(13464003)(51874003)(52536014)(2906002)(6436002)(7736002)(76116006)(53546011)(6506007)(55016002)(6306002)(256004)(14444005)(478600001)(66476007)(66556008)(76176011)(64756008)(66446008)(66946007)(14454004)(33656002)(229853002)(966005)(7696005)(6116002)(8936002)(11346002)(25786009)(486006)(305945005)(110136005)(6246003)(86362001)(102836004)(2501003)(71190400001)(71200400001)(8676002)(81166006)(81156014)(186003)(99286004)(5660300002)(9686003)(46003)(74316002)(476003)(316002)(446003); DIR:OUT; SFP:1101; SCL:1; SRVR:BN8PR11MB3538; H:BN8PR11MB3666.namprd11.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1;
received-spf: None (protection.outlook.com: cisco.com does not designate permitted sender hosts)
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: ficviFvknQ1/O+vc8azLn9oAlzzmyaInUuQUqU9LSN5Ay5WGe6/vifs6xi/Pbxy3pKqS3000/Md4KgirzlBRAKEfEXEDRIviAkS1dN9aHLU+rBp8QccnhbPF7Bp9pw3vAEW1UrdNmrkF+AQHPBtN9+gx8OcwiCNMVZhqgqHeBTAPLodCOFlW4qeiLLeUf3cy/VmaP/NxCAHDWC6tvL8g6/4iyvhkPr1zybbQsoXs/p3DGd1hPnQNNvJ9DuXxxurtqow5MVNn6+WtgQb/N2ny6UXzuPvp48vP/EV5KKQkQXQpL2dJBOTkjgzPwW5iKPW6wELgyHnLRpAGrPCmxdGtOMFYj+RzlgpAi317l4YIJQux13guMERpwNFxp61vSUJAydbbGiE9JpDPvWdBewJDvuQSuAiToxYJbJaSoJ/jxk6nvOUZ5eTXFKH+IYKp5BxP
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-Network-Message-Id: 5c1d64d5-cb44-4584-f14e-08d76ca57930
X-MS-Exchange-CrossTenant-originalarrivaltime: 19 Nov 2019 04:03:45.2840 (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: HNuoaluwcI/XCYrvR+aMUDC84c0RyZmofA/v5vL6uO62Xw5vOHZrqigNUlxSeVocGb3S5pVjWQTO0/W0yx2wAw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN8PR11MB3538
X-OriginatorOrg: cisco.com
X-Outbound-SMTP-Client: 173.36.7.22, xch-aln-012.cisco.com
X-Outbound-Node: alln-core-11.cisco.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/08_2qYcsxtPzycvJo2iD5fzGbC4>
Subject: Re: [Cfrg] One question about MODP: the structure of DLP prime in a finite field
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: Tue, 19 Nov 2019 04:03:54 -0000

> -----Original Message-----
> From: Cfrg <cfrg-bounces@irtf.org>; On Behalf Of Wang Guilin
> Sent: Monday, November 18, 2019 9:46 PM
> To: cfrg@irtf.org
> Cc: Wang Guilin <Wang.Guilin@huawei.com>;
> Subject: [Cfrg] One question about MODP: the structure of DLP prime in a
> finite field
> 
> Dear everyone,
> 
> Highly appreciate if anyone can help on the following question.
> 
> RFC 3526 (https://tools.ietf.org/html/rfc3526) offers a number of DLP
> parameters in a finite field. An example is group ID 14, detailed specification
> copied below.
> 
> =========================
> This group is assigned id 14.
> 
>    This prime is: 2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 }
> 
>    Its hexadecimal value is:
>       FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
>       29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
>       EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
>       E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
>       EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
>       C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
>       83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
>       670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
>       E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
>       DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
>       15728E5A 8AACAA68 FFFFFFFF FFFFFFFF
> 
>    The generator is: 2.
> =========================
> 
> The question is: What is the structure or factors of prime p-1, where the
> value of p is given above?

The prime factors of p-1 are known to be 2 and q = (p-1)/2.

> Also, if we do not know the factors of p-1, it is risky
> to just use g=2 as a generator as the order of 2 could be quite small.

The order of g=2 is known to be q

>  In FRC
> 3526, the suggested exponent size for group ID 14 is 220 bits or more.

Yes; the reasoning is that there are two style of attacks to solve the discrete log problem:

- A NFS attack against the group (which is estimated to take approximately 2**110 effort
- A Giant-step-baby-step attack against the exponent; if the exponent is N bits, this takes about 2**(N/2) effort

Selecting an exponent size of 220 makes these two attacks approximately the same effort; selecting an exponent from a smaller range would actively decrease security, while selecting from a significantly larger range would increase the work required without increasing security.

Personally, I'd use a slightly larger range (perhaps 256 bits); our estimates for NFS might be a bit off, and increasing the exponent size modestly doesn't increase time that much...

> 
> My real reason to ask this question is: We want to test SPEKE (a PAKE
> protocol) by using group ID 14. However, to run SPEKE, we need to know a
> prime factor q of p-1, i.e. (p-1)=qk, where k is an integer. Ideally, the bit
> length of q is between 220-256.

Actually, the length of q is 2047 bits; it's not obvious to me what a large q would be an issue in this situation...

>  Once we know such a prime factor q for p-1,
> then both client and server in SPEKE can calculate a generator something like
> g=(H(pw, salt))^k. Then, they can run DH key exchange normally by using g.
> 
> So, the difficulty here is: Without knowing the factors of p-1 in group ID 14, it
> seems not possible to generate such a generator g in SPEKE.

As above, that's not an issue...

> 
> Thanks in advance,
> 
> Guilin
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg