| Internet-Draft | Hybrid PQ-PAKE | April 2026 |
| Vos, et al. | Expires 29 October 2026 | [Page] |
This document describes the CPaceOQUAKE+ protocol, a hybrid asymmetric password-authenticated key exchange (aPAKE) that supports mutual authentication in a client-server setting secure against quantum-capable attackers. CPaceOQUAKE+ is composed of two stages — CPace and OQUAKE+ — that run sequentially, with the output of CPace feeding as context into OQUAKE+. OQUAKE+ is an augmented variant of OQUAKE that adds password confirmation. This document also describes standalone OQUAKE+, a post-quantum aPAKE, and CPaceOQUAKE, the hybrid symmetric PAKE composed of the CPace and OQUAKE stages. This document recommends configurations for CPaceOQUAKE+.¶
This note is to be removed before publishing as an RFC.¶
The latest revision of this draft can be found at https://example.com/LATEST. Status information for this document may be found at https://datatracker.ietf.org/doc/draft-vos-cfrg-pqpake/.¶
Discussion of this document takes place on the CFRG Crypto Forum Research Group mailing list (mailto:WG@example.com), which is archived at https://example.com/WG.¶
Source for this draft and an issue tracker can be found at https://github.com/USER/REPO.¶
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶
This Internet-Draft will expire on 29 October 2026.¶
Copyright (c) 2026 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.¶
Asymmetric (or Augmented) Password Authenticated Key Exchange (aPAKE) protocols are designed to provide password authentication and mutually authenticated key exchange in a client-server setting without relying on a public key infrastructure (PKI) and without disclosing passwords to servers or other entities other than the client machine. The only stage where PKI is required is during a client's registration.¶
In the asymmetric PAKE setting, the client first registers a password verifier with the server. A verifier is a value that is derived from the password and which the server will later use to verify the client knowledge of the password. After registration, the client uses its password and the server uses the corresponding verifier to establish an authenticated shared secret such that the server learns nothing of the client's password.¶
OPAQUE-3DH [OPAQUE] and SPAKE2+ [SPAKE2PLUS] are two examples of specified aPAKE protocols. These protocols provide security in classical threat models. However, in the presence of a quantum-capable attacker, both OPAQUE and SPAKE2+ fail to provide the desired level of security. Both protocols are vulnerable to a Harvest Now, Decrypt Later attack executed by a quantum-capable attacker, in which the attacker learns the shared secret and uses it to compromise application traffic. Upgrading both protocols to provide post-quantum security is non-trivial, especially as there are no known efficient constructions for certain building blocks used in these protocols (such as the OPRF used in OPAQUE-3DH). As the threat of quantum-capable attackers looms, the viability of existing aPAKE protocols in practice diminishes in time.¶
This document describes the CPaceOQUAKE+ protocol, an aPAKE that supports mutual authentication in a client-server setting secure against quantum-capable attackers. CPaceOQUAKE+ is composed of two stages that run sequentially: CPace and OQUAKE+. The design securely composes multiple existing primitives [VJWYMS25].¶
This document fully specifies CPaceOQUAKE+ and all dependencies necessary to implement it. Section 8 provides recommended configurations.¶
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶
The following functions and operators are used throughout the document.¶
The function random(n) generates a cryptographically secure pseudorandom
byte string of length n bytes.¶
The associative binary operator || denotes concatenation of two byte strings.¶
The binary function XOR(a, b) denotes an element-wise XOR operation between
two byte strings a and b of the same length.¶
The functions bytes_to_int and int_to_bytes convert
byte strings to and from non-negative integers. bytes_to_int and int_to_bytes
are implemented as OS2IP and I2OSP as described in [RFC8017], respectively.¶
The function lv_encode encodes a byte string with a two-byte, big-endian
length prefix. For example, lv_enode((0x00, 0x01, 0x02)) = (0x00, 0x03, 0x00, 0x01, 0x02).
The function lv_decode parses a byte string that is expected to be encoded
with a two-byte length preceding the remaining bytes, e.g.,
lv_decode((0x00, 0x03, 0x00, 0x01, 0x02)) = (0x00, 0x01, 0x02). Note that lv_decode
can fail when the length of the actual bytes does not match that encoded in the
prefix. For example, lv_decode((0xFF, 0xFF, 0x00)) will fail.¶
The notation bytes[l..h] refers to the slice of byte array bytes starting
at index l and ending at index h-1. For example, given bytes = (0x00, 0x01, 0x02), then bytes[0..1] = 0x00 and bytes[0..3] = (0x00, 0x01, 0x02). Similarly, the notation bytes[l..] refers to the slice of the byte
array bytes starting at l until the end of bytes, i.e.., bytes[l..] = bytes[l..len(bytes)].¶
All algorithms and procedures described in this document are laid out in a Python-like pseudocode. Each function takes a set of inputs and parameters and produces a set of output values. Parameters become constant values once the protocol variant and the configuration are fixed.¶
This document aims to specify two protocols: a symmetric and an asymmetric hybrid PAKE. In the symmetric PAKE setting, the client and server share a password and use it to establish an authenticated shared secret. In the asymmetric PAKE setting, the client first registers a password verifier with the server. A verifier is a value that is derived from the password and which the client will later use to demonstrate knowledge of the password. After registration, the client uses its password and the server uses the corresponding verifier to establish an authenticated shared secret such that the server learns nothing of the client's password.¶
The protocols specified in this document are built from two stages:¶
CPace [CPACE]: A classical elliptic curve-based symmetric PAKE.¶
OQUAKE: A new post-quantum symmetric PAKE built from a BUA-sKEM; see Section 6.2.¶
An abstract overview of CPaceOQUAKE+ is shown in the figure below.¶
Additionally, the document specifies OQUAKE+, an augmented variant of OQUAKE that adds password confirmation to upgrade the symmetric PAKE to an asymmetric PAKE; see Section 7.2.¶
These building blocks are composed into the following named protocols:¶
CPaceOQUAKE: A hybrid symmetric PAKE combining CPace and OQUAKE.¶
OQUAKE+: A post-quantum aPAKE; see Section 7.2.¶
CPaceOQUAKE+: A hybrid aPAKE combining CPace and OQUAKE+.¶
An abstract overview of CPaceOQUAKE+ is shown in the figure below.¶
We note that this standard only specifies the compositions listed above. It is not necessarily true that one can securely compose all PAKEs this way.¶
The rest of this document specifies CPaceOQUAKE+ and its dependencies. Section 6 specifies CPace and OQUAKE as individual stages and their composition into CPaceOQUAKE. Section 7 specifies OQUAKE+ and its composition with CPace into CPaceOQUAKE+. Each of these pieces build upon the cryptographic dependencies specified in Section 4.¶
The protocols in this document have four primary dependencies:¶
Key Encapsulation Mechanism (KEM); Section 4.1¶
Splittable Binary Key Encapsulation Mechanism with specific uniformity properties (binary UPK-ANO-KEM, or BUA-sKEM); Section 4.2¶
Key Derivation Function (KDF); Section 4.3¶
Key Stretching Function (KSF); Section 4.4¶
Section 8 specifies different combinations of each of these dependencies that are suitable for implementation.¶
A Key Encapsulation Mechanism (KEM) is an algorithm that is used for exchanging a secret from one party to another. We require an IND-CCA-secure KEM with key derivation from a seed. It consists of the following syntax.¶
DeriveKeyPair(seed): Deterministic algorithm to derive a key pair
(sk, pk) from the byte string seed, where seed MUST have Nseed bytes.¶
Encaps(pk): Randomized algorithm to generate an ephemeral,
fixed-length symmetric key (the KEM shared secret) and
a fixed-length encapsulation of that key that can be decapsulated
by the holder of the secret key corresponding to pk. This function
can raise an EncapsError on encapsulation failure.¶
Decaps(ct, sk): Deterministic algorithm using the secret key sk
to recover the ephemeral symmetric key (the KEM shared secret) from
its encapsulated representation ct. This function can raise a
DecapsError on decapsulation failure.¶
Nseed: The length in bytes of the seed used to derive a key pair.¶
Nct: The length in bytes of an encapsulated key produced by this KEM.¶
Npk: The length in bytes of a public key for this KEM.¶
A binary UPK-ANO-KEM supports the same functions as defined above for a KEM, and it must also be IND-CCA secure, but it must also achieve two additional security properties. Namely, in addition to IND-CCA security, a binary UPK-ANO-KEM requires that:¶
Public keys are indistinguishable from random strings of bytes (of the same length), i.e. uniform public keys (UPK); and¶
Ciphertexts are anonymous in the presence of chosen ciphertext attack (ANO-CCA), i.e. anonymous ciphertexts (ANO).¶
These additional properties are crucial for the security of OQUAKE. In other words, one MUST NOT use a KEM that has no uniform public keys and/or no anonymous ciphertexts in place of a UPK-ANO-KEM.¶
In this specification, we also require a third property: the KEM must be splittable. A splittable KEM (sKEM) implements the Split(pk) -> (t, ⍴) function and its inverse, which takes a public key and splits it into a part ⍴ that is indepdendent of the KEM's secret key and can therefore be made public, and a part t that does depend on the secret key. This property allows parties to perform variable-time operations on ⍴ without revealing information about the secret key. We use N⍴ to denote the byte-length of ⍴ and Nt to denote the byte-length of t. We use Combine(t, ⍴) -> pk to refer to the inverse operation of Split.¶
In the remainder of this specification, we abbreviate 'splittable binary UPK-ANO-KEM' as BUA-sKEM. This specification uses a variant of ML-KEM1024 [FIPS203], which we therefore denote by ML-BUA-sKEM1024. It is specified in Section 5. This is instantiated with "KemeleonNR - ML-KEM1024" [KEMELEON]. Note that, while Kemeleon provides uniform encoding for KEM ciphertexts and public keys, we only require uniform enoding for public keys. Future specifications can replace ML-BUA-sKEM1024 with another splittable binary UPK-ANO-KEM that is more efficient if one becomes available.¶
A Key Derivation Function (KDF) is a function that takes some source of initial keying material and uses it to derive one or more cryptographically strong keys. This specification uses a KDF with the following API and parameters:¶
Extract(salt, ikm): Extract a pseudorandom key of fixed length Nx bytes from
input keying material ikm and an optional byte string salt.¶
Expand(prk, info, L): Expand a pseudorandom key prk using the optional string info
into L bytes of output keying material.¶
Nx: The output size of the Extract() function in bytes.¶
This specification makes use of a Key Stretching Function (KSF), which is a slow and expensive cryptographic hash function with the following API:¶
Stretch(msg, salt, L): Apply a key stretching function to stretch the input msg
and salt salt, hardening it against offline dictionary attacks. This function also
needs to satisfy collision resistance. The output is a string of L bytes.¶
ML-KEM [FIPS203] is already specified in a way that allows one to separate out the part of the public key that does not depend on the secret key; this feature is also used in Kemeleon [KEMELEON]. The Split function is defined as follows for ML-KEM [TEMPO]. The part of the public key that does not depend on the secret key represents the final 32 bytes. For this reason, Nt = ML-KEM.Npk - 32 and N⍴ = 32.¶
ML-KEM.Split Input: - pk, an ML-KEM public key, a byte string of ML-KEM.Npk bytes Output: - t, part of the public key that depends on the secret key - ⍴, part of the public key that does NOT depend on the secret key def Split(pk): t = pk[0 : ML-KEM.Npk - 32] ⍴ = pk[ML-KEM.Npk - 32 : ML-KEM.Npk] return t, ⍴¶
For ML-KEM, the inverse of the split operation is concatenation.¶
ML-KEM.Combine Input: - t, part of the public key that depends on the secret key - ⍴, part of the public key that does NOT depend on the secret key Output: - pk, an ML-KEM public key, a byte string of ML-KEM.Npk bytes def Combine(t, ⍴): return t || ⍴¶
The design of ML-BUA-sKEM is such that it does not change the internals of ML-KEM; it only uses the Split function. To ensure that the public key generated by ML-BUA-sKEM.DeriveKeyPair is binary and uniform, it uses Kemeleon [KEMELEON] to (re-)encode ML-KEM's public keys. In the PAKEs described in this specification, it is crucial that this happens in constant time. For this reason, ML-BUA-sKEM uses the non-rejection sampling variants of Kemeleon, as denoted by VectorEncodeNR and VectorDecodeNR. ML-BUA-sKEM is defined as follows.¶
ML-BUA-sKEM.DeriveKeyPair Input: - seed, a random byte string of ML-BUA-sKEM.Nseed bytes Output: - sk, a secret decapsulation key, a byte string - upk, a uniform public key for encapsulation, a byte string Parameter: - Kemeleon.sec_param, a security parameter that tunes the bias of the produced upk def DeriveKeyPair(seed): (sk, pk) = ML-KEM.DeriveKeyPair(seed) (t, ⍴) = ML-KEM.Split(pk) ut = VectorEncodeNR(t) upk = ut || ⍴ return sk, upk¶
The uniform public keys produced by ML-BUA-sKEM are longer than those produced by ML-KEM. The final 32 bytes of the public key still represent the part that does not depend on the secret key.¶
ML-BUA-sKEM.Split Input: - upk, an ML-BUA-sKEM public key, a byte string of ML-BUA-sKEM.Npk bytes Output: - ut, part of the uniform public key that depends on the secret key - ⍴, part of the uniform public key that does NOT depend on the secret key def Split(upk): ut = upk[0 : ML-BUA-sKEM.Nt] ⍴ = upk[ML-BUA-sKEM.Nt : ML-BUA-sKEM.Npk] return ut, ⍴¶
For ML-BUA-sKEM, the inverse of the split operation is concatenation.¶
ML-BUA-sKEM.Combine Input: - ut, part of the uniform public key that depends on the secret key - ⍴, part of the uniform public key that does NOT depend on the secret key Output: - upk, an ML-BUA-sKEM public key, a byte string of ML-BUA-sKEM.Npk bytes def Combine(ut, ⍴): return ut || ⍴¶
ML-BUA-sKEM encapsulation undoes the uniform encoding performed during key derivation before calling ML-KEM.Encaps on the non-uniform public key.¶
ML-BUA-sKEM.Encaps Input: - upk, an ML-BUA-sKEM public key Output: - k, a symmetric shared secret, a byte string - ct, an anonymous ciphertext encapsulating k, a byte string Parameter: - Kemeleon.sec_param, a security parameter that tunes the bias of the consumed upk def Encaps(upk): (ut, ⍴) = ML-BUA-sKEM.Split(upk) t = VectorDecodeNR(ut) pk = ML-KEM.Combine(t, ⍴) return ML-KEM.Encaps(pk)¶
The decapsulation procedure for ML-BUA-sKEM is exactly the same as for ML-KEM.¶
ML-BUA-sKEM.Decaps Input: - ct, an anonymous ciphertext encapsulating k, a byte string - sk, a secret decapsulation key, a byte string Output: - k, a symmetric shared secret, a byte string def Decaps(ct, sk): return ML-KEM.Decaps(ct, sk)¶
The hybrid, symmetric PAKE protocol, denoted CPaceOQUAKE consists of CPace [CPACE] combined with OQUAKE [ABJ25]. OQUAKE is a PAKE built from a BUA-sKEM and KDF, using a 2-rounds of Feistel network to password-encrypt the BUA-sKEM public key. The OQUAKE protocol is based on the "NoIC" protocol analyzed in [ABJ25].¶
The CPaceOQUAKE protocol is based on the `Sequential PAKE Combiner' protocol proposed by [HR24]. A very close variant of this protocol was also analyzed in [LL24].¶
At a high level, CPaceOQUAKE is a four-message protocol that runs between client and server wherein, upon completion, both parties share the same session key if they agree on the password-related string (PRS). Otherwise, they obtain random session keys. This is summarized in the diagram below.¶
CPaceOQUAKE composes CPace and OQUAKE by first running CPace to completion between client and server, and then running OQUAKE with the CPace session key provided as context. We explain the composition in more detail in Section 6.3.¶
As describes in Section 6.1 and Section 6.2, both CPace and OQUAKE take as input optional client and server identifiers, denoted U and S, respectively. See Section 10.2 for more discussion about these identities and how they are chosen in practice.¶
CPace is a classical elliptic curve-based PAKE [CPACE]. This section wraps the CPace specification in a consistent interface. We use an interactive version of CPace that takes two rounds, in which there is a designated initiator and responder. In other words, the responder only starts executing the protocol after it received the first message from the initiator.¶
The flow of the protocol consists of two messages sent between initiator and responder, produced by the functions Init, Respond, and Finish, described below. Both parties take as input a password-related string PRS, an optional unique shared session identifier sid, and an optional client identifier U and server identifier S (e.g., a device identifier, an IP address, or URL pertaining to the client and server). Upon completion, both parties obtain matching session keys if their PRS, sid, key length (specified by N), and client and server identifiers match. Otherwise, they obtain random keys. In exceptional cases, the protocol aborts.¶
The initiator starts the protocol using its password-related string PRS. Additionally, it may bind the session to an existing shared session identifier sid. CPace also allows to bind the session to an existing channel identifier. To remain consistent with the other PAKEs in this specification, the channel identifier is the concatenation of optional client and server identifiers.¶
CPace.Init Input: - PRS, password-related string, a byte string - sid, session identifier, a byte string - U and S, client and server identifiers Output: - ya, discrete logarithm intended to be stored in secret until the protocol finishes - Ya, public point, intended to be sent to the responder Parameters: - G, a group environment as specified in CPace def Init(PRS, sid, U, S): g = G.calculate_generator(H, PRS, U || S, sid) ya = G.sample_scalar() Ya = G.scalar_mult(ya, g) return ya, Ya¶
The responder performs the same actions as the initiator. Since it already received the initiator's message, it can immediately finish its execution of the protocol. It outputs the shared secret and a message Yb intended to be sent to the initiator.¶
CPace.Respond Input: - PRS, password-related string, a byte string - Ya, public point, received from the initiator - sid, session identifier, a byte string - U and S, client and server identifiers Output: - ISK, the established shared secret - Yb, public point, intended to be sent to the initiator Parameters: - G, a group environment as specified in CPace - H, a hash function as specified in CPace Exceptions: - CPaceError, raised when an invalid value was encountered in CPace def Respond(PRS, Ya, sid, U, S): g = G.calculate_generator(H, PRS, U || S, sid) yb = G.sample_scalar() Yb = G.scalar_mult(yb, g) K = G.scalar_mult_vfy(yb, Ya) If K = G.I, raise CPaceError ISK = H.hash(lv_cat(G.DSI || b"_ISK", sid, K) || transcript(Ya, Yb)) return ISK, Yb¶
The functions lv_cat and transcript are defined in [CPACE].¶
The initiator finishes the protocol by combining the discrete logarithm ya generated by CPace.Init and the message Yb received from the responder.¶
CPace.Finish Input: - ya, discrete logarithm that was generated using CPace.Init - Yb, public point, received from the responder - sid, session identifier, a byte string Output: - ISK, the established shared secret Parameters: - G, a group environment as specified in CPace - H, a hash function as specified in CPace Exceptions: - CPaceError, raised when an invalid value was encountered in CPace def Finish(ya, Yb, sid): K = G.scalar_mult_vfy(ya, Yb) If K = G.I, raise CPaceError ISK = H.hash(lv_cat(G.DSI || b"_ISK", sid, K) || transcript(Ya, Yb)) return ISK¶
OQUAKE is a PAKE built on a BUA-sKEM and KDF. If the BUA-sKEM provides security against quantum-enabled attacks, then so does OQUAKE. It consists of two messages sent between initiator and responder, produced by the functions Init, Respond, and Finish, described below. Both parties take as input a password-related string PRS, an optional application-provided context, an optional session identifier sid, and an optional client identifier U and server identifier S. Upon completion, both parties obtain matching session keys if their PRS, context, sid, key length (specified by N), and client and server identifiers match. Otherwise, they obtain random session keys.¶
When a context is provided, OQUAKE derives an effective password from (PRS, context) and uses it in place of PRS throughout the protocol. This allows OQUAKE to be securely composed with a preceding protocol stage whose output key is provided as context.¶
The shared session identifier has the following requirements. If a client and server identifier are provided:¶
The session identifier must match between the client and server¶
This session identifier has not been used before in a session between the client and server¶
If no client and server identifiers are provided:¶
The session identifier must match between the client and server¶
This session identifier has not been used before by the client or server in any session with any other party¶
These requirements originate from the security proof for OQUAKE. If these requirements are not met, the proof does not apply, but this does not mean that the protocol becomes vulnerable.¶
The specification follows the design as presented in [VJWYMS25], with the splittable KEM technique described in [TEMPO], which prevents timing attacks caused by rejection sampling in ML-KEM. See Section 10.3 for more information on the timing attack and this fix.¶
Init takes as input the initiator's PRS, an optional context, an optional session identifier sid, and optional client and server identifiers U and S. It produces a context for the initiator to store, as well as a protocol message that is sent to the responder. Its implementation is as follows.¶
OQUAKE.Init
Input:
- PRS, password-related string, a byte string
- context, optional application-provided context, a byte string
- sid, session identifier, a byte string
- U and S, client and server identifiers
Output:
- context, opaque state for the initiator to store
- msg, an encoded protocol message for the initiator to send to the responder
Parameters:
- BUA-sKEM, a BUA-sKEM instance
- KDF, a KDF instance
- DST, domain separation tag, a byte string
def Init(PRS, context, sid, U, S):
fullsid = encode_sid(sid, U, S)
if context is not None:
prk_ePRS = KDF.Extract(PRS, DST || "OQUAKE-context" || fullsid || context)
effective_PRS = KDF.Expand(prk_ePRS, DST || "effective_PRS", Nkey)
else:
effective_PRS = PRS
seed = random(BUA-sKEM.Nseed)
(pk, sk) = BUA-sKEM.DeriveKeyPair(seed)
(ut, ⍴) = BUA-sKEM.Split(pk)
r = random(3 * Nsec)
// T = XOR(t, H(fullsid, effective_PRS, ⍴, r))
prk_T_pad = KDF.Extract(effective_PRS, DST || "OQUAKE" || fullsid || ⍴ || r)
T_pad = KDF.Expand(prk_T_pad, DST || "T_pad", BUA-sKEM.Nt)
T = XOR(ut, T_pad)
// s = XOR(r, H(fullsid, effective_PRS, ⍴, T))
prk_s_pad = KDF.Extract(effective_PRS, DST || "OQUAKE" || fullsid || ⍴ || T)
s_pad = KDF.Expand(prk_s_pad, DST || "s_pad", 3 * Nsec)
s = XOR(r, s_pad)
init_msg = s || T || ⍴
return Context(effective_PRS, sk, pk, s, T, fullsid), init_msg
¶
The encode_sid function is defined below.¶
encode_sid
Input:
- sid, session identifier, a byte string
- U and S, client and server identifiers
Output:
- fullsid, a byte string
Parameters:
- BUA-sKEM, a BUA-sKEM instance
- KDF, a KDF instance
def encode_sid(sid, U, S):
fullsid =
bytes_to_int(len(sid), 4) || sid ||
bytes_to_int(len(U), 4) || U ||
bytes_to_int(len(S), 4) || S
return fullsid
¶
Respond takes as input the PRS, an optional context, the initiator's protocol message, an optional session identifier, and optional client and server identifiers. It produces a 32-byte symmetric key and a protocol message intended to be sent to the initiator. Its implementation is as follows.¶
OQUAKE.Respond
Input:
- PRS, password-related string, a byte string
- context, optional application-provided context, a byte string
- init_msg, encoded protocol message, a byte string
- sid, session identifier, a byte string
- U and S, client and server identifiers
Output:
- ss, output shared secret, a byte string of 32 bytes
- resp_msg, encoded protocol message, a byte string
Parameters:
- BUA-sKEM, a BUA-sKEM instance
- KDF, a KDF instance
- DST, domain separation tag, a byte string
def Respond(PRS, context, init_msg, sid, U, S):
(s, T, ⍴) = init_msg[0 : (3 * Nsec)], init_msg[(3 * Nsec) : (6 * Nsec)], init_msg[(6 * Nsec) : (6 * Nsec) + N⍴]
fullsid = encode_sid(sid, U, S)
if context is not None:
prk_ePRS = KDF.Extract(PRS, DST || "OQUAKE-context" || fullsid || context)
effective_PRS = KDF.Expand(prk_ePRS, DST || "effective_PRS", Nkey)
else:
effective_PRS = PRS
prk_s_pad = KDF.Extract(effective_PRS, DST || "OQUAKE" || fullsid || ⍴ || T)
s_pad = KDF.Expand(prk_s_pad, DST || "s_pad", 3 * Nsec)
r = XOR(s, s_pad)
prk_T_pad = KDF.Extract(effective_PRS, DST || "OQUAKE" || fullsid || ⍴ || r)
T_pad = KDF.Expand(prk_T_pad, DST || "T_pad", BUA-sKEM.Nt)
ut = XOR(T, T_pad)
pk = BUA-sKEM.Combine(ut, ⍴)
(ct, k) = BUA-sKEM.Encaps(pk)
prk_sk = KDF.Extract(effective_PRS, DST || "OQUAKE" || fullsid || s || T || pk || ct || k)
key = KDF.Expand(prk_sk, DST || "sk", Nkey)
h = KDF.Expand(prk_sk, DST || "confirm", Nkc)
resp_msg = ct || h
return resp_msg, key
¶
Finish takes as input the initiator-created context that is output from Init as well as the responder's reply message resp_msg. It produces a symmetric key that is output to the initiator. Its implementation is as follows.¶
OQUAKE.Finish
Input:
- context, opaque state for the initiator to store
- resp_msg, encoded protocol message, a byte string
Output:
- ss, output shared secret, a byte string of 32 bytes
Parameters:
- BUA-sKEM, a BUA-sKEM instance
- KDF, a KDF instance
- DST, domain separation tag, a byte string
Exceptions:
- AuthenticationError, raised when the key confirmation fails
def Finish(context, resp_msg):
(effective_PRS, sk, pk, s, T, fullsid) = context
ct, h = resp_msg[0..Nct], resp_msg[Nct..]
try:
k = BUA-sKEM.Decaps(sk, ct)
prk_sk = KDF.Extract(effective_PRS, DST || "OQUAKE" || fullsid || s || T || pk || ct || k)
key = KDF.Expand(prk_sk, DST || "sk", Nkey)
h_expected = KDF.Expand(prk_sk, DST || "confirm", Nkc)
if h != h_expected:
return random(Nkey)
return key
catch DecapsError:
return random(Nkey)
¶
CPaceOQUAKE is a sequential composition of CPace (see Section 6.1) and OQUAKE (see Section 6.2). Whereas running CPace and OQUAKE in parallel realizes a worst-of-both worlds PAKE, this sequential composition realizes a best-of-both worlds PAKE. In other words, CPaceOQUAKE remains as secure as the strongest PAKE, resisting attacks that break the classical CPace (e.g. by a quantum-capable attacker) or attacks that break the quantum-resistant OQUAKE (e.g. by a flaw in the BUA-sKEM). This assumes that OQUAKE is instantiated with a quantum-resistant BUA-sKEM.¶
The reason a parallel combiner does not achieve best-of-both-worlds security is that it requires both constituent PAKEs to be unconditionally password hiding, meaning that the password must not be learnable even if all computational assumptions underlying the PAKE break. Intuitively, if one PAKE is not unconditionally password hiding, an attacker that breaks its computational assumptions can recover the password, and knowing the password is sufficient to then defeat the other PAKE as well. CPace is unconditionally password hiding in the sense that, even if the Diffie-Hellman assumption fails, the protocol transcript (including the exchanged group elements) is statistically independent of the password-related string PRS: PRS is only used to derive a generator, while the transmitted points are fresh random scalar multiples of this generator and hence are uniformly distributed in the group. OQUAKE, however, is not unconditionally password hiding: an attacker that can break the D-MLWE assumption can distinguish ML-KEM public keys and ciphertexts from random bitstrings and thereby mount offline dictionary attacks to recover the password. Because no currently known post-quantum PAKE built on standard primitives such as ML-KEM achieves unconditional password hiding, a parallel combiner cannot provide the desired hybrid security guarantee.¶
The sequential combiner overcomes this limitation. Instead of running OQUAKE on the original password-related string PRS, CPaceOQUAKE feeds the CPace session key to OQUAKE as context, which binds the original PRS to the CPace session key. Even if an attacker breaks D-MLWE and can distinguish OQUAKE public keys and ciphertexts, offline dictionary attacks against the original PRS are infeasible because the CPace-derived session key material is computationally indistinguishable from a random value (under the gap Diffie-Hellman assumption). The sequential composition is analyzed in [HR24] and a close variant is analyzed in [LL24].¶
To be precise, CPaceOQUAKE first runs CPace to completion using password-related string PRS, establishing a session key SK1. It then runs OQUAKE using PRS and context=SK1. OQUAKE derives an effective password from (PRS, SK1) and uses it throughout the protocol, producing session key SK2. The CPaceOQUAKE session key is SK2, which transitively depends on SK1 through the effective password derivation.¶
This is outlined in the diagram below. CPace is initiated by the client, and OQUAKE is also initiated by the client after CPace completes. This results in a four-message protocol.¶
Unlike OQUAKE, CPaceOQUAKE does not require a shared session identifier sid, although this is strongly recommended. If no sid is provided, CPace will run without an sid, and OQUAKE will use a random string generated with random material provided by both parties. If an sid is provided, both CPace and OQUAKE will use this sid.¶
An overview of the protocol flow is shown below. The protocol has five functions. Init, InitiatorContinue, and InitiatorFinish are intended to be called by the client, and Respond and ResponderFinish are intended to be called by the server.¶
The client initiates a CPace exchange with the server using input PRS, an optional session identifier sid, and optional client and server identifiers U and S. The output of this process is some context for completing the protocol and a protocol message. The client sends this message to the server.¶
CPaceOQUAKE.Init Input: - PRS, password-related string, a byte string - sid, session identifier, a byte string - U and S, client and server identifiers Output: - context, opaque state for the initiator to store - msg, an encoded protocol message for the initiator to send to the responder Parameters: - CPace, parameterized instance of CPace def Init(PRS, sid, U, S): ctx1, msg1 = CPace.Init(PRS, sid, U, S) s1 = random(32) init_msg = s1 || lv_encode(msg1) return (ctx1, s1), init_msg¶
The server processes the client message using its input PRS, an optional session identifier sid, and optional client and server identifiers U and S. The server responds to the CPace session that the client initiated, completing Stage 1.¶
The server MUST ensure that exactly one of s1 and sid exists. It MUST abort if the message does
not have the correct length.¶
CPaceOQUAKE.Respond Input: - PRS, password-related string, a byte string - init_msg, the message received from the client - sid, session identifier, a byte string - U and S, client and server identifiers Output: - context, opaque state for the responder to store - msg, an encoded protocol message for the responder to send to the initiator Parameters: - CPace, parameterized instance of CPace - DST, domain separation tag, a byte string def Respond(PRS, init_msg, sid, U, S): s1, msg1 = init_msg[0..32], lv_decode(init_msg[32..]) key1, msg2 = CPace.Respond(PRS, msg1, sid, U, S) s2 = random(32) resp_msg = s2 || lv_encode(msg2) return Context(s1, s2, key1), resp_msg¶
The client finishes CPace (Stage 1) and initiates OQUAKE (Stage 2). The client derives the CPace session key, then uses it as context for OQUAKE. The output is a new context and an OQUAKE init message to send to the server.¶
The client must ensure that exactly one of (s1, s2) and sid exists. The client should abort when the message does not have the correct length.¶
CPaceOQUAKE.InitiatorContinue Input: - PRS, password-related string, a byte string - (ctx1, s1), the context generated by CPaceOQUAKE.Init - resp_msg, the message received from the server - sid, session identifier, a byte string - U and S, client and server identifiers Output: - context, opaque state for the initiator to store - msg, an encoded protocol message for the initiator to send to the responder Parameters: - CPace, parameterized instance of CPace - OQUAKE, parameterized instance of OQUAKE - DST, domain separation tag, a byte string def InitiatorContinue(PRS, (ctx1, s1), resp_msg, sid, U, S): s2 = resp_msg[0..32] msg2 = lv_decode(resp_msg[32..]) key1 = CPace.Finish(ctx1, msg2, sid) prk_extended_sid = KDF.Extract(s1 || s2, DST || "CPaceOQUAKE") extended_sid = KDF.Expand(prk_extended_sid, DST || "SID", 32) ctx2, msg3 = OQUAKE.Init(PRS, key1, extended_sid, U, S) return ctx2, msg3¶
The server completes the protocol by responding to the OQUAKE session (Stage 2). The server uses the CPace session key from Stage 1 as context for OQUAKE. The OQUAKE output key is the CPaceOQUAKE session key.¶
The server should abort when the message does not have the correct length.¶
CPaceOQUAKE.ResponderFinish Input: - PRS, password-related string, a byte string - ctx, context from the server's Response - msg3, the message received from the client, a byte string - sid, session identifier, a byte string - U and S, client and server identifiers Output: - key, an N-byte shared secret - msg, an encoded protocol message for the responder to send to the initiator Parameters: - OQUAKE, parameterized instance of OQUAKE - DST, domain separation tag, a byte string def ResponderFinish(PRS, ctx, msg3, sid, U, S): (s1, s2, key1) = ctx prk_extended_sid = KDF.Extract(s1 || s2, DST || "CPaceOQUAKE") extended_sid = KDF.Expand(prk_extended_sid, DST || "SID", 32) resp_msg, server_key = OQUAKE.Respond(PRS, key1, msg3, extended_sid, U, S) return server_key, resp_msg¶
The client finishes the protocol by completing OQUAKE (Stage 2). The OQUAKE output key is the CPaceOQUAKE session key.¶
CPaceOQUAKE.InitiatorFinish Input: - ctx, context from OQUAKE.Init (stored by CPaceOQUAKE.InitiatorContinue) - msg4, the message received from the server, a byte string Output: - key, an N-byte shared secret Parameters: - OQUAKE, parameterized instance of OQUAKE def InitiatorFinish(ctx, msg4): client_key = OQUAKE.Finish(ctx, msg4) return client_key¶
CPaceOQUAKE+ is the five-message aPAKE resulting from composing CPace (Stage 1) and OQUAKE+ (Stage 2). At a high level, this involves running CPace on a verifier of the client's password, followed by OQUAKE+, which performs the post-quantum key exchange and password confirmation in a single stage. To ensure that the client does indeed know the password pertaining to that verifier, the OQUAKE+ stage uses a seed derived from the password. Both the verifier and the seed are derived from the password using a key stretching function. The seed is later used to derive a KEM public key. We refer to the collection of the verifier and this public key as 'the verifiers'.¶
This document also specifies standalone OQUAKE+ (see Section 7.3), a post-quantum aPAKE that uses the OQUAKE+ stage without the classical CPace stage.¶
The CPaceOQUAKE+ protocol can be seen as a close variant (and a specific instance) of the `augmented PAKE' construction presented in [LLH24] and in [Gu24].¶
This subsection specifies functions for generating the verifiers and a protocol for registering clients.¶
Verifiers are random-looking value derived from password-related strings from which it is computionally impractical to derive the password-related string. To make verifiers unique between different users with the same password or servers that they interact with, we employ a salt, a user account identifier, and an optional server identifier. The material required for the verifiers is generated as follows:¶
GenVerifierMaterial Input: - PRS, password-related string, a byte string - salt, client-specific salt, a byte string - U and S, client and server identifiers Output: - ss, output shared secret, a byte string of 32 bytes - resp_msg, encoded protocol message, a byte string Parameters: - KEM, a KEM instance - KSF, a parameterized KSF instance - DST, domain separation tag, a byte string def GenVerifierMaterial(PRS, salt, U, S): verifier_seed = KSF.Stretch(DST || PRS || U || S, salt, Nverifier + KEM.Nseed) verifier = verifier_seed[0:Nverifier] seed = verifier_seed[Nverifier:Nverifier + KEM.Nseed] return verifier, seed¶
To derive an actual public key from the verifier material, we use the following function:¶
GenVerifiers Input: - PRS, password-related string, a byte string - salt, client-specific salt, a byte string - U and S, client and server identifiers Output: - ss, output shared secret, a byte string of 32 bytes - resp_msg, encoded protocol message, a byte string Parameters: - KEM, a KEM instance def GenVerifiers(PRS, salt, U, S): verifier, seed = GenVerifierMaterial(PRS, salt, U, S) (pk, sk) = KEM.DeriveKeyPair(seed) return verifier, pk¶
The server MUST store pk; it MUST NOT store seed.¶
The registration phase consists of one message sent from the client to the server. This message contains the verifier, a public key, and 32-byte salt. The server stores this information corresponding to the client for future use in the verification flow. This phase requires a secure channel from client to server in order to transfer the password verifier and public key. The salt can be sent in plain text.¶
We recommend that the salt is a random byte string: salt = random(32). However, in practice this
may require an additional communication flow, used by the server to send the salt to the client
before protocol CPaceOQUAKE+ starts. Instead, one may consider deriving the salt from some
client-specific value that it knows and can retain locally.¶
A high level flow overview of the registration flow is below.¶
OQUAKE+ is an augmented variant of OQUAKE that adds password confirmation to upgrade the symmetric PAKE to an asymmetric PAKE. It uses the registered verifiers from the previous subsection. In the OQUAKE+ stage, the client proves knowledge of its password without revealing it by responding to a challenge from the server. OQUAKE+ is parameterized by a BUA-sKEM, KEM, KDF, and KSF; see Section 8 for specific parameter configurations.¶
OQUAKE+ is a three-message flow between the client and server. The client initiates the OQUAKE key exchange. The server responds with the OQUAKE key exchange response and a password confirmation challenge (piggybacked into a single message). The client completes the OQUAKE key exchange, then responds to the challenge.¶
A high level overview of this flow is below.¶
Init takes the same inputs as OQUAKE.Init and produces the same outputs. It is defined identically to OQUAKE.Init (see Section 6.2).¶
OQUAKE+.Init Input: - PRS, password-related string, a byte string - context, optional application-provided context, a byte string - sid, session identifier, a byte string - U and S, client and server identifiers Output: - context, opaque state for the initiator to store - msg, an encoded protocol message for the initiator to send to the responder Parameters: - BUA-sKEM, a BUA-sKEM instance - KDF, a KDF instance - DST, domain separation tag, a byte string def Init(PRS, context, sid, U, S): return OQUAKE.Init(PRS, context, sid, U, S)¶
Respond takes as input the PRS, an optional context, the initiator's protocol message, the client's registered public key, an optional session identifier, and optional client and server identifiers. It produces an opaque context and a protocol message that combines the OQUAKE response with a password confirmation challenge.¶
The implementation MUST NOT reveal server_key from the context.¶
OQUAKE+.Respond Input: - PRS, password-related string, a byte string - context, optional application-provided context, a byte string - init_msg, encoded protocol message, a byte string - pk, client-registered public key, a KEM public key - sid, session identifier, a byte string - U and S, client and server identifiers Output: - context, opaque state for the server to store values to complete the protocol - resp_msg, encoded protocol message, a byte string Parameters: - BUA-sKEM, a BUA-sKEM instance - KEM, a KEM instance - KDF, a KDF instance - DST, domain separation tag, a byte string def Respond(PRS, context, init_msg, pk, sid, U, S): oquake_resp, SK = OQUAKE.Respond(PRS, context, init_msg, sid, U, S) (c, k) = KEM.Encaps(pk) r = KDF.Expand(SK, DST || "OTP", Nct) enc_c = XOR(c, r) confirm_input = encode_sid(sid, U, S) || enc_c prk_k_h1 = KDF.Extract(SK, DST || "h1" || confirm_input) prk_k_h2 = KDF.Extract(SK, DST || "h2" || confirm_input || k) client_confirm = KDF.Expand(prk_k_h1, DST || "client_confirm", Nkc) server_confirm = KDF.Expand(prk_k_h2, DST || "server_confirm", Nkc) server_key = KDF.Expand(prk_k_h2, DST || "key", Nkey) resp_msg = oquake_resp || enc_c || client_confirm return Context(server_confirm, server_key), resp_msg¶
Finish takes as input the initiator-created context from Init, the seed used to derive the KEM key pair during registration, the responder's combined reply message, a session identifier, and client and server identifiers.¶
The client completes the OQUAKE key exchange to recover the shared secret, then uses it to decrypt the password confirmation challenge. The client re-derives the KEM key pair from the seed and decapsulates the KEM ciphertext to recover the shared secret and derive password confirmation values and a new shared secret.¶
The client checks that the server-provided confirmation value matches its own and aborts if not. Otherwise, it returns its own password confirmation value. The client outputs the new shared secret as its output.¶
OQUAKE+.Finish
Input:
- context, opaque state for the initiator to store
- seed, seed used to derive KEM public key
- resp_msg, encoded protocol message, a byte string
- sid, session identifier, a byte string
- U and S, client and server identifiers
Output:
- client_key, a 32-byte string
- response, an encoded protocol message for the client to send to the server
Exceptions:
- AuthenticationError, raised when the password confirmation values do not match
Parameters:
- BUA-sKEM, a BUA-sKEM instance
- KEM, a KEM instance
- KDF, a KDF instance
- DST, domain separation tag, a byte string
def Finish(context, seed, resp_msg, sid, U, S):
oquake_resp = resp_msg[0 : Nct_bua + Nkc]
enc_c = resp_msg[Nct_bua + Nkc : Nct_bua + Nkc + Nct]
client_confirm_target = resp_msg[Nct_bua + Nkc + Nct :]
SK = OQUAKE.Finish(context, oquake_resp)
r = KDF.Expand(SK, DST || "OTP", Nct)
c = XOR(enc_c, r)
(pk, sk) = KEM.DeriveKeyPair(seed)
try:
k = KEM.Decaps(sk, c)
confirm_input = encode_sid(sid, U, S) || enc_c
prk_k_h1 = KDF.Extract(SK, DST || "h1" || confirm_input)
prk_k_h2 = KDF.Extract(SK, DST || "h2" || confirm_input || k)
client_confirm = KDF.Expand(prk_k_h1, DST || "client_confirm", Nkc)
server_confirm = KDF.Expand(prk_k_h2, DST || "server_confirm", Nkc)
client_key = KDF.Expand(prk_k_h2, DST || "key", Nkey)
if client_confirm != client_confirm_target:
raise AuthenticationError
return client_key, server_confirm
catch DecapsError:
raise AuthenticationError
¶
Upon receipt of the response, the server validates that the password confirmation value matches its own value. If the value does not match, the server aborts. Otherwise, the server outputs the new shared secret as its output.¶
OQUAKE+.Verify
Input:
- context, opaque context produced by Respond
- server_confirm_target, client's response message, a byte string
Output:
- server_key, a 32-byte string
Exceptions:
- AuthenticationError, raised when the password confirmation values do not match
Parameters:
def Verify(context, server_confirm_target):
(server_confirm, server_key) = context
if server_confirm != server_confirm_target:
raise AuthenticationError
return server_key
¶
OQUAKE+ can be used as a standalone post-quantum aPAKE without the classical CPace stage. The client runs OQUAKE+ with the verifier as the password-related string, and uses the seed to respond to the password confirmation challenge.¶
Standalone OQUAKE+ consists of three messages:¶
CPaceOQUAKE+ is the composition of CPace (Stage 1) and OQUAKE+ (Stage 2). It is a hybrid aPAKE that provides security against both classical and quantum-capable attackers.¶
The composition is strictly sequential. First, the parties run CPace
using the verifier derived from the client's password.
The client recovers this verifier using the GenVerifierMaterial function.
After CPace completes, the parties proceed with OQUAKE+,
which is initiated by the client. The server uses the stored
public key to challenge the client, and the client uses the seed produced
by GenVerifierMaterial to prove knowledge of the password. This seed
MUST remain secret to prevent impersonation.¶
An overview of the composition is below.¶
Upon successful completion of the entire protocol, the client and server will share a symmetric key that was authenticated by knowledge of the password. The protocol aborts if the password did not match. The protocol flows are shown below. Note here that if the client does not know the salt, the server must send it to the client before the protocol starts, which it can do in plain text.¶
CPaceOQUAKE+ is instantiated by selecting a configuration of a group and hash function for the CPace protocol, a KEM, KDF, KSF, for the OQUAKE+ stage, and a KEM and KDF for the OQUAKE stage, and a general purpose cryptographic hash function H. The KEM, KDF, are not required to be the same, so they are distinguished by "PC-" and "PAKE-" prefixes, e.g., PC-KDF and PAKE-KDF are the KDFs for the OQUAKE+ stage and the OQUAKE stage, respectively.¶
The RECOMMENDED configuration is below.¶
CPace-Hash: SHA-512¶
KEM: X-Wing [XWING], where Nseed = 32, Nct = 1120, and Npk = 1216.¶
PC-KDF: HKDF-SHA-256¶
PC-KSF: Argon2id(S = zeroes(16), p = 4, T = Nh, m = 2^21, t = 1, v = 0x13, K = nil, X = nil, y = 2) [ARGON2]¶
BUA-sKEM: ML-BUA-sKEM1024 Section 4.2, where Kemeleon.sec_param = 256, Nseed = 64, Npk = 1594, and Nct = 1568.¶
PAKE-KDF: HKDF-SHA-256¶
H: SHA256¶
DST: "1b3abc3cd05e8054e8399bc38dfcbc1321d2e1b02da335ed1e8031ef5199f672" (a randomly generated 32-byte string)¶
The RECOMMENDED parameters are (see Appendix A):¶
Nverifier = 32¶
Nkc = 64¶
Nsec = 32¶
Nkey = 32, this is achieved by choosing H in CPace with H.b_in_bytes = 32¶
Other documents can define configurations as needed for their use case, subject to the following requirements:¶
KEM MUST be a hybrid KEM, i.e., one that achieves both classical and post-quantum security.¶
The parameters must be chosen so they correspond with this KEM. E.g., Nseed must have the correct length.¶
For instance, one possible additional configuration is as follows.¶
CPace-Group: CPACE-P256XMD:SHA-256_SSWU_NU-SHA256 Section 4 of [CPACE]¶
CPace-Hash: SHA-256¶
KEM: X-Wing [XWING], where Nseed = 32, Nct = 1120, and Npk = 1216.¶
PC-KDF: HKDF-SHA-256¶
BUA-sKEM: ML-BUA-sKEM1024 Section 4.2, where Kemeleon.sec_param = 256, Nseed = 64, Npk = 1594, and Nct = 1568.¶
PAKE-KDF: HKDF-SHA-256¶
H: SHA256¶
DST: "b840fa4d4b4caec9e25d13d8c016cfe93e7468d54e936490bd0b0a3ffca1a01b" (a randomly generated 32-byte string)¶
Some functions included in this specification are fallible (as noted by their ability to raise exceptions). The explicit errors generated throughout this specification, along with conditions that lead to each error, are as follows:¶
AuthenticationError: The OQUAKE+ stage fails password confirmation checks at the client or server; Section 7.2¶
Beyond these explicit errors, CPaceOQUAKE+ implementations can produce implicit errors. For example, if protocol messages sent between client and server do not match their expected size, an implementation should produce an error.¶
The errors in this document are meant as a guide for implementors. They are not an exhaustive list of all the errors an implementation might emit. For example, an implementation might run out of memory.¶
This section discusses security considerations for the protocols specified in this document.¶
CPaceOQUAKE and CPaceOQUAKE+ are hybrid PAKE protocols, meaning that the overall protocol remains secure so long as either the classical assumptions underlying CPace, i.e., the gap Diffie-Hellman assumption, or the post-quantum assumptions, i.e., D-MLWE used by OQUAKE, hold. This protects against vulnerabilities in either the classical or post-quantum components.¶
Moreover, OQUAKE does not unconditionally hide the password. If the underlying security assumptions were to break, then the password would be revealed to the attacker. The reason for this is that an attacker that can break the D-MLWE assumption can distinguish actual ML-KEM public keys and ciphertexts from random bitstrings. For OQUAKE, this would allow the attacker to perform offline dictionary attacks on the password. This is also the reason a parallel combiner cannot provide the desired hybrid security (see Section 6.3): if one PAKE is not unconditionally password hiding, breaking its underlying assumption can yield the password, and learning the password is sufficient to also break the other PAKE. In contrast, the sequential hybrid variants do not suffer from the same weakness: the input to OQUAKE is an effective password, derived from (PRS, context) where context is the CPace session key, not the original PRS. Performing an offline dictionary attack against the original PRS would require the attacker to also guess the CPace-derived key, which is computationally indistinguishable from a random value under the gap Diffie-Hellman assumption.¶
The benefits of this hybrid protection come at the cost of protocol and round complexity. From a protocol perspective, beyond two independent PAKEs treated nearly as black boxes, additional protocol logic is needed to combine the PAKEs together and produce a shared secret based on both PAKEs. From a round perspective, the hybrid PAKE introduces additional round trips, complicating integration into higher-level protocols like TLS. Specifically, integrating CPaceOQUAKE+ into TLS would require five messages:¶
Client -> Server: ClientHello carrying msg1 (CPace init)¶
Server -> Client: ServerHello carrying msg2 (CPace resp)¶
Client -> Server: msg3 (OQUAKE+ init)¶
Server -> Client: msg4 (OQUAKE+ resp + PC challenge)¶
Client -> Server: msg5 (PC response)¶
Compared to the basic TLS handshake, which has three messages:¶
Client -> Server: ClientHello¶
Server -> Client: ServerHello...Finished¶
Client -> Server: Finished¶
Finally, the hybrid protocol is comparatively new and has not yet received significant peer review (compared to the non-hybrid PAKEs). However, the backing analysis has been independently analyzed by at least three different groups, improving overall confidence in the design.¶
Client and server identities are essential to authenticated key exchange protocols, and PAKEs are no exception. This section discusses the role and importance of identities in the PAKE protocols specified in this document.¶
PAKEs are often analyzed in the universal composability (UC) framework, which imposes several requirements on the protocols: (1) the existence of a globally-unique session identifer associated with each protocol invocation, and (2) unique party identifiers. Both are considered as inputs to PAKEs, along with the password itself. In practice, however, computing or agreeing on session and party identifiers is non-trivial and cumbersome. For example, agreeing on a globally unique session identifier requires a protocol to run before the PAKE. Moreover, assigning identifiers to parties -- especially in symmetric PAKE settings -- is problematic as there are rarely pragmatic choices to be made for each party's identifier. IP addresses are not always unique, PKI or some other registry mechanism for assigning names may not exist, and so on.¶
Intuitively, in symmetric settings, passwords are the only secret input to the PAKE protocol; party identities are assumed to be public. As such, an adversary is assumed to know these identifiers. Fortunately, there exists a UC model in which symmetric PAKEs such as CPace are proven secure without requiring party or session identifiers -- the bare PAKE model [BARE-PAKE]. The UC bare PAKE model, and proof of security for CPace in this model, demonstrate that PAKEs are universally composable without relying on unique party or session identifiers. We believe that the current proof of security of OQUAKE in [ABJ25] can be extended to show that NoIC, the basis of OQUAKE, realizes the Bare PAKE model as well, although we note that that this proof has not been published yet.¶
As such, for the PAKEs in Section 6, both the party and session identifier are optional. Applications are free to choose values for these identifiers if applicable, but they are not required for security.¶
[[OPEN ISSUE: adjust the requirements for the identities in OQUAKE on the basis on the bare PAKE analysis]]¶
In contrast to the symmetric PAKE setting, party identities in the asymmetric PAKE setting play a different role. The very nature of the asymmetric PAKE is that one server, with many different registered passwords, can authenticate many different clients. Consequently, when the protocol runs, the server needs some way to determine which password registration to use in the protocol. Beyond ensuring that the server is authenticating the correct client, the client's identity is what helps the server make this selection.¶
However, the server identifier carries a similar burden. Indeed, the server identifier is used to distinguish distinct server instances from each other so, for example, a client cannot mistakenly authenticate with server A when communicating with server B. This is especially important if the client re-uses their identifier across server instances, since a password registration for server A would then be valid for server B if the server identity were not incorporated into the protocol.¶
Based on this, client and server identities are RECOMMENDED for the asymmetric PAKEs specified in this document (in Section 7). Both client and server identities can be long-lived, e.g., a client identity could be an email address and a server identity could be a domain name.¶
Practically, applications should be mindful of what happens when these identities change. Since they are both included in the password verifier (see Section 7.1.1), changing either identifier will require the veirifer to be re-computed and the client to be re-registered. For a single client, this change is minimal, but for a single server, which can have many registered clients, this change can be expensive. Applications therefore ought to consider the longevitiy and uniqueness of their party identifiers when instantiating these protocols.¶
OQUAKE (without the fix from [TEMPO]) is subject to a timing attack due to how the ML-KEM expands the key-generation seed (rho) to a matrix (A). An internal function — SampleNTT — uses rejection sampling based on the seed and therefore is variable time. In NoIC / OQUAKE, after a sender password-encrypts a public key, an attacker can perform an offline dictionary attack based on this key in the following way:¶
Password-decrypt the authenticated public key using a candidate password.¶
Time the seed-to-matrix expansion step using this candidate public key and compare it against the known timing target.¶
The Tempo fix addresses this issue by ensuring that input to SampleNTT is not secret-dependent.¶
This document has no IANA actions.¶
This section discusses how to generate parameters, given an upper bound on an adversary's advantage in breaking the hybrid (a)PAKE. The parameters in this standard correspond to a classical hardness of 117 bits (considering the attacker can break CPace) and a quantum hardness of 100 bits. We assume that an adversary can perform at most 2^qq queries to random oracles or (a)PAKE sessions. We use qq = 64. The derivation below uses some approximations, ignoring small constants in the exponent such as 1 and 1.6. We also only study dominant terms in the advantage equations.¶
We have the following requirements:¶
Nseed * 8 + Nverifier * 8 >= 2 * qq + classical hardness¶
Nverifier * 8 >= qq + classical hardness¶
Nkc * 8 >= qq + classical hardness¶
KEM failure <= -qq - classical hardness¶
KEM ind vs classical <= -qq - classical hardness¶
KEM ind vs quantum <= -qq - quantum hardness¶
CPaceOQUAKE vs classical <= classical hardness¶
CPaceOQUAKE vs quantum <= quantum hardness¶
For ML-KEM we have Nseed = 32. For consistency, the spec uses Nverifier = 32. ML-KEM1024's failure probability is 2^-175.2. This is slightly too large, but we deem it acceptable: the chance that an adversary encounters a failure is purely statistical and very small.¶
The following subsection discusses the parameters and hardness of CPaceOQUAKE.¶
For the security of CPaceOQUAKE+, we require that CPaceOQUAKE provides:¶
We have the following requirements when CPaceOQUAKE relies on CPace's security:¶
CPace vs classical <= classical hardness¶
Nkey * 8 >= qq + classical hardness¶
KEM failure <= -qq - classical hardness¶
We have the following requirements when CPaceOQUAKE relies on OQUAKE's security:¶
OQUAKE vs classical <= classical hardness¶
OQUAKE vs quantum <= quantum hardness¶
Nkey * 8 >= 2*qq + classical hardness¶
So, the smallest Nkey = 32. We ignore the KEM failure following the same reasoning as above.¶
The following subsections discuss the parameters and hardness of CPace and OQUAKE.¶
We refer to the CPace [CPACE]. This standard requires Nkey, the number of bytes in CPace's session key, to be 32, so one must set H.bmax_in_bytes = 32.¶
We have the following requirements:¶
BUA-sKEM ind vs classical <= -qq - classical hardness¶
BUA-sKEM ind vs quantum <= -qq - quantum hardness¶
BUA-sKEM public key uniformity vs classical <= -qq - classical hardness¶
BUA-sKEM public key uniformity vs quantum <= -qq - quantum hardness¶
BUA-sKEM ciphertext uniformity vs classical <= -qq - classical hardness¶
BUA-sKEM ciphertext uniformity vs quantum <= -qq - quantum hardness¶
BUA-sKEM key * 8 >= qq + classical hardness¶
KEM failure <= -qq - classical hardness¶
For ML-BUA-sKEM, if we set Kemeleon.sec_param to 256, it is as hard or harder to break public key and ciphertext uniformity as it is to break indistinguishability, so we discuss all three properties at once.¶
For ML-BUA-sKEM1024, the resistance to classical attacks is approximately 253 - qq bits of security. So for qq = 64, classical hardness is approximately 189 bits of security. The resistance to quantum attacks is approximately 230 - qq bits of security. So for qq = 64, quantum hardness is approximately 166 bits of security.¶
The ML-BUA-sKEM key is 32 bytes, so this satisfies the requirements. We ignore the KEM failure following the same reasoning as above.¶