Michel Abdalla
email: michel.abdalla@gmail.com

Björn Haase
email: bjoern.haase@endress.com

Julia Hesse

Security Analysis of CPace

In response to standardization requests regarding password-authenticated key exchange (PAKE) protocols, the IRTF working group CFRG has setup a PAKE selection process in 2019, which led to the selection of the CPace protocol in the balanced setting, in which parties share a common password. In subsequent standardization efforts, the CPace protocol further developed, yielding a protocol family whose actual security guarantees in practical settings are not well understood. In this paper, we provide a comprehensive security analysis of CPace in the universal composability framework. Our analysis is realistic in the sense that it captures adaptive corruptions and refrains from modeling CPace's Map2Pt function that maps field elements to curve points as an idealized function. In order to extend our proofs to different CPace variants optimized for specific elliptic-curve ecosystems, we employ a new approach which represents the assumptions required by the proof as libraries accessed by a simulator. By allowing for the modular replacement of assumptions used in the proof, this new approach avoids a repeated analysis of unchanged protocol parts and lets us efficiently analyze the security guarantees of all the different CPace variants. As a result of our analysis, all of the investigated practical CPace variants enjoy adaptive UC security.

Introduction

Security analysis and efficient implementation of cryptographic protocols are often split into separate working groups. As a result, subtle differences between the actually implemented and analyzed protocols easily emerge, for example when implementors slightly tweak the protocol to improve efficiency. An example where particularly aggressive optimizations for efficiency are implemented on the protocol level is CPace as specified in current internet drafts [START_REF] Haase | CPace, a balanced composable PAKE[END_REF][START_REF] Haase | AuCPace: Efficient verifier-based PAKE protocol tailored for the IIoT[END_REF]. CPace is a passwordauthenticated key exchange protocol (PAKE) [START_REF] Bellovin | Encrypted key exchange: Password-based protocols secure against dictionary attacks[END_REF], which allows two parties to establish a shared cryptographic key from matching passwords of potentially low entropy. PAKEs are extremely useful for establishing secure and authenticated communication channels between peers sharing short common knowledge. The common knowledge could be a PIN typed into different wearables in order to pair them, sensor readings recorded by several cars in order to create an authenticated platoon or a security code manually entered by an admin to connect her maintenance laptop with a backbone router.

On a high level, CPace works as follows. Given a cyclic group G, parties first locally and deterministically compute a generator g ← Gen(pw), g ∈ G from their passwords in a secure way, so that g reveals as little information about the password as possible. Then, both parties perform a Diffie-Hellman key exchange by choosing secret exponents x and y, respectively, exchanging g x and g y and locally compute K = (g x ) y = (g y ) x . The final key is then computed as the hash of K together with session-identifying information such as transcript. The currently most efficient implementations of the above blueprint protocol use elliptic curve groups of either prime or composite order. To securely compute the generator, the password is first hashed to the finite field F q over which the curve is constructed, and then mapped to the curve by a map called Map2Pt. Depending on the choice of curve, efficiency tweaks such as simplified point verification on curves with twist security, or computation with only x-coordinates of points can be applied [START_REF] Haase | AuCPace: Efficient verifier-based PAKE protocol tailored for the IIoT[END_REF][START_REF] Haase | CPace, a balanced composable PAKE[END_REF]. Unfortunately, until today, it is not clear how these modifications impact security of CPace, and whether the protocol can be proven secure without assuming (Map2Pt • H) to be a truly random function.

A short history of CPace. In 1996, Jablon [START_REF] Jablon | Strong password-only authenticated key exchange[END_REF] introduced the SPEKE protocol, which performs a Diffie-Hellman key exchange with generators computed as g ← H G (pw), i.e. using a function H G hashing directly to the group. Many variants of SPEKE have emerged in the literature since then, including ones that fixed initial security issues of SPEKE. Among them, the PACE protocol [START_REF]Advanced security mechanism for machine readable travel documents (extended access control (EAC), password authenticated connection establishment (PACE), and restricted identification (RI))[END_REF][START_REF] Bender | Security analysis of the PACE key-agreement protocol[END_REF] aims at circumventing direct hashing onto the group with an interactive Map2Pt protocol to compute the password-dependent generators. From this, CPace [START_REF] Haase | AuCPace: Efficient verifier-based PAKE protocol tailored for the IIoT[END_REF] emerged by combining the best properties of PACE and SPEKE, namely computing the generator without interaction while avoiding the need to hash directly onto the group. More precisely, password-dependent generators are computed as g ← Map2Pt(H(pw)). In 2020, the IRTF working group CFRG has chosen CPace as the recommended protocol for (symmetric) PAKE.

Prior work on the security of CPace. Bender et al. [START_REF] Bender | Security analysis of the PACE key-agreement protocol[END_REF] conducted a game-based security analysis of the explicitly authenticated PACE protocol variants used in travel documents. Their work focusses on different variants of interactive Map2Pt constructions and hence does not allow for any conclusions about CPace which uses a (non-interactive) function Map2Pt.

Static security of CPace, including function Map2Pt and some implementation artifacts such as cofactor clearing, was formally analyzed in [START_REF] Haase | AuCPace: Efficient verifier-based PAKE protocol tailored for the IIoT[END_REF]. Their work is the first to attempt a formalization of Map2Pt that allows for a security analysis. However, their proof was found to be insufficient by reviews done during the CFRG selection process [START_REF] Tackmann | Updated review of PAKEs[END_REF][START_REF] Hesse | Review of (security of) remaining candidates. Posting to the CFRG mailing list[END_REF], and indeed, the claimed security under the plain computational Diffie-Hellman assumption seems to be difficult to achieve. Besides these issues, their work does not consider adaptive corruptions and implementation artifacts such as twist security or single-coordinate representations.

Abdalla et al. [START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF] analyzed static security of several EKE [START_REF] Bellovin | Encrypted key exchange: Password-based protocols secure against dictionary attacks[END_REF] and SPEKE variants in the UC framework, including SPAKE2 [START_REF] Abdalla | Simple password-based encrypted key exchange protocols[END_REF] and TBPEKE [START_REF] Pointcheval | VTBPEKE: Verifier-based two-basis password exponential key exchange[END_REF]. They indicate that their proof for TBPEKE could be extended to CPace with generators computed as H G (pw) (i.e., without function Map2Pt) if the protocol transcript and password-dependent generator is included in the final key derivation hash. However, in practice it is desirable to avoid unnecessary hash inputs for efficiency reasons and protection against side-channel attacks.

In a concurrent work, Abdalla et al. [START_REF] Abdalla | Algebraic adversaries in the universal composability framework[END_REF] formalized the algebraic group model within the UC framework and proved that the SPAKE2 and CPace protocols are universally composable in the new model with respect to the standard functionality for password-based authenticated key exchange in [START_REF] Canetti | Universally composable password-based key exchange[END_REF]. Stebila and Eaton [START_REF] Eaton | The "quantum annoying" property of passwordauthenticated key exchange protocols[END_REF] provided a game-based analysis of CPace in the generic group model. As in [START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF], these further studies do not deal with adaptive security and only consider a basic version of CPace without Map2Pt and without considering any implementation artifacts.

The above analyses demonstrate that a basic version of CPace, which essentially is a Diffie-Hellman key exchange computed on hashed passwords instead of a public generator, is UC-secure if the attacker is restricted to static corruptions. Unfortunately, this leaves many open questions. Does this basic protocol remain (UC-)secure if we use generator Map2Pt(H(pw)) instead, as it is done in practice to avoid direct hashing onto elliptic curves? Can the protocol handle adaptive corruptions? Which impact on security do implementation artifacts have, such as co-factor clearing on a composite-order curve group, or single-coordinate representation as used in, e.g., TLS1.3? Can we reduce hash inputs in order to make the protocol less prone to side-channel attacks? Altogether, it turns out the security of the actually implemented CPace protocol is not well understood.

Our Contributions. In this paper, we provide the first comprehensive security analysis of the CPace protocol that applies also to variants of CPace optimized for usage with state-of-the-art elliptic curves. We identify the core properties of the deterministic Map2Pt function that allow to prove strong security properties of CPace. Crucially, we restrict the use of random oracles to hash functions only and refrain from modeling Map2Pt as an idealized function, as it would not be clear how to instantiate it in practice. We show that, using some weak invertibility properties of Map2Pt that we demonstrate to hold for candidate implementations, CPace can be proven secure under standard Diffie-Hellman-type assumptions in the random-oracle model and with only minimal session-identifying information included in the final key derivation hash. Our security proof captures adaptive corruptions and weak forward secrecy 1 and is carried out in the Universal Composability (UC) framework, which is today's standard when analyzing security of password-based protocols. Our work provides the first evidence that SPEKE-type protocols can handle adaptive corruptions.

We then turn our attention to modifications of CPace and, for each modification individually, state under which assumptions the security properties are preserved. In more detail, our analysis captures the following modifications.

• Using groups of composite order c•p, where p is a large prime and c is a small cofactor coprime to p. • Realize Gen(pw) generator calculations using Map2Pt with either map-twice-and-add strategy or as single execution. • Using single-coordinate-only representations of elliptic-curve points in order to speed up and facilitate implementation. • Avoiding computationally costly point verification on curves with secure quadratic twists such as Curve25519 [START_REF] Daniel | Curve25519: New Diffie-Hellman speed records[END_REF]. To demonstrate the security of these variants, we take a new approach that saves us from a repeated analysis of unchanged parts of CPace. Namely, we implement the CDH-type cryptographic assumptions required by CPace as libraries which a simulator can access. This allows for modular replacement of assumptions required in the security proof, and lets us efficiently analyze all the different CPace variants' security guarantees. We believe that this new proof technique might be of independent interest in particular for machine-assisted proving, since reductions are captured in code instead of textual descriptions only.

As a side contribution, we identify a common shortcoming in all UC PAKE security definitions in the literature [START_REF] Canetti | Universally composable password-based key exchange[END_REF][START_REF] Jarecki | OPAQUE: An asymmetric PAKE protocol secure against pre-computation attacks[END_REF][START_REF] Hesse | Separating symmetric and asymmetric password-authenticated key exchange[END_REF][START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF], which impacts the suitability of these definitions as building blocks in higher-level applications. Namely, all these definitions allow a malicious party to learn the shared key computed by an honest party without knowing her password. We strengthen the definition to prevent such attacks, and demonstrate with our analysis of CPace that our fix yields a security definition that is still met by PAKE protocols.

In conclusion, our results demonstrate that CPace enjoys strong provable security guarantees in a realistic setting, and this holds for all its variants that have been proposed in the different elliptic-curve ecosystems.

Technical overview of our results

Map2Pt's impact on security. At its core, the CPace protocol is a SPEKE-type protocol, meaning that it is simply a Diffie-Hellman key exchange (DHKE) computed with a generator that each party individually computes from her password. Intuitively, the most secure choice is to compute g ← H G (pw), and indeed this was proven secure [START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF][START_REF] Abdalla | Algebraic adversaries in the universal composability framework[END_REF] conditioned on H being a perfect hash function (or, put differently, a random oracle (RO)). However, DHKE-type protocols are most efficient when implemented on elliptic-curve groups, and it is not known how to efficiently hash directly onto such groups. Recent standardization efforts by the CFRG [START_REF] Faz-Hernandez | Hashing to elliptic curves[END_REF] show that, in practice, one would always first hash to the finite field F q over which the curve is constructed, and then map the field element to the curve G using some curve-specific mapping Map2Pt : F q → G. Hence, the generator in CPace can be assumed to be computed as g ← Map2Pt(H(pw)) for a H being a hash function such as SHA-3.

In order to analyze how the function Map2Pt impacts CPace's security, it is obviously not helpful to abstract Map2Pt • H as a truly random function. In a first attempt to analyze under which properties of Map2Pt CPace remains secure, Haase et al. [START_REF] Haase | AuCPace: Efficient verifier-based PAKE protocol tailored for the IIoT[END_REF] assumed Map2Pt to be a bijection. Intuitively, a bijective Map2Pt function does not "disturb" the "nice" distribution of the prepended hash function, and in particular does not introduce any collisions. Besides the known shortcomings in their conducted analysis (the claimed security under CDH does not seem to hold, and their proof lacks an indistinguishability argument [START_REF] Tackmann | Updated review of PAKEs[END_REF][START_REF] Hesse | Review of (security of) remaining candidates. Posting to the CFRG mailing list[END_REF]), it does not cover non-bijective mappings on widely used short-weierstrass curves such as NIST P-256. Hence, in our work we refrain from assuming Map2Pt to be a bijection. Instead, we introduce a property of probabilistic invertibility, which demands that, given an element g in the group G, we can efficiently compute all preimages h ∈ F q such that Map2Pt(h) = g. On a high level, this invertibility property will aid the simulation of CPace since it allows to "tightly" link a group element g to a previously computed hash h and thus recognize collisions efficiently. Here, tightly/efficiently means without iterating over all hash queries in the system. We demonstrate that all mappings used in practice [START_REF] Faz-Hernandez | Hashing to elliptic curves[END_REF] are probabilistically invertible. As a result, we conclude that CPace implemented with current mappings enjoys strong security guarantees.

Adaptive security. Just like any other PAKE protocol, CPace comes with a large likelihood for idling. Indeed, in practice it will most likely be the same person who jumps between the two devices running the PAKE, to manually enter the same password, PIN or code. This gives room for attackers to corrupt devices during the run of the protocol, and hence calls for analyzing security of CPace in the presence of adaptive corruptions. To our knowledge, there is no proof of adaptive security for any SPEKE-type protocol in the literature. In this work, we closely investigate CPace's guarantees under adaptive corruptions and come to an indeed surprising conclusion:

CPace enjoys adaptive UC security under the same DH-type assumptions that seem required for static security.

The challenge of proving adaptive security lies in the need to reveal suitable secret values computed by a previously honest party during the run of the protocol. For CPace, these are the secret Diffie-Hellman exponents x, y randomly chosen by parties. A bit simplified, our idea is to start the simulation of an honest party with g z for a generator g of group G and randomly chosen exponent z, and hence independent of the actual (unknown) password used by that party. Upon corruption, the simulator learns pw and looks up the corresponding hash value g r = H(pw) for which it knows r -1 thanks to H being modeled as a random oracle. This allows the simulator to compute the "actual" secret exponent y ← zr -1 that the simulated party would have used if started with actual password pw. Crucially, no additional assumptions or secure erasures are required and, as we demonstrate in the body of our paper, this simplified strategy still works when generators are computed using Map2Pt • H. Altogether, our analysis shows that CPace enjoys UC-security under adaptive corruptions.

Falsifiable assumptions and a new approach to simulation-based proofs. A falsifiable assumption can be modeled as an interactive game between an efficient challenger and an adversary, at the conclusion of which the challenger can efficiently decide whether the adversary won the game [START_REF] Gentry | Separating succinct non-interactive arguments from all falsifiable assumptions[END_REF]. Most standard cryptographic assumptions such as CDH, DDH, RSA, and LWE are falsifiable. An example of a non-falsifiable assumption is the gap simultaneous Diffie-Hellman assumption, which was used in prior CPace security analyses [START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF][START_REF] Abdalla | Algebraic adversaries in the universal composability framework[END_REF] and features a full DDH oracle that cannot be efficiently implemented by the challenger. Intuitively, the DDH oracle seems inherent for proving UC security of CPace since the attacker (more detailed, the distinguishing environment) determines passwords pw used by honest parties and also receives their outputs, which is the final key K. More detailed, the attacker can deterministically compute the generator G used by an honest party from only pw, and it also receives the honest party's message g x . The attacker can now enforce the final key to be a DDH tuple K = g xy by simply sending g y to the honest party (we omit the final key derivation hash in this explanation for simplicity). Hence, to correctly simulate the final key output by an honest party under attack, the simulator relies on a DDH oracle. However, we observe that this oracle can be limited to specific inputs g, g x that the attacker cannot influence. This turns out to be an important limitation, because the restricted DDH oracle DDH(g, g x , •, •) can actually be implemented efficiently using knowledge of trapdoor exponents r, r -1 of g. Thus, our conclusion is that CPace's security holds under falsifiable DH-type assumptions.

As another contribution, we define falsifiable assumptions as efficiently implementable libraries that a simulator can call. The advantage of this approach is that reductions to the underlying assumptions are integrated in the simulator's code, which will hence abort and detect itself whenever a query to the library solves the underlying hard problem. This makes reduction strategies readable from simulator codes and hence opens a new path for automatic verification of simulation-based proofs. While we demonstrate this only to work for proofs conducted in the UC framework and when using variants of strong CDH, we conjecture that our approach can be used for simulation-based proofs in arbitrary frameworks whenever only falsifiable assumptions are used.

Minimal protocol design. For optimal protection against side-channel attacks, we would like to have parties touch their passwords as little as possible. Optimally, passwords are only used to compute the generator of the DHKE. Unfortunately, in simulation-based frameworks a security proof often crucially relies on hashing of secrets, and indeed previous CPace security analysis has relied on the password being included in the final key derivation hash [START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF]. In this work we ask what the minimal set of protocol-related values is that needs to be included in both hash functions used in CPace. Perhaps surprisingly, we find that CPace's security can be proven when (1) the password hash does not get any additional inputs and (2) the final key derivation hash is over session-specific values and the Diffie-Hellman key. Regarding (1), we observe that the simulation strategy (described above for adaptive corruptions) works even if the generator g chosen by the simulator is used to simulate multiple instances of CPace, and where different parties use the same password: Choosing fresh secret exponents z A for each such simulated party A ensures that all the revealed exponents z A r -1 are still uniformly distributed. Regarding (2), our simulation simply does not need to learn the password from an adversarial key derivation hash query: The simulator simply reads the simulated parts g z and adversarial part Y of the transcript from the hash query and checks consistency of the query's format by checking whether it is a DDH tuple with respect to each trapdoor generated upon password hashing. Since there can be only a polynomial number of such queries, this simulation strategy is tight and efficient and saves us from hashing the password another time.

Implementation artifacts. Depending on the type of curve CPace is deployed in, the implementation will vary in certain aspects for which it is not clear how they will impact CPace's security. By adopting the security analysis to capture actual Map2Pt mappings used in practice we already demonstrated how to deal with the probably most important such artifact above. Closely related to this, we also analyze security of CPace when implemented on curves of composite order p • c with a small co-factor c, which needs to be "cleared" in order to ensure that parties use generators of the large subgroup. We can integrate this modification by chaining Map2Pt with a co-factor clearing function and by demonstrating that the resulting mapping is still probabilistically invertible. Technically, we "lift" our proof of security w.r.t simple Map2Pt described above by letting the simulator call a co-factor clearing class that ensures that simulated values will remain in the large subgroup.

