[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