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