A typical implementation pitfall is incorrectly implemented group-membership verification. As such a failure easily remains unnoticed, optimized resilient protocols such as X25519 and X448 [START_REF] Langley | Elliptic Curves for Security[END_REF] have been suggested for the conventional Diffie-Hellman use-case. We believe that we are the first to formalize the exact hardness assumption, the twist CDH problem sTCDH, under which the claimed resilience regarding group membership omission is actually justified. We show that under the sTCDH assumption, resilience with respect to incorrectly implemented point verification can also be achieved for CPace, when instantiated using single-coordinate Montgomery ladders on so-called "twist-secure" [START_REF] Daniel | SafeCurves: Choosing safe curves for elliptic-curve cryptography. Definition of Twist security[END_REF] elliptic curves. For details on how to deal with other implementation artifacts we refer the reader to Section 6 in the main body of the paper.

Roadmap. We introduce the PAKE security model in Section 2 and hardness assumptions and requirements for Map2Pt in Section 3. Details of the CPace protocol are in Section 4. Then we analyse CPace, first using a simplified CPace in Section 5 (modeling the map as random-oracle) and then extending the analysis to real-world instantiations using actually deployed mapping constructions, composite-order groups, details on twist security and single-coordinate representations in Section 6. Full proofs (Appendix A), a description of issues with previous UC PAKE functionalities (Appendix C) and implementation recommendations (Appendix G) can be found in the appendices.

PAKE Security Model

We use the Universal Composability (UC) framework of Canetti [START_REF] Canetti | Universally composable security: A new paradigm for cryptographic protocols[END_REF] to formulate security properties of CPace. For PAKE, usage of the simulation-based UC framework comes with several advantages over the game-based model for PAKE introduced by Bellare et al. [START_REF] Bellare | Authenticated key exchange secure against dictionary attacks[END_REF]. Most importantly, UC secure PAKE protocols preserve their security properties in the presence of adversarially-chosen passwords and when composed with arbitrary other protocols. Originally introduced by Canetti et al. [START_REF] Canetti | Universally composable password-based key exchange[END_REF], the ideal functionality F pwKE for PAKE (depicted in Fig. 1) is accessed by two parties, P and P , who both provide their passwords. F pwKE then provides both parties with a uniformly random session key if passwords match, and with individual random keys if passwords mismatch. Since an adversary can always engage in a session and guess the counterpart's password with non-negligible probability, F pwKE must include an adversarial interface TestPwd for such guesses. Crucially, only one guess against every honest party is allowed, modeling the fact that password guessing is an online attack and cannot be used to brute-force the password from a protocol's transcript. We refer the reader to [START_REF] Canetti | Universally composable password-based key exchange[END_REF] for a more comprehensive introduction to the PAKE functionality.

An ideal functionality for the SPEKE protocol family. Unfortunately, F pwKE is not suitable to analyze SPEKE-like PAKE protocols such as CPace, where session keys are computed as hashes of Diffie-Hellman keys (and possibly parts of the transcript). The reason is that F pwKE 's TestPwd interface allows password guesses only during a protocol run, which requires a simulator to extract password guesses from the protocol's transcript. When the final output is a hash, the adversary might postpone its computation, keeping information from the simulator that is required for password extraction. To circumvent these issues, recently a "lazy-extraction PAKE" functionality F lePAKE was proposed and shown useful in the analysis of SPEKE-like protocols by Abdalla et al. [START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF]. F lePAKE , which we also depict in Fig. 1, allows either one online or one offline password guess after the key exchange was finished. One might argue that usage of keys obtained from F lePAKE is never safe, since the adversary might eventually extract the key from it at any later point in time. This however can be easily prevented by adding a key confirmation round, which keeps an adversary from postponing the final hash query and guarantees perfect forward secrecy [START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF]. We refer the reader to [START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF] for a thorough discussion of F lePAKE .

Our adjustments to F lePAKE . The main difference between our F lePAKE and all PAKE functionalities from the literature [START_REF] Canetti | Universally composable password-based key exchange[END_REF][START_REF] Jarecki | OPAQUE: An asymmetric PAKE protocol secure against pre-computation attacks[END_REF][START_REF] Hesse | Separating symmetric and asymmetric password-authenticated key exchange[END_REF][START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF] is that we remove a shortcoming that rendered these functionalities essentially useless as building blocks for higher-level applications. More detailed, we remove the ability of the adversary to determine an honest party's output key in a corrupted session. The change can be seen in Fig. 1, where the dashed box shows the weakening that we simply omit in our version of F lePAKE . In reality, nobody would want to use a PAKE where an adversary can learn (even set) the key of an honest party without knowing the honest party's password. This is not what one would expect from an authenticated key exchange protocol. In Appendix C we explain why existing PAKE protocols can still be considered secure, but also provide an illustrating example how this shortcoming hinders usage of PAKE functionalities in modular protocol analysis. In this paper, we demonstrate that CPace can be proven to protect against such attacks.

We also make two minor adjustments, which are merely to ease presentation in this paper. Namely, we omit roles since we analyze a protocol where there is no dedicated initiator, and we add an explicit interface for adaptive corruptions. The latter interface can only be asked upon getting instructed to do so by the environment.

How many keys can a PAKE functionality exchange? All PAKE functionalities in Fig. 1 produce only a single key for a single pair of parties P, P . This can be seen from the NewSession interface, which takes action only upon the first such query (from any party P) and the corresponding second query by the indicated counterparty P . The motivation behind this design choice is simplicity in the security analysis: one can prove security of a PAKE protocol for only a single session, and then run arbitrary many copies of the PAKE functionality to exchange arbitrarily many keys (between arbitrary parties). Consequently, by the UC composition theorem, replacing all those copies with the PAKE protocol that provably realizes the single-session F pwKE is at least as secure.

On party authentication. The PAKE functionalities from Fig. 1 require the party identifier of the counter party as input. In case of a mismatch (e.g., Alice wants to exchange a key with Bob, but Bob wants to exchange with Charlie), in an unattacked session, the functionalities' NewKey interface ensures that both parties obtain random keys. In case of the adversary playing a man in the middle, if he guesses both passwords correctly, the adversary can make the two parties output matching keys regardless of the parties' intentions who they want to exchange a key with.

Preliminaries

Notation

With ← R we denote uniformly random sampling from a set. With oc(X, Y ) we denote ordered concatenation, i.e., oc(X, Y ) = X||Y if X ≤ Y and oc(X, Y ) = Y ||X otherwise. We use multiplicative notation for the group operation in a group G and hence write, e.g., g • g = g2 for an element g ∈ G. I G denotes the neutral element in G. To enhance readability, we sometimes break with the convention of denoting group elements with small letters and write X := g x . We denote by G m a subgroup of G of order m, and with Ḡ we denote the quadratic twist of elliptic curve group G. Throughout the paper, we use λ as security parameter 2 .

Cryptographic assumptions

The security of CPace is based on the hardness of a combination of strong and simultaneous Diffie-Hellman problems. To ease access to the assumptions, we state them with increasing complexity. Definition 3.1 (Strong CDH problem (sCDH) [START_REF] Abdalla | The oracle Diffie-Hellman assumptions and an analysis of DHIES[END_REF]). Let G be a cyclic group with a generator g and (X = g x , Y = g y ) sampled uniformly from (G \ {I G }) 2 . Given access to oracles DDH (g, X, •, •) and DDH (g, Y, •, •), provide K such that K = g xy .

Session initiation

On (NewSession, sid , P, P , pw) from P, send (NewSession, sid , P, P ) to A. In addition, if this is the first NewSession query, or if this is the second NewSession query and there is not yet a record (sid , P, * , * ), then record (sid , P, P , pw) and mark this record fresh.

Active attack

• On (TestPwd, sid , P, pw * ) from A, if ∃ a fresh record sid , P, P , pw, • then:

-If pw * = pw then mark it compromised and return "correct guess";

-If pw * = pw then mark it interrupted and return "wrong guess".

• On (RegisterTest, sid , P) from A, if ∃ a fresh record sid , P, P , • then mark it interrupted and flag it tested.

• On (LateTestPwd, sid , P, pw * ) from A, if ∃ a record sid , P, P , pw, K marked completed with flag tested then remove this flag and do:

-If pw * = pw then return K to A;

-If pw * = pw then return K $ ←R {0, 1} λ to A.

Key generation

On (NewKey, sid , P, K * ) from A, if ∃ a record sid , P, P , pw not marked completed then do:

• If the record is compromised, or either P or P is corrupted, then K := K * .

• If the record is fresh and ∃ a completed record sid , P , P, pw, K that was fresh when P output (sid , K ), then set K := K . • In all other cases pick K ←R {0, 1} λ . Finally, append K to record sid , P, P , pw , mark it completed, and output (sid , K) to P.

Adaptive corruption

On (AdaptiveCorruption, sid , P) from A, if ∃ a record sid , P, P , pw then:

• if (sid , K) was output to P, send (sid , P , pw, K) to A;

• otherwise send (sid , P , pw, ⊥) to A. We note that sCDH is a weaker variant of the so-called gap-CDH assumption, where the adversary has access to "full" DDH oracles with no fixed inputs. Next we provide a stronger variant of sCDH where two CDH instances need to be solved that involve a common, adversarially chosen element. Definition 3.2 (Strong simultaneous CDH problem (sSDH)). Let G be a cyclic group and (X, g 1 , g 2 ) sampled uniformly from (G \ {I G }) 3 . Given access to oracles DDH (g 1 , X, •, •) and DDH (g 2 , X,

•, •), provide (Y, K 1 , K 2 ) ∈ (G \ {I G }) × G × G s. th. DDH (g 1 , X, Y, K 1 ) = DDH (g 2 , X, Y, K 2 ) = 1
As a cryptographic assumption sSDH above is justified since sSDH is implied by the gap simultaneous Diffie-Hellman assumption [START_REF] Pointcheval | VTBPEKE: Verifier-based two-basis password exponential key exchange[END_REF][START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF], which allows for unlimited (i.e., with no fixed input) access to a DDH oracle. Lastly, we state a variant of the sSDH assumption where generators are sampled according to some probability distribution. Looking ahead, we require this variant since in CPace parties derive generators by applying a map which does not implement uniform sampling from the group. We state the non-uniform variant of sSDH for arbitrary probability distributions and investigate its relation to "uniform" sSDH afterwards.

With Clearly, U G\{I G } -sSDH is equivalent to sSDH. We show that hardness of uniform and nonuniform sSDH are equivalent given that the distribution allows for probabilistic polynomial time (PPT) rejection sampling, which we now formalize. Definition 3.4 (Rejection sampling algorithm for (G, D G )). Let G be a group and D G be a probability distribution on G. With D G (g) we denote the probability for point g. Let RS be a probabilistic algorithm taking as input elements g ∈ G and outputting ⊥ or a value =⊥. Then RS is called a rejection sampling algorithm for (G, D G ) if there is a scaling factor k such that P r[RS(g

) =⊥] = k • D G (g) for g ∈ G.
Informally RS is a probabilistic algorithm which accepts (output different from ⊥) or rejects (output ⊥) a candidate point. When queried multiple times on the same input g ∈ G, the probability that g will be accepted or rejected models a scaled distribution that is proportional to D G . In this paper, we are interested in rejection samplers with "good" acceptance rate, such that they can be efficiently used to sample elements from the scaled distribution. We formalize the acceptance rate as follows. Definition 3.5 (Acceptance rate of a rejection sampler for (G, D G )). Let G be a group and D G be a probability distribution on G. Let RS be a rejection sampling algorithm for (G, D G ). Let g i ∈ G be a sequence of m uniformly drawn points and r i = RS(g i ). Then RS is said to have an acceptance rate of (1/n) if the number of accepted points with r i =⊥ converges to m/n when m → ∞.

Using these definitions, we are able to prove that given some assumptions on the distribution D G hardness of sSDH and D G -sSDH are equivalent up to the additional PPT computational effort for the rejection sampling algorithm. Proof. sSDH hard ⇒ D G -sSDH hard: Given an adversary B D G -sSDH against D G -sSDH with non-negligible success probability ν, we show how to construct an adversary A sSDH . On receiving an sSDH-challenge (X, g 1 , g 2 ), first note that X is uniformly sampled from G \ {I G }. A sSDH uniformly samples r, s ∈ Z p until RS(g r 1 ) =⊥ and RS(g s 2 ) =⊥, which requires 2n calls to RS on average.

A sSDH runs B D G -sSDH on input (X, g r 1 , g s 2 )
. If B queries DDH(g r 1 , X, Z, L), A queries his own oracle with DDH(g 1 , X, Z, L 1/r ) and relays the answer to B (queries g s 2 are handled analogously). On receiving

(Y, K 1 , K 2 ) from B D G -sSDH , A sSDH provides (Y, K 1/r 1 , K 1/s 2 ) as solution in his sSDH experiment. As RS is a rejection sampler for D G , (X, g r 1 , g s 2 )
is a random D G -sSDH challenge, and thus B solves it with probability ν. If B provides a solution, then A sSDH succeeds in solving his own challenge unless g r 1 or g s 2 = I G or g r 1 = g s 2 which occurs at most with probability (2D G (I G ) + 1/p). As RS executes in PPT, A sSDH is PPT, uses (2n) calls to RS on average and succeeds with probability

ν(1 -2D G (I G ) -1/p), which is non-negligible since ν is.
sSDH hard ⇒ D G -sSDH hard: Given an adversary A sSDH against sSDH with non-negligible probability µ we show how to construct a D G -sSDH adversary B D G -sSDH . On receiving a D G -sSDH challenge (X, g 1 , g 2 ), B samples r, s ∈ Z p \ 0 and starts A sSDH on input (X, g r 1 , g s 2 ). DDH oracle queries are handled the same as above. On receiving

(Y, K 1 , K 2 ) from A sSDH , B provides (Y, K 1/r 1 , K 1/s
2 ) as solution to his own challenge. If A is successful, then B succeeds unless either g 1 or g 2 = I G or g r 1 = g s 2 which occurs at most with probability (2D

G (I G ) + 1/p). Thus, B is a PPT adversary against D G -sSDH succeeding with non-negligible probability µ(1 -2D G (I G ) -1/p).
Informally, the assumptions sSDH and D G -sSDH become equivalent if stepping over an element that gets accepted in the sampling process becomes sufficiently likely for a randomly drawn sequence of candidates. Secondly, the probability of accidentally drawing the neutral element from D G needs to be negligible.

Transforming passwords to points on an elliptic curve

The generators of the Diffie-Hellman exchange in CPace are computed using a deterministic mapping function Gen(pw). For a given curve group G over a field F q , Gen(pw) is calculated with the help of either one (Gen 1MAP ) or two (Gen 2MAP ) invocations of a function Map2Pt G : F q → G and a hash function H 1 hashing to F q . For the sake of shortened notation, we will drop the G subscript where the group is obvious from the context. In both cases, security of CPace relies on Map2Pt meeting the requirements from this section. Informally, we first require Map2Pt to be "invertible". That is, for any point on the image of the map, there must be an efficient algorithm that outputs all preimages in F q of Map2Pt G for a given group element g. We use the notation Map2Pt G .PreImages(g). Details on how such an inversion algorithm can be efficiently implemented for various elliptic curve groups are given in [START_REF] Faz-Hernandez | Hashing to elliptic curves[END_REF][START_REF] Daniel | Elligator: ellipticcurve points indistinguishable from uniform random strings[END_REF][START_REF] Brier | Efficient indifferentiable hashing into ordinary elliptic curves[END_REF][START_REF] Hamburg | Indifferentiable hashing from elligator 2[END_REF] and references therein. Secondly, a bound for the maximum number of preimages n max that Map2Pt G maps to the same element must be known and this n max bound needs to be small (we use the notation Map2Pt G .n max for the bound that applies for a given Map2Pt G function and group G). This is needed in order to construct a rejection sampling algorithm whose acceptance rate must depend on n max . Definition 3.7. Let G be a group of points on an elliptic curve over a field F q . Let Map2Pt : F q → G be a deterministic function. Then Map2Pt(•) is called probabilistically invertible with at most n max preimages if there exists a probabilistic polynomial-time algorithm (r 1 , . . . , r ng ) ← Map2Pt.PreImages(g) that outputs all n g values r i ∈ F q such that g = Map2Pt(r i ) for any g ∈ G; and ∀g ∈ G, n max ≥ n g ≥ 0.

For a map Map2Pt that fulfills the previous definition with a bound for the numbers of preimages Map2Pt.n max , we define an "inversion algorithm" Map2Pt -1 : G → F q that, on input g ∈ G, returns one of potentially many preimages of g under Map2Pt if a biased coin comes up heads. If the coin comes up tails, the algorithm outputs failure. The "inversion algorithm" also serves as rejection sampling algorithm for the distribution D G that is produced by Map2Pt(r) for uniformly distributed inputs r ∈ F q : Algorithm 1 Map2Pt -1 : G -→ F q ∪ {⊥} On input g ∈ G: Sample i uniformly from {1, . . . , Map2Pt.n max }; Then obtain n g ∈ {0, . . . , Map2Pt.n max } pre-images (r 1 , . . . , r m ) ← Map2Pt.PreImages(g); If n g < i return ⊥, else return r i . Lemma 3.8. Let Map2Pt : G → F q be probabilistically invertible with at most Map2Pt.n max preimages and let D G denote the distribution it induces on G. Then Algorithm 1 is a PPT rejection sampler for (G, D G ) with average acceptance rate (|F q |/|G|)/Map2Pt.n max .

Proof. We first define the average number of preimages n max ≥ n ≥ 1 as the quotient of the order of the field F q and the number of points on the image of the map, i.e., n = |F q |/|support(D G )|. When drawing an element g uniformly from G, the probability that the number of preimages n g for g is nonzero is given by the quotient of the order of the support of D G and the order of the group. By the definition of n above this is |F q |/(n|G|).

For any point on the map with a nonzero number n g of preimages, Algorithm 1 returns a result =⊥ with probability n g /n max . As the average value for the number of preimages for any point on the image of the map is n, the average acceptance rate is

