(strong) AuCPace, an augmented PAKE

1.1. Outcome of the CFRG PAKE selection process

AuCPace was one of the two finalists of the CFRG PAKE selection process for the augmented pake protocol use-case in which ultimately OPAQUE was selected as general recommendation of the CFRG working group. OPAQUE and strong AuCPace share the security model and security guarantees but come with specific advantages and drawbacks.¶

The key advantage of OPAQUE in comparison with AuCPace is that one communication round less than AuCPace is required, allowing for easier integration into TLS 1.3. Applications where the number of communication round-trips are considered critical are encouraged to consider OPAQUE.¶

The key advantages of AuCPace in comparison are much smaller password verifiers and the possibility to run AuCPace in conjunction with legacy-style password dictionaries that store the conventional triples of (username, salt, password hash). Moreover AuCPace provides a certain level of resilience with respect to adversaries with access to large-scale quantum computers ("quantum annoying property") which OPAQUE does not provide.¶

1.2. Key design objectives for AuCPace

The AuCPace protocol was specifically tailored for constrained server devices. As such, the computationally complex password hash operation is refered to the clients. AuCPace is also designed for enabling a smooth migration of legacy user credential databases.¶

AuCPace is designed to be compatible with any group of both prime- and non-prime order and comes with a security proof providing composability guarantees. AuCPace uses CPace as a building block which is described in a separate internet draft document.¶

AuCPace moreover designed to provide flexibility and a smooth migration process for applications that today don't use a PAKE protocol for authentication but work with conventional password verifier databases instead.¶

3.1. Setup

Let C be a group in which there exists a subgroup of prime order p where the computational simultaneous Diffie-Hellman (SDH) problem is hard. C has order p*c where p is a large prime; c will be called the cofactor. Let I be the unit element in C, e.g., the point at infinity in if C is an elliptic curve group. We denote the operations in the group using addition and multiplication operators, e.g. P + (P + P) = P + 2 * P = 3 * P. We refer to a sequence of n additions of an element in P as scalar multiplication by n. With B we denote a generator of the prime-order subgroup in C that we call the base point.¶

With F we denote a field that may be associated with C, e.g. the prime base field used for representing the coordinates of points on an elliptic curve.¶

We assume that for any element P in C there is a representation modulo negation, encode_group_element_mod_neg(P) as a byte string such that for any Q in C with Q != P and Q != -P, encode_group_element_mod_neg(P) != encode_group_element_mod_neg(Q). It is recommended that encodings of the elements P and -P share the same result string. Common choices would be a fixed (per-group) length encoding of the x-coordinate of points on an elliptic curve C or its twist C' in Weierstrass form, e.g. according to [IEEE1363] in case of short Weierstrass form curves. For curves in Montgomery form correspondingly the u-coordinate would be encoded, as specified, e.g., by the encodeUCoordinate function from [RFC7748].¶

With J we denote the group modulo negation associated to C. Note that in J the scalar multiplication operation is well defined since scalar_multiply(P,s) == -scalar_multiply(-P,s) while arbitrary additions of group elements are no longer available.¶

With J' be denote a second group modulo negation that might share the byte-string encoding function encode_group_element_mod_neg with J such for a given byte string either an element in J or J' is encoded. If the x-coordinate of an elliptic curve point group is used for the encoding, J' would commonly be corresponding to the group of points on the elliptic curve's quadratic twist. Correspondingly, with p' we denote the largest prime factor of the order of J' and its cofactor with c'.¶

Let scalar_cofactor_clearing(s) be a cofactor clearing function taking an integer input argument and returning an integer as result. For any s, scalar_cofactor_clearing(s) is REQUIRED to be of the form c * s1. I.e. it MUST return a multiple of the cofactor. An example of such a function may be the cofactor clearing and clamping functions decodeScalar25519 and decodeScalar448 as used in the X25519 and X448 protocols definitions of [RFC7748]. In case of prime-order groups with c == 1, it is RECOMMENDED to use the identity function with scalar_cofactor_clearing(s) = s.¶

