[Cfrg] My review of the four PAKEs

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Tue, 25 February 2020 20:45 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 265803A157F for <cfrg@ietfa.amsl.com>; Tue, 25 Feb 2020 12:45:56 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -9.599
X-Spam-Level:
X-Spam-Status: No, score=-9.599 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, HTML_MESSAGE=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=aGSEy1hu; dkim=pass (1024-bit key) header.d=cisco.onmicrosoft.com header.b=DcycIbUP
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 ruium41CXym9 for <cfrg@ietfa.amsl.com>; Tue, 25 Feb 2020 12:45:53 -0800 (PST)
Received: from alln-iport-6.cisco.com (alln-iport-6.cisco.com [173.37.142.93]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 4B6553A157D for <cfrg@irtf.org>; Tue, 25 Feb 2020 12:45:53 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=17122; q=dns/txt; s=iport; t=1582663553; x=1583873153; h=from:to:subject:date:message-id:mime-version; bh=qEex04OXbIffSm2gLjU/hOoo39s+ttu2H2lRzpjbBgA=; b=aGSEy1hukHfKnncGcGLxxvEDoJb9TBydt7BOZUEFaPlhYJgPHRgVGZ0D M2Bn69HWqfAAWIpw2wnoUm6qOQmdW/eMOQbrCjAHbxIM97APd63Fnm69F qyhzNtomrP+Py7VAdQvDQoWr8QDZyu5wAVndlLoRbL2VXNSSElUc4/IfK o=;
IronPort-PHdr: =?us-ascii?q?9a23=3AQdw8Vx+4GE4Fcv9uRHGN82YQeigqvan1NQcJ65?= =?us-ascii?q?0hzqhDabmn44+8ZR7E/fs4iljPUM2b8P9Ch+fM+4HYEW0bqdfk0jgZdYBUER?= =?us-ascii?q?oMiMEYhQslVdWLDVD7NvPwRyc7B89FElRi+iLzPA=3D=3D?=
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0C6EQBCh1Ve/5BdJa1lHgFDDIJ4L1A?= =?us-ascii?q?FbFggBAsqCodQA4pzTpVDhGKCUgNUCQEBAQwBAR8OAgQBAYRAAoF+JDgTAgM?= =?us-ascii?q?NAQEFAQEBAgEFBG2FCwYmAQuFaBQbEwEBIxURAThIJgEEGxqDBYF9TQMuAQ6?= =?us-ascii?q?jWwKBOYhigieCfwEBBYEvAYNaGIIMAwaBOIlbgSuBHhqBQT+BEUeBTi4ig1A?= =?us-ascii?q?DgUwaKyKCdIIsllWZRQqCPIdRjzCCSZQZhEyOcIFNhy+SSwIEAgQFAg4BAQW?= =?us-ascii?q?BaSJEgRRwFYMnUBgNhwqHHgEXg1CFFIVBdAKBJ44ZgQ0BgQ8BAQ?=
X-IronPort-AV: E=Sophos;i="5.70,485,1574121600"; d="scan'208,217";a="460020148"
Received: from rcdn-core-8.cisco.com ([173.37.93.144]) by alln-iport-6.cisco.com with ESMTP/TLS/DHE-RSA-SEED-SHA; 25 Feb 2020 20:45:51 +0000
Received: from XCH-RCD-004.cisco.com (xch-rcd-004.cisco.com [173.37.102.14]) by rcdn-core-8.cisco.com (8.15.2/8.15.2) with ESMTPS id 01PKjp7i032280 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=FAIL) for <cfrg@irtf.org>; Tue, 25 Feb 2020 20:45:51 GMT
Received: from xhs-rtp-001.cisco.com (64.101.210.228) by XCH-RCD-004.cisco.com (173.37.102.14) with Microsoft SMTP Server (TLS) id 15.0.1473.3; Tue, 25 Feb 2020 14:45:50 -0600
Received: from xhs-aln-003.cisco.com (173.37.135.120) by xhs-rtp-001.cisco.com (64.101.210.228) with Microsoft SMTP Server (TLS) id 15.0.1473.3; Tue, 25 Feb 2020 15:45:50 -0500
Received: from NAM04-BN3-obe.outbound.protection.outlook.com (173.37.151.57) by xhs-aln-003.cisco.com (173.37.135.120) with Microsoft SMTP Server (TLS) id 15.0.1473.3 via Frontend Transport; Tue, 25 Feb 2020 14:45:49 -0600
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=QpGpK1lkv8TCJCplkI6diBD7mnduc5WN+M2w9j55ooaxo+u9CfhgGtUP8ggfOrJpFENikIBcbTBUGdJqHQiviXKf2vP9OqErFRsZd3Z0x3Qmk65D6GDulo4URPqBHJsYQy3M6hCq2sIkcTMyw7A5Ep7Cevcj4TCc+VHcVslPdZMZBKgFaYBfNaAq6KNS3BYSR14lzFLJiI0E2kbOF48ol5vYjKGrDnJJdkvmUFco/V8mZHKzu5ggbcjqKPAFxN+8gNr2FSILb+4R8I/2dcSxAZ7bhDvvoC3yWWsWbvrVwZeoZ7FHqEnPKLqR/bJjILpNzuwVCJS714RjoPM2Vk2eDg==
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=2ygnlXzzWrjCKQ9bu7ggLM8+a80YGdPBh/dotuXmYtg=; b=mIAIFjnDzpKqatGzONic2ul5nTkpOSCdgzjd3RRtQs3lceTpgPXAZpuBB3QeQIyc2bA0qXIuFWN4HdMYeldoykmPCZU02ApLFl7qtQ72DQubJ1lEWAi2FAAJaB+2HsEj0T3B2E/bpqUwcsPeUWb8LrwMdKc+vh5xJlHRaaQp51fTXx30VkM6g9JqK6lYifqqiRuTc3qk0+yTBFKNmfu5ML7+ZnMsOKYf8mUG4p1lF1QMFlWErb6Ey0eSN3sVCT4SKzwLM4loowi5gQNWAGI/e+dbmsP1F4CJQnhV09iwvV1MEmXK8PnFxX6so1biL1nO3M16xxG2cVvmUFavQ7r7nQ==
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=2ygnlXzzWrjCKQ9bu7ggLM8+a80YGdPBh/dotuXmYtg=; b=DcycIbUP9BNnAWv4DwxWcTKsIxMXsviR52cpQW9Om8hhSb5SXNx/GJ9meyRyn0VXPcXb5ye4k1WHu+d3u/jYpgNzM72UE5KA++8WDUg2XYMd71jXZu2au1tpzqBBofhnpURfJ8uUPGwt6NT4vQ9p9cMZ+q2h79mr2AHuNsyCZlI=
Received: from MN2PR11MB3936.namprd11.prod.outlook.com (2603:10b6:208:13f::15) by MN2PR11MB4496.namprd11.prod.outlook.com (2603:10b6:208:18e::26) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2750.17; Tue, 25 Feb 2020 20:45:48 +0000
Received: from MN2PR11MB3936.namprd11.prod.outlook.com ([fe80::71a0:2f72:8146:9d8]) by MN2PR11MB3936.namprd11.prod.outlook.com ([fe80::71a0:2f72:8146:9d8%6]) with mapi id 15.20.2772.012; Tue, 25 Feb 2020 20:45:48 +0000
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: My review of the four PAKEs
Thread-Index: AdXsG2T3zLVp9Ju5S2qhyavstwvS6g==
Date: Tue, 25 Feb 2020 20:45:47 +0000
Message-ID: <MN2PR11MB3936CB4ED454E8ED8694B8E7C1ED0@MN2PR11MB3936.namprd11.prod.outlook.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.68]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 9a8dfb89-e777-4aae-83f4-08d7ba33b199
x-ms-traffictypediagnostic: MN2PR11MB4496:
x-microsoft-antispam-prvs: <MN2PR11MB4496BD6FD09EF7A5A2AC76EAC1ED0@MN2PR11MB4496.namprd11.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-forefront-prvs: 0324C2C0E2
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(4636009)(376002)(39860400002)(396003)(366004)(136003)(346002)(189003)(199004)(6916009)(81156014)(66556008)(966005)(81166006)(64756008)(478600001)(8676002)(76116006)(186003)(8936002)(66446008)(86362001)(6506007)(66946007)(66476007)(26005)(7696005)(52536014)(2906002)(5660300002)(316002)(71200400001)(55016002)(9686003)(33656002); DIR:OUT; SFP:1101; SCL:1; SRVR:MN2PR11MB4496; H:MN2PR11MB3936.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: y+8HQXgthZ/bpOTzbPgVZRj8rPcYdG/hJJ/Y80pFyFMClDqdtvCsLq3ONWVnOtRcwsH3CEWvtW0+XvTJw8bJwQZTt1HYQ406AtOyREwyQxaF0+qkiRPuhgUdX7EgnGAQZzMjULrzU6b+/J+BopmRfKhumZk2MOyLOVdfwoLCHl3xKMH/W2jfqoGjygqz22mZIUBEzO0xIO8LGc1QmwUZf2Z0JUNGHgsSKpRzgVH9YfCV0QTcB/FisG0d4z2//UfUBthO8vhzdY5oxxNLL3WLpGnsyvesS0kIiG/87Qb8ot1UBCa2sqelKoxe/s/v2IO5PuOUlKWCibgZpjxcPNzg5HEIJqGGVnrivncUrwOMAQjGMVTA3d3mJ2rmdpm1Hy+/O2dngurudPKo4CUeAZb3LhR/l4lcS4Pyv8OnZAaI0i/FXsjs4Yu7FbdrT7X9khCjZTtBESU9OO9CA9uCvBUfcCcHR40DU9t3Ikb9wq1zwNxm37OYwXc9fiKf5xV8eKE4sgUUraVJqWx8nQaOZRksUw==
x-ms-exchange-antispam-messagedata: NWB+1+0roWJO/H6KWOBtBPN3e/pRaZjS9UAnGRg/oCUidE98Mwz/CNbkaiFgjQ62BT58wo+UJh7U0g4GKYxHFsVNOdCEw/3dSgcnBgT46oSim8y4nHMyMTWmzKJiDjpWChEvP+gj88BAgMLCy2VPBw==
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_MN2PR11MB3936CB4ED454E8ED8694B8E7C1ED0MN2PR11MB3936namp_"
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-Network-Message-Id: 9a8dfb89-e777-4aae-83f4-08d7ba33b199
X-MS-Exchange-CrossTenant-originalarrivaltime: 25 Feb 2020 20:45:47.9502 (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: Igek3mA6FHBfAJJvidb1cq45iJvL7NY9hzIAXknuxZPYXwEa4conYPAMxVvMYv//XnvTzTX52EQegNdssWQ3/w==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR11MB4496
X-OriginatorOrg: cisco.com
X-Outbound-SMTP-Client: 173.37.102.14, xch-rcd-004.cisco.com
X-Outbound-Node: rcdn-core-8.cisco.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/JwBPf_71G6JcfUttFw9MbvnIDCU>
Subject: [Cfrg] My review of the four PAKEs
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, 25 Feb 2020 20:45:56 -0000

Summary of my vote: Balanced PAKE: CPace; Augmented PAKE: OPAQUE
CPace vs SPAKE2 reasoning:
My opinion is essentially unchanged from my initial review.  The difference comes down to the superior Quantum Annoyance of CPace vs the implementation simplicity and potential side channel resistance of SPAKE2 (CPace absolutely needs a side channel free hash-to-curve routine; even if SPAKE2 is used with a hash-to-curve algorithm, it needn't be side channel resistant).  Even though SPAKE2 has potentially improved its Quantum Annoyance ("potentially" because it's now an option, and so the protocol might not decide to use it), it's still not to the level that CPace gives.  I am of the opinion that factor outweighs the implementation issues.
Opaque vs AuCPace reasoning:
I did not review Opaque for the previous round; when I reviewed it for this round, I was impressed.  It uses fewer messages than AuCPace (even with AuCPace reducing the round trips it requires for this round); this makes it easier to insert into existing protocols.  In addition, Opaque uses potentially less computation and to be, in general, a cleaner design.  In addition, after the first pass, both sides have the other's public signature key; this may mean that a protocol using it might have the option of using Opaque as a certificate replacement (and processing the signatures using its own logic rather than using Sigma).  I do see two downsides; for one, both the client and the server have long-term public signature keys, and I don't see a clean way (apart from re-registration) to update those public keys.  In addition, Opaque is not Quantum Annoying (a single DLog by a passive attacker would allow a dictionary search) - the submitters tried to argue that wasn't important, see below why I disagree with that assessment.  Despite those two points, I believe that, in this case, the practical issues outweigh this lack of Quantum Annoyance and the rekeying difficulties.
More detailed review (and random thoughts):
SPAKE2:
In response to question 1, they did add an option that would allow M and N to be different for every single pair of peers; they also added an option that allows M=N.  I would further note that, because the Hash2Curve operation is on public data, including that operation does not add potential side channel vulnerabilities.  While this mitigates the vulnerability of solving one DLog problem breaks the system globally, it still cannot be considered fully "quantum annoying" (although it is better) - solving one discrete log problem (as an active attacker) or two discrete log problems (as a passive attacker) would still allow a dictionary attack (and in the passive case, also recover the shared secret on the session under attack).  One issue I have is that the draft gives no guidance to the protocol designer as to when the various options (fixed vs dynamic N, M; distinct N, M vs identical) should be used (and it can be assumed that if we don't give such guidance, the protocol designers will select the cryptographically worse option).
CPace and AuCPace:
In response to question 5, they suggested that a postquantum version of (Au)CPace might be able to be done using Isogenies.  I am personally skeptical about that - the chief issue is that the protocol receives a Ya/Yb value from the peer, and uses it to compute the shared secret.  An active attacker would be able to submit a malicious Ya/Yb value; if he selects a value that (after transformation by the honest peer) maps to a comparatively small set of values, then the attacker could guess the shared secret (and log in, even though he did not know the password).  Sanity checking these received values would be mandatory, and with isogenies there is no obvious way to do so.
One advantage of accepting both CPace and AUCPace would be so that a protocol that needs both would be able to take advantage of the commonality.  I personally don't expect protocols to use both a balanced and an augmented PAKE; I believe most protocols are either strictly peer-to-peer or strictly client-server (and hence this need not be a major consideration).
OPAQUE:
The Opaque paper emphasizes that, with Opaque, an attacker who managed to recover the client database would not be able to use precomputation to help recover the passwords; he would need to perform all the computations involved with the dictionary search after he has recovered the password file.  I don't believe that's that important (at least, with comparison to AuCPace).  With AuCPace, an attacker could use precomputation, however any such precomputation would be usable only against a single user on a single server.  So, the difference is that, in both cases, the attacker uses X time to recover a single password; it's just that in the AuCPace case, the attacker may choose to perform that computation beforehand; however that computation result cannot be reused to recover any other session (either on the same server, or the same user logging into a different one).  Given that the attacker doesn't get any time savings for attacking multiple logins, I don't see when the attacker performs the computation as that critical (hence I did not mention it above).
The submitters tried to argue that our current understanding of Quantum Annoyance isn't what's important, and that they are the only submission that can be made Quantum Resistant to store-and-decrypt-latter Quantum Attacks.  I disagree on both points.  For one, any protocol that we endorse will likely to continue to be used 20 years from now, and so Quantum Attacks that recover the password are a nontrivial concern (even though, as my review above states, perhaps not the overriding concern).  In addition, any PAKE can be made resistant to store-and-decrypt-latter attacks (by simply performing an additional Quantum Safe KEM at the end, authenticated by the PAKE shared secret).  I note that, for AuCPace (OPAQUE's sole competitor), this can be done in parallel with the Explicit Mutual Authentication step, and so might not cost you an addition pass.
I would be nice if they had a Quantum-Safe OPRF (which would allow the entire structure to be Quantum Safe); however, I am unaware of any such construction.
Also, my opinion of Question 5: although none of the candidates are currently directly translatable to postquantum primitives, I don't know if that's actually a big deal.  When the CFRG feels the need to propose a postquantum PAKE, I would suggest we would have another contest specifically for that purpose; at the very least, there exists https://eprint.iacr.org/2014/589.pdf as a balanced postquantum PAKE candidate.