(|F q |/(n|G|)) • n/n max = (|F q |/|G|)/n max .
Use of Map2Pt -1 for uniformly sampling field elements from F q . As Map2Pt is deterministic, each point g from G is characterized by the number of preimages n g for Map2Pt in F q with n max ≥ n g ≥ 0. When generating points Map2Pt(s) ∈ G for uniformly sampled field elements s ← R F q , the probability of obtaining a given point g is (n g /q) and can only take the values of zero or integer multiples of 1/q up to n max /q. In order to compensate for this, Map2Pt -1 is constructed such that the probability of returning r =⊥ for a point g increases proportionally with n g making any actually produced field element r =⊥ equally likely in F q . As a result, we can use Map2Pt -1 for transforming a sequence of uniformly sampled group elements g l ∈ G to a sequence of uniformly sampled field elements r l ∈ F q Corollary 3.9. Let Map2Pt be a probabilistically invertible map with at most Map2Pt.n max preimages and let g l ← R G. Then r l ← Map2Pt -1 (g l ) outputs results r l =⊥ with probability p ≥ (|F q |/|G|)/Map2Pt.n max and the distribution of outputs r l =⊥ is uniform in F q .

Moreover as the collision probability when drawing two elements r a , r b from F q is 1/q and as there are at most n max values s l generating the same group element g = Map2Pt(s l ) the collision probability for g a = Map2Pt(r a ) and

g b = Map2Pt(r b ) is increased at most by n 2 max .
Corollary 3.10. When sampling two field elements r a , r b ← R F q uniformly, we have Map2Pt(r a ) = Map2Pt(r b ) with a probability of at most n 2 max /q.

The CPace protocol

The CPace protocol [START_REF] Haase | AuCPace: Efficient verifier-based PAKE protocol tailored for the IIoT[END_REF] is a SPEKE-type protocol [START_REF] Jablon | Strong password-only authenticated key exchange[END_REF] allowing parties to compute a common key via a Diffie-Hellman key exchange with password-dependent generators. The blueprint of the protocol is depicted in Fig. 2. Informally, a party P willing to establish a key with party P first computes a generator g from a password pw. Next, P generates an element Y a = g ya from a secret value y a sampled at random and sends it to P . Upon receiving a value Y b from P , P then computes In order to allow for efficient instantiations over different types of groups, most of which are elliptic curves, we present the CPace protocol in form of a blueprint CPace[Gen, ScMul, ScMulVf, ScSam] in Fig. 2 that provides the following generalizations: (1) The blueprint uses a generic algorithm Gen : D × P ID × P ID → G that turns a password from dictionary D and two party identifiers into a group element. For correctness we require that the order in which party identifiers are input to Gen does not influence the output, i.e., Gen(pw, P, P ) = Gen(pw, P , P) for all P, P ∈ P ID and pw ∈ D; (2) The computation of the y i and Y i values is done with generic algorithms for sampling (SamSc : 0, 1 * → 0, 1 * ) and scalar multiplication (ScMul : G × Z |G| → G); (3) The Diffie-Hellman key is computed with another generic algorithm ScMulVf : G × Z |G| → G, in order to allow for additional point verification that is necessary on some curves (but not on all) to protect against trivial attacks; (4) the blueprint protocol uses an ordered concatenation function oc so that messages can be sent in any order and parties do not have to play a specific initiator or responder role(see Appendix D). In the remainder of the paper, we will instantiate the CPace blueprint in various ways, by specifying a set of concrete algorithms Gen, ScMul, ScMulVf, ScSam.

P(pw, P ) public: G, c • p, H 2 , Gen, P (pw , P) ScMul, ScMulVf, ScSam g ← Gen(pw, P , P) g ← Gen(pw , P, P ) y a ← ScSam() y b ← ScSam() Y a ← ScMul(g, y a ) Y b ← ScMul(g , y b ) sid , Y b sid , Y a K ← ScMulVf(Y b , y a ) K ← ScMulVf(Y a , y b ) Abort if K = I G Abort if K = I G ISK ← H 2 (K||oc(Y a , Y b )) ISK ← H 2 (K ||oc(Y a , Y b )) Output ISK Output ISK
On the necessity of point verification. Many elliptic curve scalar multiplication algorithms will work correctly independent whether the input operand encodes a point on the correct curve or not. As a consequence if group membership is not correctly verified by an implementation various attack scenarios become feasible. An active attacker may for instance provide a point on a curve of low order on which the discrete-logarithm problem could be solved. The threat for real-world implementations is that this serious error might remain undetected as the corresponding verification event is never generated in communications of honest parties. In order to make CPace resilient to this type of attack and implementation pitfalls, [START_REF] Haase | AuCPace: Efficient verifier-based PAKE protocol tailored for the IIoT[END_REF] suggested to first restrict invalid curve attacks to the quadratic twist (by using a single-coordinate Montgomery ladder) and then choose a curve where also the twist has a large prime-order subgroup and invalid curve attacks become impossible. The CPace draft [START_REF] Haase | CPace, a balanced composable PAKE[END_REF] highlights this aspect on the protocol specification level by introducing a ScMulVf function which is specified to include point verification.

Security of Simplified CPace

In this Section, as a warm-up, we analyze security of a "basic" variant of CPace, which we call CPace base and which is depicted in Fig. 2. We instantiate Gen with a hash function H G that hashes onto the group G. This way, parties compute generators as g ← H G (pw). Further, we assume G to be a multiplicatively written group of prime order p where group membership is efficiently decidable. We instantiate ScMul(g, y) := g y as exponentiation, and ScMulVf(g, y) such that it returns the neutral element if g is not in the group and g y otherwise, and SamSc with uniform sampling from {1 . . . p}. A formal description of the protocol is given in Fig. 2, where the blueprint protocol is instantiated with the algorithms at the bottom of the Figure.

For clarity, we give a UC execution of CPace base in Fig. 15 and prove its security properties in the following theorem.

Theorem 5.1 (Security of CPace base ). Let λ, p ∈ N with p prime. Let G be a group of order p, and let H 1 : {0, 1} * → G, H 2 : {0, 1} → {0, 1} λ be two hash functions. If the sCDH and sSDH problems are hard in G, then protocol CPace base depicted in Fig. 2 UC-emulates F lePAKE in the random-oracle model with respect to adaptive corruptions when both hash functions are modeled as random oracles. More precisely, for every adversary A, there exist adversaries B sSDH and B sCDH against the strong CDH (sCDH) and strong simultaneous CDH (sSDH) problems such that