Let scalar_mult_cc(P,s) be a joint "scalar multiplication and cofactor clearing" function of an integer s and an string-encoded value P, where P could represent an element either on J or J'. If P is an element in J or J', the scalar_mult_cc function returns a string encoding of an element in J or J' respectively, such that the result of scalar_mult_cc(P,s) encodes (scalar_cofactor_clearing(s) * P).¶

Let si = invert_scalar_mult_cc(P,s) be a function such that for any point Z in the prime-order subgroup of J, invert_scalar_mult_cc(scalar_mult_cc(Q,s),s) == Q. A typical implemention will involve calculating the inverse in the prime field mod p on the scalar generated by scalar_cofactor_clearing(s).¶

Let scalar_mult_ccv(P,s) be a "scalar multiplication cofactor clearing and verify" function of an integer s and an encoding of a group element P. Unlike scalar_mult_cc, scalar_mult_ccv additionally carries out a verification that checks that the computational simultaneous Diffie-Hellman problem (SDH) is hard in the subgroup (in J or J') generated by the encoded element SP = scalar_mult_cc(P,s). In case that the verification fails (SP might be of low order or on the wrong curve), scalar_mult_ccv is REQUIRED to return the encoding of the identity element I. Otherwise scalar_mult_ccv(P,S) is REQUIRED to return the result of scalar_mult_cc(P,s). A common choice for scalar_mult_ccv for Montgomery curves with twist security would be the X25519 and X448 Diffie-Hellman functions as specified in [RFC7748]. For curves in short Weierstrass form, scalar_mult_ccv could be implemented by the combination of a point verification of the input point with a scalar multiplication. Here scalar_mult_ccv SHALL return the encoding of the neutral element I if the input point P was not on the curve C.¶

Let P=map_to_group_mod_neg(r) be a mapping operation that maps a string r to an encoding of an element P in J. Common choices would be the combination of map_to_base and map_to_curve methods as defined in the hash2curve draft [HASH2CURVE]. Note that we don't require and RECOMMEND cofactor clearing here since this complexity is already included in the definition of the scalar multiplication operation calar_mult_cc above. Additionally requiring cofactor clearing also in map_to_group_mod_neg() would result in efficiency loss.¶

|| denotes concatenation of strings. We also let len(S) denote the length of a string in bytes. Finally, let nil represent an empty string, i.e., len(nil) = 0.¶

[f,g,h] denotes alternatives where exactly one of the comma-separated options is to be chosen.¶

Let H(m) be a hash function from arbitrary strings m to bit strings of a fixed length. Common choices for H are SHA256 or SHA512 [RFC6234]. H is assumed to segment messages m into blocks m_i of byte length H_block. E.g. the blocks used in SHA512 have a size of 128 bytes.¶

Let strip_sign_information(P) be function that takes a string encoding of an element P in J and strips any information regarding the sign of P, such that strip_sign_information(P) = strip_sign_information(-P). For short Weierstrass (Montgomery) curves this function will return a string encoding the x-coordinate. The purpose of defining this function is for allowing for x-coordinate only scalar multiplication algorithms. The sign is to be stripped before generating the intermediate session key ISK.¶

With ISK we denote the intermediate session key output string provided by CPace that is generated by a hash operation on the Diffie-Hellman result.¶

MAC(msg,key) is a message authentication code. Common examples are HMAC_SHA512, a block cipher based MAC or a hash-function based tag.¶

AEAD(msg,key) is used for denoting an authenticated encryption scheme. A common example would be AES128GCM or Salsa20Poly1305.¶

KDF(Q) is a key-derivation function that takes a string and derives key of length L. Common choices for KDF are HMAC_SHA512.¶

With DSI we denote domain-separation identifier strings that may be prepended to the inputs of Hash and KDF functions.¶

Let IHF(salt, username, pw, sigma) be an iterated hash function that takes a salt value, a user name and a password as input. IHF is designed to slow down brute-force attackers as controlled by a workload parameter set sigma. State of the art iterated hash functions are designed for requiring a large amount of memory for its operation and will be referred to as memory-hard hash functions (MHF). Scrypt [RFC7914] or Argon2 are common examples of a MHF primitive.¶

With PRS we denote a string that is a required input of the CPace subprotocol and generated by the AuCPace protocol.¶

Let A and B be two parties. A and B may also have digital representations of the parties' identities such as Media Access Control addresses or other names (hostnames, usernames, etc). We denote the parties' representation and the parties themselves both by using the identifiers A and B.¶

With CI we denote a string that is a required input of the CPace subprotocol. CI is generated together with PRS by the AuCPace augmentation layer. CI SHALL be formed by the concatenation of the identifiers A and B and an associated data string AD, CI = A || B || AD;¶

With uad we denote an optional string that is specifying user-associated data in a password file entry, such as authorization rights or permissions or account expiration dates. Specification of this string is outside of the scope of the AuCPace protocol.¶

Let sid be a session id byte string chosen for each protocol session before protocol execution; The length len(sid) SHOULD be larger or equal to 16 bytes.¶

5.1. Authentication Protocol Flow

AuCPace is a protocol run between two parties, A and B, for establishing a shared secret key with explicit mutual authentication. AuCPace is implemented by four messages as indicated by the numbers in the figure below. The roles of the two parties are different. Party B, the client, is provided a user name and a password as input. Party A, the server, has access to a user credentials database that stores password verifiers. Both parties share a channel identifier string CI characterizing the communication channel (e.g. information on IP addresses and port numbers of both sides).¶

The channel identifier, CI, SHOULD include an encoding of the identities of both parties A and B if these are available prior to starting the communication protocol.¶

Both sides also share a common subsession ID (ssid) string. ssid could be pre-established by a higher-level protocol invocing AuCPace. If no such ssid is available from a higher-level protocol, a suitable approach is including ssid in the first message from B to A as shown in the figure below.¶

                A                  B
                |       ssid       |
                |<1----------------| (sample ssid)

       ---------- AuCPace protocol -----------
 In: ssid       |                  | In: name, passw.
                |     name,U       |     ssid
                |<1----------------|
 DB lookup      |                  |
                |[UQ,salt],X,sigma |
 det. CI,PRS    |----------------2>| det. CI,PRS
       ---------------------------------------
In: CI, PRS,   || (CPace substep)  || In: CI, PRS,
    ssid       ||                  ||     ssid
               ||        Ya        ||
               ||----------------2>||
               ||        Yb        ||
  Output: ISK  ||<3----------------|| Output: ISK
       ---------------------------------------
     expl.auth. |        Tb        | expl.auth.
                |<3----------------|
                |        Ta        |
                |----------------4>|
     Output: SK |                  | Output: SK

5.2. AuCPace

Both parties start with agreed values on the ssid string. The server side has access to a user credentials database. The client side holds a user name, a clear-text password to be used for the authentication session. Both sides share an encoding CI specifying the communication channel, such as IP addresses and port numbers.¶

To begin, B calculates an element Z = map_username_password_to_J(username || password) in J.¶

B then picks r randomly and uniformly according to the requirements for group J scalars and calculates U = scalar_mult_cc(Z,r).¶

B then sends (name,U) to A.¶

A then queries its database for the user name and retrieves the information as specified in section Section 4.6 , i.e. the set (W,sigma,salt-derivation parameter [q,salt]). (Note that according to the specification of the database lookup, such a set is provided, even if there is no database entry for the given user name.)¶

A picks x randomly and uniformly according to the requirements for group J scalaras and calculates X = scalarmult_cc(B,x) and WX = scalarmult_ccv(W,x). A MUST abort if WX is the neutral element (this indicates an error in the database contents).¶

A strips the sign information from WX to obtain WXs. A picks ya randomly and uniformly. A then calculates G = map_to_group_mod_neg(DSI1 || WXs || ZPAD || ssid || CI) and Ya = scalar_mult_cc(G,ya). I.e. WXs takes over the role of CPace's PRS string.¶

The following operations will variate, depending on the type of salt-derivation entry in the database.¶

• If the salt derivation parameter is for strong AuCPace, A calculates UQ = scalarmult_cc(U,q) and sends (UQ,X,sigma,Ya) to B. B then calculates salt as salt = strip_sign_information(inverse_scalarmult_cc(UQ,r)).¶
• If the salt derivation parameter is for AuCPace, A sends (salt,X,sigma,Ya) to B.¶

B then calculates w = IHF(salt, username, pw, sigma) and XW = scalarmult_ccv(X,w). B MUST abort, if XW is the neutral element I.¶

B strips the sign information from XW to obtain XWs. B picks yb randomly and uniformly. B then calculates G = map_to_group_mod_neg(DSI1 || XWs || ZPAD || ssid || CI) and Yb = scalar_mult_cc(G,yb). B then calculates K = scalar_mult_ccv(Ya,yb). B MUST abort if K is the encoding of the neutral element I. Otherwise B sends Yb to A and proceeds as follows. B strips the sign information from K, Ya and Yb to obtain the strings Ks, Yas and Ybs by using the strip_sign_information() function. B calculates ISK = H(DSI2 || ssid || Ks || Yas || Ybs).¶

B calculates Tb = MAC(ISK,DSI4) and Ta_v = MAC(ISK,DSI3) and sends (Yb,Tb) to A.¶

Upon reception of Yb, A calculates K = scalar_mult_ccv(Yb,ya). A MUST abort if K is the neutral element I. If K is different from I, A strips the sign information from K, Ya and Yb and calculates ISK = H(DSI2 || ssid || Ks || Yas || Ybs).¶

A calculates Tb_v = MAC(ISK,DSI4) and Ta = MAC(ISK,DSI3). If the received authentication tag Tb did not match the verification value Tb_v A MUST abort. Otherwise A sends Ta to B and returns the session key SK = KDF(DSI5 || ISK || ssid).¶

When B receives T_a it compares this to the verification value Ta_v. B MUST abort if Ta != Ta_v. Otherwise B returns the session key SK = KDF(DSI5 || ISK || ssid).¶

Upon completion of this protocol, the session key SK returned by A and B will be identical by both parties if and only if the supplied input parameters ssid and CI match on both sides and the password verifier in the server database for the user was calculated from the clear-text password used by B.¶

6.1. Transaction Protocol Flow

The protocol flow corresponds to the session key generation above with the difference that the authenticator messages Ta and Tb are replaced by two transaction messages TMa and TMb.¶

Before starting the protocol, the client has setup a transaction message MT.¶

As above, the channel identifier, CI, SHOULD include an encoding of the identities of both parties A and B if these are available prior to starting the communication protocol.¶

Both sides also share a common subsession ID (ssid) string. ssid could be pre-established by a higher-level protocol invocing AuCPace. If no such ssid is available from a higher-level protocol, a suitable approach is including ssid in the first message from B to A as shown in the figure below.¶

                A                  B
                |       ssid       |
                |<1----------------| (sample ssid)

       ---------- AuCPace protocol -----------
 In: ssid       |                  | In: name, passw.
                |     name,U       |     ssid, MT
                |<1----------------|
 DB lookup      |                  |
                |[UQ,salt],X,sigma |
 det. CI,PRS    |----------------2>| det. CI,PRS
       ---------------------------------------
In: CI, PRS,   || (CPace substep)  || In: CI, PRS,
    ssid       ||                  ||     ssid
               ||        Ya        ||
               ||----------------2>||
               ||        Yb        ||
  Output: ISK  ||<3----------------|| Output: ISK
       ---------------------------------------
     expl.auth. |       TMb        | expl.auth.
                |<3----------------|
    process TMb |       TMa        |
                |----------------4>|
                |                  | process TMa

6.2. AuCPace authenticated transactions

The protocol flow is identical to the case of session key generation except for the fact that the authenticators Ta and Tb are replaced by TMa and TMb. TMa is generated by TMb = AEAD(MT,ISK), i.e. the payload MT is encrypted and authenticated by use of ISK. If verification of the authentication tag of TMb succeeds on the server the transaction message is decrypted and executed. E.g. upon a password change transaction message, the new password verifier would be written to the database of the server. The result of the transaction execution is encoded in a response message MR and TMa is calculated as TMa = AEAD(MR,ISK). The client authenticates TMa and returns the decrypted response message MR upon success.¶