idnits 2.17.1 draft-irtf-cfrg-cpace-02.txt: -(3): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(7): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding 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: ---------------------------------------------------------------------------- == There are 4 instances of lines with non-ascii characters in the document. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 2021) is 1016 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group M. Abdalla 3 Internet-Draft DI, École Normale Supérieure, Paris 4 Intended status: Informational B. Haase 5 Expires: 25 January 2022 Endress + Hauser Liquid Analysis 6 J. Hesse 7 IBM, Zürich Research Laboratory 8 July 2021 10 CPace, a balanced composable PAKE 11 draft-irtf-cfrg-cpace-02 13 Abstract 15 This document describes CPace which is a protocol for two parties 16 that share a low-entropy secret (password) to derive a strong shared 17 key without disclosing the secret to offline dictionary attacks. 18 This method was tailored for constrained devices, is compatible with 19 any group of both prime- and non-prime order, and comes with a 20 security proof providing composability guarantees. 22 Status of This Memo 24 This Internet-Draft is submitted in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF). Note that other groups may also distribute 29 working documents as Internet-Drafts. The list of current Internet- 30 Drafts is at https://datatracker.ietf.org/drafts/current/. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 This Internet-Draft will expire on 2 January 2022. 39 Copyright Notice 41 Copyright (c) 2021 IETF Trust and the persons identified as the 42 document authors. All rights reserved. 44 This document is subject to BCP 78 and the IETF Trust's Legal 45 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 46 license-info) in effect on the date of publication of this document. 47 Please review these documents carefully, as they describe your rights 48 and restrictions with respect to this document. Code Components 49 extracted from this document must include Simplified BSD License text 50 as described in Section 4.e of the Trust Legal Provisions and are 51 provided without warranty as described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 56 2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 3 57 3. Definition CPace . . . . . . . . . . . . . . . . . . . . . . 3 58 3.1. Setup . . . . . . . . . . . . . . . . . . . . . . . . . . 3 59 3.2. Protocol Flow . . . . . . . . . . . . . . . . . . . . . . 7 60 3.3. CPace . . . . . . . . . . . . . . . . . . . . . . . . . . 8 61 4. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 8 62 4.1. CPACE-X25519-ELLIGATOR2_SHA512-SHA512 . . . . . . . . . . 9 63 4.2. CPACE-P256-SSWU_SHA256-SHA256 . . . . . . . . . . . . . . 12 64 5. Security Considerations . . . . . . . . . . . . . . . . . . . 14 65 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 66 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 15 67 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 68 8.1. Normative References . . . . . . . . . . . . . . . . . . 15 69 8.2. Informative References . . . . . . . . . . . . . . . . . 16 70 Appendix A. CPace25519 Test Vectors . . . . . . . . . . . . . . 17 71 A.1. X25519 test vectors . . . . . . . . . . . . . . . . . . . 17 72 A.2. Elligator2 test vectors . . . . . . . . . . . . . . . . . 19 73 A.3. Test vectors for the secret generator G . . . . . . . . . 19 74 A.4. Test vectors for CPace DH . . . . . . . . . . . . . . . . 20 75 A.5. Test vectors for intermediate session key generation . . 21 76 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 78 1. Introduction 80 This document describes CPace which is a protocol for two parties 81 that share a low-entropy secret (password) to derive a to derive a 82 strong shared key without disclosing the secret to offline dictionary 83 attacks. This preliminary working version is a renamed version of 84 the earlier draft-haase-cpace-01 with minor corrections. It has been 85 uploaded for starting the work in the newly formed team of editors 86 (M. Abdalla, B. Haase, J. Hesse) and did not yet see a detailed 87 review by M. Abdalla and J. Hesse. The CPace method was tailored 88 for constrained devices and specifically considers efficiency and 89 hardware side-channel attack mitigations at the protocol level. 90 CPace is designed to be compatible with any group of both prime- and 91 non-prime order and explicitly handles the complexity of cofactor 92 clearing on the protcol level. CPace comes with a security proof 93 providing composability guarantees. As a protocol, CPace is designed 94 to be compatible with so-called "x-coordinate-only" Diffie-Hellman 95 implementations on elliptic curve groups. 97 CPace is designed to be suitable as both, a building block within a 98 larger protocol construction using CPace as substep, and as a 99 standalone protocol. 101 It is considered, that for composed larger protocol constructions, 102 the CPace subprotocol might be best executed in a separate 103 cryptographic hardware, such as secure element chipsets. The CPace 104 protocol design aims at considering the resulting constraints. 106 2. Requirements Notation 108 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 109 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 110 "OPTIONAL" in this document are to be interpreted as described in BCP 111 14 [RFC2119] [RFC8174] when, and only when, they appear in all 112 capitals, as shown here. 114 3. Definition CPace 116 3.1. Setup 118 Let C be a group in which there exists a subgroup of prime order p 119 where the strong computational simultaneous Diffie-Hellman (sSDH) and 120 the strong Diffie-Hellman problem (sCDH) problem [VTBPEKE] is hard. 121 C has order p*c where p is a large prime; c will be called the 122 cofactor. Let I be the unit element in C, e.g., the point at 123 infinity in if C is an elliptic curve group. We denote the 124 operations in the group using addition and multiplication operators, 125 e.g. P + (P + P) = P + 2 * P = 3 * P. We refer to a sequence of n 126 additions of an element in P as scalar multiplication by n and use 127 the notation scalar_multiply(P,n). 129 With F we denote a field that may be associated with C, e.g. the 130 prime base field used for representing the coordinates of points on 131 an elliptic curve. 133 We assume that for any element P in C there is a representation 134 modulo negation, encode_group_element_mod_neg(P) as a byte string 135 such that for any Q in C with Q != P and Q != -P, 136 encode_group_element_mod_neg(P) != encode_group_element_mod_neg(Q). 137 It is recommended that encodings of the elements P and -P share the 138 same result string. Common choices would be a fixed (per-group) 139 length encoding of the x-coordinate of points on an elliptic curve C 140 or its twist C' in Weierstrass form, e.g. according to [IEEE1363] in 141 case of short Weierstrass form curves. For curves in Montgomery form 142 correspondingly the u-coordinate would be encoded, as specified, 143 e.g., by the encodeUCoordinate function from [RFC7748]. 145 With J we denote the group modulo negation associated to C. Note 146 that in J the scalar multiplication operation scalar_multiply is well 147 defined since scalar_multiply(P,s) == -scalar_multiply(-P,s) while 148 arbitrary additions of group elements are no longer available. 150 With J' be denote a second group modulo negation that might share the 151 byte-string encoding function encode_group_element_mod_neg with J 152 such for a given byte string either an element in J or J' is encoded. 153 If the x-coordinate of an elliptic curve point group is used for the 154 encoding, J' would commonly be corresponding to the group of points 155 on the elliptic curve's quadratic twist. Correspondingly, with p' we 156 denote the largest prime factor of the order of J' and its cofactor 157 with c'. 159 Let scalar_cofactor_clearing(s) be a cofactor clearing function 160 taking an integer input argument and returning an integer as result. 161 For any s, scalar_cofactor_clearing(s) is REQUIRED to be of the form 162 c * s1. I.e. it MUST return a multiple of the cofactor. An example 163 of such a function may be the cofactor clearing and clamping 164 functions decodeScalar25519 and decodeScalar448 as used in the X25519 165 and X448 protocols definitions of [RFC7748]. In case of prime-order 166 groups with c == 1, it is RECOMMENDED to use the identity function 167 with scalar_cofactor_clearing(s) = s. 169 Let scalar_mult_cc(P,s) be a joint "scalar multiplication and 170 cofactor clearing" function of an integer s and an string-encoded 171 value P, where P could represent an element either on J or J'. If P 172 is an element in J or J', the scalar_mult_cc function returns a 173 string encoding of an element in J or J' respectively, such that the 174 result of scalar_mult_cc(P,s) encodes (scalar_cofactor_clearing(s) * 175 P). 177 Let scalar_mult_ccv(P,s) be a "scalar multiplication cofactor 178 clearing and verify" function of an integer s and an encoding of a 179 group element P. Unlike scalar_mult_cc, scalar_mult_ccv additionally 180 carries out a verification that checks that the computational 181 simultaneous Diffie-Hellman problem (SDH) is hard in the subgroup (in 182 J or J') generated by the encoded element SP = scalar_mult_cc(P,s). 183 In case that the verification fails (SP might be of low order or on 184 the wrong curve), scalar_mult_ccv is REQUIRED to return the encoding 185 of the identity element I. Otherwise scalar_mult_ccv(P,S) is 186 REQUIRED to return the result of scalar_mult_cc(P,s). A common 187 choice for scalar_mult_ccv for Montgomery curves with twist security 188 would be the X25519 and X448 Diffie-Hellman functions as specified in 189 [RFC7748]. For curves in short Weierstrass form, scalar_mult_ccv 190 could be implemented by the combination of a point verification of 191 the input point with a scalar multiplication. Here scalar_mult_ccv 192 SHALL return the encoding of the neutral element I if the input point 193 P was not on the curve C. 195 Let P=map_to_group_mod_neg(r) be a mapping operation that maps a 196 string r to an encoding of an element P in J. Common choices would 197 be the combination of map_to_base and map_to_curve methods as defined 198 in the hash2curve draft [HASH2CURVE]. Note that we don't require and 199 RECOMMEND cofactor clearing here since this complexity is already 200 included in the definition of the scalar multiplication operation 201 calar_mult_cc above. Additionally requiring cofactor clearing also 202 in map_to_group_mod_neg() would result in efficiency loss. 204 || denotes concatenation of strings. We also let len(S) denote the 205 length of a string in bytes. Finally, let nil represent an empty 206 string, i.e., len(nil) = 0. 208 Let H(m) be a hash function from arbitrary strings m to bit strings 209 of a fixed length. Common choices for H are SHA256 or SHA512 210 [RFC6234]. H is assumed to segment messages m into blocks m_i of 211 byte length H_block. E.g. the blocks used in SHA512 have a size of 212 128 bytes. 214 Let strip_sign_information(P) be function that takes a string 215 encoding of an element P in J and strips any information regarding 216 the sign of P, such that strip_sign_information(P) = 217 strip_sign_information(-P). For short Weierstrass (Montgomery) 218 curves this function will return a string encoding the x-coordinate 219 (u-coordinate). The purpose of defining this function is for 220 allowing for x-coordinate only scalar multiplication algorithms. The 221 sign is to be stripped before generating the intermediate session key 222 ISK. 224 With ISK we denote the intermediate session key output string 225 provided by CPace that is generated by a hash operation on the 226 Diffie-Hellman result. It is RECOMMENDED to apply ISK to a KDF 227 function prior to using the key in a higher-level protocol. 229 KDF(Q) is a key-derivation function that takes an string and derives 230 key of length L. A common choice for a KDF would be HMAC-SHA512. 232 With DSI we denote domain-separation identifier strings that may be 233 prepended to the inputs of Hash and KDF functions. 235 Let A and B be two parties. A and B may also have digital 236 representations of the parties' identities such as Media Access 237 Control addresses or other names (hostnames, usernames, etc). We 238 denote the parties' representation and the parties themselves both by 239 using the identifiers A and B. 241 With prepend_len(byte_sequence) we denote the byte sequence that is 242 obtained from prepending the length of the byte sequence as an utf-8 243 to the byte sequence itself. (This will prepend one single byte for 244 sequences shorter than 128 bytes and more bytes otherwise) 246 With CI we denote an OPTIONAL string containing information on the 247 communication channel. If knowledge on the identies is known before 248 protocol start for both parties, CI is RECOMMENDED to be formed by 249 the concatenation of the identifiers A and B and an an OPTIONAL 250 associated data string, each with prepended length. AD includes 251 information which A and B might want to authenticate in the protocol 252 execution. CI = prepend_len(A) || prepend_len(B) || prepend_len(AD); 253 One other possibility for CI data might be an encoding of the 254 concatenation of MAC-addresses of both communication partners. AD 255 might include a list of supported protocol versions if CPace were 256 used in a higher-level protocol which negotiates use of a particular 257 version. Including this list would ensure that both parties agree 258 upon the same set of supported protocols and therefore prevent 259 downgrade attacks. 261 We also assume that A and B share a common encoding of a password 262 related string PRS. Typically PRS is derived from a low-entropy 263 secret such as a user-supplied password (pw) or a personal 264 identification by PRS = prepend_len(pw) Note that CPace is NOT 265 RECOMMENDED to be used in conjunction with user datbases that include 266 more than one user account. CPace does not provide mechanisms for 267 agreeing on user names, deriving salt values and agreeing on workload 268 parameters, as required by the memory hard iterated hash functions 269 that should be used for such databases. In such settings it is 270 RECOMMENDED to use CPace as a subcomponent of the higher-level 271 AuCPace protocol. 273 Let sid be a session id byte string chosen for each protocol session 274 before protocol execution; The length len(sid) SHOULD be larger or 275 equal to 16 bytes. 277 With ZPAD we denote a zero-padding string that is appended to PRS 278 such that DSI||PRS has a length of at least H_block. CPace aims at 279 mixing in entropy of PRS into the full internal state of the hash 280 function before any adversary-known variable information (ADVI) 281 enters the hashing algorithm. ADVI such as party identities or 282 session IDs might be partially controlled by an adversary. 283 Correlations of ADVI with the bare PRS string are considered to be 284 easier exploitable by side-channel methods in comparison to a pre- 285 hashed representation of PRS. 287 3.2. Protocol Flow 289 CPace is a one round protocol to establish an intermediate shared 290 secret ISK with implicit mutual authentication. Prior to invocation, 291 A and B are provisioned with public (CI) and secret information (PRS) 292 as prerequisite for running the protocol. During the first round, A 293 sends a public share Ya to B, and B responds with its own public 294 share Yb. Both A and B then derive a shared secret ISK. ISK is 295 meant to be used for producing encryption and authentication keys by 296 a KDF function outside of the scope of CPace. Prior to entering the 297 protocol, A and B agree on a sid string. sid is typically pre- 298 established by a higher-level protocol invocing CPace. If no such 299 sid is available from a higher-level protocol, a suitable approach is 300 to let A choose a fresh random sid string and send it to B together 301 with Ya. This method is shown in the setup protocol section below. 303 This sample trace is shown below. 305 A B 306 | (setup protocol | 307 (sample sid) | and sid) | 308 |----------------->| 309 --------------------------------------- 310 | | 311 (compute Ya) | Ya | 312 |----------------->| 313 | Yb | (compute Yb) 314 |<-----------------| 315 | (verify data) | 316 | (derive ISK) | 318 3.3. CPace 320 Both parties start with agreed values on the sid string, the channel 321 identifier CI and the password-related string PRS. 323 The channel identifier, CI, SHOULD include an encoding of the 324 communication channel used by both parties A and B, such as, e.g., IP 325 and port numbers of both parties. 327 To begin, A calculates a generator G = map_to_group_mod_neg(DSI1 || 328 PRS || ZPAD || sid || CI). 330 A picks ya randomly and uniformly according to the requirement of the 331 group J and calculates Ya=scalar_mult_cc (G,ya). A then transmits Ya 332 to B. 334 B picks yb randomly and uniformly. B then calculates G = 335 map_to_group_mod_neg(DSI1 || PRS || ZPAD || sid || CI) and Yb = 336 scalar_mult_cc(G,yb). B then calculates K = scalar_mult_ccv(Ya,yb). 337 B MUST abort if K is the encoding of the neutral element I. 338 Otherwise B sends Yb to A and proceeds as follows. B strips the sign 339 information from K, Ya and Yb to obtain the strings Ks, Yas and Ybs 340 by using the strip_sign_information() function. B returns ISK = 341 H(DSI2 || sid || Ks || Yas || Ybs). 343 Upon reception of Yb, A calculates K = scalar_mult_ccv(Yb,ya). A 344 MUST abort if K is the neutral element I. If K is different from I, 345 A strips the sign information from K, Ya and Yb and returns ISK = 346 H(DSI2 || sid || Ks || Yas || Ybs). 348 K and Ks are shared values, though they MUST NOT be used as a shared 349 secret key. Note that calculation of ISK from Ks includes the 350 protocol transcript and prevents key malleability with respect to 351 man-in-the-middle attacks from active adversaries. 353 Upon completion of this protocol, the session key ISK returned by A 354 and B will be identical by both parties if and only if the supplied 355 input parameters sid, PRS and CI match on both sides and the 356 information on the public elements in J were not modified by an 357 adversary. 359 4. Ciphersuites 361 This section documents CPACE ciphersuite configurations. A 362 ciphersuite is REQUIRED to specify all of, 364 * a group modulo negation J with an associated 365 encode_group_element_mod_neg function 367 * scalar_mult_cc(P,s) and scalar_mult_ccv(P,s) functions operating 368 on encodings of elements P in J 370 * a mapping function map_to_group_mod_neg(r) converting byte strings 371 r into elements in J 373 * a strip_sign_information(Q) function operating on string 374 representations of elements Q 376 * a hash function H 378 * and domain separation strings DSI1, DSI2 380 Currently, detailed specifications are available for CPACE- 381 X25519-ELLIGATOR2_SHA512-SHA512 and CPACE-P256-SSWU_SHA256-SHA256. 382 These cipher suites are specifically designed for suitability also 383 with constrained hardware. It is recommended that cipher suites for 384 short Weierstrass curves are specified in line with the corresponding 385 definitions for NIST-P256. Cipher suites for modern Montgomery or 386 Edwards curves are recommended to be specified in line with the 387 definitions for Curve25519. 389 +============+==========================+==================+ 390 | J | map_to_group_mod_neg | KDF | 391 +============+==========================+==================+ 392 | X25519 | ELLIGATOR2_SHA512 | SHA512 [RFC6234] | 393 +------------+--------------------------+------------------+ 394 | NIST P-256 | SSWU_SHA256 [HASH2CURVE] | SHA256 [RFC6234] | 395 +------------+--------------------------+------------------+ 397 Table 1: CPace Ciphersuites 399 4.1. CPACE-X25519-ELLIGATOR2_SHA512-SHA512 401 This cipher suite targets particularly constrained targets and 402 implements specific optimizations. It uses the group of points on 403 the Montgomery curve Curve25519 for constructing J. The base field F 404 is the prime field built upon the prime 2^255 - 19. The Diffie- 405 Hellmann protocol X25519 and the group are specified in [RFC7748]. 406 The encode_group_element_mod_neg(P) is implemented by the 407 encodeUCoordinate(P) function defined in [RFC7748]. The neutral 408 element I is encoded as a 32 byte zero-filled string. 410 The domain separation strings are defined as DSI1 = "CPace25519-1", 411 DSI2 = "CPace25519-2" (twelve-byte ASCII encoding without ANSI-C 412 style trailing zeros). 414 Both, scalar_mult_cc and scalar_mult_ccv, are implemented by the 415 X25519 function specified in [RFC7748]. 417 The secret scalars ya and yb used for X25519 shall be sampled as 418 uniformly distributed 32 byte strings. 420 The map_to_group_mod_neg function is implemented as follows. First 421 the byte length of the ZPAD zero-padding string is determined such 422 that len(ZPAD) = max(0, H_block_SHA512 - len(DSI1 || PRS)), with 423 H_block_SHA512 = 128 bytes. Then a byte string u is calculated by 424 use of u = SHA512(DSI1||PRS||ZPAD||sid||CI). The resulting string is 425 interpreted as 512-bit integer in little-endian format according to 426 the definition of decodeLittleEndian() from [RFC7748]. The resulting 427 integer is then reduced to the base field as input to the Elligator2 428 map specified in [HASH2CURVE] to yield the secret generator G = 429 Elligator2(u). 431 CPace25519 returns a session key ISK of 64 bytes length by a single 432 invocation of SHA512(DSI2||sid||K||Ya||Yb). Since the encoding does 433 not incorporate the sign from the very beginning Qs = 434 strip_sign_information(Q) == Q for this cipher suite. 436 The following sage code could be used as reference implementation for 437 the mapping and key derivation functions. 439 440 def littleEndianStringToInteger(k): 441 bytes = [ord(b) for b in k] 442 return sum((bytes[i] << (8 * i)) for i in range(len(bytes))) 444 def map_to_group_mod_neg_CPace25519(sid, PRS, CI): 445 m = hashlib.sha512() 446 p = 2^255 - 19 448 H_block_SHA512 = 128 449 DSI1 = b"CPace25519-1" 450 ZPAD_len = max(0,H_block_SHA512 - len(CI) - len(PRS)) 451 ZPAD = ZPAD_len * "\0" 453 m.update(DSI1) 454 m.update(PRS) 455 m.update(ZPAD) 456 m.update(sid) 457 m.update(CI) 458 u = littleEndianStringToInteger(m.digest()) 459 return map_to_curve_elligator2_curve25519(u % p) 461 def generate_ISK_CPace25519(sid,K,Ya,Yb): 462 m = hashlib.sha512(b"CPace25519-2") 463 m.update(sid) 464 m.update(K) 465 m.update(Ya) 466 m.update(Yb) 467 return m.digest() 468 470 The definitions above aim at making the protocol suitable for 471 outsourcing CPace to secure elements (SE) where nested hash function 472 constructions such as defined in [RFC5869] have to be considered to 473 be particularly costly. As a result, the task of generating session 474 keys by a strong KDF function is left out of the scope of the CPace 475 protocol. This fact is expressed by the naming of the intermediate 476 shared Key ISK. The definitions above regarding the mapping deviate 477 from the definition in the encode_to_curve function from [HASH2CURVE] 478 by significantly reducing the amount of hash invocations. Moreover, 479 the CPace protocol specification, unlike the hash-to-curve draft 480 specification also considers the risk of side-channel leakage during 481 the hashing of PRS by introducing the ZPAD padding. Mitigating 482 attacks of an adversary that analyzes correlations between publicly 483 known information with the low-entropy PRS strings was considered 484 relevant in important settings. We also avoid the overhead of 485 redundant cofactor clearing, by making the Diffie-Hellman protocol 486 responsible for this task (and not the mapping algorithm). Due to 487 its use in Ed25519 [RFC8032], SHA512 is considered to be the natural 488 hash choice for Curve25519. The 512 bit output of SHA512 moreover 489 allows for removing any statistical bias stemming from the non- 490 canonical base field representations, such that the overhead of the 491 HKDF_extract/HKDF_expand sequences from [HASH2CURVE] are considered 492 not necessary (in line with the assessments regarding Curve25519 in 493 [HASH2CURVE]). 495 4.2. CPACE-P256-SSWU_SHA256-SHA256 497 This cipher suite targets applications that do not as agressively 498 focus on efficiency, bandwidth and code size as the Curve25519 499 implementation. Instead it aims at reusing existing encoding and 500 curve standards wherever possible. 502 It uses the group of points on the NIST P-256 curve which is defined 503 in short Weierstrass form for constructing J [RFC5480]. The base 504 field F is the prime field built upon the Solinas prime p = 505 2^256-2^224+2^192+2^96-1. Encoding of full group elements requires 506 both, x and y coordinates. In order to facilitate point validation 507 and in order to be in line with recent TLS 1.3 requirements, 508 implementations MUST encode both, x and y coordinates. It is 509 RECOMMENDED to use the uncompressed format from [SEC1] using the 0x04 510 octet prefix. The strip_sign_information() function returns the 511 substring from the SEC1 representation encoding the x-coordinate of 512 the curve point. 514 NIST P-256 is of prime order and does not require cofactor clearing. 515 The scalar_cofactor_clearing function is the identity function with 516 scalar_cofactor_clearing(s) == s 518 The domain separation strings are defined as DSI1 = "CPace-P256-1", 519 DSI2 = "CPace-P256-2". 521 For the scalar_mult_cc function operating on the internally generated 522 points, a conventional scalar multiplication on P-256 is used, i.e. 523 without the need of further verification checks. The scalar_mult_ccv 524 function that operates on remotely generated points includes the 525 mandatory verification as follows. First from the encoded point the 526 x and y coordinates are decoded. These points are used for verifying 527 the curve equation. If the point is not on the curve, 528 scalar_mult_ccv returns the neutral element I. If the point is on 529 the curve, scalar_mult_ccv calls scalar_mult_cc and returns the 530 result of the scalar multiplication. 532 For P-256, the map_to_group_mod_neg function is implemented as 533 follows. The zero-padding string length is calculated as len(ZPAD) = 534 max(0, H_block_SHA256 - len(DSI1 || PRS)) with H_block_SHA256 = 64. 536 For the mapping to the curve, a 32 byte string U1 = SHA256(DSI1 || 537 PRS || ZPAD || sid || CI) is calculated. From U1 a second 32 byte 538 value is calculated as U2 = SHA256(U1). The concatenation of U1 and 539 U2 is interpreted as a 512 bit integer u by use of the u = 540 OS2IP(U1 || U2) function from [HASH2CURVE]. This value is reduced to 541 a 32 byte representation of a field element fu = u % p. The 542 coordinates (x,y) in F of the secret generator G are calculated as 543 (x,y) = map_to_curve_simple_swu_3mod4(fu) function from [HASH2CURVE]. 545 As hash function H SHA256 is chosen, returning a session key ISK of 546 32 bytes length with ISK=SHA256(DSI2 || sid || Ks || Yas || Ybs). 548 The following sage code could be used as reference implementation for 549 the mapping and key derivation functions. 551 552 def map_to_group_mod_neg_CPace_P256(sid, PRS, CI): 553 m = hashlib.sha256() 555 H_block_SHA256 = 64 556 DSI1 = b"CPace-P256-1" 557 ZPAD_len = max(0,H_block_SHA256 - len(CI) - len(PRS)) 558 ZPAD = ZPAD_len * "\0" 560 m.update(DSI1) 561 m.update(PRS) 562 m.update(ZPAD) 563 m.update(sid) 564 m.update(CI) 565 U1 = m.digest() 566 U2 = hashlib.sha256(U1).digest() 567 u = OS2I(U1 + U2) 568 return map_to_curve_simple_swu_3mod4(u) 570 def generate_ISK_CPace_P256(sid,K,Ya,Yb): 571 m = hashlib.sha256(b"CPace-P256-2") 572 m.update(sid) 573 m.update(strip_sign_information(K)) 574 m.update(strip_sign_information(Ya)) 575 m.update(strip_sign_information(Yb)) 576 return m.digest() 577 579 Similarly to the Curve25519 implementation, the definitions above aim 580 at making the protocol suitable for outsourcing to secure elements 581 where hash function invocations have to be considered to be 582 particularly costly. As a result, the task of generating session 583 keys by a strong KDF function is left out of the scope of the CPace 584 protocol. The naming of ISK as intermediate shared key reflects this 585 fact. Also the method for calculating the generator has been 586 optimized for reducing the number of hash calculations in comparison 587 to the suggestions [HASH2CURVE]. 589 5. Security Considerations 591 A security proof of CPace is found in [cpace_paper]. 593 Elements received from a peer MUST be checked by a proper 594 implementation of the scalar_mult_ccv method. Failure to properly 595 validate group elements can lead to attacks. The Curve25519-based 596 cipher suite employs the twist security feature of the curve for 597 point validation. As such, it is mandatory to check that all low- 598 order points on both the curve and the twist are mapped on the 599 neutral element by the X25519 function. Corresponding test vectors 600 are provided in the appendix. 602 The choices of random numbers MUST be uniform. Randomly generated 603 values (e.g., ya and yb) MUST NOT be reused. 605 CPace is NOT RECOMMENDED to be used in conjunction with applications 606 supporting different username/password pairs. In this case it is 607 RECOMMENDED to use CPace as building block of the augmented AuCPace 608 protocol [aucpace_paper]. 610 If CPace is used as a building block of higher-level protocols, it is 611 RECOMMENDED that sid is generated by the higher-level protocol and 612 passed to CPace. It is RECOMMENDED sid, is generated by sampling 613 ephemeral random strings. 615 Since CPace is designed to be used as a building block in higher- 616 level protocols and for compatibility with constrained hardware, it 617 does not by itself include a strong KDF construction. CPace uses a 618 simple hash operation for generating its intermediate key ISK. It is 619 RECOMMENDED that the ISK is post-processed by a KDF according the 620 needs of the higher-level protocol. In case that the CPace protocol 621 is delegated to a secure element hardware, it is RECOMMENDED that the 622 main processing unit applies a KDF to the externally generated ISK. 624 In case that side-channel attacks are to be considered practical for 625 a given application, it is RECOMMENDED to focus side-channel 626 protections such as masking and redundant execution (faults) on the 627 process of calculating the secret generator G. The most critical 628 aspect to consider is the processing of the first block of the hash 629 that includes the PRS string. The CPace protocol construction 630 considers the fact that side-channel protections of hash functions 631 might be particularly resource hungry. For this reason, CPace aims 632 at minimizing the number of hash functions invocations in the 633 specified mapping method. 635 CPace is proven secure under the hardness of the computational 636 Simultaneous Diffie-Hellmann (SDH) assumption in the group J (as 637 defined in [VTBPEKE]). Still, even for the event that large-scale 638 quantum computers (LSQC) will become available, CPace forces an 639 active adversary to solve one CDH per password guess. Using the 640 wording suggested by Steve Thomas on the CFRG mailing list, CPace is 641 "quantum-annoying". 643 6. IANA Considerations 645 No IANA action is required. 647 7. Acknowledgments 649 Thanks to the members of the CFRG for comments and advice. Any 650 comment and advice is appreciated. 652 Comments are specifically invited regarding the following aspect. 653 The CPace mapping function design is based on the following 654 assessments. 1.) Masked, hardware-side-channel-protected hash 655 function implementations should be considered highly desirable for 656 the calculation of the generators G if an implementation might be 657 exposed to physical attacks. 2.) The complexity of such protected 658 hash implementations (possibly with lots of boolean-arithmetic 659 masking conversions) was assessed critical for constrained hardware. 660 Hash operation complexity was also assessed to be critical for secure 661 element chipsets that often were assessed to run hash operations in 662 software without hardware accellerator support. 664 This assessment is not in line with the assumptions for the hash-to- 665 curve-05 draft. As a consequence, this draft aimed at more 666 aggressively reducing the number of nested hash function invocations 667 in comparison to the suggestions of the hash-to-curve-05 draft. 669 8. References 671 8.1. Normative References 673 [SEC1] SEC, "STANDARDS FOR EFFICIENT CRYPTOGRAPHY, "SEC 1: 674 Elliptic Curve Cryptography", version 2.0", May 2009, 675 . 677 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 678 Requirement Levels", BCP 14, RFC 2119, 679 DOI 10.17487/RFC2119, March 1997, 680 . 682 [RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, 683 "Elliptic Curve Cryptography Subject Public Key 684 Information", RFC 5480, DOI 10.17487/RFC5480, March 2009, 685 . 687 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 688 Key Derivation Function (HKDF)", RFC 5869, 689 DOI 10.17487/RFC5869, May 2010, 690 . 692 [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms 693 (SHA and SHA-based HMAC and HKDF)", RFC 6234, 694 DOI 10.17487/RFC6234, May 2011, 695 . 697 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 698 for Security", RFC 7748, DOI 10.17487/RFC7748, January 699 2016, . 701 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 702 Signature Algorithm (EdDSA)", RFC 8032, 703 DOI 10.17487/RFC8032, January 2017, 704 . 706 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 707 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 708 May 2017, . 710 [HASH2CURVE] 711 Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R., and 712 C. Wood, "draft-irtf-cfrg-hash-to-curve-05", 2019. IRTF 713 draft standard 715 [IEEE1363] IEEE, ""Standard Specifications for Public Key 716 Cryptography", IEEE 1363", 2000. IEEE 1363 718 8.2. Informative References 720 [cpace_paper] 721 Abdalla, M., Haase, B., and J. Hesse, "Security analysis 722 of CPace.", January 2021. eprint.iacr.org/2021/114 724 [aucpace_paper] 725 Haase, B. and B. Labrique, "AuCPace. PAKE protocol 726 tailored for the use in the internet of things.", February 727 2018. eprint.iacr.org/2018/286 729 [VTBPEKE] Pointcheval, D. and G. Wang, "VTBPEKE: Verifier-based Two- 730 Basis Password ExponentialKey Exchange", 2017. 731 Proceedings of the 2017 {ACM} on Asia Conference on 732 Computer and Communications Security, AsiaCCS 2017 734 Appendix A. CPace25519 Test Vectors 736 The test vectors for CPace25519 consist of three blocks. 738 First test vectors for X25519 are provided which is used as combined 739 scalar multiplication, cofactor clearing and verification function. 740 Specifically, test vectors for the small order points are provided 741 for checking that all small order points are mapped to the neutral 742 element 744 Then test vectors for the Elligator2 primitive are provided. 746 Then test vectors for the encoding of the secret generator are 747 provided combining the hash operation and the encoding of the 748 generator. 750 Finally test vectors for a honest party protocol execution are 751 provided, including derivation of the session key ISK. 753 A.1. X25519 test vectors 755 ########################### /X25519 ############################### 756 Test vectors for X25519 include three values: 757 - The scalar encoding prior to co-factor clearing and clamping, s 758 - The little-endian byte string encoding of the input point, u 759 - The expected little-endian byte string encoding of the result, r 761 The test vectors below shall be applied to the X25519 function 762 called with the outputs of the decode-u-coordinate function 763 (that is expected to clear the most significant bit. 765 Test vector for X25519 with a coordinate on J: 766 s: a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4 767 u: e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c 768 r: c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552 770 Test vector for X25519 with a coordinate on the twist J': 771 s: 4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d 772 u: e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a413 773 r: 95cbde9476e8907d7aade45cb4b873f88b595a68799fa152e6f8f7647aac7957 775 Out in the wild there might be two variants of X25519 which 776 differ by clearing or not clearing bit #255 of inputs. 778 Test vectors for plain X25519 that MUST return the neutral element 779 for X25519 implementations that don't clear bit #255 of inputs. 780 u0: 0000000000000000000000000000000000000000000000000000000000000000 781 u1: 0100000000000000000000000000000000000000000000000000000000000000 782 u2: e0eb7a7c3b41b8ae1656e3faf19fc46ada098deb9c32b1fd866205165f49b800 783 u3: 5f9c95bca3508c24b1d0b1559c83ef5b04445cc4581c8e86d8224eddd09f1157 784 u4: ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f 785 u5: edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f 786 u6: eeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f 787 u7: cdeb7a7c3b41b8ae1656e3faf19fc46ada098deb9c32b1fd866205165f49b880 788 u8: 4c9c95bca3508c24b1d0b1559c83ef5b04445cc4581c8e86d8224eddd09f11d7 789 u9: d9ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff 790 ua: daffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff 791 ub: dbffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff 793 Results for X25519 implementations *not* clearing bit #255: 794 s = af46e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449aff 795 rN = X25519(uX, s); 796 r0: 0000000000000000000000000000000000000000000000000000000000000000 797 r1: 0000000000000000000000000000000000000000000000000000000000000000 798 r2: 0000000000000000000000000000000000000000000000000000000000000000 799 r3: 0000000000000000000000000000000000000000000000000000000000000000 800 r4: 0000000000000000000000000000000000000000000000000000000000000000 801 r5: 0000000000000000000000000000000000000000000000000000000000000000 802 r6: 0000000000000000000000000000000000000000000000000000000000000000 803 r7: 0000000000000000000000000000000000000000000000000000000000000000 804 r8: 0000000000000000000000000000000000000000000000000000000000000000 805 r9: 0000000000000000000000000000000000000000000000000000000000000000 806 ra: 0000000000000000000000000000000000000000000000000000000000000000 807 rb: 0000000000000000000000000000000000000000000000000000000000000000 809 Results for X25519 implementations that *do* clear bit #255: 810 s = af46e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449aff 811 qN = X25519(uX & ((1 << 255) - 1),s); 812 q0: 0000000000000000000000000000000000000000000000000000000000000000 813 q1: 0000000000000000000000000000000000000000000000000000000000000000 814 q2: 0000000000000000000000000000000000000000000000000000000000000000 815 q3: 0000000000000000000000000000000000000000000000000000000000000000 816 q4: 0000000000000000000000000000000000000000000000000000000000000000 817 q5: 0000000000000000000000000000000000000000000000000000000000000000 818 q6: 0000000000000000000000000000000000000000000000000000000000000000 819 q7: e062dcd5376d58297be2618c7498f55baa07d7e03184e8aada20bca28888bf7a 820 q8: 993c6ad11c4c29da9a56f7691fd0ff8d732e49de6250b6c2e80003ff4629a175 821 q9: db64dafa9b8fdd136914e61461935fe92aa372cb056314e1231bc4ec12417456 822 qa: d8e2c776bbacd510d09fd9278b7edcd25fc5ae9adfba3b6e040e8d3b71b21806 823 qb: c85c655ebe8be44ba9c0ffde69f2fe10194458d137f09bbff725ce58803cdb38 825 ########################### X25519/ ############################### 827 A.2. Elligator2 test vectors 829 Two test vectors are provided 831 #################### /Elligator 2 ################################## 833 Vector set 1 as little endian byte strings: 834 in: bc149a46d293b0aeea34581349d72f8a5a96cd531102d67379cd9bfadd4ec800 835 out:66b68f7575cd282403fc2bd323ff04601203c1ec5516ce247f7c0adbef05d367 837 Vector set 1 as base 10 numbers: 838 in: 35391373371110637358764021258915994089392966 839 2186061014226937583985831318716 840 out: 46961069109971370193035504450677895166687682 841 601074157241352710439876254742118 843 #################################################################### 845 Vector set 2 as little endian byte strings: 846 in: 89cf55d4b5d3f84b1634957ac503a32b84ba11471a96b227bca70a0c3bf26375 847 out:1db163c86ceca7621903c9412d6dc71b4ed263b687eed092b194b5e540bba308 849 Vector set 2 as base 10 numbers: 851 in: 530971929581761349677698694411105058011053992421528586742712709 852 85522606362505 853 out: 390779123641965710057372702362153599533842156764537839663973068 854 2305857171741 856 #################### Elligator 2/ ################################## 858 A.3. Test vectors for the secret generator G 859 ###################### /Secret generator G ######################### 860 Inputs: 861 DSI1 = 'CPace25519-1' 862 sid = SHA512('sid'), bytes 0 to 15 864 Input strings without prepended length: 865 pw = 'password' 866 A = 'Ainitiator' 867 B = 'Bresponder' 868 AD = 'AD' 869 #################################################################### 870 Outputs and intermediate results: 872 DSI11= 435061636532353531392d31 string (b'CPace25519-1') of len(12) 873 PRS = 0870617373776f7264 (b'\x08password') string of len(9) 874 ZPAD = 107 zero bytes (before mixing in adversary controlled var. data) 875 sid = 7e4b4791d6a8ef019b936c79fb7f2c57 string of len(16) 876 CI = 0a41696e69746961746f720a42726573706f6e646572024144 877 (b'\nAinitiator\nBresponder\x02AD') string of len(25) 879 u = SHA512(DSI1||PRS||ZPAD||sid||CI) as 512 bit little-endian int: 880 0xc2d3f2db868b7cde013b1b7d3b27c9cdf6845ec2eaf18ec6bffcf70f40e73349 881 << 256 882 + 0x491041def788da930a86b7dbfedbe016200c259d2d2a980dfde2238a3ea0a6c8 883 u as reduced base field element coordinate: 884 0x34864e74f03d6387394ccc72c6c3d4a8b7b2368c0d05c98e7d6ecfcde0f247ec 885 Elligator2 output G as base field element coordinate: 886 0xf0fdadcc2e334ceb73832be22e736a2a296dd46438f0541c1447dfbaf85ce1d 888 ###################### Secret generator G/ ######################### 890 A.4. Test vectors for CPace DH 891 ##################### /CPace Diffie-Hellman ######################## 892 Inputs: 894 Elligator2 output G as base field element coordinate: 895 0x307760941be97d7c68b037cb9d22d69838b60e194c50ded8b85873f9e1395126 896 Elligator2 output G encoded as little endian byte string: 897 265139e1f97358b8d8de504c190eb63898d6229dcb37b0687c7de91b94607730 899 Secret scalar ya=SHA512('ya'), bytes 0...31, as integer: 900 0xbfec93334144994275a3eba9eb0adf3fe40d54e400d105d59724bee398b722d1 901 ya encoded as little endian byte string: 902 d122b798e3be2497d505d100e4540de43fdf0aeba9eba375429944413393ecbf 904 Secret scalar yb=SHA512('yb'), bytes 0...31, as integer: 905 0xb16a6ff3fcaf874cb59058493cb1f28b3e20084ad6d46fcd3c053284d60cecc0 906 yb encoded as little endian byte string: 907 c0ec0cd68432053ccd6fd4d64a08203e8bf2b13c495890b54c87affcf36f6ab1 909 #################################################################### 910 Outputs: 912 Public point Ya as integer: 913 0x79f9f2c1245fd8c4ab38bc75082f2daf6f47ca53fd5f0de7af72fee9c7ddd993 914 Ya encoded as little endian byte string: 915 93d9ddc7e9fe72afe70d5ffd53ca476faf2d2f0875bc38abc4d85f24c1f2f979 917 Public point Yb as integer: 918 0x18ac9063b4419695db48028d2eda7b2b2e649d22f56a5987eba9f05941de1c74 919 Yb encoded as little endian byte string: 920 741cde4159f0a9eb87596af5229d642e2b7bda2e8d0248db959641b46390ac18 922 DH point K as integer: 923 0x276896a227a09f389a04b9656099aa05ef8ec2b394cf32cc50cca9ae56334215 924 K encoded as little endian byte string: 925 15423356aea9cc50cc32cf94b3c28eef05aa996065b9049a389fa027a2966827 927 ##################### CPace Diffie-Hellman/ ######################## 929 A.5. Test vectors for intermediate session key generation 930 #################### /Session Key derivation ####################### 931 Inputs: 933 DSI2 = 435061636532353531392d32 string ('CPace25519-2') of len(12) 934 sid = 7e4b4791d6a8ef019b936c79fb7f2c57 string of len(16) 936 strings of length 32: 937 K = 15423356aea9cc50cc32cf94b3c28eef05aa996065b9049a389fa027a2966827 938 Ya= 93d9ddc7e9fe72afe70d5ffd53ca476faf2d2f0875bc38abc4d85f24c1f2f979 939 Yb= 741cde4159f0a9eb87596af5229d642e2b7bda2e8d0248db959641b46390ac18 941 #################################################################### 943 string of length 64: 944 ISK = SHA512(DSI2 || sid || K || Ya || Yb) 945 = de0be1eeb7e6453d8c961353cd333694866f5432f24b0d4ed393cb6473e835df 946 265ce72613effa3368a907031d897c733d300dfdb364ff66d270b404cdfbcb0a 948 #################### Session Key derivation/ ####################### 950 Authors' Addresses 952 Michel Abdalla 953 DI, École Normale Supérieure, Paris 955 Email: michel.abdalla@ens.fr 957 Bjoern Haase 958 Endress + Hauser Liquid Analysis 960 Email: bjoern.m.haase@web.de 962 Julia Hesse 963 IBM, Zürich Research Laboratory 965 Email: JHS@zurich.ibm.com