|P r[Real Z (CPace base , A)] -P r[Ideal Z (F lePAKE , S)| ≤ l 2 H 1 /p + 2l 2 H 1 Adv sSDH B sSDH (G) + Adv sCDH B sCDH (G)
where l H 1 denotes the number of H 1 queries made by the adversary A and the simulator S is depicted in Fig. 3.

Sketch. The main idea of the simulation is to fix a secret generator g ∈ G and carry out the simulation with respect to g. Messages of honest parties are simulated as g z for a fresh exponent z. Queries H 1 (pw) are answered with g r for a freshly chosen "trapdoor" r. The simulator might learn an honest party's password via adaptive corruption or via an adversarial password guess. The simulator can now adjust the simulation in retrospective to let the honest party use g r = H 1 (pw) by claiming the party's secret exponent to be zr -1 . This already concludes simulation of honest parties without passwords. Adversarial password guesses can be read from A injecting X (or, similarly, Y )

The simulator S (G2)samples and stores a generator g ← G.

On

(G4) if ∃ rec. (H1, pw||oc(Pi, Pj), r, r -1 , * ): yi ← zir -1 (G4) else: r ←R Zp; yi ← zir -1 and (G4) store (H1, pw||oc(Pi, Pj), r, r -1 , g r ) (G4) if ISK = ⊥, let Yj denote the message sent to Pi (G4)
and store (H2,

Y y i j ||oc(Yi, Yj), ISK ) (G4) send (sid , Pi, Pj, pw, yi, Yi, Y y i j , ISK ) to A On H2(K||Yi||Yj) from A: (G4)if this is the first such query then (G7) if ∃ rec.(Pi, Pj, zi, Yi, * ), (Pj, Pi, zj, Yj, * ), (H1, * , r, * ) such that K r = g z i z j : abort; (G4) if rec.(Pi, Pj, * , Yi, * ) or (Pj, Pi, * , Yj, * ), or if Ya||Y b = oc(Ya, Y b ): A ←R {0, 1} 2k ; (G4) if ∃ records (Pi, Pj, zi, Yi, ISK ) with ISK = ⊥ and (G5)(H1, pw||oc(Pi, Pj), r, r -1 , G) s.th. K = Y z i r -1 j : (G5) Record (guess, G, Yj); abort if ∃ rec. (guess, G , Yj) with G = G . (G5)
Send (LateTestPwd, sid , Pi, pw) to F lePAKE . Upon answer K set A ← K;

(G4) if ∃ (Pj, Pi, zj, Yj, ISK ) with ISK = ⊥ and (G5)(H1, pw||oc(Pj, Pi), r, r -1 , G) s.th.

K = Y z j r -1 i : (G5) Store (guess, G, Yi); Abort if ∃ record (guess, G , Yi) with G = G ; (G5)
Send (LateTestPwd, sid , Pj, pw) to F lePAKE . Upon answer K set A ← K (G4) if no matching H1 records are found set A ←R {0, 1} 2k (G4) finally, store (H2, K||Yi||Yj, A) and reply with A (G4)else retrieve record (H2, K||Yi||Yj, A) and reply with A and then querying H 2 (K||X||Y ) with K being a correctly computed key w.r.t some generator g r provided by the simulation. S can now read the guessed password from the H 1 list, and submit it as password guess to F lePAKE . In case of success, the simulator sets the key of the honest party to H 2 (K||X||Y ).

The simulation is complicated by the order of honest parties' outputs (which are generated upon receipt of the single message) and the adversary's computation of final session keys via H 2 queries. If the key is generated by F lePAKE before A computes it via H 2 (which constitutes a password guess as detailed above), then S needs to invoke the LateTestPwd query of F lePAKE instead of TestPwd. In case of a correct guess, this lets S learn the output key of the honest party, which S can then program into the corresponding H 2 query.

Finally, the simulation can fail in some cases. Firstly, S might find more than one password guess against an honest party with simulated message X. In this case, the simulation cannot continue since F lePAKE allows for only one password guess per party. In this case, however, A would provide (g r , X, Y, K),(g r , X, Y, K ) which are two CDH tuples for passwords pw, pw with g r ← H 1 (pw), g r ← H 1 (pw ). Provided that the simultaneous strong CDH assumption (sSDH, cf. Definition 3.2) holds, this cannot happen. Here, the "strong" property, providing a type of DDH oracle, is required to help S identify CDH tuples among all queries to H 2 . A second case of simulation failure occurs when A wants to compute a key of an uncorrupted session via a H 2 query. Since S does not know such keys, it would have to abort. Using a similar strategy as above, pseudorandomness of keys can be shown to hold under the strong CDH assumption, and thus the probability of A issuing such a H 2 query is negligible. The full proof can be found in Appendix A.

Our Theorem 5.1 demonstrates that adaptive security of CPace can be proven with only minimal information included in the hashes, i.e., the first hash requires only the password and the final key derivation hash requires the Diffie-Hellman key and the unique protocol transcript. We detail now under which circumstances additional data such as session identifiers needs to be included in the hashes. We further note that adding additional inputs to hashes, such as the name of a ciphersuite that an application wants parties to agree on, does not harm security.

On multi-session security and hash domain separation Theorem 5.1 demonstrates that CPace base allows to securely turn a joint password into one key. In practice, one would of course want to exchange more than one key, and many parties will end up using the same password. If session identifiers are globally unique, then the UC composition theorem (more detailed, the composition theorem of UC with Joint State [START_REF] Canetti | Universal composition with joint state[END_REF]) allows to turn Theorem 5.1 into a proof of "multisession CPace" by simply appending the unique session identifiers to all hash function inputs. This ensures that hash domains of individual sessions are separated and the programming activities of the individual simulators do not clash. To summarize, we obtain a secure multi-session version of CPace by ensuring uniqueness of session identifiers and including them in hashes. In practice, this can be ensured by, e.g., agreeing on a joint session identifier to which both users contributed randomness and in which party identifiers are incorporated (see, e.g., [START_REF] Barak | Protocol initialization for the framework of universal composability[END_REF]). The agreement needs to happen before starting CPace, but does not require secrecy and can thus potentially be piggybacked to messages sent by the application. As a last note, applications might choose to add more values to hashes, for example to authenticate addresses or to ensure agreement on a ciphersuite. We stress that such additional values do not void our security analysis, but care still needs to be taken in order to protect against side-channel attacks.

Embedding CDH experiment libraries into the simulator

In this section, we discuss an alternative approach to carrying out reductions to cryptographic assumptions in the case of CPace/CDH. Both assumptions required by CPace base , sCDH and sSDH, allow for an efficient implementation of experiments in the following sense: the secret exponents that are sampled by the experiment code (often also called the challenger ) are sufficient for answering the restricted DDH queries allowed by both assumptions. An example for an assumption that does not allow for such efficient instantiation is, e.g., gap-CDH. In gap-CDH, the adversary is provided with a "full" DDH oracle that he can query on arbitrary elements, of which the experiment might not know an exponent for.

Due to this property, we can integrate implementations of the sCDH and sSDH experiments in the simulator's code. The simulator implements the DDH oracles on its own, and abort if at any time an oracle query solves the underlying assumption. We chose to integrate experiments as libraries (written as objects in python-style notation in Fig. 4) into the simulator's code. This eases not only presentation but is also useful for analyzing variants of CPace that require slightly different assumptions.

The simulator S(exp) is parametrized by an experiment class exp.

On (NewSession, sid, P i , P j ) from F lePAKE : (G 4 )set Y i ← exp.sampleY(); (G 4 )store (P i , P j , Y i , ⊥); (G 4 )send Y i to A intended to P j ; On Z * from A as msg to (sid, P i ): (G 4 )if Z * is adversarially generated (G 4 )and exp.isValid(Z * ): (G 4 ) send (RegisterTest, sid, P i ) to F lePAKE Upon P i receiving (sid, Y j ) from P j : retrieve record

(P i , * , z i , Y i , * ) (G 1 )if not exp.isValid(Y j ): return; (G 4 )if ∃ records (H 1 , pw, h), (H 2 , K||(oc(Y i , Y j ), ISK ) (G 4 )such that exp.DDH(h, Y i , Y j , K) = 1:
(G 4 ) send (TestPwd, sid, P i , pw) to F lePAKE (G 4 ) send (NewKey, sid, P i , ISK ) to F lePAKE and store (P i , P j , Y i , ISK ) (G 4 )else sample a fresh random ISK and send (NewKey, sid,

P i , ISK ) to F lePAKE (G 4 ) # F lePAKE will discard ISK On H 1 (pw||P i ||P j )) from A: (G 2 )if not ∃ record (G 2 ) (H 1 , pw||P i ||P j , h): (G 2 ) h ← exp.sampleH1() (G 2 ) store (H 1 , pw||P i ||P j , h) (G 2 )lookup(H 1 , pw||P i ||P j , h) (G 2 )reply with h
On (AdaptiveCorruption, sid) from A as msg to P i : Lookup (P i , P j , Y i , * ); send (AdaptiveCorruption, sid, P i ) to F lePAKE and obtain back (sid, pw,ISK ); (G 4 )if a message Y i was already sent to P j , then: (G 4 ) query H 1 (pw) and retrieve record (H 1 , pw, h) The corresponding result for CPace base is shown in Fig. 5 when the challenge-generating experiment exp ← sSDH(sCDH) is used (Fig. 4). The instance of the sSDH object first samples a random generator as member s.g and creates a member instance s.scdh ← sCDH(g) of the experiment for the sCDH problem. The sCDH member object produces a challenge consisting of two uniformly drawn group elements Y 1 ← g y 1 , Y 2 ← g y 2 . The limited DDH oracle provided by the sCDH assumption can only receive inputs w.r.t one of these elements, and thus it can be implemented efficiently using secret exponents y 1 , y 2 . If a correct CDH solution g, Y 1 , Y 2 , g y 1 •y 2 is provided, the sCDH object aborts. In its implementation for H 1 , the sSDH object samples random new generators as R ← (s.g) r which will be used for simulating password-dependent base points and uses the s.scdh member and the known exponent r for answering DDH queries by use of the s.scdh.DDH function. The corrupt queries are implemented likewise and forwarded to the s.scdh member object. The simulator from Fig. 3 is adapted to call the experiment. As an example, honest parties' messages are simulated by calling the challenge sampling procedure exp.sampleY() from sSDH which itself calls the corresponding function from its sCDH member.

(G 4 ) y i ←exp.corrupt(h, Y i ); (G 4 ) if ISK =⊥: (G 4 ) let Y j denote the message sent to P i (G 4 ) store (H 2 , sid||Y y 1 j ||oc(Y i , Y j ), ISK ) (G 4 ) send (sid, P i ,pw, y i , Y i , Y y i j , ISK ) to A On H 2 (sid||K||Y i ||Y j ) from A: (G 4 )lookup (H 2 , sid||K||Y i ||Y j ,
Proving indistinguishability. With this simulation approach, a proof consists in demonstrating that ideal and real world executions are indistinguishable except for events in which the experiment libraries abort because a challenge was correctly answered. Compared to our proof of Theorem 5.1, the indistinguishability argument becomes simpler because the reduction strategies to both CDH-type assumptions are already embedded in the corresponding assumption experiment libraries. Losses such as the factor 2l 2

H 1 in the reduction to sSDH in game G 5 translate to libraries producing more than one challenge per simulation run, as is the case for the sSDH experiment from Fig. 5. Altogether, the simulation with integrated CDH experiment libraries is an alternative approach of proving Theorem 5.1, as we formalize in the following.

Theorem 5.2 (Alternative simulation for Theorem 5.1). The simulator depicted in Fig. 5 is a witness for the UC emulation statement in Theorem 5.1 Proof sketch. The output distribution of the simulator S from Fig. 5 is indistinguishable from the one of the simulator from Fig. 3 as it is obtained from internal restructuring. S aborts if either the sSDH or the sCDH experiment class aborts, which occurs iff a correct solution has been provided to the experiment implementation or a H 1 collision is observed. These cases coincide with the abort cases in the proof of Theorem 5.1. As the sSDH object outputs 2l 2 H 1 different challenges and as it is sufficient for Z to provide a solution to one of these challenges for distinguishing both worlds, the advantage for solving the sSDH problem needs to be multiplied by this factor, thus reproducing the bounds from Theorem 5.1.

Advantages of embedding libraries in the simulation. To clarify, the approach presented in this section does not allow to prove stronger security statements. As demonstrated above, it is merely an alternative way of presenting security proofs in the UC framework or other simulationbased frameworks, and it works whenever the underlying cryptographic assumptions are efficiently implementable. However, we believe that the approach has its merits especially in the following dimensions.

• Modular security analysis. Slight modifications in the protocol might require to change the cryptographic assumption. As long as the public interface does not change, our approach allows to switch between assumptions by simply calling a different library. Cryptographers then need to only analyze this "local" change in the simulation, which prevents them from re-doing the whole indistinguishability argument.

• Presentation of reduction strategies. In normal game-based indistinguishability arguments [START_REF] Shoup | Sequences of games: a tool for taming complexity in security proofs[END_REF], reductions to cryptographic assumptions are hidden within side-long proofs. With our approach, the reduction strategy is depicted in clear code as part of the simulator's code. This makes checking of proofs easier not only for readers but also might make simulation-based proofs more accessible to automated verification. else: return g y return y

Figure 6: Protocol CPace 1MAP for an elliptic curve group G of prime order p, over finite field F q . Generators are computed as Map2Pt(H 1 (pw)) with a hash function H 1 : {0, 1} * → F q . Differences to CPace base are marked gray .

In this paper, our motivation is the first dimension. In the upcoming section, the library-based approach will turn out to be extremely useful to analyze the various variants of CPace that stem from (efficiency-wise) optimized implementations on different elliptic curves.

Analysis of Real-World CPace

The currently most efficient way to run CPace is over elliptic curves. Therefore, from this point onwards, we consider G to be an elliptic curve constructed over field F q . From a historical perspective, both CPace research and implementation first focused on prime order curves, such as the NIST-P-256 curve [START_REF]National Institute of Standards and Technology (NIST)[END_REF]. Subsequently significantly improved performance was shown on Montgomery-and (twisted-)Edwards curves, notably Curve25519 and Ed448 curves [START_REF] Daniel | Curve25519: New Diffie-Hellman speed records[END_REF][START_REF] Hamburg | Ed448-goldilocks, a new elliptic curve[END_REF], which both have a small cofactor c in their group order c • p. These approaches consider also implementation pitfalls, e.g., by designing the curve such that there are no incentives for implementers to use insecure speed-ups. Thirdly, recently ideal group abstractions have been presented in order to avoid the complexity of small cofactors in the group order [START_REF] Hamburg | Decaf: Eliminating cofactors through point compression[END_REF][START_REF] De Valence | The ristretto255 and decaf448 groups. Rfc, IRTF[END_REF], while maintaining all advantages of curves with cofactor.

For smooth integration into each of these different curve ecosystems, CPace needs to be instantiated slightly differently regarding, e.g., computation of the DH generator, group size, multiplication and sampling algorithms. In this section, we analyze how such differences impact security. Using our modular approach with assumption libraries called by a simulator, we are able to present security in terms of differences from our basic CPace analysis in Section 5 in a concise way.

CPace without Hashing to the Group

We now analyze a variant of the CPace protocol case-tailored for elliptic curve groups G over finite field F q . The protocol is depicted in Fig. 6. The only difference to CPace base analyzed in the previous section is how parties compute the generators: now the function H 1 hashes onto the field F q , and generators are computed as g ← Map2Pt(H 1 (pw)) for a function Map2Pt : F q → G. This way, the H 1 outputs can be considered to form an alternative encoding of group elements, where Map2Pt decodes to the group. ScMul, ScMulVf and SamSc are as in Section 5.

Security analysis.

Compared to the analysis of CPace base , the security analysis is complicated by the different computation of the generators in essentially two ways: first, the possibly nonuniform distribution of Map2Pt induces non-uniformity of DH generators computed by the parties. Second, embedding of trapdoors no longer works by simply programming elements with known exponents into H 1 . Instead, the proof will exploit that Map2Pt is probabilistically invertible, such that preimages of generators with known exponents can be programmed into H 1 instead. Consequently, security of CPace will be based on the D G -sSDH problem Definition 3.3 instead of the sSDH problem, where the distribution D G corresponds to the distribution of group elements Map2Pt(h i ) obtained for uniformly sampled field elements h i ← R F q . All these changes can be captured by replacing library sSDH with a new library for D G -sSDH, as we demonstrate below.

Theorem 6.1 (Security of CPace 1MAP ). Let λ, p, q ∈ N with p prime. Let G an elliptic curve of order p over field F q . Let H 1 : {0, 1} * → F q , H 2 : {0, 1} * → {0, 1} λ be two hash functions and Map2Pt : F q → G probabilistically invertible with bound Map2Pt.n max . If the sCDH and sSDH problems are hard in G, then the CPace protocol depicted in Fig. 2 UC-emulates F lePAKE in the random-oracle model with respect to adaptive corruptions and both hash functions modeled as random oracles. More precisely, for every adversary A, there exist adversaries B sSDH and B sCDH against the sSDH and sCDH problems such that

|P r[Real(Z, A, CPace 1MAP )] -P r[Ideal(F lePAKE , S)]| ≤ (Map2Pt.n max )l H 1 /q + (l H 1 ) 2 /p + (Map2Pt.n max • l H 1 ) 2 /q +2l 2 H 1 Adv sSDH B sSDH (G) + Adv sCDH B sCDH (G)
where l H 1 denotes the number of H 1 queries made by the adversary A and the simulator S is as in Fig. 5 but using the object distExp (cf. Fig. 7) instead of the object sSdhExp.

Proof Sketch. Let D G denote the distribution on G induced by Map2Pt. First note, that if the sSDH is hard in G then the corresponding D G -sSDH problem is hard by Theorem 3.6 as Map2Pt -1 (implemented in the body of the sampleH1 method by the distExp object) is a rejection sampler for D G . We adjust the simulator for "basic" CPace from Fig. 5 as follows. First, we embed the reduction strategy from Theorem 3.6 into an experiment library that converts sSDH challenges into D G -sSDH challenges and obtain the class D G _sSDH depicted in Fig. 7. The class D G _sSDH uses the Map2Pt.PreImages function (passed as a constructor parameter) for implementing the Map2Pt -1 as defined in Algorithm 1 and an instance of the sSDH class implementing a sSDH experiment that is assigned to a member variable.

Each time the main body of the simulator from Fig. 5 makes calls to its exp object, the corresponding method of the new D G _sSDH object will be executed, which itself translates the queries into calls to the sSDH object that was passed as constructor parameter.

Importantly, D G _sSDH provides the same public API as the sSDH class with the distinction that sampling for H 1 returns results from F q instead of G. Moreover D G _sSDH aborts if the code of its sSDH object aborts and, now additionally, also upon H 1 collisions.

We explain now how the indistinguishability argument of Theorem 5.1 needs to be adjusted in order to work for Theorem 6.1 and this new simulator. The first difference applies in game G 2 , where we must make sure that the distribution of points provided by the D G _sSDH object is uniform in F q as was in the previous game. This is the case due to Corollary 3.9. In game G 3 no change is needed except for adjusting the collision probability following the derivation from Corollary 3.10 which is now bound by (n max • l H 1 ) 2 /q in addition to the previous l 2 H 1 /p probability. The probability that sampleH1 aborts because it samples the identity element from the distribution is bounded by (Map2Pt.n max )l H 1 /q. Apart of these modification the proof applies without further changes. Instantiating Map2Pt. Various constructions have been presented for mapping field elements to elliptic curve points such as Elligator2 [START_REF] Daniel | Elligator: ellipticcurve points indistinguishable from uniform random strings[END_REF], simplified SWU [START_REF] Faz-Hernandez | Hashing to elliptic curves[END_REF] and the Shallue-van de Woestijne method (SvdW) [START_REF] Shallue | Construction of rational points on elliptic curves over finite fields[END_REF] (see also [START_REF] Faz-Hernandez | Hashing to elliptic curves[END_REF] and references therein). When considering short-Weierstrass representations of a curve, the general approach is to first derive a set of candidate values x l for the x coordinate of a point such that for at least one of these candidates x l there is a coordinate y l such that (x l , y l ) is a point on the curve. Subsequently one point (x l , y l ) is chosen among the candidates. The property of probabilistic invertibility is fulfilled for all of the algorithms mentioned above and those currently suggested in [START_REF] Faz-Hernandez | Hashing to elliptic curves[END_REF]. The most generic of these algorithm, SvdW, works for all elliptic curves, while the simplified SWU and Elligator2 algorithms allow for more efficient implementations given that the curve fulfills some constraints.

All these mappings have a fixed and small bound n max regarding the number of pre-images and come with a PPT algorithm for calculating all preimages. For instance, Elligator2 [START_REF] Daniel | Elligator: ellipticcurve points indistinguishable from uniform random strings[END_REF] comes with a maximum n max = 2 of two pre-images per point and n max ≤ 4 for the simplified SWU and SvdW algorithms [START_REF] Faz-Hernandez | Hashing to elliptic curves[END_REF]. For all these algorithms, the most complex substep for determining all preimages is the calculation of a small pre-determined number of square roots and inversions in F q which can easily be implemented in polynomial time with less computational complexity than one exponentiation operation.

Gen 2MAP (pw, P i , P j ) :

ScMul base (g, y) : ScMulVf base (g, y) : ScSam p () :

(h, h ) ← H 1 (pw||oc(P i , P j )) return g y if g / ∈ G: return I G y ← R 1 . . . p return Map2Pt(h) else: return g y return y

• Map2Pt(h ) Figure 8: Protocol CPace 2MAP , with generators computed by two executions of Map2Pt, using hash function H 1 : {0, 1} * → (F q ) 2 . Other algorithms remain unchanged.

Map-twice-and-add constructions.

Some mapping constructions aim at producing more uniform distributions using a map-twice-andadd approach, such as presented in [START_REF] Faz-Hernandez | Hashing to elliptic curves[END_REF] and also adopted by the ristretto25519 and decaf ecosystems [START_REF] De Valence | The ristretto255 and decaf448 groups. Rfc, IRTF[END_REF][START_REF] Hamburg | Decaf: Eliminating cofactors through point compression[END_REF]. We capture this with protocol CPace 2MAP depicted in Fig. 8. The protocol computes generators by adding two points generated by Map2Pt. H 1 and the library simulating H 1 produce two elements from F q instead of a single one. Again we make use of the property of probabilistic invertibility which guarantees (Corollary 3.9) that algorithm two field elements output by the sampleH1() function implementing the Map2Pt -1 algorithm are uniformly distributed in F q .

As shown in [START_REF] Hamburg | Indifferentiable hashing from elligator 2[END_REF][START_REF] Brier | Efficient indifferentiable hashing into ordinary elliptic curves[END_REF][START_REF] Faz-Hernandez | Hashing to elliptic curves[END_REF][START_REF] Fouque | Indifferentiable hashing to Barreto-Naehrig curves[END_REF], for many maps the map-twice-and-add approach of Gen 2MAP (pw) can be shown to produce a distribution that is indistinguishable from a uniform distribution in G. Under this additional assumption the collision bound ≤ l 2 H 1 /p is maintained at the expense of doubling the computational complexity for calculating generators.

Apart from the uniformity requirement, security holds under the same assumption set as for CPace 1MAP . Specifically Map2Pt needs to be probabilistically invertible such that the rejection samplers in Fig. 9 can be implemented and such that the simulated H 1 outputs become uniform in F q × F q . Theorem 6.2 (Security of CPace 2MAP ). Let λ, p, q ∈ N with p prime. Let G an elliptic curve of order p over field F q . Let H 1 : {0, 1} * → F q ×F q , H 2 : {0, 1} * → {0, 1} λ be two hash functions and Map2Pt : F q → G probabilistically invertible with bound Map2Pt.n max . If the sCDH and sSDH problems are hard in G and if the output of Gen 2MAP (.) is indistinguishable from a uniform distribution in G, then the CPace 2MAP protocol depicted in Fig. 8 UC-emulates F lePAKE in the random-oracle model with respect to adaptive corruptions and both hash functions modeled as random oracles. More precisely, for every adversary A, there exist adversaries B sSDH and B sCDH against the sSDH and sCDH problems such that

|P r[Real(Z, A, CPace 2MAP )] -P r[Ideal(F lePAKE , S)]| ≤ l H 1 /p + 2l 2 H 1 /p + 2l 2 H 1 Adv sSDH B sSDH (G) + Adv sCDH B sCDH (G)
where l H 1 denotes the number of H 1 queries made by the adversary A and the simulator S is as in Fig. 5 using the object coffeeExp (cf. Fig. 9).

Proof Sketch. The same approach as for Theorem 6.1 applies. The difference consists in the fact that now the simulator's experiment library additionally aborts if collisions in the final outputs of the sampleH1 method are detected. In order to show that this collision probability is actually only l 2 H 1 /p we employ that the map-twice-and-add strategy was required to produce a distribution that Theorem 6.3 (Security of CPace co ). Let λ, p, q, c ∈ N, p, c coprime with p prime. Let G be an elliptic curve of order p•c over field F q and G p ⊂ G a subgroup of order p. Let CC c : (g) → ((g c ) 1/c mod p ) be a cofactor clearing function for c, H 1 : {0, 1} * → F q , H 2 : {0, 1} * → {0, 1} λ be two hash functions and Map2Pt : F q → G probabilistically invertible with bound Map2Pt.n max . Let be the chained function Map2Pt Gp := (CC c • Map2Pt). Let D Gp denote the distribution on G p induced by Map2Pt Gp . If the sCDH and sSDH problems are hard in G p , then the D Gp -sSDH problem is hard in G p and CPace co UC-emulates F lePAKE in the random-oracle model with respect to adaptive corruptions when both hash functions are modeled as random oracles. More precisely, for every adversary A, there exist adversaries B sCDH and B sSDH against the sCDH and sSDH problems such that

|P r[Real(Z, A, CPace co )] -P r[Ideal(F lePAKE , S)]| ≤ (Map2Pt.n max • c)l H 1 /q + 2l 2 H 1 /p + (Map2Pt.n max • c • l H 1 ) 2 /q +2l 2 H 1 Adv sSDH B sSDH (G p ) + Adv sCDH B sCDH (G p )
where l H 1 denotes the number of H 1 queries made by the adversary A and the simulator S is as in Fig. 5 but using class ccDistExp (cf. Fig. 11) instead of object sSdhExp.

Proof Sketch. The full group G has a point g 1 of order c with g c 1 = I G where I G denotes the identity element in G, i.e., there are c low-order points g i 1 , i ∈ {1 . . . c}. For any point Y ∈ G we can consider the points Y i = Y • g i as alternative ambiguous representations of the point CC c (Y ) ∈ G p . For any input point Y ∈ G p , all these c alternative representations can be easily calculated using group operations and g i . For any of these c alternative representations of Y at most Map2Pt.n max preimages will be returned by Map2Pt.PreImages since Map2Pt is probabilistically invertible on G. Correspondingly, the probability of accidently drawing a representation of the identity element needs to be multiplied by c and is now bounded by (Map2Pt.n max •c)l H 1 /q. If up to Map2Pt.n max preimages exist per point on the full curve, the chained function Map2Pt Gp is probabilistically invertible also on G p . Its preimage function Map2Pt Gp .PreImages for G p can be defined such that it returns all of the preimages of the c ambiguous representations of an input and the maximum number of preimages Map2Pt Gp .n max is, thus, bounded by Map2Pt Gp .n max = c • Map2Pt.n max . Since we are able to provide all preimages for Map2Pt Gp and a bound for their number is known Map2Pt Gp is probabistically invertible. We thus can employ Theorem 3.6 and show that if the sSDH is hard in G p then the corresponding D Gp -sSDH problem is also hard.

As ScMulVf co and ScMul co use exponents that are a multiples of c they are guaranteed to produce a unique result on G p for all of the c ambiguous representations of an input point. The additional factor of c in the exponents is compensated by the simulation by calling an experiment library using the ccExp class from Fig. 11. 3 The ccExp object forwards queries to a D Gp _sSDH object such that all inputs to the DDH oracle will be in G p .

Note that without exponents being a multiple of c, we would have had game G 3 and G 4 distinguishable because without the factor c in the secret scalars of honest parties, Y a and Y b could have nontrivial low-order components, which is noticeable and does occur in game G 4 .

CPace using twist secure curves

For a curve in Weierstrass form constructed over a field F q , a coordinate x ∈ F q represents either the x coordinate of a point on the curve itself or of a point on a second curve, its so-called quadratic twist Ḡ. On elliptic curves groups G that provide a property coined twist security in [START_REF] Daniel | SafeCurves: Choosing safe curves for elliptic-curve cryptography. Definition of Twist security[END_REF], CPace allows for implementations with reduced computational complexity and code size under an additional assumption including the group Ḡ on the curve's quadratic twist.

Twist secure curve groups G are characterized by the fact that both the curve and the twist have small co-factors c, c and large prime-order subgroups G p and Ḡp of orders p and p. Some curves such as Curve25519 [START_REF] Daniel | Curve25519: New Diffie-Hellman speed records[END_REF], Curve19119 [START_REF] Haase | Making password authenticated key exchange suitable for resource-constrained industrial control devices[END_REF] and Ed448-Goldilocks [START_REF] Hamburg | Ed448-goldilocks, a new elliptic curve[END_REF] have been specifically tailored for this property.

For Diffie-Hellmann protocols where active adversaries are relevant invalid curve attacks need to be considered. As a result, point verification is a crucial substep in most protocols based on Diffie-Hellman style key agreement. Unfortunately incorrectly implemented point verification might easily remain undetected as interacting honest parties are not affected at all.

In order to make implementations resilient against this common pitfall, the popular X448 and X25519 Diffie-Hellman protocols from RFC7748 and [START_REF] Daniel | Curve25519: New Diffie-Hellman speed records[END_REF] employ a specific property of twist-secure curves for offering security without any point verification. To our best knowledge the assumption has not been formally defined previously. For the sake of security analysis of the corresponding CPace construction we formally define the "twist CDH problem" sTCDH on the two prime-order subgroups on the curve and the twist as follows. (Its defined in its strong variant allowing for restricted DDH oracle access). Definition 6.4 (Strong twist CDH problem (sTCDH)). Let G p be a first cyclic group of prime order p with a generator g and (Y = g y ) sampled uniformly from (G p \ I Gp ). Let Ḡp be a second cyclic group of prime order p with p = p. Given g, Y and access to DDH oracle DDH(g, Y,

•, •) in G p , provide X, Z ∈ Ḡp \ I Ḡp with Z = X y .
Correspondingly, with Adv sTCDH B sTCDH (G p , Ḡp ) we denote the probability that an adversarial algorithm B sTCDH calculates a solution for the sTCDH problem for a single randomly sampled challenge for the groups G p , Ḡp when given access to the restricted DDH oracle in G p .

Why hardness of this problem allows for the strategy from [START_REF] Daniel | Curve25519: New Diffie-Hellman speed records[END_REF] regarding omitting point verification in protocols such as X448 and X25519 becomes transparent when considering singlecoordinate scalar multiplication algorithms. Single-coordinate scalar multiplication algorithms Z ← ScMul(X, y) commonly accept inputs X from both, the curve and its twist and return the result Z = X y on the same curve as the input X.

Using single-coordinate Diffie-Hellman provides the advantage that the adversary may only insert inputs X taken from either the curve or the twist. I.e. if a honest party publishes a public key Y = g y an active adversary can provide a point X either on G or Ḡ and make the honest party calculate a Diffie-Hellman result Z = ScMul(X, y) = X y where Z comes from the same group as X.

The conventional strong Diffie-Hellman assumption states that the adversary cannot calculate the honest party result point Z for any given random challenge X from G p . Hardness of the twist problem sTCDH above implies that the adversary also cannot predict the honest party's result point Z for any chosen adversial point X from the twist Ḡp group. Note that it is easy for the adversary to predict Z = Y x for an adversially chosen point X = g x from the original curve group G p by following the protocol for a honest participant. Obviously, in comparison, the task of calculating Z = X y is harder if X needs to be on the twist.

Obviously the sTCDH problem is easy if the order of the points Y or Z is small. For making sure that Y and Z come from the prime-order subgroups, X448 and X25519 employ a co-factor clearing procedure where secret exponents are chosen to be multiples of the co-factor c. Corollary 6.5. Let G be an elliptic curve of order c • p where c, p coprime with a subgroup G p of prime order p over base field F q . Let Ḡ be the quadratic twist of G of order p • c with a subgroup Ḡp of prime order p. Let c be equal to c or an integer multiple of c. Then for any integer y and point

X ∈ (G ∪ Ḡ) it holds that X y•c ∈ (G p ∪ Ḡp ).
If the cofactor c is equal or a multiple of the cofactor c of the twist, multiplicative co-factor clearing with c is functional for both, the curve and its twist. I.e. for any exponent being a multiple of c and X ∈ (G ∪ Ḡ) then Z = X c•y is guaranteed to be either of large prime order or the neutral element of the curve or the twist. Note that the neutral elements on G and Ḡ in X448 and X25519 share the same binary representations (all bits zero). Here checks for a low-order Z corresponds to just verifying that Z = X c•y differs from the representation of the neutral elements.

It is easy to see, as the orders of the groups differ [START_REF] Daniel | Curve25519: New Diffie-Hellman speed records[END_REF], that there is no homomorphic mapping between the curve and its twist. Finally, hardness of sTCDH relates to the hardness of the DLP. sTCDH is easy if the DLP can be solved for (g, Y ).

The twist security property can be employed also in the context of CPace for making implementations faster and more resilient against implementation errors regarding the point verification, specifically if CPace is implemented using scalar multiplication based on single-coordinate Montgomery ladders. Theorem 6.6 (Security of CPace twist on twist-secure curves with co-factor.). Let λ, c, p, c, p, q ∈ N with p, p prime. Let G be the group of points on an elliptic curve over field F q and Ḡ its quadratic twist. Let p • c be the order of G. Let p • c be the order of Ḡ. Let G p be a subgroup of G of order p. Let group Ḡp be a subgroup of order p of Ḡ. Let c be equal or an integer multiple of c. Let H 1 : {0, 1} * → F q , H 2 : {0, 1} * → {0, 1} λ be two hash functions and Map2Pt : F q → G probabilistically invertible with bound Map2Pt.n max .

Then the protocol CPace twist from Fig. 13 UC-emulates F lePAKE in the random oracle model with respect to adaptive corruptions and both hash functions modeled as random oracles. More precisely, def class sCDH_sTCDH ():

"Accepts X, K inputs from G and the twist Ḡ" def _init_(s, g): s.g ← g; s.i ← 0; s.s1, s.s2 ← fresh; def sampleY(s): if s.i ≤ 2: s.i+ = 1; s.yi ←R Fp \ 0; s.Yi ← (s.g) y i ; return s.Yi;

def corrupt(s,Y ): for 1 ≤ m ≤ s.i): if (Y = (s.g) s.ym ):
x ← s.ym; s.si ← corrupt; return x; def DDH(s, B, Y, X, K):

if (B = s.g) and ({Y, X}={s.Y1, s.Y2}) and (s.s1 = fresh) and (s.s2 = fresh) . . . and (K = (s.g) s.y 1 •s.y 2 ): abort("K solves sCDH(B, Y1, Y2)"); if (B = s.g) and (Y = s.Y1):

if(s.s1 = fresh) and (X ∈ Ḡ \ I Ḡ ) and (X s.y 1 = K): abort("X, K solve sTCDH(B, Y1)"); return (X s.y 1 = K); if (B = s.g) and (Y = s.Y2):

if(s.s2 = fresh) and (X ∈ Ḡ \ I Ḡ ) and (X s.y 2 = K): abort("X, K solve sTCDH(B, Y2)"); return (X s. In addition to the previous challenge generator class for sCDH, point verification now also accepts points from the twist except for the twist's neutral element. Moreover the code for the DDH oracle now also accepts its third and fourth inputs X, K from the twist and aborts in case that (X, K) forms a solution of the sTCDH problem for (g, Y ). for every adversary A, there exist adversaries B sTCDH , B sSDH and B sCDH against the sTCDH, sSDH and sCDH problems such that

y 2 = K); def isValid(X): return (X ∈ (G \ IG)) or (X ∈ ( Ḡ \ I Ḡ );
CPace twist :=CPace[Gen 1MAP , ScMul co , ScMulVf tw , ScSam p ] Gen 1MAP (pw, P i , P j ) : ScMul co (g, y) : ScMulVf tw (g, y) : ScSam p () : return Map2Pt( return g c•y if g / ∈ G ∪ Ḡ : return I G y ← R 1 . . . p H 1 (pw||oc(P i , P j ))) K ← g c•y return y if K = I Ḡ : K ← I G return K
|P r[Real(Z, A, CPace twist )] -P r[Ideal(F lePAKE , S)]| ≤ (Map2Pt.n max • c)l H 1 /q + (l H 1 ) 2 /p + (c • Map2Pt.n max • l H 1 ) 2 /q +2l 2 H 1 Adv sSDH B sSDH (G p ) + Adv sCDH B sCDH (G p ) + 2 • Adv sTCDH B sTCDH (G p , Ḡp )
where l H 1 denotes the number of H 1 queries made by the adversary A and simulator S is as in Fig. 5 but using the object twistDistExp (cf. Fig. 12) instead of the object sSdhExp.

Proof. The only difference in the real-world protocol between CPace twist and CPace co consists in the fact that the latter variant's scalar multiplication and verify function now also accepts inputs from the twist. I.e. differing from CPace co , CPace twist issues a session key without aborting if the output of the ScMulVf tw function is not the identity element I G .

The difference for the proof strategy for Theorem 5.1 consists in the fact that we now need to handle events where the adversarial strategy is based on injecting points from the twist.

First note that the twist has cofactor c and thus c low-order points. As c is an integer multiple of c the exponentiation by multiples of c maps all inputs from the full twist curve to the twist's prime-order subgroup by Corollary 6.5.

In the simulation we additionally need to handle the case that the adversary provides an input from the twist. We add an additional game after G 0 , where we abort if the adversary queries H 2 for Y, X, K for a honest Y = g c•y calculated from a generator g, an adversarial input X from the twist Ḡp such that K = X c•y ∈ Ḡp \ I Ḡ , where y is the private scalar of one of the honest parties.

This change is distinguishable only if A provided a solution to the sTCDH problem from Definition 6.4 and the advantage of a distinguisher in this additional game is bounded by Adv sTCDH B sTCDH (G p , Ḡp ) for the groups G p and Ḡp . In any other case the honest party will return ISK values indistinguishable from random values in both, the real world and the ideal world. As the adversary may choose to attack both honest parties, the advantage has to be multiplied by two. We incorporate this change in the simulator by replacing the sCDH object instance that is embedded by the sSDH experiment class by an instance of the sCDH_sTCDH class from Fig. 12.

CPace using single-coordinate Diffie-Hellman

Some Diffie-Hellman-based protocols, including CPace, can be implemented also on a group modulo negation, i.a. a group where a group element Y and its inverse Y -1 (i.e. the point with I = Y •Y -1 ) are not distinguished and share the same binary representation 4 .

An elliptic curve in Weierstrass representation becomes a group modulo negation when only using x-coordinates as representation. We use the notation Ŷ for such ambiguous encodings and use Ŷ ← SC(Y ) for a function returning the x-coordinate for a point Y and (Y -1 , Y ) ← RC( Ŷ ) for the inverse operation reconstructing Y and Y -1 in an undefined order.

The major advantage of using this type of ambiguous encoding is that it can be helpful in practice for all of the following: reducing code size, reducing public key sizes and network bandwidth, avoiding implementation pitfalls [START_REF] Daniel | Curve25519: New Diffie-Hellman speed records[END_REF] and restricting invalid curve attacks to the curve's quadratic twist.

def class moduloNegationAdapter:

"uses the strip-and reconstruct functions SC and RC." def _init_(s,, baseExperiment): s.exp ←baseExperiment;s.records← []; def sampleY(s): Y ← ((s.exp).sampleY()) s.c ; s.records.append(Y ); return SC(Y ); def isValid( X):(X0, X1)←RC( X); return (s.exp).isValid(X0); def sampleH1(s): return (s.exp).sampleH1(); Consequently, many real-world protocols such as TLS only use this single coordinate for deriving their session key, as to give implementers the flexibility to take benefit of the above advantages.

def corrupt(s, h, Ŷ ): (Y, Y * ) ← RC( Ŷ ); if Y * in s.records: Y ← Y * ; return (s.exp).corrupt(h, Y ); def DDH(s,g, Ŷ , X, K): (Y, Y * ) ← RC( Ŷ ); if Y * in s.records: Y ← Y * ; (X, X * ) ← RC( X); (K, K * ) ← RC( K); return (
For the purpose of function definitions by chaining, we introduce a function RSC( Ŷ , x) that takes one ambigously encoded group element Ŷ in addition to one scalar x, i.e. takes the same operands as ScMul. We define RSC( Ŷ , x) such that it returns a tuple (Y, x) such that SC(Y ) = Ŷ . With this definition, we can formalize CPace using single-coordinate scalar multiplications with the chained functions ScMul x-only := (SC • ScMul • RSC), ScMulVf x-only := (SC • ScMulVf • RSC) and Gen x-only := SC • Gen, such that the ambiguous encodings are used. 5Theorem 6.7 (Security of CPace x-only ). Given a group G, assume CPace[Gen, ScMul, ScMulVf, SamSc] on G can be distinguished from an ideal-world run of F lePAKE and S from Fig. 5 with negligible advantage, where S embeds an experiment object exp. Then CPace[SC • Gen, SC • ScMul • RSC, SC • ScMulVf • RSC, SamSc] on the corresponding group modulo negation Ĝ cannot be distinguished from F lePAKE running with a simulator Ŝ that is obtained by chaining exp with moduloNegationAdapter, the adapter class from Fig. 14, and the difference in the distinguishing advantage is bounded by a factor of 2.

Proof Sketch. First note that the functions SC,RC and RSC that implement conversion between group and group modulo negations are all efficient, as in practice the most complex substep is a square root in F q . Secondly, CPace does not need a full group structure at any point. Instead, only chained exponentiations are used (K = Y y b a = Y ya b = g ya•y b ), which can likewise be implemented on a group modulo negation. The protocol's correctness is not affected.

When starting with single-coordinate CPace in the real world, the same proof strategy applies, however the collision probability in game G 3 is increased by a factor of 2. In game G 4 no change is required. Also in games G 5 and G 6 the only difficulty shows up when splitting off the code for the full-group versions of the sSDH and sCDH experiments exp from the simulator code. We cannot embed the experiment object exp as-is but need to reconstruct the sign information in order to serve the API of the full-group experiments. The corresponding strategy is implemented in the moduloNegationAdapter adapter class from Fig. 14. Note that this strategy never aborts itself but its incorporated sSDH or sCDH experiments abort upon DDH queries. As the moduloNegationAdapter adapter queries the DDH at most two times, the loss of CPace x-only in comparison to CPace is at most a factor of two.

Chaining the experiment classes

In Appendix G, we describe 3 CPace implementations which combine the single aspects discussed in the previous sections in various combinations. The experiment that encodes the assumptions that apply for the construction that we recommend for use on twist secure Montgomery curves is specified by the "twistXonlyExp" object from Fig. 12. Correspondingly the assumption set that is necessary for proving the security of CPace on the group abstraction construction from Appendix G for ristretto25519 and decaf448 [START_REF] Hamburg | Decaf: Eliminating cofactors through point compression[END_REF][START_REF] De Valence | The ristretto255 and decaf448 groups. Rfc, IRTF[END_REF] is defined by the "coffeeExp" object from Fig. 9. The assumption set needed for proofs for our recommended construction with short-Weierstrass curves is specified by the "singleCoorExp" object in figure Fig. 14. A concrete example how this process is carried out is given in Appendix F.

The protocol is parametrized by a security parameter λ and operates on a group G of prime order p, of which membership is efficiently decidable. Let H1 : {0, 1} * → G and H2 : {0, 1} * → {0, 1} λ be two hash functions. Protocol:

1. When P receives input (NewSession, sid, P, P , pw), it sets g ← H1(pw). P then samples y ←R Z * p and sets Y ← g y . P stores a session record (sid, P , y, Y, fresh) and sends (sid, Y ) to P .

2. When P receives message (sid, X) from P with X ∈ G, and P finds a session record (sid, P , y, Y, fresh), it sets K ← X y . If K = IG, then P aborts. If K = IG, P calculates ISK ← H2(K||oc(X, Y )) and outputs (sid, ISK). In either case P rewrites the session record from fresh to completed . A Proof of Theorem 5.1

We start with the real execution of the CPace protocol with an adversary A, and gradually modify it, ending up with the ideal execution F lePAKE with a simulator S. The changes will go unnoticed by an (adaptively corrupting) environment Z interacting with parties and the adversary. For clarity, we formalize the UC execution of CPace base in Fig. 15.

Let Real Z (CP ace, A) be the event that environment Z with adversary A and an execution of CPace outputs 1 and Ideal Z (F lePAKE , S) be the corresponding event in the ideal execution with functionality F lePAKE depicted in Fig. 1.

Game G 0 : The real protocol execution. This is the real world in which the adversary interacts with real players and may view, modify and/or drop network messages and adaptively corrupt parties.

P r[Real

Z (CPace, A)] = P r[G 0 ]
Game G 1 : Introducing the simulator. In this game we move the whole execution into one machine and call in the simulator S. Note that this implies that S implements the random oracles H 1 , H 2 and runs the execution with actual passwords as input. We will change the simulation to work without passwords in the upcoming games. In this game for any new input query s for H 1 (H 2 ) samples a point on the curve (a random string) respectively. No re-programming operation is yet needed. The changes are only syntactical and thus

Pr [G 0 ] = Pr [G 1 ]
Game G 2 : Embedding trapdoors. In this game we start keeping track of secret exponents for generators created from passwords. S samples a fixed generator g ← G. For every hash query H 1 (pw), S samples r ← F p , stores (H 1 , pw, r, r -1 , g r ) and replies to the query with g r . The only difference is that the simulator now keeps track of the secret exponents for H 1 queries and the distributions of this and the previous game are perfectly indistinguishable

Pr [G 1 ] = Pr [G 2 ]
Game G 3 : Abort on collisions of the random oracle H 1 . The simulator aborts if a collision occurs in H 1 , i.e., if S samples an answer for a fresh H 1 query that he already gave before. Note that without collisions two honest parties will always output matching (respectively differing) session keys if both, passwords and party identifiers, match (respectively differ). Note that authenticating party identifiers in addition to the password is important for fending off relay attacks. As the order of the group is p ≈ 2 λ and Z can only make a polynomially bounded number l H 1 ) of H 1 queries, the probability of aborts is negligible in λ by the birthday bound. Thus this and the previous game are indistinguishable.

| Pr [G 2 ] -Pr [G 3 ] | ≤ l 2 H 1 /p
Game G 4 : Introduce F and simulate the protocol messages. In the real world all session keys will be calculated by using H 2 queries. In the ideal world session keys of honest parties will not be generated by H 2 queries but will be provided separately by the ideal functionality (with mechanisms in F for synchronizing H 2 outputs and session keys in case of successful password guesses). Here we prepare this separation and use programming operations for the H 2 RO for keeping session key outputs consistent with H 2 .

Changes to the functionality. In this game we add an ITI F external to the simulator. F has all interfaces of F lePAKE except that we don't yet limit the number of calls to the LateTestPwd and TestPwd queries and make the NewKey interface always relay keys coming from the simulator via NewKey queries. Also in this game we let F inform the simulator about the clear-text passwords upon NewSession events.

Changes to the simulation. Upon receiving an adversarially generated Y a ∈ G \I G or Y b ∈ G \I G aimed at a party P, S sends (RegisterTest, P) to F. S simulates protocol messages Y a = g za and Y b = g z b on behalf of honest parties by sampling exponents z a , z b uniformly from Z * q-1 . Upon an adaptive corruption query of Z for a party P sending Y a (respectively Y b ), S obtains P , pw, ISK from the ideal functionality, computes secret scalars y a (respectively y b ) used by the real-world protocol as y a = z a • r -1 (respectively y b = z b • r -1 ), where r -1 has been looked up in the record (H 1 , pw||oc(P, P ), * , r, r -1 , g). (S creates a new such record for pw||oc(P, P ) if none yet exists.) Sim then uses y a to compute K, program H 2 (K||oc(Y a , Y b )) = ISK and reveal (P , pw, y a , Y a , K, ISK) to A as the internal state of the corrupted P. As r = 0 uniformly sampling y a (y b ) or z a (z b y) is equivalent. In the following we detail how the simulator produces consistent outputs and answers to H 2 queries. While being straightforward, the presentation is slightly involved since the order of queries and messages impacts the simulation.

When S needs to issue a key to a party P using password pw for points Y a and Y b , then either Y a or Y b will have been generated on behalf of P. S looks for a record (H 1 , pw||oc(P, P ), * , r, r -1 , g) (and creates a H 1 entry for pw||oc(P, P ) if no such record exists). If Y a was generated for P,

then set K = Y zar -1 b , otherwise set K = Y z b r -1 a .
• Adjust output of P to earlier H 2 query: S then checks whether there is any record (H 2 , K||oc(Y a , Y b ), ISK) such that K = K . Note that in this case it holds that both, DDH(g r , Y a , Y b , K) = DDH(g, Y a , Y b , K r -1 ) = 1. In this case S executes the TestPwd query of F for pw and subsequently passes ISK to the NewKey query of F. We note that our simulator does not make use of the reply "correct/wrong guess" (since there are no more values of the honest party to simulate after the guess happens), but still needs to issue TestPwd in order to be able to determine the attacked party's output via NewKey in case of a successful guess. • Adjust H 2 query to key of P: Else if all of (1) Y a = g za was simulated for honest party P and (2) NewKey was already delivered to F for P and (3) there is a record (H 1 , pw||oc(P, P ), r, r -1 , g) such that K = Y zar -1 b (which occurs if DDH(g r , Y a , Y b , K) = DDH(g, Y a , Y b , K r -1 ) = 1) then: S sends (LateTestPwd, P, pw) to F. S programs F's answer to this query as reply to the H 2 query.

• Adjust H 2 query to key of P : Else if Y b = g z b was simulated for honest party P . S proceeds as for honest P but checks for K = Y z b r -1 a .

• Else we conclude that there is no need for adjustment and the H 2 query is answered as in the previous game.

Note that with these changes, S never needs to actually calculate itself a Diffie-Hellman result point K, instead it only makes sure that H 2 queries for parties that adhere to the protocol and keys output to honest parties match. Instead from this point on, the simulators will only need access to DDH(g, Y, •, •) or DDH(g r , Y, •, •) oracles for a fixed generator g and a honestly generated point Y as second parameter which we could implement easily in this game as we have access to the secret exponents.

Indistinguishability argument. There is no change from the viewpoint of Z between this and the previous game. The game only differs in the way how session keys and H 2 queries are output. In both games, both, the output of H 2 queries and session keys, are uniformly sampled. Just as in the previous game, session keys output to two honest parties match if P and P have used same password and differ otherwise.

Finally the session keys output to honest parties with password pw match H 2 queries taken for queries using a Diffie-Hellman point K that would be calculated by parties that follow the protocol. It follows that

Pr [G 3 ] = Pr [G 4 ]
Game G 5 : Limit number of password guesses

Changes to the functionality.

] -Pr [G 5 ] |≤ 2l 2 H 1 Adv sSDH B sSDH (G).
Remark. We note that any reduction could make use of the true password of P , since a reduction interfaces with Z and thus also receives protocol inputs. However, it is unclear how to leverage this, since multguess implies that Z makes at least one incorrect guess. Thus, S needs to turn password guesses into CDH solutions regardless of whether a guess is correct or not. Further, we note that a reduction to the strong CDH assumption seems infeasible here. In case of LateTestPwd (H 2 was queried after P generated output), the key output to P was the randomly chosen K generated by the LateTestPwd interface of F lePAKE in the previous game, which is perfectly indistinguishable from the randomly chosen one that the NewKey interface of F lePAKE outputs directly to P in this game due to the record being interrupted.

Game G 7 : Output random keys for honest sessions

In this game, we let the functionality generate parties' outputs in honest sessions. We change the simulation to work without passwords and without knowledge of the honest parties outputs.

Changes to the ideal functionality. We now add the full NewKey interface to F.

Changes to the simulation. Let m denote the number of H 1 queries issued by Z and r 1 , . . . r n ← F q the trapdoors embedded in these queries (see G 2 Game G 8 : Remove passwords from simulation.

Changes to the ideal functionality. We remove passwords from NewSession queries sent from F to S.

Changes to the simulation. As the simulation already is independent of the password, there are no further changes required.

Since we are just removing unused values from the output of F towards S, the output distributions towards Z of this and the previous game are indistinguishable. Hence,

P r[G 7 ] = P r[G 8 ] = P r[Ideal Z (F lePAKE , S)]
This game is identical to the ideal execution since F = F lePAKE , which concludes the proof. The simulator of this final game is depicted in Fig. 3 P a :

public: G, p, P b : P b , pw a ScMul base , ScSam p , P a , pw b ScMulVf base , H 1 , H 2 , Map2Pt g a ← Map2Pt(H 1 (pw a )) g i ← Map2Pt(H 1 (pw b )) y a ← ScSam p () y b ← ScSam p () Y a ← ScMul base (g a , y a ) Y b ← ScMul base (g b , y b ) P b , Y b P a , Y a K a ← ScMulVf base (Y b , y a ) K b ← ScMulVf base (Y a , y b ) Abort if K a = I G Abort if K b = I G ISK a ← H 2 (K a ||oc(Y a , Y b ))||oc(P a , P b )) ISK b ← H 2 (K b ||oc(Y a , Y b ))

B Game-based security analysis

In the main body of this paper we demonstrated strong composability guarantees for several CPace variants. These strong guarantees come at the cost of requiring pre-established unique session identifiers sid , for each exchanged key. This might require an additional round of messages in practice, and it is thus a reasonable question to ask which security guarantees CPace features if such overhead is unacceptable for the application. In this section we therefore complement the conducted analysis in the UC framework with a corresponding game-based analysis, exemplarily considering the case of CPace 1MAP . In Fig. 16 we show "sid-free" protocols CPace 1MAP_NoSID and CPace 1MAP_NoSID_ID .

• CPace 1MAP_NoSID is a symmetric protocol where both parties initially send their messages, and compute their outputs after receiving the message from the peer. Both parties know the identities (P a , P b ) involved in the exchange, and hence there is no need to inform the other peer about the own identity.

• CPace 1MAP_NoSID_ID is an asymmetric protocol where one party, say, P b initializes the key exchange with peer P a by sending the first message. This message contains identity P b . P a only acts upon receipt of such message, informing P b about its own identity by appending it to the message. Such a protocol layout is useful in cases where P a might not know under which name (e.g., IP address and port) it got contacted by P b -might it be because of proxying, NATing, or simply because the API running the PAKE protocol does not have access to the routing information.

B.1 Security Model

We base our analysis on the PAKE security model of Bellare, Pointcheval and Rogaway [START_REF] Bellare | Authenticated key exchange secure against dictionary attacks[END_REF], refined for analyzing the PAKE protocol SPAKE2 by Abdalla et al. [START_REF] Abdalla | Perfect forward security of SPAKE2[END_REF][START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF]. The definition comprises specifications of procedures to respond to various queries issued by an adversarial algorithm A. A "real-or-random" game is run with an adversary A as follows. First INITIALIZE runs and its outputs, except for secrets such as the challenge bit, are passed to A. Subsequently A is executed and its oracle queries are answered by the procedures of the game. When A terminates, its output is passed to FINALIZE, which returns true if the adversary manages to guess the challenge bit correctly. During the game, A has access to test queries (we allow multiple such queries, as suggested by Abdalla, Fouque, and Pointcheval [START_REF] Abdalla | Password-based authenticated key exchange in the three-party setting[END_REF][START_REF] Abdalla | Password-based authenticated key exchange in the three-party setting[END_REF]), which reveal real or random keys according to the challenge bit. A REVEAL query models leakage of session keys, where the adversary obtains the session key computed by an honest party. We assign honest parties a number i, a distinct party identifier bit string P i and consider that party P i may be interacting in multiple protocol instances l i . We use the notation (P i , l i ) for referring to the protocol instance l i of party P i . Initially, at the INITIALIZE operation for each pair of parties a password is drawn uniformly from a dictionary D pw . We call two instances partnered if they share a common communication transcript. Each instance (P i , l i ) may be in state waiting, accepted or aborted. State waiting corresponds to an instance which has produced its own CPace message but not yet received the remote side's message. State accepted models an instance which has received and processed the remote side's protocol message and calculated its session key ISK . State aborted models an instance of a party which has aborted due to invalid inputs. TEST queries are only allowed if no REVEAL query has been asked for the party itself or a partnered party. The adversary has the option of either querying REVEAL or TEST, but not both.

Adaptions to the security model of Abdalla et al. [START_REF] Abdalla | Perfect forward security of SPAKE2[END_REF][START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF]. Previous game-based security analysis of PAKE protocols did assume protocols which clearly assign initiator and responder roles.

Instead, here we also consider the option of a symmetric CPace 1MAP_NoSID construction where any honest party first outputs its own message before processing the remote party's message.

For this, we strengthen the adversary model by allowing A to adaptively react to the messages sent by honest parties. As a result of this adaptions, we do not have an additional SENDRESP query [START_REF] Abdalla | Perfect forward security of SPAKE2[END_REF][START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF]. The parts in the security games for the initiator-responder instantiation that are not present in the symmetric variant are highlighted by using gray-shaded boxes. In both variants we use the ordered concatenation operation oc as in the symmetric setting there is no natural ordering enforced by the message sequence (see also the corresponding discussion in Appendix D).

Altogether, we give A access to the following queries:

• H 1 (pw), a hash function taking a bit string and returning an element in F q . This models that A has access to the same random oracle as the honest parties and is able to calculate CPace's password-dependent generators as g pw ← Map2Pt(H 1 (pw)).

• H 2 (•), the hash function used for generating CPace's session key ISK , is a function that takes a bit string of arbitrary length and returning a bit string of size λ.

• SENDINIT(P i , l i , P j ) a query returning the message produced by instance l i of a honest party P i that was generated for initiating a communication with a remote party P j . This query leaves (P i , l i ) in state waiting.

• SENDFINALIZE(P j , l j , ( P i , Y )), makes a waiting instance (P j , l j ) transition to state accepted. It models the action the protocol party takes upon reception of the remote side's message. SENDFINALIZE in conjunction with SENDINIT can be used for modeling both, active and passive adversaries.

• REVEAL(P j , l j ), this query returns ⊥ if the instance was not accepted or TEST was previously called. Otherwise it marks the transcript of the instance as revealed and reveals the session key.

• TEST(P i , l i ), if instance l i of party P i is not in accepted state or a REVEAL or TEST query has been run previously on an instance with the same transcript it returns ⊥. Otherwise this query reveals either the session key of P i , l i (case b = 0) or a freshly sampled random key (case b = 1).

Note that we do not have the EXEC(P i , l i , P j , l j ) query from [START_REF] Abdalla | Perfect forward security of SPAKE2[END_REF]. The reason is that it can be implemented by first calling SENDINIT(P i , l i ) and SENDINIT(P j , l j ) and passing the respective results without any modification to two SENDFINALIZE queries to (P i , l i ) and (P j , l j ). I.e., there is no need for a dedicated separate EXEC query returning the transcript that a passive adversary records when eavesdropping the communication between two honest parties as also observed in [START_REF] Bellare | Authenticated key exchange secure against dictionary attacks[END_REF]. We call a query SENDFINALIZE(P j , l j , ( P i , Y )) to be a passive attack query if Y was returned as the result of a previous SENDINIT(P i , l i , P j ) query. Otherwise we define a SENDFINALIZE query to be an active attack query.

In Fig. 17 we depict how the game is played for CPace 1MAP_NoSID and CPace 1MAP_NoSID_ID , where all adversarial queries are implemented by an object of class GameA. (Note that we follow the convention of the Python programming language and use a prepended underscore for distinguishing private functions accessed only from within the class from the public API that is available for the adversary.)

B.2 Game-based security of CPace

Theorem B.1 (Security of CPace 1MAP_NoSID and CPace 1MAP_NoSID_ID ). Let λ, p, q ∈ N with p prime. Let G be an elliptic curve group of order p over field F q . Let H 1 : {0, 1} * → F q , H 2 : {0, 1} * → {0, 1} λ be two hash functions and Map2Pt : F q → G probabilistically invertible with bound Map2Pt.n max . Let D pw denote a uniformly distributed dictionary of passwords of size |D pw |. If the sCDH and sSDH problems are hard in G, then CPace 1MAP_NoSID (CPace 1MAP_NoSID_ID ) is secure in the model of Fig. 17, when both hash functions are modeled as random oracles.

More precisely, for any adversary A against CPace 1MAP_NoSID (CPace 1MAP_NoSID_ID ) there exist adversaries B sCDH and B sSDH against the sCDH and sSDH problems such that the advantage of A of producing the correct test bit in the FINALIZE query of the security game is bound by For the proof we follow the proof of SPAKE2 [START_REF] Abdalla | Perfect forward security of SPAKE2[END_REF][START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF], using a sequence of game hops. We start with Game A which represents the security Game for CPace 1MAP_NoSID ( CPace 1MAP_NoSID_ID ). Throughout the proof we will modify the security games such that they are indistinguishable from the viewpoint of the adversary except for some bad events, for which the games abort and where we declare the adversary to win.

Adv(A) ≤
Game B : Unique transcripts.

In this game we consider collisions in the transcripts and abort if we observe a collision, declaring the adversary to win. We also abort if we observe an accidental collision between a public key Y generated by a SENDINIT query and a preceding H 2 query which includes the same value Y . 6As each session transcript with one honest party involved includes an ephemeral public key Y which is uniformly distributed in G, this can be bounded by a statistical analysis to ((n s + n H 2 ) 2 /p) where n is the number of SENDINIT queries and p the order of G. In this game we replace the implementation of H 1 by an implementation based on Algorithm 1 for Map2Pt -1 . As by Corollary 3.9 the modified sampling strategy using Map2Pt -1 still results in uniformly distributed outputs in F q . This makes the two games indistinguishable. Moreover the adversarial advantage does not differ in comparison to the previous game.

access to the secret exponents r. Also we have access to the secret exponent y used for generating the point Y produced for instance (P i , l i ). I.e. just as in the case of the UC proof, we can use the secret exponents for implementing a restricted sSDH DDH oracle. This allows us to detect specific values K in the hash query that correspond to password guesses. This way, we are able to count the number of successful adversarial guesses for K for different passwords. If we observe more than a single successful guess, then we let the code abort. If we observe a first password guess by the adversary, we return the adversary the same result as produced by the private _H 2 query, as in the previous game. However, if we do not detect any password guess, we give the adversary a result from a private random oracle.

In both, the previous game and this game any session key calculated by a protocol instance will necessarily correspond to some password. A hash query on the _H 2 as used by the simulated instances is, thus always unrelated to a H 2 query that corresponds to no password guess. As a result the change in this game can only be distinguished if the adversary's query corresponds to a password guess. Indeed for the first observed password guess the public H 2 is returning the same result as the private oracle _H 2 . We identify this condition by using the _DDH function prepared in the previous game.

On the other hand, the bad event of more than a single password guess can be reduced to the sSDH problem with a loss proportional to the square of the number of H 1 queries (See the corresponding game 5 in the UC proof.) As a result, this and the previous game are indistinguishable except for the bad event that a solution to the sSDH challenge that is provided by the code of the H 1 and SENDINIT queries. could keep going on like this, having to solve one instance of a DLP per password guess. Moreover, if generators depend only on passwords, as is the case in Fig. 16, then solving a single DLP with respect to g pw allows A to efficiently compute the key corresponding to pw in all actively attacked sessions. For a more quantum annoying CPace, Gen must contain session-specific information. Computing g pw ← Map2Pt(H 1 (P ||P ||pw)) forces A to solve one DLP instance per password per pair of parties, and computing g pw ← Map2Pt(H 1 (sid ||P ||P ||pw)) with session-specific information sid finally forces A to solve one DLP per password guess.

Conclusion.

Our security analysis of CPace in the UC framework in Section 5 requires that, prior to entering the protocol, a pre-established unique session identifier sid is available to both parties. As the above game-based security analysis highlights, CPace features also strong albeit different8 security guarantees if there is no such pre-established sid .

C On shortcomings of UC PAKE functionalities

We provide an illustrating example on how a shortcoming in existing PAKE functionalities from the literature [START_REF] Canetti | Universally composable password-based key exchange[END_REF][START_REF] Jarecki | OPAQUE: An asymmetric PAKE protocol secure against pre-computation attacks[END_REF][START_REF] Hesse | Separating symmetric and asymmetric password-authenticated key exchange[END_REF][START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF] impacts their suitability for building higher-level applications from PAKE. Let us first detail what shortcoming we are talking about. In PAKE functionalities, the adversary A gets to determine the session key of honest users in some cases. This makes sense if A manages to guess an honest party's password during an interaction with said party, in which case A can compute the very same session key and thus the party's output is no longer uniformly random (from the viewpoint of the adversary). But strangely, all existing PAKE functionalities also allow the adversary to determine the honest party's key K * via NewKey queries if (cf. Fig. 1) either P or P is corrupted. This contradicts the principle of authenticated key exchange, where unauthenticated entities (i.e., honest or malicious parties not knowing the password) should not be allowed to learn the key computed by an honest party.

Does this mean all known PAKE protocols are insecure? Most importantly, all PAKE protocols proven w.r.t any of the existing PAKE functionalities can still be considered secure. On a technical level, the reason is that these functionalities still provide all guarantees one would expect from a PAKE against network attackers, as long as no corruptions occur. Besides that, we are not aware of any actual UC PAKE security analysis that exploits the above shortcoming in their simulation, and conjecture that they can be proven secure without this shortcoming.

Why bother then to fix this? The shortcoming's effect shows when a PAKE functionality is used to modularly build other protocols. Modular protocol analysis requires strong composability guarantees of security proofs and is one of the main features of the UC framework. As an example, assume we want to build password-authenticated secure channels from F pwKE depicted in Fig. 1. Intuitively, a password-authenticated secure channel allows two parties to securely communicate if and only if they hold the same password. Consider the following password-based channel toy

Figure 1 :

 1 Figure 1: UC PAKE variants: The original PAKE functionality F pwKE of Canetti et al.[START_REF] Canetti | Universally composable password-based key exchange[END_REF] is the version with all gray text omitted. The lazy-extraction PAKE functionality F lePAKE[START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF] includes everything, and the variant of F lePAKE used in this work includes everything but the dashed box.

Theorem 3 . 6

 36 (sSDH ⇐⇒ D G -sSDH). Let G be a cyclic group of order p and D G a probability distribution on G. If there exists a PPT rejection sampler RS for (G, D G ) with acceptance rate (1/n) then the probability of PPT adversaries against D G -sSDH and sSDH of solving the respectively other problem differs by at most (2D(I G ) + (1/p)) and solving sSDH with the help of a D G -sSDH adversary requires at most 2n executions of RS on average.

Figure 2 :

 2 Figure 2: Above: Blueprint protocol CPace[Gen, ScMul, ScMulVf, ScSam] requiring group G of order c • p with prime p and algorithms for DH generator computation (Gen), exponentiation (ScMul, ScMulVf) and scalar sampling (ScSam). H 2 : {0, 1} * → {0, 1} λ denotes a hash function. This blueprint can capture most artifacts of current CPace implementations. Below: "Basic" CPace CPace base with c = 1, generators computed from hash function H G : {0, 1} * → G and canonical exponentation, point verification and sampling.

Figure 3 :

 3 Figure 3: Simulator for CPace base , with game numbers to indicate which game introduces a particular line of code (cf. full proof of Theorem 5.1 in Appendix A). For brevity we omit the session identifier sid from all records stored by the simulator.

Figure 4 :

 4 Figure 4: Libraries implementing sCDH and sSDH experiments.

Figure 5 :

 5 Figure 5: Generic simulator for different CPace variants, embedding challenges generated by the experiment object exp. The simulator for CPace base is obtained when using exp ← sSDH(sCDH) from Fig. 4.

Figure 7 :

 7 Figure 7: Experiment class definition D G -sSDH using single executions of Map2Pt, where H 1 hashes to F q .

Figure 11 :

 11 Figure 11: Cofactor-clearer class definition use for elliptic curves of order p • c with a quadratic twist having a subgroup of order p. Note that the inverses s.i and s.it are constructed such that they are multiples of c.

#

  Chaining the experiment objects for the case of X25519 and X448 twistSdhExp = sSDH(sCDH_sTCDH); twistCcExp = cofactorClearer(twistSdhExp,c, p, p); twistDistExp = DG_sSDH(Map2Pt,twistCcExp); twistXonlyExp =moduloNegationAdapter(twistDistExp);

Figure 12 :

 12 Figure12: Class combining sCDH and sTCDH experiments. In addition to the previous challenge generator class for sCDH, point verification now also accepts points from the twist except for the twist's neutral element. Moreover the code for the DDH oracle now also accepts its third and fourth inputs X, K from the twist and aborts in case that (X, K) forms a solution of the sTCDH problem for (g, Y ).

Figure 13 :

 13 Figure 13: Definition of CPace twist for curves G of order p • c with a quadratic twist Ḡ. The only difference to CPace co is that the scalar multiplication functions accept inputs also from the twist.

Figure 14 :

 14 Figure 14: Single-coordinate experiment class definition for CPace instantiations on groups modulo negation.

Figure 15 :

 15 Figure 15: UC execution of CPace base from Fig. 2 (bottom), proven secure in Theorem 5.1.

=

  g y b ya1/a , where (g, Y a , Y b , K a ) is a CDH tuple. We stress that P computes the same value K regardless of whether both parties use matching or mismatching passwords, since P's output only depends on the simulated Y b and is independent of the generator used by P . We show that if sCDH holds in G then S never aborts. Consider the following efficient adversary B sCDH . B sCDH obtains an sCDH challenge (g, Y a , Y b ) and executes the simulation of game G 7 with it. Upon Z querying H 2 (K||oc(Y a , Y b )), B sCDH needs to detect CDH solutions using his own oracle instead of knowledge of exponents of Y a , Y b . For this, B sCDH calls b ← DDH(g, Y a , Y b , K a i ) and outputs K a i as sCDH solution if b = 1 happens. It follows that | Pr [G 6 ] -Pr [G 7 ] |≤ Adv sCDH B sCDH (G).

Figure 18 :

 18 Figure 18: Guarantee unique transcripts.

  Adv sCDH B sCDH (G) and Adv sSDH B sSDH (G), we denote the probabilities that adversarial algorithms B sSDH and B sSDH having access to the restricted DDH oracles provide a solution for the sCDH and sSDH problems respectively in G when given a single randomly drawn challenge. Definition 3.3 (Strong simultaneous non-uniform CDH problem (D G -sSDH)). Let G be a group and D G be a probability distribution on G. The strong simultaneous non-uniform CDH problem D G -sSDH is defined as the sSDH problem but with (X, g 1 , g 2 ) sampled using U G × D G × D G , where U G denotes the uniform distribution on G.

  (NewSession, sid , Pi, Pj) from F lePAKE : (G4)sample zi ←R Zp (G4)set Yi ← g z i ; store (Pi, Pj, zi, Yi, ⊥) (G4)send Yi to A intended to Pj On Z * from A as msg to (sid , Pi): (G4)if Z * is adversarially generated (G4)and Z G5) store (guess, G, Yj); abort if ∃ record (guess, G , Yj) with G = G ; (G4) send (TestPwd, sid , Pi, pw) to F lePAKE ; (G4) send (NewKey, sid , Pi, ISK ) to F lePAKE and store (Pi, Pj, zi, Yi, ISK ) (G4)else: sample a fresh random ISK and send (NewKey, sid , Pi, ISK ) to F lePAKE On msg (AdaptiveCorruption, sid , Pi) from A (instructed by Z): send AdaptiveCorruption, sid , Pi) to F lePAKE Upon receiving (sid , Pj, pw, ISK ): (G4)if a msg Yi := g z i already sent to Pj:

	On H1(pw||P||P ) from A:
	(G2)if this is the first such query:
	(G2) sample r ←R Fp \ {0}
	(G3) abort if ∃ rec. (H1, * , r, * , * ) (G2) store (H1, pw||P||P , r, r -1 , g r )
	(G2)retrieve rec. (H1, pw||P||P , * , * , h)
	(G2)reply with h

