Asymmetric PAKE with low computation and communication 📺
In Crypto'21 Gu, Jarecki, and Krawczyk  showed an asymmetric password authenticated key exchange protocol (aPAKE) whose computational cost matches (symmetric) password authenticated key exchange (PAKE) and plain (i.e. unauthenticated) key exchange (KE). However, this minimal-cost aPAKE did not match prior aPAKE's in round complexity, using 4 rounds assuming the client initiates compared to 2 rounds in an aPAKE of Bradley et al. In this paper we show two aPAKE protocols that achieve optimal computational cost and optimal round complexity. Our protocols can be seen as applications of the Encrypted Key Exchange (EKE) compiler of Bellovin and Merritt , which creates password-authenticated key exchange by password-encrypting messages in a key exchange protocol. Whereas Bellovin and Merritt used this method to construct a PAKE by applying password-encryption to KE messages, we construct an aPAKE by applying password-encryption to messages of a unilaterally authenticated Key Exchange (ua-KE). We present two versions of this compiler. The first uses salted password hash and takes 3 rounds if the client initiates. The second uses unsalted password hash and takes a single simultaneous flow (it is the first aPAKE to do so), thus simultaneously matching the minimal computational cost and the minimal round complexity of PAKE and KE. We analyze our aPAKE protocols assuming Ideal Cipher (IC) on a group as modular constructions from ua-KE realized via a (universally composable) Authenticated Key Exchange where the server uses one-time keys (otk-AKE). We then show that one-pass variants of 3DH and HMQV securely realize otk-AKE in ROM. Interestingly, the two resulting concrete aPAKE's use the exact same protocol messages as two natural variants of EKE, and the only difference between the symmetric PAKE (EKE) and asymmetric PAKE (our protocols) is in the key derivation equation used to derive the final session key output.
KHAPE: Asymmetric PAKE from Key-Hiding Key Exchange 📺
OPAQUE [Jarecki et al., Eurocrypt 2018] is an asymmetric password authenticated key exchange (aPAKE) protocol that is being developed as an Internet standard and for use within TLS 1.3. OPAQUE combines an Oblivious PRF (OPRF) with an authenticated key exchange to provide strong security properties, including security against pre-computation attacks (called saPAKE security). However, the security of OPAQUE relies crucially on the integrity of the OPRF. If the latter breaks (by cryptanalysis, quantum attacks or security compromise), the user's password is immediately exposed to an offline dictionary attack. To address this weakness, we present KHAPE, a variant of OPAQUE that does not require the use of an OPRF to achieve aPAKE security, resulting in improved resilience and performance. An OPRF can be optionally added to KHAPE, for enhanced saPAKE security, but without opening the password to an offline dictionary attack upon OPRF compromise. In addition to resilience to OPRF compromise, a DH-based implementation of KHAPE (using HMQV) offers the best performance among aPAKE protocols in terms of exponentiations with less than the cost of an exponentiation on top of an unauthenticated Diffie-Hellman exchange. KHAPE uses three messages with explicit client authentication and four with explicit server authentication (one more than OPAQUE in the latter case). All results in the paper are proven within the UC framework in the ideal cipher model. Of independent interest is our treatment of "key-hiding AKE" which KHAPE uses as a main component, and our UC proofs of AKE security for protocols 3DH (a basis of Signal) and HMQV that we use as efficient instantiations of KHAPE.