[Cfrg] Nomination of AuCPace and CPace as balanced and augmented PAKE schemes
Björn Haase <bjoern.m.haase@web.de> Sun, 16 June 2019 22:08 UTC
Return-Path: <bjoern.m.haase@web.de>
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 864BD1200E9 for <cfrg@ietfa.amsl.com>; Sun, 16 Jun 2019 15:08:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.698
X-Spam-Level:
X-Spam-Status: No, score=-2.698 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=unavailable autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=web.de
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 vaBgTitreRrR for <cfrg@ietfa.amsl.com>; Sun, 16 Jun 2019 15:08:02 -0700 (PDT)
Received: from mout.web.de (mout.web.de [217.72.192.78]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 930FD120020 for <cfrg@irtf.org>; Sun, 16 Jun 2019 15:08:01 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1560722872; bh=BP6L/JRZ05LIDePImKGr9Q6Ont5CSuwTkYmdqMtAg94=; h=X-UI-Sender-Class:Subject:To:References:From:Date:In-Reply-To; b=WcJZlpE5un7jntDa4ehC99p0YfhpeSFl0IZIcoNTxbEGulk1wfvVZy8ftdlRQQzW2 Xw3USZGGE99ZSWVY7sTUWOCnsoQwhzs/jSFo50SdFb4BdTmVPzikumUzj7Vpc3LKX+ lE0DuANVWYReYs4ZUjkGpjhcjlFF3+tkYOsCfra0=
X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9
Received: from [192.168.2.161] ([178.2.114.231]) by smtp.web.de (mrweb102 [213.165.67.124]) with ESMTPSA (Nemesis) id 0LdVvS-1iJuTi0lSU-00injW; Mon, 17 Jun 2019 00:07:52 +0200
To: Nick Sullivan <nick=40cloudflare.com@dmarc.ietf.org>, cfrg@irtf.org
References: <CAFDDyk9RXZrBoQ0s0_cj_Q0PPYkaVjnx7voctz0TU8dL57B+1A@mail.gmail.com>
From: Björn Haase <bjoern.m.haase@web.de>
Message-ID: <561e4f0c-a044-f7ac-591e-46bc4ea076d7@web.de>
Date: Mon, 17 Jun 2019 00:07:53 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.7.1
MIME-Version: 1.0
In-Reply-To: <CAFDDyk9RXZrBoQ0s0_cj_Q0PPYkaVjnx7voctz0TU8dL57B+1A@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"; format="flowed"
Content-Transfer-Encoding: quoted-printable
X-Provags-ID: V03:K1:ZcIQxcROifoxGU961Smu8qaCGaFoaZ0f8eqJMQfFGn124bbaroQ EFYr41X8wOwDuz7dBOJV2poyXU6lQU55ztyu2I2rRQNqwJcPAkwF9J70+yCTLVYTwKAyb0F qbXxL2R559Tu74LEWglVcXXMxH9E2yNukqtiSb0czIhZOlchNjM6BrWFw1eONS5bCMj+8FB kE/46MVn+pEUO7I8jzfEw==
X-UI-Out-Filterresults: notjunk:1;V03:K0:BX0yXA8Ixfw=:CvgFljAt1iHkCdpreezKph zL0Dtxp85RMbKsJ6s0eyXHpI5kPfhkzr308T9VqmtYZx6N1dREEptXL7CAHfigQsS2pt7jOFa cNwPYjcir5kEr0RAaBFFH05c+/FSsrGsxRqFM7cMigLfVJXamz5dYe6TmTCAq6HpngZkHlFXm WyiYZhXWMuNiqkG+WKoLmb2WzgfdH5BxvdiY9KYmCqt/0+RJv4ktoISX6PJfxX/i39R4iAetO uXIq25VlR9kYyFjwxBYOPUOMQW7zCJ4jNgsm0+CsyLKnWUuKG1gZdRSceWTqSG62hqloriPsO hBUjSJtDmSVCfn335Cu41TWOZ1hdDZ4M44o0QynRHW8V/S9DZ8Z1KFLn1g27e/Yzl2aYAMP2f GGsWo0tsnC4iVk6137l9y5a2lseJvdLBIV/IF3vJ5D0mzGpWsDdIkkhGm7TXd1m4yjxVEeAdj O5Uq+DuWBtFjSo6+coKJeNn1RCP4IGoO9VqKnaer9iq3kGpcUDuFz7AHlIcxpjVP04EV1Mguk uEdYYrhBOzfaSZnlqHK4GPJOTibWvHSYpe+I/Stc1rU4NJjMe2DFeJH8YysvnO6glXRfeD9g3 BudrIeA/VRCqDkNdhSPBHCIc/GQSoQ+GAb2AZ2DH3Mpu89MvCJf8mYwUvu1U3mxWd2GhGkRMq f3+40hDoa3LHuqcp+GPQU2s+EXClLDMjRvVUv6eduW5u8XQPII2U8UGowH3GWe2qMvImTt+ip oOkMk2hBqDNFOKFs82b/YrlGaikWDo4hwbDDXhJdLeuh4g7Nh0a7m3aC/ZpitRAeg+K7KBS7X PXrTxB1/MKfYuIbB/Mun8vFgGWEi4hYDR0WT2HJmFPB43toqtDdNrfLSR0ensV7Bhh77kNNaT B7Z3K+0PAxHBgWNOj07jBOo8WJVLjdyEHt7mbPOWX59hXCHDHmvwuflHkFhvmxigl5m7hYZvz twGJPcNpr84Ae5OCCTTEl4pNUcYFyKbNKN54V5uR5hD2dH+dYZeZU
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/JrzdTUFj2oULmRtQ3Z3j5Tn4yT4>
Subject: [Cfrg] Nomination of AuCPace and CPace as balanced and augmented PAKE schemes
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: Sun, 16 Jun 2019 22:08:05 -0000
I would like to nominate the protocols AuCPace (augmented) and CPace (balanced) as candidates for the CFRG PAKE selection process. AuCPace is actually a SPEKE variant which incorporates all of the necessary modifications to SPEKE that are required for allowing for 1) a security proof in the UC framework in conjunction with 2) secure use also with elliptic curves of both, prime or non-prime order 3) efficient and patent-free constant-time implementation The protocol and the ideas underlying its construction is described in detail in the AuCPace paper [1] to be presented this year at CHES 2019 in Atlanta. In the following paragraphs I will try to boil down the essence and describe specific features. ####################################### Background of the AuCPace / CPace construction: 1.) On constrained devices the asymmetric crypto should be considered to be the most ressource-hungry and most challenging component in the security framework. Computational complexity was identified as one of the most important design objectives for real-world settings [2]. 2.) Regarding PAKE protocols, SPEKE-based constructions are known to provide the computationally most efficient solution by requiring only two exponentiations. [3] 3.) Since SPEKE used to be patented until very recently a number of patent-circumvention approaches such as PACE [4] or DragonFly were developed. This approach did result in larger computational complexity (e.g. PACE with "generic mapping" [5]) and/or implementation pitfalls (e.g. DragonFly [discussions on the CFRG list]). 4.) The SPEKE patents did expire recently. This allows for a larger desing space in comparison to what was available, e.g. at the times when SPAKE2 [7] and PACE [4] were conceived. ####################################### Special properties of AuCPace / CPace AuCPace/CPace should actually not be considered new designs but are merely a tailored combination of known features from other known constructions such as SPEKE[6], TBPEKE [3] and PACE [4]. It takes benefit of the larger design-space available after the SPEKE patent expiration for achieving the following main objectives: - A comprehensive proof of security in the UC framework for both, CPace and AuCPace, covering also "adaptive adversaries" - Computational efficiency, specifically regarding constrained servers - Ease-of-implementation and avoidance of implementation pitfalls According to the analysis in [1] AuCPace and CPace presentlly provide computationally-wise the most efficient solutions respectively for augmented and balanced PAKE, specifically for constrained servers. As a consequence the security proof relies on a random oracle (RO). Note that this assumption allows for a more efficient construction in comparison, e.g., J-PAKE. CPace (and AuCPace) offer the following particular benefits in comparison to other candidates, such as PAK and SPAKE2: - CPace does not rely on a trusted setup (such as nothing-upon-my-sleeves group elements with unkonwn discrete log). - CPace is perfectly symmetric, either side could take over the role of initiator / responder. - CPace is specifically designed and proven secure for use on elliptic curves with both, prime order and small co-factor - CPace could be implemented using x-coordinate-only scalar multiplications (restricting weak curve attacks to the curve's quadratic twist and allowing for simplified point verification on curves with twist-security) - CPace is optimized for reduced RAM requirements. E.g. there is no need for hashing and storing full transcripts of the protocol communication. Special properties of AuCPace include - Specific consideration of settings where several, e.g. redundant servers are expected to share the same passwords. As a consequence of this property, AuCPace does not form a "strong" augmented PAKE, i.e. it does not provide pre-computation-attack resistance, such as OPAQUE. - AuCPace considers the complexity introduced by the existance of more than one user (including the option of user-specific granted authorizations) and - AuCPace is specifically designed for use in conjunction with memory-hard password hashes, such as Argon2 or scrypt, even if the constrained servers themselves don't have the memory/computational resources for calculating state-of-the-art password hashes. - AuCPace features particularly small memory footprint for password verifiers and communication bandwidth. Both constructions (balanced/augmented) don't require explicit authentication, but allow for explicit authentication. ####################################### Notes: 1.) CPace and AuCPace are inteded to be used in combination with a Map2Curve primitive, but both could alternatively be instantiated in a TBPEKE [3]-like setting where Map2Curve is replaced by one additional scalar multiplication and point addition (see appendix B of [1]). In this optinal setting the - computational complexity is essentially increased by one exponentiation. - Trusted setup of two "nothing upon my sleeves" curve points with unknown discrete log becomes necessary (just as for SPAKE2) - the UC security proof only covers the setting of "static adversaries" In this "no Map2Curve" setting the performance should be considered somewhat equivalent to SPAKE2, while maintaining the properties of the composable UC proof and the advantages regarding x-coordinate-only DH and simplified point verification options. 2.) CPace and AuCPace are designed for security in a setting with an arbitrary number of concurrent sessions. For this purpose the security analysis was carried out in the UC framework. In the UC framework each such individual session needs to be uniquely identified by a session id (sid). The sid takes over a similar role to an assignment of a IP-Address and port number of server and client for a TCP client. If no network protocol layer is available that allows for unique identification of concurrent active sessions (e.g. by "port numbers" at client and server and a time-stamp of session establishment) one alternative option of establishment of the sid is an additional communication round used for establishing a common nonce. For this reason the required number of communication rounds for CPace / AuCPace depends on the properties of the underlying network protocols and the respective distinction of different concurrent parallel sessions. (Note that this specific technical property comes with any security analysis in the UC model and holds also for constructions such as OPAQUE). ####################################### References [1] "AuCPace: Efficient verifier-based PAKE protocol tailored for the IIoT" https://tches.iacr.org/index.php/TCHES/article/view/7384 [2] "Making Password Authenticated Key Exchange Suitable for Resource-Constrained Industrial Control Devices" https://link.springer.com/chapter/10.1007/978-3-319-66787-4_17 [3] "VTBPEKE: Verifier-based Two-Basis Password ExponentialKey Exchange" https://www.di.ens.fr/david.pointcheval/Documents/Papers/2017_asiaccsB.pdf [4] "Security Analysis of the PACE Key-Agreement Protocol" https://eprint.iacr.org/2009/624 [5] "Supplemental Access Control (PACE v2): Security Analysis ofPACE Integrated Mapping" https://eprint.iacr.org/2011/058.pdf [6] "Strong Password-Only Authenticated Key Exchange" https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.4798 [7] "SimplePassword-BasedEncryptedKeyExchangeProtocols" https://www.di.ens.fr/~mabdalla/papers/AbPo05a-letter.pdf
- [Cfrg] Proposed PAKE Selection Process Nick Sullivan
- Re: [Cfrg] Proposed PAKE Selection Process William Whyte
- Re: [Cfrg] Proposed PAKE Selection Process Stephen Farrell
- Re: [Cfrg] Proposed PAKE Selection Process Stanislav V. Smyshlyaev
- Re: [Cfrg] Proposed PAKE Selection Process Hao, Feng
- [Cfrg] Nomination of AuCPace and CPace as balance… Björn Haase
- Re: [Cfrg] Proposed PAKE Selection Process Crockett, Eric
- Re: [Cfrg] Proposed PAKE Selection Process steve
- Re: [Cfrg] Proposed PAKE Selection Process Hugo Krawczyk
- Re: [Cfrg] Proposed PAKE Selection Process Björn Haase