* ∈ G \ IG: send (RegisterTest, sid , Pi) to F lePAKE Upon Pi receiving (sid, Yj) with Yj ∈ G from Pj: (G4)retrieve record (Pi, Pj, zi, Yi, * ) (G4)if ∃ records (G5)(H1, pw||oc(Pi, Pj), r, r -1 , G), (H2, K||oc(Yi, Yj), ISK ) s.th. K = Y z i r -1 j : (

  # using python-style notation with self pointer s and _init_ constructor def class sCDH: def _init_(s, g): s.g ← g; s.i ← 0; s.state← fresh; def sampleY(s): if s.i < 2: s.i+ = 1; sample s.yi ←R Fp \ 0; return (s.g) s.y i ; X}={s.Y1, s.Y2}) and (s.state= fresh) and (K = (s.g) s.y 1 •s.y 2 ): = (s.g) s.ym ): return (K = X s.ym ); def isValid(X): return (X ∈ G \ {IG}) def class sSDH: # using python-style notation [ ] for list containers def _init_(s,sCdhExp): # Gets sCDH class; samples g; creates a sCDH instance s.g ←R G; s.scdh = sCdhExp(s.g); s.records =[ ]; s.guess = "yet no guess"; def sampleY(s): return (s.scdh).sampleY();

	def corrupt(s,X):
	for 1 ≤ m ≤ s.i:
	if (X = (s.g) s.ym ): s.state← corrupt; return s.ym;
	def DDH(s, g, Y, X, K):
	if (g = s.g): return;
	if ({Y, abort("sCDH(g, Y1, Y2) solved")
	for 1 ≤ m ≤ s.i:
	if (Y

def isValid(s, X): return (s.scdh).isValid(X); def sampleH1(s): sample r ←R Fp \ {0}; if (r, * ) in s.records: abort("Hash to group collision"); else: s.records.append((r, (s.g) r )); return (s.g) r ; def corrupt(s, R, Y ): if there is (r, R) in s.records: return (s.scdh).corrupt(Y 1/r ); def DDH(s,R, Y, X, K): if there is (r, R) in s.records: match ← (s.scdh).DDH(s.g, Y, X, K 1/r ); if match and (s.guess = "yet no guess"): (s.guess.g,s.guess.X)← (R, X); elif match and (s.guess.X = X) and (s.guess.g = R): abort("sSDH problem (Y, R, s.guess.g) solved"); return match;

  h) and send h if it exists; (G 4 )else if this is the first such query: (G 4 ) if there are no records (P i , P j , Y i , * ) or (P j , P i , Y j , * ), or if Ya||Y b = oc(Ya, Y b ):

	(G 4 )	sample A ← {0, 1} 2k ;

(G 4 ) if ∃ records (P i , P j , Y i , ISK ) with ISK = ⊥ and (H 1 , pw, h)

(G 4 ) such that exp.DDH(h, Y i , Y j , K) = 1: (G 5 ) send (LateTestPwd, sid, P i , pw) to F lePAKE . Upon answer K set A ← K (G 4 ) if ∃ records (P j , P i , Y j , ISK ) with ISK = ⊥ and (H 1 , pw, h) (G 4 ) such that exp.DDH(h, Y j , Y i , K) = 1: (G 5 ) send (LateTestPwd, sid, P j , pw) to F lePAKE . Upon answer K set A ← K (G 4 ) if no matching H 1 records are found set A ← {0, 1}

2k

(G 4 ) finally, store (H 2 , sid||K||Y i ||Y j , A) and reply with A

  CPace 1MAP := CPace[Gen 1MAP , ScMul base , ScMulVf base , ScSam p ] Gen 1MAP (pw, P i , P j ) : ScMul base (g, y) : ScMulVf base (g, y) : ScSam p () : return return g y if g / ∈ G: return I G y ← R 1 . . . p Map2Pt(H 1 (pw||oc(P i , P j )))

  # using python-style notation with self pointer s def class cofactorClearer:"interfaces S to a prime-order experiment class" def _init_(s, c, p, primeOrderExpInstance ,p): s.c=c; s.i= s.c • integer(1/(s.c 2 ) mod p);s.it= s.c • integer(1/(s.c 2 ) mod p); s.exp = primeOrderExpInstance; def sampleY(s): return ((s.exp).sampleY()) s.c ; def isValid(X): return (s.exp).isValid(X s.i ) def sampleH1(s): return (s.exp).sampleH1(); def corrupt(s, h, Y ): { return (s.exp).corrupt(h, Y s.i ); } def DDH(s,g, Y, X, K):if X ∈ G: return (s.exp).DDH(g, Y s.i , X s.i , K s.i•s.i ) if X on twist: return (s.exp).DDH(g, Y s.i , X s.it , K s.it•s.it )

	sSdhExp = sSDH(sCDH); ccExp = cofactorClearer(sSdhExp);
	ccDistExp = DG_sSDH(Map2Pt,ccExp);

•

  Align keys in case of matching passwords: If no corresponding H 2 record is found and both points Y a , Y b were generated by honest parties and the passwords of both parties match and a NewKey query has already been issued to the other party, then S calls NewKey for P using the key already passed to P .• In any other case there is no output yet to keep consistent with. S samples a new random key just as for new H 2 queries and passes this key to the NewKey query of F.Upon Z querying H 2 (K||Y a ||Y b )for a yet unqueried input, • Query not related to any honest output: If neither Y a nor Y b were generated by an honest party or Y a ||Y b = (Y a || < ||Y b ) then sample a new random value and output it as result for H 2 .

  The number of password guesses is now limited to one guess per party. I.e. there is one guess per record (sid , P, P , pw).Changes to the simulation. S looks for CDH tuples in H 2 queries w.r.t all recorded exponents r in its H 1 list. If S finds a CDH tuple (G, X, Y, K) that meets the conditions of G 4 (where Y denotes the adversarially-generated message), S creates a record (guess, G, Y ). If at this point there is already a record (guess, G , Y ) with G = G , we say that event multguess happens and let S abort.Indistinguishability argument. The change is only recognizable if S has to abort. We show that this happens only with negligible probability if the sSDH assumption holds in G.We construct an efficient sSDH adversary B sSDH interacting with Z. Let (Y, G 1 , G 2 ) denote a sSDH challenge. B sSDH embeds the challenge in this game as follows: first, B sSDH flips a coin and sets Y to be either the message of P or P . B sSDH aborts if the chosen party is corrupted or gets corrupted at a later stage. Then, B sSDH randomly chooses two out of all H 1 queries made by Z and answer them with G 1 ← H 1 (pw||oc(P, P )) and G 2 ← H 1 (pw ||oc(P, P )) (pw and pw are going to be Z's two password guesses). B sSDH replaces the check performed by the simulator with oracle queriesDDH(G i , Y, Y , K), i = 1,2, where Y denotes the (simulated or adversarial) other message. If multguess occurs, then two CDH solutions were found, namely one for each G i . B sSDH outputs these two solutions. Since w.l.o.g Z corrupts at most one party and has a view independent of the coin flipped by B sSDH , B sSDH has to abort only with probability 1/2. Overall, it follows that P r[multguess] ≤ 2l 2 H 1 Adv sSDH B sSDH (G), where l H 1 denotes the number of H 1 queries made by Z. We thus have | Pr [G 4

  The reason is that S needs to detect password guesses in H 2 queries, which requires knowledge of the exponent of the simulated message Y b . The reduction however does not have this knowledge due to Y b being set to the CDH challenge, and thus needs to leverage DDH oracles w.r.t different generators for detecting both guesses.Indistinguishability argument. Assume the output was generated for an honest P (the other case works analogously). The output towards Z differs only in case TestPwd returns "wrong guess" or LateTestPwd returns a random key. S only issues these queries if he finds a CDH tuple in H 2 . In case of TestPwd (Y b was sent after H 2 query), let Y a , Y b denote the transcript and K the Diffie-Hellman value computed by P. The environment never submits (K||oc(Y a , Y b )) to H 2 , as otherwise the previous game would abort due to multguess happening. Thus, the output H 2 (K||oc(Y a , Y b )) of P in G 5 is uniformly random from the viewpoint of Z, and replacing it with a fresh random output chosen by F due to the interrupted record is perfectly indistinguishable.

	Changes to the simulation. -

Game G 6 : Random key if passwords mismatch Changes to the functionality. In case a record is interrupted, F now outputs a random key (instead of the one given by the simulator via NewKey).

  ). Let z a , z b denote the exponents of simulated messages as of G 4 . In caseZ queries H 2 (K||oc(Y a , Y b )), where for some i ∈ [m] (g, Y a , Y b , K r i ) is a CDH tuple (which can be checked by S via g zaz b = K r i ), S aborts.Indistinguishability argument. First note that Z can only note a difference between this and the previous game if it reproduces any value K or K computed by some (honest) party in a "fresh" and honest session. In particular, this means that Z cannot corrupt a party nor inject messages (as in this case S issues TestPwd or LateTestPwd and records get interrupted or compromised). Let us detail what party P computes (argument for P is analogously).

W.l.o.g we assume that Z queried H 1 (pw||oc(P, P )), where pw is the password of P, and obtained g a as answer. P was simulated with values g, y a , and we now implicitly adjust this to g a , y a • 1/a. This lets P compute K ← Y

  ||oc(P a , P b )) Output ISK a Output ISK b Figure 16: Protocols CPace 1MAP_NoSID and CPace 1MAP_NoSID_ID (with initiator P b and responder P a ), where dashed inputs are only available in CPace 1MAP_NoSID , and gray message parts only appear in CPace 1MAP_NoSID_ID . ScMul base , ScMulVf base , ScSam p are detailed in Fig. 2, and Map2Pt : F q → G is probabilistically invertible. With H 1 : {0, 1}

* → F q and H 2 : {0, 1} * → {0, 1} λ we denote hash functions.

  n aa /|D pw |+ (Map2Pt.n max )n H 1 /q + (Map2Pt.n max • n H 1 ) 2 /q + n 2 H 2 /2 λ +2n 2 H 1 Adv sSDH B sSDH (G) + 2Adv sCDH B sCDH (G) + (n s + n H 2 ) 2 /pwhere n aa denotes the number of SENDFINALIZE queries for an active attack, n s denotes the number of SENDINIT queries and n H 1 and n H 2 denote the number of H 1 and H 2 queries made by A.

In the case of PAKE, weak forward secrecy is implied by UC security and hence achieved also by prior work. If key confirmation is added, then this gives a protocol with perfect forward secrecy as noted in[START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF].

For the hardness assumptions on elliptic curve groups, e.g. for the sCDH and sSDH problems, where security depends on the group type and the group order p, the bit size of p implicitly serves also as a further security parameter.

Note that this class also accepts points on the quadratic twist, a feature that will become relevant only when considering simplified point verification on twist-secure curves as discussed in the upcoming sections.

Counter-examples for protocols that cannot be instantiated on a group modulo negation and require full group structure are, e.g., TBPEKE[START_REF] Pointcheval | VTBPEKE: Verifier-based two-basis password exponential key exchange[END_REF] and SPAKE2[START_REF] Abdalla | Simple password-based encrypted key exchange protocols[END_REF]. The reason is that these protocols require addition of arbitrary points on the group.

Note that this definition obtained from chaining with SC and RSC for the scalar multiplications corresponds exactly to the conventional so-called single-coordinate ladder algorithms.

We included this additional abort case in order to be able to disregard a corner case in the upcoming games. With this abort we will be able to disregard the case that such an collision in a H2 query preceeding the SENDINIT query actually corresponds to some password guess for an instance which point Y that was not yet existing at the time of the H2 query.

In fact if the same point X will be embedded into both attacked parties Pi and Pj the abort case corresponds to the event of a solution of the Square-Diffie-Hellman problem. For simplification in this already lengthy paper we decided to not introduce and define this additional problem in this paper and included a loss factor of two for the sCDH problem in the theorem statement instead.

While Theorem B.1 does not imply composability and holds only for randomly chosen passwords, it implies weak forward secrecy. Hence, both CPace 1MAP_NoSID and CPace 1MAP_NoSID_ID can be turned into PAKEs with perfect forward secrecy by adding key confirmation[START_REF] Abdalla | Perfect forward security of SPAKE2[END_REF][START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF]. We note that, without key confirmation, perfect forward secrecy of CPace 1MAP_NoSID and CPace 1MAP_NoSID_ID seems only provable by relying on the algebraic adversary model, a strategy that has been demonstrated to work for SPAKE2[START_REF] Abdalla | Perfect forward security of SPAKE2[END_REF][START_REF] Abdalla | Universally composable relaxed password authenticated key exchange[END_REF].

This is just a demonstrating example and not a suggestion for a practical protocol, which would require authenticated encryption[START_REF] Canetti | Universally composable password-based key exchange[END_REF].

As the u-coordinate-only approach does not distinguish the curve points g y and g -y = g p-y , also fixing the most significant scalar bit to one is not critical here.

* Author supported by the European Union's Horizon 2020 Research and Innovation Programme under Grant Agreement No. 786725 OLYMPUS.

# using python-style notation with self pointer s def class mapTwice_sSDH: def _init_(s, Map2Pt, sSDHExp): s.sSDH = sSDHExp; s.records = []; s.preim = Map2Pt.PreImages; s.nmax = Map2Pt.nmax def sampleY(s): return (s.sSDH).sampleY(); def isValid(X): return (s.sSDH).isValid(X); def sampleH1(s):

i ← 0; g ← (s.sSDH).sampleH1(); do while (i < 2): sample ri ←R Fp; preimageList = (s.preim)(g r i ); sample m ←R {0 . . . (s.nmax -1)}; if len(preimageList) > m: hi ←preimageList[m]; i+ = 1; h ← (h0, h1); r ← (r0 + r1); if (•, g r , •) in s.records abort("Generator collision"); if r = 0: abort("Neutral element returned"); s.records.append(r, g r , h); return h; def corrupt(s, h, Y ):

if there is (r, g, h) in s.records: return (s.sSDH).corrupt(g, Y 1/r ); def DDH(s,h, Y, X, K):

if there is (r, g, h) in s.records: return (s.sSDH).DDH(g, Y, X, K 1/r ); # Chaining the experiment objects for ristretto and decaf sSdh = sSDH(sCDH); coffeeExp = mapTwice_sSDH(Map2Pt,sSdh);

Figure 9: Experiment class definition mapTwice_sSDH where H 1 hashes to F q × F q .

CPace co :=CPace[Gen 1MAP , ScMul co , ScMulVf co , ScSam p ] Gen 1MAP (pw, P i , P j ) : ScMul co (g, y) : ScMulVf co (g, y) : ScSam p () :

Map2Pt(H 1 (pw||oc(P i , P j ))) else: return g c•y return y is indistinguishable from the uniform distribution in G. The probability that sampleH1 calculates a r = 0 (r 1 accidentally sampled such that r 0 = -r 1 ) is bounded by l H 1 /p.

Considering curves with small co-factor

In this subsection, we now additionally consider that the elliptic curve group G can be of order c • p with c = 1, but where Diffie-Hellman-type assumptions can only assumed to be computationally infeasible in the subgroup of order p, denoted G p . Consequently, CPace co on curves with co-factor c = 1 requires all secret exponents to be multiples of c. Hence, CPace co depicted in Fig. 10 Game E : Do not use the password for calculating the SENDINIT result.

In this game we restructure the code such that we do not use the password in SENDINIT queries for calculating the public result message. This game is obviously indistinguishable from the previous one as the obtained distribution for the private exponents y is not modified.

In this game we also defined a private method _DDH that implements a restricted decisional Diffie-Hellman oracle that works for base points derived by the H 1 function and points Y produced by SENDINIT queries. As such the code of the SENDINIT and H 1 queries in conjunction with the _DDH function can be considered to produce challenges for the sCDH and sSDH problems. Game F : Limit adversaries to one password guess.

We now start giving the adversary and the game-class code different implementations of the H 2 queries.

Firstly note that we previously have ruled out that the adversary has queried H 2 for a string that contains a public key Y that is later returned as the result of a SENDINIT call.

For H 2 queries after a SENDINIT call, we can easily parse the adversary's H 2 hash queries for the transcripts containing public points Y a and Y b and the adversarial group element guesses K. If there is any protocol instance (P i , l i ) which shares it's generated public key with the adversarial query, we can check whether the query for K corresponds to a password-derived generator for some previously queried password pw: For this, we iterate through the H 1 table and use the trapdoor Game G : Abort on successful attacks of passive adversaries.

Again we can easily parse the adversary's H 2 hash queries for the transcripts and group elements K. If two identical transcripts exist in session records for (P i , l i ) and (P j , l j ) and as transcripts are unique as a result of the previous games, we easily identify the case of a passive attack. In this case that the adversarial query contains the same value K as calculated by a honest party, we abort and declare the adversary to win. In any other case we respond to the adversary with the results of a private random oracle. Just as in the corresponding case (Game 7 in the sequence used for the UC security analysis), this bad event can be bound to the adversarial advantage of solving the sCDH problem. We can carry out the reduction by using the self-reducibility of the sCDH problem. I.e. we embed a sCDH challenge (g, X, Y ) in the form X ξ and Y η for some known random values ξ, η into the executions of the parties P i and P j and use the constrained DDH oracle for identifying the correct solution K. In fact we have a loss of a factor of two as we need to flip coins which of the challenge points X or Y to embed in the output of a party P i as we do not assume clearly assigned user and server roles here. 7 As a result this game change is only distinguishable in case of the bad event that a solution to the sCDH problem is provided. Final bound for the adversary advantage. Throughout the game sequence the outputs of the REVEAL and TEST queries have not been modified. However the implementation of the H 2 query was modified such that A obtains independent values from a private random oracle except for the case of a single password guess iff the tested party instance was actively attacked. Note also that the H 2 query that was made accessible to the adversary never accesses the instance passwords and only accesses the secret exponents through the restricted internal _DDH function that was introduced in game E. When executing a TEST query in Game G considering passive protocol executions, the outputs given to the A are always independent fresh random values taken from the private H 2 oracle except for bad events that can be reduced to the sCDH or sSDH problems.

In the case of actively attacked instances, the only situation where the H 2 oracle that A accesses and the private _H 2 oracle produce the same result is if a password guess was detected in Game F. Moreover in Game F this event is limited to one single guess only.

As a result the best available adversarial strategy available in Game G is a random single password guess from the dictionary D pw for any of the n aa active attacks which occurs with probability n aa /|D pw |. Summarizing the distinguisher advantages, we obtain the bounds from Theorem B.1.

Other variants of CPace. This concludes our game-based security analysis of CPace 1MAP_NoSID using a hash-then-map-once approach for calculating the generators. We do not identify any obstacle for carrying out a corresponding analysis also for the other variants discussed in the simulationbased security analysis within this paper. For instance when considering CPace 2MAP , only the way the trapdoor for H 1 is implemented in game C needs to be adapted and otherwise the proof can be carried out without any further change.

Quantum Annoyance. A protocol features quantum annoyance if an adversary with access to a quantum computer still needs to solve at least one instances of a computational problem per attack [START_REF] Eaton | The "quantum annoying" property of passwordauthenticated key exchange protocols[END_REF]. CPace is prone to offline dictionary attacks when facing such an adversary. To see this, consider an attacker A sending a point Y = g y pw to an honest party, with g pw ← Gen(pw). A computes K pw ← ScMulVf base (Y , y) for Y received from the honest party and derives key ISK pw from it. Without engaging in further communication with the honest party, A can now compute the final key with respect to another password pw by computing g pw ← Gen(pw ), solving a DLP to obtain r such that g r pw = g pw , and compute K pw ← K r pw and derive ISK pw from it as usual. The adversary P P On input (Init, pw)

On input (Init, pw ) pw pw

Output m Figure 24: Toy example of a modular password-authenticated secure channel protocol with F pwKE as building block, exposing the shortcoming of F pwKE .

protocol 9 Π sc depicted in Fig. 24: users call F pwKE to turn their passwords into a cryptographic key and subsequently encrypt a message m under this key using a symmetric cipher. Intuitively, we would expect protocol Π sc to implement a secure password-authenticated channel. Unfortunately, with the shortcoming in existing PAKE functionalities, there is no way to prove this protocol secure: upon corrupting P , the adversary gets to determine the value K sent to an honest P. A simulator would now have to produce a ciphertext c that, for any K chosen by the adversary, decrypts to m -but without knowing m. Clearly, this traps the simulator.

Lastly, we note that our argument above is backed up by Canetti et al. [START_REF] Canetti | Universally composable password-based key exchange[END_REF], who could only circumvent the above simulation trap by integrating the shortcoming also into their password-based channel functionality.

To summarize, it seems necessary to strengthen UC PAKE functionalities in the way we propose in this paper, in order to make them useful as building blocks for higher level applications.

D Initiator-responder and parallel CPace protocol variants

The current CPace specification in [START_REF] Haase | CPace, a balanced composable PAKE[END_REF] describes a protocol with clear initiator and responder roles, where the responder sends his reply only upon reception of the initiator message. Astonishingly, we observed that for an analysis of such a protocol in the UC framework, an ideal PAKE functionality technically needs a richer structure than the one for a corresponding parallel protocol that does not enforce ordering. The reason is that the responder party needs to be activated twice, once for sending the network message and once for issuing the session key.

In order to avoid this purely technical complexity in our presentation we decided to analyze security of CPace here in the more complex setting where no ordering is enforced. For the purpose of the analysis, we thus had to modify the protocol from [START_REF] Haase | CPace, a balanced composable PAKE[END_REF] such that ordered concatenation (written oc(A,B)) is used for generating hash function inputs instead of just putting the initiator's message first.

We would like to stress that in case that the protocol control flow guarantees a defined sequence, as is e.g. the case for protocols such as TLS, there is no need security-wise to enforce use of ordered concatenation.

E Note on sampling of scalars

The CPace protocol needs an algorithm for sampling scalars y for use as private Diffie-Hellman exponents. Ideally for a (sub-)group of order p, these should be sampled from a uniform distribution from F p \ 0. Sometimes, in particular if p is very close to a power of two p = 2 l + p 0 with |p 0 | p, existing Diffie-Hellman libraries draw scalars from the set {1, . . . , (2 l -1)} instead or include other structure in the scalars. Examples include the X25519 Diffie-Hellman protocol [START_REF] Daniel | Curve25519: New Diffie-Hellman speed records[END_REF] on Curve25519 with it's so-called scalar-clamping procedure which has been re-used for the X448 protocol on Curve448. For the analysis of CPace this change can be considered by a specific scalar sampling function ScSam.

We also observed libraries (for X25519 and X448, but also libraries targeting short-Weierstrass curves) to fix some scalar bits to a defined 1 value in order to guarantee for a constant execution time in window-based scalar multiplication strategy. There are also good reasons for avoiding any additional calculation involving secret scalars y, such as might be required during rejection sampling, since any operation on y might put the secret at risk, e.g. due to side-channels. As CPace aims at being suitable for re-using existing well-tested libraries as-is, the implications for the protocol security due to non-uniform sampling of scalars needs to be analyzed. Unlike for conventional Diffie-Hellman protocols, for CPace not only the confidentiality of ephemeral session keys might be affected but also information on the passwords could be leaked.

In order to consider the case of p = 2 l + p 0 , we will introduce an additional game G 0 after the real-world setting and only change the scalar-sampling algorithm. In this game, we replace the possibly slightly non-uniform distribution of secret scalars y a from honest parties in the real world with a fully uniform distribution. For a group order c • (2 l + p 0 ) implementations in the real world honest parties might draw the scalars y a and y b from {1, . . . , (2 l -1)} instead of {1, . . . , (p -1)}.

Let Adv DUN B DUN (G, ScSam) be the probability of an adversarial algorithm B DUN of distinguishing a group element Y ∈ G, where y ← ScSam(), Y = g y was calculated by use of a function ScSam, from a uniformly drawn element X ← R G \ I G . Let l 1 denote the number of generated public keys Y a , Y b from honest parties and let l 2 the number of adaptive corruptions that reveal the secret exponents. Then the following bound for the possible distinguisher advantage applies:

As a result of our assessment the structure introduced by the "scalar clamping" defined for X25519 and X448 does not introduce a critical non-uniformity for CPace.

F Details on chaining challenge generator classes

Two different types of experiments can be distinguished. Firstly, the sCDH and the sCDH_sTCDH classes (Fig. 5 and Fig. 12) share the same API and specify two variants of the conventional CDH problem. Instances will be assigned a base point g in their constructor call, produce two elements from a prime-order group and answer DDH queries. Secret exponents will be revealed in case of corruption events. Also the objects inform the caller on which objects are accepted by their DDH oracle.

This API is used by the objects representing variants of the simultaneous Diffie-Hellman assumption. As security of all variants is ultimately based on the prime-order version of the sSDH problem all calls from S will ultimately be converted into a call to an instance of the sSDH class from Fig. 4. This is implemented by chaining the different classes.

As root of the chain first an instance of the prime-order sSDH class is generated which is parametrized by one of the two conventional CDH classes (sCDH or sCDH_sTCDH) by a constructor parameter. In its constructor the sSDH object will sample a generator g and create an instance of the sCDH or sCDH_sTCDH class, which will become a member of the sSDH root class. The base point is passed to this member object in its constructor call.

The challenge generator classes for the simultaneous problem variants will all produce base points for the simultaneous Diffie-Hellman problem through their API for producing H 1 samples. However the encoding of the base point varies. In the root class sSDH a uniformly sampled group element is returned directly. The derived classes could return the base point also in form of an encoding h that needs to be passed to the mapping construction for decoding.

We describe the chaining approach by using the example of single-coordinate protocol variants on curves with cofactor and twist security using a "map-once" primitive (our recommendation for twist secure Montgomery curves from Appendix G). The corresponding code is found in Fig. 12 below the class definition.

As all Montgomery curves having real-world relevance today come with twist security, the sSDH root object is instantiated with an sCDH_sTCDH object and we obtain an "twistSdhExp" instance of the sSDH class. As the curve has a cofactor, "twistSdhExp" will be passed to an instance "twistCcExp" of the class cofactorClearer and stored there as a member. "twistCcExp" makes sure that inputs for all queries, notably parameters 2,3,4 of the DDH function, will be mapped to the prime-order subgroup and transformed into calls to "twistSdhExp". The "twistCcExp" object itself is then passed to the constructor of the distribution class D G _sSDH which will be given a function reference to the implementation of the preimage calculator function for the map. This "twistDistExp" object will return H 1 samples that need to be decoded using the Map2Pt function in order to obtain group elements and require this encoding in its first operand in its DDH function. Finally an instance "twistXonlyExp" of the moduloNegationAdapter adapter class is created, having the "twistDistExp" object as a member in its body.

Calls to the DDH method of the "twistXonlyExp" object will receive the base point h in a form that needs to be passed to Map2Pt for decoding to a group element. The missing coordinate is reconstructed for the second, third and fourth operand of the DDH function and for both candidate points calls to the DDH method of the "twistDistExp" instance will be issued. The latter will convert the base point query h to a group element and forward the query to the cofactor clearer. The latter will make sure that queries for points will have their low-order component cleared and issue a call to the sSDH root object which itself will forward the query to the sCDH_sTCDH instance in its body which uses its secret exponents for giving the response.

G Recommendations: How to instantiate CPace

CPace was designed for suitability with different styles of Diffie-Hellman protocols on elliptic curves. Our perception is that it is possible to distinguish three main application scenarios with real-world relevance.

G.1 Short-Weierstrass

The first elliptic curves being standardized used a short-Weierstrass form. In practice only primeorder curves became of more widespread relevance. While some applications use point-compression, historically mostly a full coordinate representation is used for the network communication, (possibly for patent circumvention reasons that applied at the time). A typical example would be ECC on NIST-P256 and Brainpool curves [START_REF]National Institute of Standards and Technology (NIST)[END_REF][START_REF]Elliptic Curve Cryptography[END_REF][START_REF] Lochter | Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation[END_REF].

In this ecosystem, we recommend to instantiate CPace using the following features

• Encode points Y a and Y b using full coordinates and use conventional point verification.

• Still, we recommend to actually only use the x-coordinate of the Diffie-Hellman result K for the session key, as TLS does so and some libraries use an x-coordinate-only ladder internally.

• We recommend to use the nonuniform Encode2Curve algorithms from the Hash2Curve draft, i.e. the "map-once" primitive, specifically because otherwise single-coordinate scalar multiplication strategies would not be practical for CPace. The point addition required by the "map-twice-and-add" approach would require full group operations. As mapping algorithm we recommend simplified SWU [START_REF] Faz-Hernandez | Hashing to elliptic curves[END_REF] because according to our analysis this is the least complex and most efficient variant working for the established curve set, notably NIST-P256.

• In this ecosystems, implementers should carefully evaluate the process of scalar sampling chosen in their library, in particular for the NIST-P256 and Brainpool curves. We observed that some libraries might not sample scalars sufficiently uniformly. Here we recommend rejection sampling.

For this instantiation the assumption set is modeled by the challenge-generator class "single-CoorExp" in Fig. 14.

G.2 Montgomery curve ladders

In addition to the established Weierstrass ecosystem, recently constructions based on Montgomery and (twisted) Edwards curves emerged. We believe that these designs became especially attractive as their design already considered typical implementation pitfalls from the very beginning. The wide-spread use of the prominent representatives X25519 and X448 [START_REF] Langley | Elliptic Curves for Security[END_REF] resulted in standardization for internet protocols and by standardization bodies such as NIST.

The first implementations for CPace did focus on this type of Diffie-Hellman primitives. For the twist-secure Curve25519 and Ed449 we recommend the following configuration.

• Only use the u-coordinate on the Montgomery curve.

• Do not verify the curve equation explicitly, but check the neutral elements (all elements encoded with zeros), i.e. use the twist security. This way ScMulVf and ScMul become the same function and X25519(X,y) and X448(X, y) can directly be used for this purpose. Note that checking for the neutral elements (all zero encoding for X448 and X25519) is absolutely mandatory for CPace. Here the discussion from [START_REF] Langley | Elliptic Curves for Security[END_REF] which describes this check as optional does not (!) apply.

• For the map, we recommend to use non-uniform Elligator2 without co-factor clearing as this spares a field inversion ( or alternatively spares a montgomery ladder implementation working on projective-coordinate inputs instead of an affine input.).

As the group orders are very close to a power of two, the clamped scalar method can be considered suitable also for CPace instantiations 10 For the construction described in the this paragraph the assumption set is modeled by the challenge-generator class "twistXonlyExp" from Fig. 12.

G.3 Group abstraction

The speed advantage and the simplicity provided by the efficient and complete addition formulas available for Montgomery and (twisted) Edwards curves can only be obtained at the cost that protocols then need to deal with the co-factors. Not all protocols are, such as CPace, analyzed regarding this aspect. In order to allow for "the best of both worlds" projects are emerging which provide prime-order group abstractions on these curves, such as ristretto25519 and decaf448 [START_REF] Hamburg | Decaf: Eliminating cofactors through point compression[END_REF][START_REF] De Valence | The ristretto255 and decaf448 groups. Rfc, IRTF[END_REF]. As these abstractions work with the most efficient addition formulas currently known for elliptic curves, we do not see any incentive or advantage for single-coordinate instantiations for CPace. (In our opinion tightly constrained applications might rather opt for the Montgomery curve ladders anyway.) The designers of these abstraction frameworks also include mapping algorithms ("batteries included") and enforce invalid-curve checks by their API design. Here we recommend the following parameters for CPace:

• Use the compressed point encoding from the abstraction.

• Use the built-in map-twice-and-add construction that comes "batteries included" with the abstraction.

• In our opinion, the verification check for the identity element should receive some attention. Comparisons should be carried out using the unambiguous encoding provided by the abstraction and not using the intermediate representation format employed internally for the Hisil-Wong-Carter-Dawson addition formulas [START_REF] Hisil | Twisted Edwards curves revisited[END_REF].

As the group orders for ristretto25519 and decaf448 are very close to a power of two, using random-number generator outputs without rejection sampling can be considered suitable for deriving secret exponents for CPace.

For this instantiation the assumption set is modeled by the challenge-generator class "coffeeExp" in Fig. 9.