idnits 2.17.1 draft-krawczyk-cfrg-opaque-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document is more than 15 pages and seems to lack a Table of Contents. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 21, 2019) is 1643 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-15) exists of draft-ietf-tls-exported-authenticator-07 == Outdated reference: A later version (-04) exists of draft-barnes-tls-pake-02 == Outdated reference: A later version (-13) exists of draft-irtf-cfrg-argon2-03 == Outdated reference: A later version (-26) exists of draft-irtf-cfrg-spake2-05 == Outdated reference: A later version (-16) exists of draft-irtf-cfrg-hash-to-curve-01 == Outdated reference: A later version (-03) exists of draft-sullivan-cfrg-voprf-02 == Outdated reference: A later version (-01) exists of draft-sullivan-tls-opaque-00 == Outdated reference: A later version (-18) exists of draft-ietf-tls-esni-03 Summary: 2 errors (**), 0 flaws (~~), 9 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Crypto Forum Research Group H. Krawczyk 3 Internet-Draft Algorand Foundation 4 Intended status: Informational October 21, 2019 5 Expires: April 23, 2020 7 The OPAQUE Asymmetric PAKE Protocol 8 draft-krawczyk-cfrg-opaque-03 10 Abstract 12 This draft describes the OPAQUE protocol, a secure asymmetric 13 password authenticated key exchange (aPAKE) that supports mutual 14 authentication in a client-server setting without reliance on PKI and 15 with security against pre-computation attacks upon server compromise. 16 Prior aPAKE protocols did not use salt and if they did, the salt was 17 transmitted in the clear from server to user allowing for the 18 building of targeted pre-computed dictionaries. OPAQUE security has 19 been proven by Jarecki et al. (Eurocrypt 2018) in a strong and 20 universally composable formal model of aPAKE security. In addition, 21 the protocol provides forward secrecy and the ability to hide the 22 password from the server even during password registration. 24 Strong security, versatility through modularity, good performance, 25 and an array of additional features make OPAQUE a natural candidate 26 for practical use and for adoption as a standard. To this end, this 27 draft presents several optimized instantiations of OPAQUE and ways of 28 integrating OPAQUE with TLS. 30 This draft presents a high-level description of OPAQUE highlighting 31 its components and modular design. A detailed unambiguous 32 specification for standardization will be presented in future 33 revisions of this document, or separately. 35 Status of This Memo 37 This Internet-Draft is submitted in full conformance with the 38 provisions of BCP 78 and BCP 79. 40 Internet-Drafts are working documents of the Internet Engineering 41 Task Force (IETF). Note that other groups may also distribute 42 working documents as Internet-Drafts. The list of current Internet- 43 Drafts is at http://datatracker.ietf.org/drafts/current/. 45 Internet-Drafts are draft documents valid for a maximum of six months 46 and may be updated, replaced, or obsoleted by other documents at any 47 time. It is inappropriate to use Internet-Drafts as reference 48 material or to cite them other than as "work in progress." 49 This Internet-Draft will expire on April 23, 2020. 51 Copyright Notice 53 Copyright (c) 2019 IETF Trust and the persons identified as the 54 document authors. All rights reserved. 56 This document is subject to BCP 78 and the IETF Trust's Legal 57 Provisions Relating to IETF Documents 58 (http://trustee.ietf.org/license-info) in effect on the date of 59 publication of this document. Please review these documents 60 carefully, as they describe your rights and restrictions with respect 61 to this document. Code Components extracted from this document must 62 include Simplified BSD License text as described in Section 4.e of 63 the Trust Legal Provisions and are provided without warranty as 64 described in the Simplified BSD License. 66 1. Introduction 68 Password authentication is the prevalent form of authentication in 69 the web and in most other applications. In the most common 70 implementation, a user authenticates to a server by entering its user 71 id and password where both values are transmitted to the server under 72 the protection of TLS. This makes the password vulnerable to TLS 73 failures, including many forms of PKI attacks, certificate 74 mishandling, termination outside the security perimeter, visibility 75 to middle boxes, and more. Moreover, even under normal operation, 76 passwords are always visible in plaintext form at the server upon TLS 77 decryption (in particular, storage of plaintext passwords is not an 78 uncommon security incident, even among security-conscious companies). 80 Asymmetric (or augmented) Password Authenticated Key Exchange (aPAKE) 81 protocols are designed to provide password authentication and 82 mutually authenticated key exchange without relying on PKI (except 83 during user/password registration) and without disclosing passwords 84 to servers or other entities other than the client machine. A secure 85 aPAKE should provide the best possible security for a password 86 protocol, namely, it should only be open to inevitable attacks: 87 online impersonation attempts with guessed user passwords and offline 88 dictionary attacks upon the compromise of a server and leakage of its 89 password file. In the latter case, the attacker learns a mapping of 90 a user's password under a one-way function and uses such a mapping to 91 validate potential guesses for the password. Crucially important is 92 for the password protocol to use an unpredictable one-way mapping or 93 otherwise the attacker can pre-compute a deterministic list of mapped 94 passwords leading to almost instantaneous leakage of passwords upon 95 server compromise. 97 Quite surprisingly, in spite of the existence of multiple designs for 98 (PKI-free) aPAKE protocols, none of these protocols is secure against 99 pre-computation attacks. In particular, none of these protocols can 100 use the standard technique against pre-computation that combines 101 _secret_ random values ("salt") into the one-way password mappings. 102 Either these protocols do not use salt at all or, if they do, they 103 transmit the salt from server to user in the clear, hence losing the 104 secrecy of the salt and its defense against pre-computation. 105 Furthermore, the transmission of salt may incur additional protocol 106 messages. 108 This draft describes OPAQUE, a PKI-free secure aPAKE that is secure 109 against pre-computation attacks and capable of using secret salt. 110 OPAQUE has been recently defined and studied by Jarecki et al. 111 [OPAQUE] who prove the security of the protocol in a strong aPAKE 112 model that ensures security against pre-computation attacks and is 113 formulated in the Universal Composability framework [Canetti01] under 114 the random oracle model. In contrast, very few aPAKE protocols have 115 been proven formally and those proven were analyzed in a weak 116 security model that allows for pre-computation attacks (e.g., 117 [GMR06]). This is not just a formal issue: these protocols are 118 actually vulnerable to such attacks! Furthermore, as far as we know, 119 protocols discussed recently as candidates for standardization (e.g., 120 SPAKE2+ [I-D.irtf-cfrg-spake2] and AugPAKE [RFC6628]) do not enjoy a 121 proof of security, not even in a weak model. The same holds for the 122 SRP protocol [RFC2945]. VTBPEKE is analyzed in [VTBPEKE] in a weak 123 model that allows for pre-computation attacks and, as in all the 124 above cases (except OPAQUE), does not accommodate secret salt. 126 OPAQUE's design builds on a line of work initiated in the seminal 127 paper of Ford and Kaliski [FK00] and is based on the HPAKE protocol 128 of Xavier Boyen [Boyen09] and the (1,1)-PPSS protocol from Jarecki et 129 al. [JKKX16]. None of these papers considered security against pre- 130 computation attacks or presented a proof of aPAKE security (not even 131 in a weak model). 133 In addition to its proven resistance to pre-computation attacks, 134 OPAQUE's security features include forward secrecy (essential for 135 protecting past communications in case of password leakage) and the 136 ability to hide the password from the server - even during password 137 registration. Moreover, good performance and an array of additional 138 features make OPAQUE a natural candidate for practical use and for 139 adoption as a standard. Such features include the ability to 140 increase the difficulty of offline dictionary attacks via iterated 141 hashing or other hardening schemes, and offloading these operations 142 to the client (that also helps against online guessing attacks); 143 extensibility of the protocol to support storage and retrieval of 144 user's secrets solely based on a password; and being amenable to a 145 multi-server distributed implementation where offline dictionary 146 attacks are not possible without breaking into a threshold of servers 147 (such distributed solution requires no change or awareness on the 148 client side relative to a single-server implementation). 150 OPAQUE is defined and proven as the composition of two 151 functionalities: An Oblivious PRF (OPRF) and a key-exchange protocol. 152 It can be seen as a "compiler" for transforming any key-exchange 153 protocol (with KCI security and forward secrecy - see below) into a 154 secure aPAKE protocol. In OPAQUE, the user stores a secret private 155 key at the server during password registration and retrieves this key 156 each time it needs to authenticate to the server. The OPRF security 157 properties ensure that only the correct password can unlock the 158 private key while at the same time avoiding potential offline 159 guessing attacks. This general composability property provides great 160 flexibility and enables a variety of OPAQUE instantiations, from 161 optimized performance to integration with TLS. The latter aspect is 162 of prime importance as the use of OPAQUE with TLS constitutes a major 163 security improvement relative to the standard password-over-TLS 164 practice. At the same time, the combination with TLS builds OPAQUE 165 as a fully functional secure communications protocol and can help 166 provide privacy to account information sent by the user to the server 167 prior to authentication. 169 The KCI property required from KE protocols for use with OPAQUE 170 states that knowledge of a party's private key does not allow an 171 attacker to impersonate others to that party. This is an important 172 security property achieved by most public-key based KE protocols, 173 including protocols that use signatures or public key encryption for 174 authentication. It is also a property of many implicitly 175 authenticated protocols (e.g., HMQV) but not all of them. We also 176 note that key exchange protocols based on shared keys do not satisfy 177 the KCI requirement, hence they are not considered in the OPAQUE 178 setting. We note that KCI is needed to ensure a crucial property of 179 OPAQUE: even upon compromise of the server, the attacker cannot 180 impersonate the user to the server without first running an 181 exhaustive dictionary attack. Another essential requirement from KE 182 protocols for use in OPAQUE is to provide forward secrecy (against 183 active attackers). 185 This draft presents a high-level description of OPAQUE highlighting 186 its components and modular design. A detailed unambiguous 187 specification for standardization will be presented in future 188 revisions of this document, or separately. 190 We describe OPAQUE with a specific instantiation of the OPRF 191 component over elliptic curves and with a few KE schemes, including 192 the HMQV [HMQV] and SIGMA [SIGMA] protocols. We also present several 193 strategies for integrating OPAQUE with TLS 1.3 [RFC8446] offering 194 different tradeoffs between simplicity, performance and user privacy. 195 See also the companion draft [I-D.sullivan-tls-opaque]. In general, 196 the modularity of OPAQUE's design makes it easy to integrate with 197 additional key-exchange protocols, e.g., IKEv2. 199 The computational cost of OPAQUE is determined by the cost of the 200 OPRF, the cost of a regular Diffie-Hellman exchange, and the cost of 201 authenticating such exchange. In our elliptic-curve implementation 202 of the OPRF, the cost for the client is two exponentiations (one or 203 two of which can be fixed base) and one hashing-into-curve operation 204 [I-D.irtf-cfrg-hash-to-curve]; for the server, it is just one 205 exponentiation. The cost of a Diffie-Hellman exchange is as usual 206 two exponentiations per party (one of which is fixed-base). Finally, 207 the cost of authentication per party depends on the specific KE 208 protocol: it is just 1/6 of an exponentiation with HMQV and it is one 209 signature generation and verification in the case of SIGMA and TLS 210 1.3. These instantiations preserve the number of messages in the 211 underlying KE protocol except in one of the TLS instantiations where 212 user privacy may require an additional round trip (this can be saved 213 if using a mechanism similar to the proposed ESNI extension 214 [I-D.ietf-tls-esni]). 216 1.1. Terminology 218 In this document, the key words "MUST", "MUST NOT", "REQUIRED", 219 "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", 220 and "OPTIONAL" are to be interpreted as described in BCP 14, RFC 2119 221 [RFC2119] 223 1.2. Notation 225 Throughout this document the first argument to a keyed function 226 represents the key; separated by a semicolon are the function inputs 227 typically implemented as an unambiguous concatenation of strings 228 (details of encodings are left for a future, more detailed 229 specification). 231 Except if said otherwise, random choices in this specification refer 232 to drawing with uniform distribution from a given set (i.e., "random" 233 is short for "uniformly random"). 235 The name OPAQUE: A homonym of O-PAKE where O is for Oblivious (the 236 name OPAKE was taken). 238 2. DH-OPRF 240 A fundamental piece in the definition of OPAQUE is an Oblivious 241 Pseudo Random Function (OPRF). 243 An Oblivious PRF (OPRF) is an interactive protocol between a server S 244 and a user U defined by a special pseudorandom function (PRF), 245 denoted F. The server's input to the protocol is a key k for PRF F 246 and the user's input is a value x in the domain of F. At the end of 247 the protocol, U learns F(k;x) and nothing else while S learns nothing 248 from the protocol execution (in particular nothing about x or the 249 value F(k;x)). 251 OPAQUE uses a specific OPRF instantiation, called DH-OPRF, where the 252 PRF, denoted F, is defined as follows (a detailed specification 253 appears in [I-D.sullivan-cfrg-voprf] which defines several 254 instantiation suites for DH-OPRF). 256 Parameters: Hash function H (e.g., SHA2 or SHA3 function) with 257 256-bit output at least, a cyclic group G of prime order q, a 258 generator g of G, and hash function H' mapping arbitrary strings into 259 G (where H' is modeled as a random oracle). 261 o DH-OPRF domain: Any string 263 o DH-OPRF range: The range of the hash function H 265 o DH-OPRF key: A random element k in [0..q-1]; denote v=g^k 267 o DH-OPRF Operation: F(k; x) = H(x, v, H'(x)^k) 269 Protocol for computing DH-OPRF, U with input x and S with input k: 271 o U: choose random r in [0..q-1], send alpha=H'(x)*g^r to S 273 o S: upon receiving a value alpha, respond with v=g^k and 274 beta=alpha^k 276 o U: upon receiving values beta and v, set the PRF output to 277 H(x, v, beta*v^{-r}) 279 All received values (alpha, beta, v) are checked to be elements in G 280 other than the identity. A party aborts if the check fails. In the 281 case of Elliptic Curves this test is typically inexpensive - see 282 [I-D.irtf-cfrg-spake2] for ways to deal with this check (including 283 co-factor exponentiation) that apply to DH-OPRF as well. 285 Note (exponential blinding): An alternative way of computing DH-OPRF 286 is for U to send alpha=(H'(x))^r in the first message and set the 287 function output to H(x,v,beta^{1/r}) upon receiving S's response. 288 However, note that the multiplicative blinding above allows for a 289 more efficient implementation as the g^r exponentiation uses a fixed 290 base. Moreover, in cases where the user caches v (e.g., for sites it 291 visits often) then one can also use a fixed-base optimized 292 computation of the exponentiation v^{-r}. In any case, it is up to 293 the user to decide on what form of blinding it uses; the server's 294 response is the same in both cases. 296 Note: For elliptic curve implementations of DH-OPRF, the hashing into 297 the curve operation has been studied extensively with known efficient 298 implementations, see [I-D.irtf-cfrg-hash-to-curve] and references 299 therein. 301 2.1. Hardening OPRF via user iterations 303 Protocol OPAQUE can be further strengthened against offline 304 dictionary attacks by applying to the output of DH-OPRF an iterated 305 hash for some number n of iterations. This increases the cost of an 306 offline attack upon the compromise of the server as the attacker will 307 need to perform n iterations for each guess of PwdU it tries to 308 validate. For this purpose we would re-define DH-OPRF as 309 F(k;x) = I^n( H(x, v, H'(x)^k) ) where I is an appropriately chosen 310 function and the symbol I^n denotes n iterations of function I. More 311 generally, any form of hardened password-based key derivation can be 312 used, e.g., PBKDF2 [RFC8018], Argon 2 [I-D.irtf-cfrg-argon2], scrypt 313 [RFC7914]. As we will see, in OPAQUE it is the user who runs this 314 key derivation. The iteration value n or any other parameter 315 required by these functions can be set as public constants or can be 316 set at time of password registration and later communicated by the 317 server as part of its OPAQUE message. (Note: these hardened KDFs 318 often require a salt value as input; for OPAQUE this value can be be 319 set to a constant, e.g., all zeros.) 321 3. OPAQUE Specification 323 OPAQUE consists of the concurrent run of an OPRF protocol and a key- 324 exchange protocol KE (one that provides mutual authentication based 325 on public keys and satisfies the KCI requirement). We first define 326 OPAQUE in a generic way based on any OPRF and any PK-based KE, and 327 later show specific instantiation using DH-OPRF (defined in 328 Section 2) and several KE protocols. The user takes the role of 329 initiator in these protocols and the server the responder's. The 330 private-public keys for the user are denoted PrivU and PubU, and for 331 the server PrivS and PubS. In Section 3.4 we augment the protocol 332 with user-side hardening to increase resistance to offline attacks in 333 case of server compromise. 335 3.1. Password registration 337 Password registration is run between a user U and a server S. It is 338 assumed that the user can authenticate the server during this 339 registration phase (this is the only part in OPAQUE that requires 340 some form of authenticated channel, either physical, out-of-band, 341 PKI-based, etc.) 343 o U chooses password PwdU and a pair of private-public keys PrivU 344 and PubU for the given protocol KE. 346 o S chooses OPRF key kU (random and independent for each user U) and 347 sets vU = g^kU; it also chooses its own pair of private-public 348 keys PrivS and PubS for use with protocol KE (the server can use 349 the same pair of keys with multiple users), and sends PubS to U. 351 o U and S run OPRF(kU;PwdU) as defined in Section 2 with only U 352 learning the result, denoted RwdU (mnemonics for "Randomized 353 PwdU"). 355 o U generates an "envelope" EnvU defined as 357 EnvU = AuthEnc(RwdU; PrivU, PubU, PubS) 359 where AuthEnc is an authenticated encryption function with the 360 "random-key robustness" property as specified in Section 3.1.1 361 below. In EnvU, all values require authentication and PrivU also 362 requires encryption. However, for simplicity and to hide the EnvU 363 contents, we specify that all values are encrypted (not just 364 authenticated). PubU can be omitted from EnvU if it is not needed 365 for running the key-exchange protocol by the client or if it can 366 be reconstructed from PrivU. 368 o U sends EnvU and PubU to S and erases PwdU, RwdU and all keys. 369 S stores (EnvU, PubS, PrivS, PubU, kU, vU) in a user-specific 370 record. If PrivS and PubS are used for multiple users, S can 371 store these values separately and omit them from the user's 372 record. 374 Note (salt). We note that in OPAQUE the OPRF key acts as the secret 375 salt value that ensures the infeasibility of pre-computation attacks. 376 No extra salt value is needed. 378 Note (password rules). The above procedure has the significant 379 advantage that the user's password is not disclosed to the server 380 even during registration. Some sites require learning the user's 381 password for enforcing password rules. Doing so voids this important 382 security property of OPAQUE and is not recommended. Moving the 383 password check procedure to the client side is a more secure 384 alternative (limited checks at the server are possible to implement, 385 e.g., detecting repeated passwords). 387 3.1.1. Implementing the EnvU envelop 389 The function AuthEnc used to compute EnvU needs to satisfy a property 390 called "random-key robustness". That is, given a pair of random 391 AuthEnc keys, it should be infeasible to create an authenticated 392 ciphertext that successfully decrypts under the two keys. Not all 393 AuthEnc schemes enjoy this property, and this includes the standard 394 GCM mode. We describe a few methods for implementing a key-robust 395 AuthEnc scheme (a default mechanism needs to be chosen when 396 specifying a standard). 398 (1) Encrypt-then-HMAC: Implement the AuthEnc scheme using any 399 encryption function in encrypt-then-pad-then-MAC mode where the MAC 400 is implemented with HMAC with a tag size of at least 256 bits (HMAC 401 ensures robustness through the collision-resistant property of the 402 underlying hash function). This requires two separate keys, one for 403 encryption and one for HMAC, which can be derived from RwdU using, 404 for example, the HKDF-Expand function from [RFC5869]. 406 [Author note: Is there a standardized definition of Encrypt-then-HMAC 407 that one can refer? Two possible sources are RFC 7366 and signal 408 [SIGNAL]. Note that here we just need it for generating EnvU, 409 without the complexities of a full interactive secure-channel 410 implementation.] 412 (2) Fixed-string MAC: Any AuthEnc scheme can be made random-key 413 robust by simply concatenating to it a MAC computed on a fixed 414 string. Specifically, one derives two keys from RwdU: one is a key 415 to the AuthEnc function and the other is a key to a MAC (any secure 416 MAC function works). EnvU is then defined as before except that to 417 the output of AuthEnc one concatenates the output of the MAC function 418 computed with the second derived key on a fixed string (e.g., all 419 zeros). 421 (3) To make GCM key robust one can use any of the two methods above 422 or use the following GCM-specific mechanism. To the plaintext 423 specified by the definition of EnvU, concatenate a string of all 424 zeros so that the last full block of the resultant plaintext is an 425 all-zero block (of the length of the underlying block cipher, i.e., 426 128 for AES). Use regular GCM on this augmented plaintext with a 427 nonce value of zero (a zero nonce is OK since RwdU is a one-time 428 encryption key, namely, no two EnvU encryptions will use the same 429 RwdU, except for negligible probability). 431 Note: With the 128-bit output for the authentication tag in GCM-AES, 432 there is a 2^64 collision attack against the robustness property that 433 seems impractical in the OPAQUE setting but should be considered. 434 The first two methods above don't have this issue. 436 Note (authentication-only EnvU): It is possible to dispense with 437 encryption in the construction of EnvU to obtain a shorter EnvU 438 (resulting in less storage at the server and less communication from 439 server to client). In this case, p_u is derived using a PRF keyed 440 with RwdU. For cases where p_u is not a random string of a given 441 length, e.g., RSA, we define a more general procedure. Namely, 442 what's derived from RwdU is a random seed used as an input to a key 443 generation procedure that generates (p_u, P_U). The resultant scheme 444 is as follows: 446 o Set Km = f(0), seed = f(1), (p_u, P_u) = KeyGen(seed), where f is 447 a regular PRF keyed with RwdU (it can also be implemented with 448 HKDF-Expand). 450 o Set EnvU = (P_s, HMAC_Km(P_s)) where P_s is the server's public 451 key. HMAC_Km denotes HMAC computed with key Km. This MAC needs 452 to have a key-robust property hence it is implemented with HMAC 453 that satisfies this property. 455 Assuming that the server derives per-user kU using a PRF and global 456 key, and that it uses the same pair (p_s,P_s) with all users, the 457 per-user storage for the server consists of P_u and HMAC_Km(P_s), a 458 total of 64-byte overhead with 256-bit curve and hash. Yet, in spite 459 of these storage and communication savings, using encryption for EnvU 460 avoids the need for running the key generation procedure at the 461 client and allows OPAQUE to also serve as a retrieval mechanism for 462 other secrets or credentials. 464 3.2. Online OPAQUE protocol 466 After registration, the user and server can run the OPAQUE protocol 467 as a password-authenticated key exchange. The protocol proceeds as 468 follows: 470 o User transmits user/account information to the server so that the 471 server can retrieve the user's record. 473 o Server sends EnvU and vU to user. 475 o Server and User execute the OPRF protocol as defined in Section 2; 476 User sets RwdU to the result of this computation. 478 o User decrypts EnvU using RwdU to obtain PrivU, PubU, PubS. 480 o User and server run the specified KE protocol using their 481 respective public and private keys. 483 Note that the steps preceding the run of KE can be arranged in just 484 two messages (one from the user and a response from the server). 485 Furthermore, OPAQUE is optimized by running the OPRF and KE 486 concurrently with interleaved and combined messages (while preserving 487 the internal ordering of messages in each protocol). In all cases, 488 the user needs to obtain EnvU, vU and RwdU (i.e., complete the OPRF 489 protocol) before it can use its own private key PrivU and the 490 server's public key PubS in the run of KE. 492 3.3. OPAQUE Instantiations 494 We present several instantiations of OPAQUE using DH-OPRF as the OPRF 495 and different KE protocols. For the sake of concreteness we focus on 496 KE protocols consisting of three messages, denoted KE1, KE2, KE3, and 497 such that KE1 and KE2 include DH values sent by user and server, 498 respectively, and KE3 provides explicit user authentication. (As 499 shown in [OPAQUE], OPAQUE cannot use less than three messages so the 500 3-message instantiations presented here are optimal in terms of 501 number of messages.) 503 Generic OPAQUE with 3-message KE: 505 o C to S: Uid, alpha=H'(PwdU)*g^r, KE1 507 o S to C: beta=alpha^kU, vU, EnvU, KE2 509 o C to S: KE3 511 Key derivation and other details of the protocol are fully specified 512 by the KE scheme. We do note that by the results in [OPAQUE], KE2 513 and KE3 should include authentication of the OPRF messages (or at 514 least of the value alpha). 516 We provide two instantiations of OPAQUE (with HMQV and SIGMA-I) next 517 and discuss integration with TLS in [RFC8446]. 519 3.3.1. Instantiation with HMQV 521 The integration of OPAQUE with HMQV [HMQV] leads to the most 522 efficient instantiation of OPAQUE in terms of exponentiation count. 523 Performance is close to optimal due to the low cost of authentication 524 in HMQV: Just 1/6 of an exponentiation for each party over the cost 525 of a regular DH exchange. The private and public keys of the parties 526 are Diffie-Hellman keys, namely, PubU=g^PrivU and PubS=g^PrivS. The 527 HMQV exchange can be represented schematically as follows: 529 o KE1 = g^x 531 o KE2 = g^y, Mac(Km1; g^x, g^y) 533 o KE3 = Mac(Km2; g^y, g^x) 535 Keys in HMQV, namely, MAC keys Km1, Km2 and session/traffic keys are 536 derived from a common key K computed as follows: 538 C computes K = H((g^y * PubS^e)^{x + d*PrivU)) 540 S computes K = H((g^x * PubU^d)^{y + e*PrivS)) 542 where d = H(g^x, IdS) and e = H(g^y, IdU), and IdU, IdS represent the 543 identities of user and server (typically, a user id and domain name, 544 respectively, and can include the party's public key value). The 545 function H can be the same as used for the DH-OPRF computation. 546 Using multi-exponentiation optimization, the computation of K 547 involves a single multi-exponentiation whose cost is only 17% more 548 than a regular exponentiation. 550 This is a minimal skeleton. A fully-specified protocol will include 551 additional details and a careful key derivation scheme. In 552 particular, the Mac computation will cover the whole preceding 553 transcript. In addition, the parties will check group membership for 554 g^x, g^y or use co-factor computation, e.g., as in 555 [I-D.irtf-cfrg-spake2], and also reject these values if they equal 556 the identity. The check for PubU and PubS can be done only once at 557 user registration. 559 Note (IP disclosure): IBM has a patent that covers HMQV. If there is 560 interest in standardizing this mode one can check if a free license 561 of the HMQV patent could be provided for such use. 563 3.3.2. Instantiation with SIGMA-I 565 We show how OPAQUE can be built around the 3-message SIGMA-I protocol 566 [SIGMA]. This example is significant as it shows integration with a 567 signature-based KE protocol and because TLS 1.3 follows the design of 568 SIGMA-I hence the example helps understanding the proposed 569 integration of OPAQUE with TLS in [RFC8446]. 571 SIGMA-I can be represented schematically as follows: 573 o KE1 = g^x 575 o KE2 = g^y, Sig(PrivS; g^x, g^y), Mac(Km1; IdS) 577 o KE3 = Sig(PrivU; g^y, g^x), Mac(Km2; IdU) 579 In this case, the private keys of user and server are signature keys. 580 Key derivation is based on the DH value g^xy. 582 As before, this is only a skeleton to illustrate the protocol. 583 Full details need to be filled in for a self-contained specification. 584 See also Section 4 for the integration of SIGMA in TLS 1.3. 586 3.4. Hardening OPAQUE via hardened key derivation 588 As noted in Section 2.1 one can increase the resistance of OPAQUE to 589 offline attacks in case of server compromise by applying a password- 590 hardening key derivation function (KDF) on top of the regular DH-OPRF 591 when computing RwdU. Specifically, the user computes the OPRF in 592 interaction with the server and inputs its result into the KDF in 593 lieu of the password on which this function acts. The output of this 594 computation is set as the value RwdU. Parameters to the KDF function 595 can be set to public values or set at the time of password 596 registration and stored at the server. In this case, the server 597 communicates these parameters to the user during OPAQUE executions 598 together with the second OPRF message. We note that the salt value 599 typically input into the KDF can be set to a constant, e.g., all 600 zeros. 602 4. Integrating OPAQUE with TLS 1.3 604 Note: This section is intended as a basis for discussion on ways to 605 integrate OPAQUE with TLS (particularly TLS 1.3). Precise protocol 606 details are left for a future specification. A preliminary draft is 607 [I-D.sullivan-tls-opaque]. 609 As stated in the introduction, the standard password-over-TLS 610 mechanism for password authentication suffers from significant 611 weaknesses due to the essential reliance of the protocol on PKI and 612 the exposure of passwords to the server (and other observers) upon 613 TLS decryption. Here we propose integrating OPAQUE with TLS in order 614 to remove these vulnerabilities while at the same time armoring TLS 615 itself against PKI failures. Such integration also benefits OPAQUE 616 by leveraging the standardized negotiation and record-layer security 617 of TLS. Furthermore, TLS can offer an initial PKI-authenticated 618 channel to protect the privacy of account information such as user 619 name transmitted between client and server. 621 If one is willing to forgo protection of user account information 622 transmitted between user and server, integrating OPAQUE with TLS 1.3 623 is relatively straightforward and follows essentially the same 624 approach as with SIGMA-I in Section 3.3.2. Specifically, one reuses 625 the Diffie-Hellman exchange from TLS and uses the user's private key 626 PrivU retrieved from the server as a signature key for TLS client 627 authentication. The integrated protocol will have as its first 628 message the TLS's Client Hello augmented with user account 629 information and with the DH-OPRF first message (the value alpha). 630 The server's response includes the regular TLS 1.3 second flight 631 augmented with the second OPRF message which includes the values 632 beta, vU and EnvU. For its TLS signature, the server uses the 633 private key PrivS whose corresponding public key PubS is 634 authenticated as part of the user envelope EnvU (there is no need to 635 send a regular TLS certificate in this case). Finally, the third 636 flight consists of the standard client Finish message with client 637 authentication where the client's signature is produced with the 638 user's private key PrivU retrieved from EnvU and verified by the 639 server using public key PubU. 641 The above scheme is depicted in Figure 1 where the sign + indicates 642 fields added by OPAQUE, and DH-OPRF1, DH-OPRF2 denote the two DH-OPRF 643 messages. Other messages in the figure are the same as in TLS 1.3. 644 Notation {...} indicates encryption under handshake keys. Note that 645 ServerSignature and ClientSignature are performed with the private 646 keys defined by OPAQUE and they replace signatures by traditional TLS 647 certificates. 649 Client Server 651 ClientHello 652 key_share 653 + userid + DH-OPRF1 --------> 654 ServerHello 655 key_share 656 {+ DH-OPRF2 + vU + EnvU} 657 {+ ServerSignature} 658 <-------- {ServerFinished} 660 {+ ClientSignature} 661 {ClientFinished} --------> 663 Figure 1: Integration of OPAQUE in TLS 1.3 (no userid 664 confidentiality) 666 Note that in order to send DH-OPRF1 in the first message, the client 667 needs to know the DH group the server uses for OPRF, or it needs to 668 "guess" it. This issue already appears in TLS 1.3 where the client 669 needs to guess the key_share group and it should be handled similarly 670 in OPAQUE (e.g., the client may try one or more groups in its first 671 message). 673 Protection of user's account information can be added through TLS 1.3 674 pre-shared/resumption mechanisms where the account information 675 appended to the ClientHello message would be encrypted under the pre- 676 shared key. 678 When a resumable session or pre-shared key between the client and the 679 server do not exist, user account protection requires a server 680 certificate. One option that does not add round trips is to use a 681 mechanism similar to the proposed ESNI extension [I-D.ietf-tls-esni]. 682 Without such extension, one would run a TLS 1.3 handshake augmented 683 with two first OPAQUE messages interleaved between the second and 684 third flight of the regular TLS handshake. That is, the protocol 685 consists of five flights as follows: (i) A regular 2-flight 1-RTT 686 handshake to produce handshake traffic keys authenticated by the 687 server's TLS certificate; (ii) two messages that include user 688 identification information, the DH-OPRF messages exchanged between 689 client and server, and the retrieved vU and EnvU, all encrypted under 690 the handshake traffic keys (thus providing privacy to user account 691 information); (iii) the TLS 1.3 client authentication flight where 692 client authentication uses the user's private signature key PrivU 693 retrieved from the server in step (ii). 695 Note that server authentication in (i) uses TLS certificates hence 696 user account privacy (but not user authentication) is dependent on 697 PKI. In cases where PKI authentication for the server is deemed 698 acceptable then there is no need for further server authentication. 699 However, if one wants to enforce server authentication without 700 reliance on PKI, then the server needs to authenticate using the 701 private key PrivS whose corresponding public key PubS is sent to the 702 user as part of EnvU. There are two options: If PubS is the same as 703 the public key the server used in the 1-RTT authentication (step (i)) 704 then there is no need for further authentication. In this case, U 705 gets assurance from the authenticated EnvU, not (only) from the PKI 706 certificates. Otherwise, the server needs to send a signature under 707 PrivS that is piggybacked to the second OPAQUE message in (ii). In 708 this case the signature would cover the running transcript hash as is 709 standard in TLS 1.3. The client signature in the last message also 710 covers the transcript hash including the regular handshake and OPAQUE 711 messages. 713 The above scheme is depicted in Figure 2. Please refer to the text 714 before Figure 1 describing notation. Note the asterisk in the 715 ServerSignature message. This indicates that this message is 716 optional as it is used only if the server's key PubS in OPAQUE is 717 different than the one in the server's certificate (transmitted in 718 the second protocol flight). 720 Client Server 722 ClientHello 723 key_share --------> 724 ServerHello 725 key_share 726 {Certificate} 727 {CertificateVerify} 728 <-------- {ServerFinished} 730 {+ userid + DH-OPRF1} --------> 732 {+ DH-OPRF2 + EnvU} 733 {+ DH-OPRF2 + vU + EnvU} 734 <-------- {+ ServerSignature*} 736 {ClientSignature} 737 {ClientFinished} --------> 739 Figure 2: Integration of OPAQUE in TLS 1.3 (with userid 740 confidentiality) 742 We note that the above approaches for integration of OPAQUE with TLS 743 may benefit from the post-handshake client authentication mechanism 744 of TLS 1.3 and the exported authenticators from 746 [I-D.ietf-tls-exported-authenticator]. Also, formatting of messages 747 and negotiation information suggested in [I-D.barnes-tls-pake] can be 748 used in the OPAQUE setting. 750 5. User enumeration 752 User enumeration refers to attacks where the attacker tries to learn 753 whether a given user identity is registered with a server. 754 Preventing such attack requires the server to act with unknown user 755 identities in a way that is indistinguishable from its behavior with 756 existing users. Here we suggest a way to implement such defense, 757 namely, a way for simulating the values beta, vU and EnvU for non- 758 existing users. Note that if the same pair of user identity UId and 759 value alpha is received twice by the server, the response needs to be 760 the same in both cases (since this would be the case for real users). 761 For this, the server S will have two keys MK, MK' for a PRF f (this 762 refers to a regular PRF such as HMAC or CMAC). Upon receiving a pair 763 of user identity UId and value alpha for a non-existing user UId, S 764 computes kU=f(MK; UId) and kU'=f(MK'; UId) and responds with three 765 values beta=alpha^kU, vU=g^kU and EnvU where the latter is computed 766 as the AuthEnc function with key kU' applied to the all-zero string 767 (of the length of a regular EnvU plaintext). Care needs to be taken 768 to avoid side channel leakage (e.g., timing) from helping 769 differentiate these operations from a regular server response. The 770 above requires changes to the server-side implementation but not to 771 the protocol itself or the client side. 773 There is one form of leakage that the above allows and whose 774 prevention would require a change in OPAQUE. Note that an attacker 775 that tests a UId (and same alpha) twice and receives different 776 responses can conclude that either the user registered with the 777 service between these two activations or that the user was registered 778 before but changed its password in between the activations (assuming 779 the server changes kU at the time of a password change). In any 780 case, this indicates that UId is a registered user at the time of the 781 second activation. To conceal this information, S can implement the 782 derivation of kU as kU=f(MK; UId) also for registered users. Hiding 783 changes in EnvU, however, requires a change in the protocol. Instead 784 of sending EnvU as is, S would send an encryption of EnvU under a key 785 that the user derives from the OPRF result (similarly to RwdU) and 786 that S stores during password registration. During login, the user 787 will derive this key from the OPRF result, use it to decrypt EnvU, 788 and continue with the regular protocol. If S uses a randomized 789 encryption, the encrypted EnvU will look each time as a fresh random 790 string, hence S can simulate the encrypted EnvU also for non-existing 791 users. 793 [Author note: How significant is the user enumeration issue? The 794 first case above does not change the protocol so its implementation 795 is a server's decision. The second case, however, requires a change 796 in OPAQUE so it would be important to have feedback on whether this 797 second order attack justifies such change.] 799 6. Security considerations 801 This is an early draft presenting the OPAQUE concept and its 802 potential instantiations. More precise details and security 803 considerations will be provided in future drafts. We note that the 804 security of OPAQUE is formally proved in [OPAQUE] under a strong 805 model of aPAKE security assuming the security of the OPRF function 806 and of the underlying key-exchange protocol. In turn, the security 807 of DH-OPRF is proven in the random oracle model under the One-More 808 Diffie-Hellman assumption [JKKX16]. 810 Best practices regarding implementation of cryptographic schemes 811 apply to OPAQUE. Particular care needs to be given to the 812 implementation of the OPRF regarding testing group membership and 813 avoiding timing and other side channel leakage in the hash-to-curve 814 mapping. Drafts [I-D.irtf-cfrg-hash-to-curve] and 815 [I-D.sullivan-cfrg-voprf] have detailed instantiation and 816 implementation guidance. 818 While one can expect the practical security of the OPRF function 819 (namely, the hardness of computing the function without knowing the 820 key) to be in the order of computing discrete logarithms or solving 821 Diffie-Hellman, Brown and Gallant [BG04] and Cheon [Cheon06] show an 822 attack that slightly improves on generic attacks. For the case that 823 q-1 or q+1, where q is the order of the group G, has a t-bit divisor, 824 they show an attack that calls the OPRF on 2^t chosen inputs and 825 reduces security by t/2 bits, i.e., it can find the OPRF key in time 826 2^{q/2-t/2} and 2^{q/2-t/2} memory. For typical curves, the attack 827 requires an infeasible number of calls and/or results in 828 insignificant security loss [*]. Moreover, in the OPAQUE 829 application, these attacks are completely impractical as the number 830 of calls to the function translates to an equal number of failed 831 authentication attempts by a _single_ user. For example, one would 832 need a billion impersonation attempts to reduce security by 15 bits 833 and a trillion to reduce it by 20 bits - and most curves will not 834 even allow for such attacks in the first place (note that this 835 theoretical loss of security is with respect to computing discrete 836 logarithms, not in reducing the password strength). 838 [*] Some examples (courtesy of Dan Brown): For P-384, 2^90 calls 839 reduce security from 192 to 147 bits; for NIST P-256 the options are 840 6-bit reduction with 2153 OPRF calls, about 14 bit reduction with 187 841 million calls and 20 bits with a trillion calls. For Curve25519, 842 attacks are completely infeasible (require over 2^100 calls) but its 843 twist form allows an attack with 25759 calls that reduces security by 844 7 bits and one with 117223 calls that reduces security by 8.4 bits. 846 Note on user authentication vs. authenticated key exchange. OPAQUE 847 provides PAKE (password-based authenticated key exchange) 848 functionality in the client-server setting. While in the case of 849 user identification, focus is often on the authentication part, we 850 stress that the key exchange element is not less crucial. Indeed, in 851 most cases user authentication is performed to enforce some policy, 852 and the key exchange part is essential for binding this enforcement 853 to the authentication step. Skipping the key exchange part is 854 analogous to carefully checking a visitor's credential at the door 855 and then leaving the door open for others to enter freely. 857 This draft complies with the requirements for PAKE protocols set 858 forth in [RFC8125]. 860 7. Acknowledgments 862 The OPAQUE protocol and its analysis is joint work of the author with 863 Stas Jarecki and Jiayu Xu. This draft has benefited from comments by 864 multiple people. Special thanks to Richard Barnes, Dan Brown, Eric 865 Crockett, Fredrik Kuivinen, Kevin Lewi, Payman Mohassel, Jason Resch, 866 Nick Sullivan. 868 8. References 870 8.1. Normative References 872 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 873 Requirement Levels", BCP 14, RFC 2119, March 1997. 875 8.2. Informative References 877 [Boyen09] Boyen, X., "HPAKE: Password authentication secure against 878 cross-site user impersonation", Cryptology and Network 879 Security (CANS) , 2009. 881 [BG04] Brown, D. and R. Galant, "The static Diffie-Hellman 882 problem", http://eprint.iacr.org/2004/306 , 2004. 884 [Canetti01] 885 Canetti, R., "Universally composable security: A new 886 paradigm for cryptographic protocols", IEEE Symposium on 887 Foundations of Computer Science (FOCS) , 2001. 889 [Cheon06] Cheon, J., "Security analysis of the strong Diffie-Hellman 890 problem", Euroctypt 2006 , 2006. 892 [FK00] Ford, W. and B. Kaliski, Jr, "Server-assisted generation 893 of a strong secret from a password", WETICE , 2000. 895 [GMR06] Gentry, C., MacKenzie, P., and . Z, Ramzan, "A method for 896 making password-based key exchange resilient to server 897 compromise", CRYPTO , 2006. 899 [I-D.ietf-tls-exported-authenticator] 900 Sullivan, N., "Exported Authenticators in TLS", draft- 901 ietf-tls-exported-authenticator-07 (work in progress), 902 June 2018. 904 [I-D.barnes-tls-pake] 905 Barnes, R. and O. Friel, "Usage of SPAKE with TLS 1.3", 906 draft-barnes-tls-pake-02 (work in progress), June 2018. 908 [I-D.irtf-cfrg-argon2] 909 Biryukov, A., Dinu, D., Khovratovich, D., and S. 910 Josefsson, "The memory-hard Argon2 password hash and 911 proof-of-work function", draft-irtf-cfrg-argon2-03 (work 912 in progress), August 2017. 914 [I-D.irtf-cfrg-spake2] 915 Ladd, W. and B. Kaduk, "SPAKE2, a PAKE", draft-irtf-cfrg- 916 spake2-05 (work in progress), February 2018. 918 [I-D.irtf-cfrg-hash-to-curve] 919 Scott, S., Sullivan, N., and C. Wood, "Hashing to Elliptic 920 Curves", draft-irtf-cfrg-hash-to-curve-01 (work in 921 progress), July 2018. 923 [I-D.sullivan-cfrg-voprf] 924 Davidson, A., Sullivan, N., and C. Wood, "Verifiable 925 Oblivious Pseudorandom Functions (VOPRFs) in Prime-Order 926 Groups", draft-sullivan-cfrg-voprf-02 (work in progress), 927 October 2018. 929 [I-D.sullivan-tls-opaque] 930 Sullivan, N., Krawczyk, H., Friel, O., and R. Barnes, 931 "Usage of OPAQUE with TLS 1.3", draft-sullivan-tls- 932 opaque-00 (work in progress), March 2019. 934 [I-D.ietf-tls-esni] 935 Rescorla, E., Oku, K., Sullivan, N., and C. Wood, 936 "Encrypted Server Name Indication for TLS 1.3", draft- 937 ietf-tls-esni-03 (work in progress), March 2019. 939 [OPAQUE] Jarecki, S., Krawczyk, H., and J. Xu, "OPAQUE: An 940 Asymmetric PAKE Protocol Secure Against Pre-Computation 941 Attacks", Eurocrypt , 2018. 943 [JKKX16] Jarecki, S., Kiayias, A., Krawczyk, H., and J. Xu, 944 "Highly-efficient and composable password-protected secret 945 sharing (or: how to protect your bitcoin wallet online)", 946 IEEE European Symposium on Security and Privacy , 2016. 948 [SIGMA] Krawczyk, H., "SIGMA: The SIGn-and-MAc approach to 949 authenticated Diffie-Hellman and its use in the IKE 950 protocols", CRYPTO , 2003. 952 [HMQV] Krawczyk, H., "HMQV: A high-performance secure Diffie- 953 Hellman protocol", CRYPTO , 2005. 955 [VTBPEKE] Pointcheval, D. and G. Wang, "Verifier-based Two-Basis 956 Password Exponential Key Exchange", AsiaCCS , 2017. 958 [SIGNAL] "Signal recommended cryptographic algorithms", 959 https://signal.org/docs/specifications/ 960 doubleratchet/#recommended-cryptographic-algorithms , 961 2016. 963 [RFC2945] Wu, T., "The SRP Authentication and Key Exchange System", 964 RFC 2945, DOI 10.17487/RFC2945, September 2000, 965 . 967 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 968 Key Derivation Function (HKDF)", RFC 5869, DOI 10.17487/ 969 RFC5869, May 2010, . 972 [RFC6628] Shin, S. and K. Kobara, "Efficient Augmented Password-Only 973 Authentication and Key Exchange for IKEv2", RFC 6628, DOI 974 10.17487/RFC6628, June 2012, . 977 [RFC7914] Percival, C. and S. Josefsson, "The scrypt Password-Based 978 Key Derivation Function", RFC 7914, DOI 10.17487/RFC7914, 979 August 2016, . 981 [RFC8018] Moriarty, K., Ed., Kaliski, B., and A. Rusch, "PKCS #5: 982 Password-Based Cryptography Specification Version 2.1", 983 RFC 8018, DOI 10.17487/RFC8018, January 2017, 984 . 986 [RFC8125] Schmidt, J., "Requirements for Password-Authenticated Key 987 Agreement (PAKE) Schemes", RFC 8125, DOI 10.17487/RFC8125, 988 April 2017, . 990 [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol 991 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 992 . 994 Author's Address 996 Hugo Krawczyk 997 Algorand Foundation 999 Email: hugokraw@gmail.com