Re: [Cfrg] Query: Very best practice for RSA key generation

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Mon, 21 October 2019 15:25 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 954921200EC for <cfrg@ietfa.amsl.com>; Mon, 21 Oct 2019 08:25:28 -0700 (PDT)
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, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=unavailable autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cisco.com header.b=FuYgv9/K; dkim=pass (1024-bit key) header.d=cisco.onmicrosoft.com header.b=eF27Wesu
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 yeW4_zAY9x81 for <cfrg@ietfa.amsl.com>; Mon, 21 Oct 2019 08:25:26 -0700 (PDT)
Received: from rcdn-iport-4.cisco.com (rcdn-iport-4.cisco.com [173.37.86.75]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 39EA112011C for <cfrg@irtf.org>; Mon, 21 Oct 2019 08:25:26 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=15556; q=dns/txt; s=iport; t=1571671526; x=1572881126; h=from:to:subject:date:message-id:references:in-reply-to: mime-version; bh=/K20L2UvPwgX6gtTuS18e/1O3hzagvUjAeSpnA313ys=; b=FuYgv9/K0p8iZhm9sKuLrEj/h+rGu8GksFbdiiiPJ9ki/7K5fkEXp9/R OVaU7YmuOPSAouVt+nZUIzw1XnqoCpyQvpQ76KhoACpfCnrxqvrzdMJt8 wESuvxKsWiCP3C5zzz1xipeW/XWbcxyeitEfm25hPNf/ZN2DBO0A2zJD0 k=;
IronPort-PHdr: 9a23:1cZl9hbR+sO34HP/QBuOnWf/LSx94ef9IxIV55w7irlHbqWk+dH4MVfC4el20gabRp3VvvRDjeee87vtX2AN+96giDgDa9QNMn1NksAKh0olCc+BB1f8KavxYSgnHN5PTndu/mqwNg5eH8OtL1A=
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: A0BGAAC3zK1d/5pdJa1lGwEBAQEBAQEFAQEBEQEBAwMBAQGBZwYBAQELAYEbL1AFbFcgBAsqCoQcYoJlA4RYhX1Ngg9+kiOEYYEugSQDVAkBAQEMAQEtAgEBhEACF4MEJDQJDgIDCQEBBAEBAQIBBQRthQsGJgyFSwEBAQEDEhEKEwEBOA8CAQgRBAEBKwICAjAdCAIEARIIGoMBgXlNAy4BAqRTAoE4iGF1gTKCfgEBBYUKGIIXCYE2AYpLgUMYgUA/gRABRoFOSQcuPoRHJIJqMoIsj3aFOokyjnkKgiSVQZlMjjWZRgIEAgQFAg4BAQWBUjmBWHAVO4JsUBAUgRyBagkag1CKU3SBKY02AYEiAQE
X-IronPort-AV: E=Sophos;i="5.67,324,1566864000"; d="scan'208,217";a="650586708"
Received: from rcdn-core-3.cisco.com ([173.37.93.154]) by rcdn-iport-4.cisco.com with ESMTP/TLS/DHE-RSA-SEED-SHA; 21 Oct 2019 15:25:24 +0000
Received: from XCH-ALN-010.cisco.com (xch-aln-010.cisco.com [173.36.7.20]) by rcdn-core-3.cisco.com (8.15.2/8.15.2) with ESMTPS id x9LFPOqB031144 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=FAIL); Mon, 21 Oct 2019 15:25:24 GMT
Received: from xhs-aln-002.cisco.com (173.37.135.119) by XCH-ALN-010.cisco.com (173.36.7.20) with Microsoft SMTP Server (TLS) id 15.0.1473.3; Mon, 21 Oct 2019 10:25:23 -0500
Received: from xhs-aln-001.cisco.com (173.37.135.118) by xhs-aln-002.cisco.com (173.37.135.119) with Microsoft SMTP Server (TLS) id 15.0.1473.3; Mon, 21 Oct 2019 10:24:54 -0500
Received: from NAM01-SN1-obe.outbound.protection.outlook.com (173.37.151.57) by xhs-aln-001.cisco.com (173.37.135.118) with Microsoft SMTP Server (TLS) id 15.0.1473.3 via Frontend Transport; Mon, 21 Oct 2019 10:24:54 -0500
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=OlHOthVQ+Tl2quX9TV/utgPNx4twxM8coNrsgVS9rLbMvKlN4L8jktiKu/YSRUvpmKrbYHWt1BqkgZxaBiOK2ZwPx7mzYHJH74I6MfNTKw29hiCznI+SG2t09nvsZOfXk5YPVLw5s2/N6wkeRVBdoADEbMDLmAXAug5p40slUm/vV/feUE5pcRstDLO+Ra5u47XvmZO2uasjFSDGwTCOEfVwxrx71YnsEXYe5NaR9PurDaoMryfsCYITcV5eEkrYozfMKKnpKisJzMzDILGBZxzn3/z9B7NBoRhXyua4x4QseMCe2WZdaqoc3N5hsb4XeoGm54HzECFxDCMz4TyFkA==
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=/K20L2UvPwgX6gtTuS18e/1O3hzagvUjAeSpnA313ys=; b=X4cr47JplycnaWN1TwCm2qG6N+AFEa6Ag13JTHJhOEiB4p9pOsGUXMCq+GcDMSydM//bQxn6dHlgb4J7lyt4Y9XPqodSCucMi3j/LqOw3DKA/T4RANAEAqFiaF2NDMNltdPMo5wljK4uSClugTxnZ9xpXzAaOepNN+qgT/YYKz8/pL1Raeo3FWQ/E97847ABOxrD3V0Y8qN9NDvjI2cNnPNb9MGbPzZIzYRqwoGe2HSU/9YqO/xDyrJyZiLnG/JJ6uyXIN3lEKK2K/3mCQRdTe/qgb8CbUrOv8/KlvCnmZdDgiZC/skFj8n6ptLUVRA0QlCB39IhW+zp7gqxcAhSEg==
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=/K20L2UvPwgX6gtTuS18e/1O3hzagvUjAeSpnA313ys=; b=eF27Wesu26awm7AgOg3yLM4V7Vei7QE27pYHVH5YKiLnH2dfIGVlhRm+fAKvUdlbffjuYEkewmGwj0h1Bfsrkyg09XH4NE0+tzlpqzoKsZB5uB0h2SjARucyE18iB9Pemu1nENpBb6NRZUkrNb686mugWnMdePjkgB6g3VGvE2k=
Received: from BN8PR11MB3666.namprd11.prod.outlook.com (20.178.221.19) by BN8PR11MB3779.namprd11.prod.outlook.com (20.178.220.154) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2347.16; Mon, 21 Oct 2019 15:24:54 +0000
Received: from BN8PR11MB3666.namprd11.prod.outlook.com ([fe80::38cc:fcf7:a049:1c5b]) by BN8PR11MB3666.namprd11.prod.outlook.com ([fe80::38cc:fcf7:a049:1c5b%7]) with mapi id 15.20.2347.029; Mon, 21 Oct 2019 15:24:54 +0000
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: Phillip Hallam-Baker <phill@hallambaker.com>, "cfrg@irtf.org" <cfrg@irtf.org>, "mathmesh@ietf.org" <mathmesh@ietf.org>
Thread-Topic: [Cfrg] Query: Very best practice for RSA key generation
Thread-Index: AQHVhSkxQ0fWjYGDU0efycYeaXyXKqdlPC1g
Date: Mon, 21 Oct 2019 15:24:54 +0000
Message-ID: <BN8PR11MB3666C8581C62EECE4F8A6E91C1690@BN8PR11MB3666.namprd11.prod.outlook.com>
References: <CAMm+Lwixgjj-B0qG=0=Z59egb6fJ2BixW53gfvaPUcZ7r9Ys0w@mail.gmail.com> <CAMm+LwhLb7mnQmjAOxMMsPrzAZb==ix9Erfse5UDSoj0uB0iHQ@mail.gmail.com>
In-Reply-To: <CAMm+LwhLb7mnQmjAOxMMsPrzAZb==ix9Erfse5UDSoj0uB0iHQ@mail.gmail.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: [173.38.117.90]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 0efd05b2-6a13-48ad-42ba-08d7563ad2e3
x-ms-traffictypediagnostic: BN8PR11MB3779:
x-microsoft-antispam-prvs: <BN8PR11MB377934DD96CC9C44E4CE726FC1690@BN8PR11MB3779.namprd11.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-forefront-prvs: 0197AFBD92
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(4636009)(366004)(39860400002)(136003)(376002)(346002)(396003)(199004)(189003)(5660300002)(86362001)(7696005)(76176011)(6116002)(476003)(6436002)(53546011)(6506007)(26005)(99286004)(8936002)(110136005)(25786009)(229853002)(2501003)(33656002)(486006)(54896002)(9686003)(6306002)(2906002)(2201001)(102836004)(55016002)(3846002)(790700001)(66946007)(76116006)(64756008)(71190400001)(66556008)(66476007)(66066001)(66446008)(74316002)(8676002)(71200400001)(14454004)(7736002)(256004)(316002)(11346002)(6246003)(446003)(186003)(52536014)(478600001)(81156014)(81166006); DIR:OUT; SFP:1101; SCL:1; SRVR:BN8PR11MB3779; H:BN8PR11MB3666.namprd11.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX: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: tcFAR2RW6uI7FebocFldRzP/AWqx6126bVRtn81GbQntVckDB5+aGgg+nMrM7wzG7JrQq7w836fRQV3oJ5+MSD6sjmijh6NoAkiZcCUKEsS7JIKKj0K6k6WMmfVLEleOpSE5H7sF/mQ2yGDEcY7TLsI4b20i1mAKjUaL/pd9OeY4vDLPSgqQDYbs14sRMayc/JwfQHY9Cp25dCClOfnywAXNzmu8hTuNbifXp67eySLQGyCXBm8r2ecgP3fOzgbc78tkRcOYUHjuE9YBVn8RhjA9dTTO002Uu11keVr3T7IvJt9Zax5+1YWFoQq5ptnWWlWXcDkc6O++BnV0u8ujnU6THK8YzBIrDPOqIKggTy0QYQquKqkfUMgoP1PMjpkDNBJduRTsTUWDOIGeXUl5jggXUPgNpxSfVXwN5BZhAYU=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_BN8PR11MB3666C8581C62EECE4F8A6E91C1690BN8PR11MB3666namp_"
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-Network-Message-Id: 0efd05b2-6a13-48ad-42ba-08d7563ad2e3
X-MS-Exchange-CrossTenant-originalarrivaltime: 21 Oct 2019 15:24:54.2005 (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: GI5ZzSVV8pfpW5QfkBMwvgAOd/7kThGHRRD6PrpZQIRq0mXPfiPpTgaX+zq7wK9abdhU7YlqrCL3ehaSTq7PyA==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN8PR11MB3779
X-OriginatorOrg: cisco.com
X-Outbound-SMTP-Client: 173.36.7.20, xch-aln-010.cisco.com
X-Outbound-Node: rcdn-core-3.cisco.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/mb0TE44aINfIOCO_cXk44WxAvz4>
Subject: Re: [Cfrg] Query: Very best practice for RSA key generation
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: Mon, 21 Oct 2019 15:25:29 -0000

Actually, NIST SP 800-56B already defines a number of ways to map a seed into an RSA key.  While they’re not perfect (they are overly complex, and of course, there are a number of methods and parameters in those methods that we’d need to agree upon), however (IMHO) it’d make more sense to start from there rather than inventing a new method…

From: Cfrg <cfrg-bounces@irtf.org> On Behalf Of Phillip Hallam-Baker
Sent: Thursday, October 17, 2019 4:26 PM
To: cfrg@irtf.org; mathmesh@ietf.org
Subject: [Cfrg] Query: Very best practice for RSA key generation

[CC'd to CFRG as this is a crypto question, MATHMESH as the target group, OpenPGP as a group that recently asked for the same capability. Also to the cryptography list for additional eyes. Looking to add this to the UDF draft tomorrow]

A question has come up for generating key pairs from a specified random seed. I am just looking to add this to UDF and would like advice as to what the very best practices are for RSA keygen.

The use case here is that the user wants to be able to be very very sure the key was correctly generated and that they can recover it. So lets say I want to configure OpenPGP with the same keypair on three different machines without the full Mesh PKI.


The basic idea is that a user has a key which expressed in Base32 looks like this:

ZAAA-UJUY-H7TF-SFLK-CWAW-TKC4-O5HQ

The first three bytes are
C8     Type code for key generation with 16 bit key type]
00,00 RSA 2048 bit key pair

The remaining characters are to provide randomness for the key generation function. A minimum of 112 bits (work factor of RSA 2048) are required. So 112+24 = 136 bits

To generate keys, HMAC-KDF is used

p0 = KDF ("ZAAA-UJUY-H7TF-SFLK-CWAW-TKC4-O5HQ".FromBase32(), "P")
q0 = KDF ("ZAAA-UJUY-H7TF-SFLK-CWAW-TKC4-O5HQ".FromBase32(), "Q")

p = next_prime (p0)
q = next_prime (q0)

So that is the RSA part.

I don't plan to do DH. For ECDH, I suggest the NIST and CFRG curves only.


OK so some interesting variations. Lets say I don't trust the random number generator on any one machine. So lets use Shamir Secret sharing on three different machines for a 140 bit output:

f(1) = SAYE-UHOY-TVZO-LPGT-ZAGE-7JUW-6MTJ-I
f(2) = SAYX-4HWP-3753-L4P3-N4S6-C2G4-QVPA-A
f(3) = SAZD-HQNJ-KSDK-HAY7-BIFO-34Y2-NH7O-C

We can now combine the shares on the target machine to (re)generate the keypair. We can also give ourselves a couple of additional shares as well:

f(4) = SAZW-WBTE-7MJ2-44B6-TC5X-KRKQ-UEEW-U
f(5) = SA2C-H3IC-2ORN-NOK2-DM3X-OX37-FJ6W-Q