idnits 2.17.1 draft-bar-cfrg-spake2plus-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. 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 (6 July 2021) is 1018 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: '-1' is mentioned on line 590, but not defined -- Looks like a reference, but probably isn't: '0' on line 592 == Outdated reference: A later version (-26) exists of draft-irtf-cfrg-spake2-20 Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group T. Taubert 3 Internet-Draft Apple Inc. 4 Intended status: Informational C.A. Wood 5 Expires: 7 January 2022 6 July 2021 7 SPAKE2+, an Augmented PAKE 8 draft-bar-cfrg-spake2plus-03 10 Abstract 12 This document describes SPAKE2+, a Password Authenticated Key 13 Exchange (PAKE) protocol run between two parties for deriving a 14 strong shared key with no risk of disclosing the password. SPAKE2+ 15 is an augmented PAKE protocol, as only one party has knowledge of the 16 password. This method is simple to implement, compatible with any 17 prime order group and is computationally efficient. 19 Discussion Venues 21 This note is to be removed before publishing as an RFC. 23 Source for this draft and an issue tracker can be found at 24 https://github.com/chris-wood/draft-bar-cfrg-spake2plus 25 (https://github.com/chris-wood/draft-bar-cfrg-spake2plus). 27 Status of This Memo 29 This Internet-Draft is submitted in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF). Note that other groups may also distribute 34 working documents as Internet-Drafts. The list of current Internet- 35 Drafts is at https://datatracker.ietf.org/drafts/current/. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 This Internet-Draft will expire on 7 January 2022. 44 Copyright Notice 46 Copyright (c) 2021 IETF Trust and the persons identified as the 47 document authors. All rights reserved. 49 This document is subject to BCP 78 and the IETF Trust's Legal 50 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 51 license-info) in effect on the date of publication of this document. 52 Please review these documents carefully, as they describe your rights 53 and restrictions with respect to this document. Code Components 54 extracted from this document must include Simplified BSD License text 55 as described in Section 4.e of the Trust Legal Provisions and are 56 provided without warranty as described in the Simplified BSD License. 58 Table of Contents 60 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 61 2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 3 62 3. Definition of SPAKE2+ . . . . . . . . . . . . . . . . . . . . 3 63 3.1. Offline Initialization . . . . . . . . . . . . . . . . . 3 64 3.2. Protocol Flow . . . . . . . . . . . . . . . . . . . . . . 4 65 3.3. SPAKE2+ . . . . . . . . . . . . . . . . . . . . . . . . . 5 66 4. Key Schedule and Key Confirmation . . . . . . . . . . . . . . 7 67 5. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 8 68 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 69 7. Security Considerations . . . . . . . . . . . . . . . . . . . 10 70 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11 71 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 72 9.1. Normative References . . . . . . . . . . . . . . . . . . 11 73 9.2. Informative References . . . . . . . . . . . . . . . . . 12 74 Appendix A. Algorithm used for Point Generation . . . . . . . . 12 75 Appendix B. Test Vectors . . . . . . . . . . . . . . . . . . . . 14 76 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 18 78 1. Introduction 80 This document describes SPAKE2+, a Password Authenticated Key 81 Exchange (PAKE) protocol run between two parties for deriving a 82 strong shared key with no risk of disclosing the password. SPAKE2+ 83 is an augmented PAKE protocol, as only one party makes direct use of 84 the password during the execution of the protocol. The other party 85 only needs a verification value at the time of the protocol execution 86 instead of the password. The verification value can be computed 87 once, during an offline initialization phase. The party using the 88 password directly would typically be a client, and acts as a prover, 89 while the other party would be a server, and acts as verifier. 91 The protocol is augmented in the sense that it provides some 92 resilience to the compromise or extraction of the verification value. 93 The design of the protocol forces the adversary to recover the 94 password from the verification value to successfully execute the 95 protocol. Hence this protocol can be advantageously combined with a 96 salted Password Hashing Function to increase the cost of the recovery 97 and slow down attacks. The verification value cannot be used 98 directly to successfully run the protocol as a prover, making this 99 protocol more robust than balanced PAKEs which don't benefit from 100 Password Hashing Functions to the same extent. 102 This augmented property is especially valuable in scenarios where the 103 execution of the protocol is constrained and the adversary can not 104 query the salt of the password hash function ahead of the attack. 105 Constraints may consist in being in physical proximity through a 106 local network or when initiation of the protocol requires a first 107 authentication factor. 109 This password-based key exchange protocol appears in [TDH] and is 110 proven secure in [UCAnalysis]. It is compatible with any prime-order 111 group and relies only on group operations, making it simple and 112 computationally efficient. Predetermined parameters for a selection 113 of commonly used groups are also provided. 115 This document has content split out from a related document 116 specifying SPAKE2 [I-D.irtf-cfrg-spake2]. 118 2. Requirements Notation 120 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 121 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 122 document are to be interpreted as described in [RFC2119]. 124 3. Definition of SPAKE2+ 126 3.1. Offline Initialization 128 Let G be a group in which the computational Diffie-Hellman (CDH) 129 problem is hard. Suppose G has order p*h where p is a large prime; h 130 will be called the cofactor. Let I be the unit element in G, e.g., 131 the point at infinity if G is an elliptic curve group. We denote the 132 operations in the group additively. We assume there is a 133 representation of elements of G as byte strings: common choices would 134 be SEC1 uncompressed or compressed [SEC1] for elliptic curve groups 135 or big endian integers of a fixed (per-group) length for prime field 136 DH. We fix two elements M and N in the prime-order subgroup of G as 137 defined in the table in this document for common groups, as well as a 138 generator P of the (large) prime-order subgroup of G. P is specified 139 in the document defining the group, and so we do not repeat it here. 141 || denotes concatenation of strings. We also let len(S) denote the 142 length of a string in bytes, represented as an eight-byte little- 143 endian number. Finally, let nil represent an empty string, i.e., 144 len(nil) = 0. 146 KDF is a key-derivation function that takes as input a salt, 147 intermediate keying material (IKM), info string, and derived key 148 length L to derive a cryptographic key of length L. MAC is a Message 149 Authentication Code algorithm that takes a secret key and message as 150 input to produce an output. Let Hash be a hash function from 151 arbitrary strings to bit strings of a fixed length. Common choices 152 for Hash are SHA256 or SHA512 [RFC6234]. Let PBKDF be a Password- 153 Based Key Derivation Function designed to slow down brute-force 154 attackers. Brute-force resistance may be obtained through various 155 computation hardness parameters such as memory or CPU cycles, and are 156 typically configurable. Scrypt [RFC7914] and Argon2 are common 157 examples of PBKDF functions. PBKDF and hardness parameter selection 158 are out of scope of this document. Section 5 specifies variants of 159 KDF, MAC, and Hash suitable for use with the protocols contained 160 herein. 162 Let A and B be two parties. A and B may also have digital 163 representations of the parties' identities such as Media Access 164 Control addresses or other names (hostnames, usernames, etc). A and 165 B may share additional data (the context) separate from their 166 identities which they may want to include in the protocol transcript. 167 One example of additional data is a list of supported protocol 168 versions if SPAKE2+ were used in a higher-level protocol which 169 negotiates the use of a particular PAKE. Another example is the 170 inclusion of PBKDF parameters and the application name. Including 171 those would ensure that both parties agree upon the same set of 172 supported protocols and use the same PBKDF parameters and therefore 173 prevent downgrade and cross-protocol attacks. Specification of 174 precise context values is out of scope for this document. 176 3.2. Protocol Flow 178 SPAKE2+ is a two round protocol that establishes a shared secret with 179 an additional round for key confirmation. Prior to invocation, A and 180 B are provisioned with information such as the input password needed 181 to run the protocol. A preamble exchange may occur in order to 182 communicate identities, protocol version and PBKDF parameters related 183 to the verification value. Details of the preamble phase are out of 184 scope of this document. During the first round, A, the prover, sends 185 a public share pA to B, the verifier, and B responds with its own 186 public share pB. Both A and B then derive a shared secret used to 187 produce encryption and authentication keys. The latter are used 188 during the second round for key confirmation. (Section 4 details the 189 key derivation and confirmation steps.) In particular, B sends a key 190 confirmation message cB to A, and A responds with its own key 191 confirmation message cA. (Note that pB and cB MAY be sent in the 192 same message.) Both parties MUST NOT consider the protocol complete 193 prior to receipt and validation of these key confirmation messages. 195 A sample trace is shown below. 197 A B 199 | (Preamble) | 200 |<- - - - - - - - - - - - ->| 201 | | 202 | (setup protocol) | 203 (compute pA) | pA | 204 |-------------------------->| 205 | pB | (compute pB) 206 |<--------------------------| 207 | | 208 | (derive secrets) | (compute cB) 209 | cB | 210 |<--------------------------| 211 (compute cA) | cA | 212 |-------------------------->| 214 3.3. SPAKE2+ 216 Let w0 and w1 be two integers derived by hashing the password pw with 217 the identities of the two participants, A and B. Specifically, 218 compute: 220 w0s || w1s = PBKDF(len(pw) || pw || len(A) || A || len(B) || B) 221 w0 = w0s mod p 222 w1 = w1s mod p 224 If both identities A and B are absent, i.e. len(A) = len(B) = 0, then 225 the length prefixes are omitted as in Section 3.1. 227 w0s || w1s = PBKDF(pw) 229 If one or both identities A and B are unknown at the time of deriving 230 w0 and w1, w0s and w1s are computed as if the unknown identities were 231 absent. They however SHOULD be included in the transcript TT if the 232 parties exchange those prior to or as part of the protocol flow. 234 The party B stores the verification value pair L and w0. 236 L = w1*P 237 Note that standards such as NIST.SP.800-56Ar3 suggest taking mod p of 238 a hash value that is 64 bits longer than that needed to represent p 239 to remove statistical bias introduced by the modulation. Protocols 240 using this specification must define the method used to compute w0 241 and w1: it may be necessary to carry out various forms of 242 normalization of the password before hashing [RFC8265]. The hashing 243 algorithm SHOULD be a PBKDF so as to slow down brute-force attackers. 245 When executing SPAKE2+, A selects x uniformly at random from the 246 integers in [0, p), computes the public share pA=X, and transmits it 247 to B. 249 x <- [0, p) 250 X = x*P + w0*M 252 Upon receipt of X, B computes h*X and aborts if the result is equal 253 to I to ensure that X is in the large prime-order subgroup of G. B 254 then selects y uniformly at random from the integers in [0, p), 255 computes the public share pB=Y and transmits it to A. Upon receipt 256 of Y, A computes h*Y and aborts if the result is equal to I. 258 y <- [0, p) 259 Y = y*P + w0*N 261 Parties A and B compute Z and V that are now shared as common values. 262 Party A computes: 264 Z = h*x*(Y - w0*N) 265 V = h*w1*(Y - w0*N) 267 Party B computes: 269 Z = h*y*(X - w0*M) 270 V = h*y*L 272 All proofs of security hold even if the discrete log of the fixed 273 group element N is known to the adversary. In particular, one MAY 274 set N=I, i.e. set N to the unit element in G. 276 It is essential that both Z and V be used in combination with the 277 transcript to derive the keying material. The protocol transcript 278 encoding is shown below. 280 TT = len(Context) || Context || 281 || len(A) || A || len(B) || B 282 || len(M) || M || len(N) || N 283 || len(X) || X || len(Y) || Y 284 || len(Z) || Z || len(V) || V 285 || len(w0) || w0 287 Context is an application-specific customization string shared 288 between both parties and MUST precede the remaining transcript. It 289 might contain the name and version number of the higher-level 290 protocol, or simply the name and version number of the application. 291 The context MAY include additional data such as the chosen 292 ciphersuite and PBKDF parameters like the iteration count or salt. 293 The context and its length prefix MAY be omitted. 295 If an identity is absent, its length is given as zero and the 296 identity itself the empty octet string. If both A and B are absent, 297 then both lengths are zero and both A and B will be empty octet 298 strings. In applications where identities are not implicit, A and B 299 SHOULD always be non-empty. Otherwise, the protocol risks Unknown 300 Key Share attacks (discussion of Unknown Key Share attacks in a 301 specific protocol is given in [I-D.ietf-mmusic-sdp-uks]). 303 Upon completion of this protocol, A and B compute shared secrets Ka, 304 Ke, KcA, and KcB as specified in Section 4. B MUST send A a key 305 confirmation message cB so both parties can confirm that they agree 306 upon these shared secrets. After receipt and verification of B's 307 confirmation message, A MUST send B a confirmation message. B MUST 308 NOT send application data to A until it has received and verified the 309 confirmation message. Key confirmation verification requires 310 recomputation of cA or cB and checking for equality against that 311 which was received. 313 4. Key Schedule and Key Confirmation 315 The protocol transcript TT, as defined in Section 3.3, is unique and 316 secret to A and B. Both parties use TT to derive shared symmetric 317 secrets Ke and Ka. The length of each key is equal to half of the 318 digest output, e.g., |Ke| = |Ka| = 128 bits for SHA-256. 320 Ka || Ke = Hash(TT) 321 KcA || KcB = KDF(nil, Ka, "ConfirmationKeys") 323 A and B output Ke as the shared secret from the protocol. Ka and its 324 derived KcA and KcB are not used for anything except key confirmation 325 and MUST be discarded after the protocol execution. 327 Both endpoints MUST either exchange cA=KcA and cB=KcB directly, or 328 employ a secure PRF, acting as a MAC that produces pseudorandom tags, 329 for key confirmation. In the latter case, KcA and KcB are symmetric 330 keys used to compute tags cA and cB over data shared between the 331 participants. That data could for example be an encoding of the key 332 shares exchanged earlier, or simply a fixed string. 334 cA = MAC(KcA, ...) 335 cB = MAC(KcB, ...) 337 Once key confirmation is complete, applications MAY use Ke as an 338 authenticated shared secret as needed. For example, applications MAY 339 derive one or more AEAD keys and nonces from Ke for subsequent 340 application data encryption. 342 5. Ciphersuites 344 This section documents SPAKE2+ ciphersuite configurations. A 345 ciphersuite indicates a group, cryptographic hash algorithm, and pair 346 of KDF and MAC functions, e.g., SPAKE2+-P256-SHA256-HKDF-HMAC. This 347 ciphersuite indicates a SPAKE2+ protocol instance over P-256 that 348 uses SHA256 along with HKDF [RFC5869] and HMAC [RFC2104] for G, Hash, 349 KDF, and MAC functions, respectively. 351 If no MAC algorithm is used in the key confirmation phase, its 352 respective column in the table below can be ignored and the 353 ciphersuite name will contain no MAC identifier. 355 +==============+==================+================+================+ 356 | G | Hash | KDF | MAC | 357 +==============+==================+================+================+ 358 | P-256 | SHA256 [RFC6234] | HKDF [RFC5869] | HMAC | 359 | | | | [RFC2104] | 360 +--------------+------------------+----------------+----------------+ 361 | P-256 | SHA512 [RFC6234] | HKDF [RFC5869] | HMAC | 362 | | | | [RFC2104] | 363 +--------------+------------------+----------------+----------------+ 364 | P-384 | SHA256 [RFC6234] | HKDF [RFC5869] | HMAC | 365 | | | | [RFC2104] | 366 +--------------+------------------+----------------+----------------+ 367 | P-384 | SHA512 [RFC6234] | HKDF [RFC5869] | HMAC | 368 | | | | [RFC2104] | 369 +--------------+------------------+----------------+----------------+ 370 | P-521 | SHA512 [RFC6234] | HKDF [RFC5869] | HMAC | 371 | | | | [RFC2104] | 372 +--------------+------------------+----------------+----------------+ 373 | edwards25519 | SHA256 [RFC6234] | HKDF [RFC5869] | HMAC | 374 | | | | [RFC2104] | 375 +--------------+------------------+----------------+----------------+ 376 | edwards448 | SHA512 [RFC6234] | HKDF [RFC5869] | HMAC | 377 | | | | [RFC2104] | 378 +--------------+------------------+----------------+----------------+ 379 | P-256 | SHA256 [RFC6234] | HKDF [RFC5869] | CMAC-AES-128 | 380 | | | | [RFC4493] | 381 +--------------+------------------+----------------+----------------+ 382 | P-256 | SHA512 [RFC6234] | HKDF [RFC5869] | CMAC-AES-128 | 383 | | | | [RFC4493] | 384 +--------------+------------------+----------------+----------------+ 386 Table 1 388 The following points represent permissible point generation seeds for 389 the groups listed in the Table above, using the algorithm presented 390 in Appendix A. These bytestrings are compressed points as in [SEC1] 391 for curves from [SEC1]. 393 For P256: ~~~ M = 394 02886e2f97ace46e55ba9dd7242579f2993b64e16ef3dcab95afd497333d8fa12f 395 seed: 1.2.840.10045.3.1.7 point generation seed (M) 397 N = 398 03d8bbd6c639c62937b04d997f38c3770719c629d7014d49a24b4f98baa1292b49 399 seed: 1.2.840.10045.3.1.7 point generation seed (N) ~~~ 400 For P384: ~~~ M = 401 030ff0895ae5ebf6187080a82d82b42e2765e3b2f8749c7e05eba366434b363d3dc 402 36f15314739074d2eb8613fceec2853 seed: 1.3.132.0.34 point generation 403 seed (M) 405 N = 406 02c72cf2e390853a1c1c4ad816a62fd15824f56078918f43f922ca21518f9c543bb 407 252c5490214cf9aa3f0baab4b665c10 seed: 1.3.132.0.34 point generation 408 seed (N) ~~~ 410 For P521: ~~~ M = 411 02003f06f38131b2ba2600791e82488e8d20ab889af753a41806c5db18d37d85608 412 cfae06b82e4a72cd744c719193562a653ea1f119eef9356907edc9b56979962d7aa 413 seed: 1.3.132.0.35 point generation seed (M) 415 N = 416 0200c7924b9ec017f3094562894336a53c50167ba8c5963876880542bc669e494b25 417 32d76c5b53dfb349fdf69154b9e0048c58a42e8ed04cef052a3bc349d95575cd25 418 seed: 1.3.132.0.35 point generation seed (N) ~~~ 420 For edwards25519: ~~~ M = 421 d048032c6ea0b6d697ddc2e86bda85a33adac920f1bf18e1b0c6d166a5cecdaf 422 seed: edwards25519 point generation seed (M) 424 N = d3bfb518f44f3430f29d0c92af503865a1ed3281dc69b35dd868ba85f886c4ab 425 seed: edwards25519 point generation seed (N) ~~~ 427 For edwards448: ~~~ M = 428 b6221038a775ecd007a4e4dde39fd76ae91d3cf0cc92be8f0c2fa6d6b66f9a12 429 942f5a92646109152292464f3e63d354701c7848d9fc3b8880 seed: edwards448 430 point generation seed (M) 432 N = 6034c65b66e4cd7a49b0edec3e3c9ccc4588afd8cf324e29f0a84a072531c4db 433 f97ff9af195ed714a689251f08f8e06e2d1f24a0ffc0146600 seed: edwards448 434 point generation seed (N) ~~~ 436 6. IANA Considerations 438 No IANA action is required. 440 7. Security Considerations 442 SPAKE2+ appears in [TDH] and is proven secure in [UCAnalysis]. 444 Beyond the cofactor multiplication checks to ensure that elements 445 received from a peer are in the prime order subgroup of G, they also 446 MUST be checked for group membership as failure to properly validate 447 group elements can lead to attacks. 449 The choices of random numbers MUST BE uniform. Randomly generated 450 values (e.g., x and y) MUST NOT be reused; such reuse may permit 451 dictionary attacks on the password. 453 8. Acknowledgements 455 Thanks to Ben Kaduk and Watson Ladd, from which this specification 456 originally emanated. 458 9. References 460 9.1. Normative References 462 [I-D.irtf-cfrg-spake2] 463 Ladd, W. and B. Kaduk, "SPAKE2, a PAKE", Work in Progress, 464 Internet-Draft, draft-irtf-cfrg-spake2-20, 2 June 2021, 465 . 468 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 469 Hashing for Message Authentication", RFC 2104, 470 DOI 10.17487/RFC2104, February 1997, 471 . 473 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 474 Requirement Levels", BCP 14, RFC 2119, 475 DOI 10.17487/RFC2119, March 1997, 476 . 478 [RFC4493] Song, JH., Poovendran, R., Lee, J., and T. Iwata, "The 479 AES-CMAC Algorithm", RFC 4493, DOI 10.17487/RFC4493, June 480 2006, . 482 [RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, 483 "Elliptic Curve Cryptography Subject Public Key 484 Information", RFC 5480, DOI 10.17487/RFC5480, March 2009, 485 . 487 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 488 Key Derivation Function (HKDF)", RFC 5869, 489 DOI 10.17487/RFC5869, May 2010, 490 . 492 [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms 493 (SHA and SHA-based HMAC and HKDF)", RFC 6234, 494 DOI 10.17487/RFC6234, May 2011, 495 . 497 [RFC7914] Percival, C. and S. Josefsson, "The scrypt Password-Based 498 Key Derivation Function", RFC 7914, DOI 10.17487/RFC7914, 499 August 2016, . 501 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 502 Signature Algorithm (EdDSA)", RFC 8032, 503 DOI 10.17487/RFC8032, January 2017, 504 . 506 [RFC8265] Saint-Andre, P. and A. Melnikov, "Preparation, 507 Enforcement, and Comparison of Internationalized Strings 508 Representing Usernames and Passwords", RFC 8265, 509 DOI 10.17487/RFC8265, October 2017, 510 . 512 [SEC1] "Elliptic Curve Cryptography, Standards for Efficient 513 Cryptography Group, ver. 2", 2009, 514 . 516 [TDH] "The Twin-Diffie Hellman Problem and Applications", 517 EUROCRYPT 2008, Volume 4965 of Lecture notes in Computer 518 Science, pages 127-145, Springer-Verlag, Berlin, Germany , 519 2008. 521 [UCAnalysis] 522 "Security analysis of SPAKE2+", 2020, 523 . 525 9.2. Informative References 527 [I-D.ietf-mmusic-sdp-uks] 528 Thomson, M. and E. Rescorla, "Unknown Key-Share Attacks on 529 Uses of TLS with the Session Description Protocol (SDP)", 530 Work in Progress, Internet-Draft, draft-ietf-mmusic-sdp- 531 uks-07, 9 August 2019, . 534 Appendix A. Algorithm used for Point Generation 536 This section describes the algorithm that was used to generate the 537 points (M) and (N) in the table in Section 5. 539 For each curve in the table below, we construct a string using the 540 curve OID from [RFC5480] (as an ASCII string) or its name, combined 541 with the needed constant, for instance "1.3.132.0.35 point generation 542 seed (M)" for P-512. This string is turned into a series of blocks 543 by hashing with SHA256, and hashing that output again to generate the 544 next 32 bytes, and so on. This pattern is repeated for each group 545 and value, with the string modified appropriately. 547 A byte string of length equal to that of an encoded group element is 548 constructed by concatenating as many blocks as are required, starting 549 from the first block, and truncating to the desired length. The byte 550 string is then formatted as required for the group. In the case of 551 Weierstrass curves, we take the desired length as the length for 552 representing a compressed point (section 2.3.4 of [SEC1]), and use 553 the low-order bit of the first byte as the sign bit. In order to 554 obtain the correct format, the value of the first byte is set to 0x02 555 or 0x03 (clearing the first six bits and setting the seventh bit), 556 leaving the sign bit as it was in the byte string constructed by 557 concatenating hash blocks. For the [RFC8032] curves a different 558 procedure is used. For edwards448 the 57-byte input has the least- 559 significant 7 bits of the last byte set to zero, and for edwards25519 560 the 32-byte input is not modified. For both the [RFC8032] curves the 561 (modified) input is then interpreted as the representation of the 562 group element. If this interpretation yields a valid group element 563 with the correct order (p), the (modified) byte string is the output. 564 Otherwise, the initial hash block is discarded and a new byte string 565 constructed from the remaining hash blocks. The procedure of 566 constructing a byte string of the appropriate length, formatting it 567 as required for the curve, and checking if it is a valid point of the 568 correct order, is repeated until a valid element is found. 570 The following python snippet generates the above points, assuming an 571 elliptic curve implementation following the interface of 572 Edwards25519Point.stdbase() and Edwards448Point.stdbase() in 573 Appendix A of [RFC8032]: 575 def iterated_hash(seed, n): 576 h = seed 577 for i in range(n): 578 h = hashlib.sha256(h).digest() 579 return h 581 def bighash(seed, start, sz): 582 n = -(-sz // 32) 583 hashes = [iterated_hash(seed, i) for i in range(start, start + n)] 584 return b''.join(hashes)[:sz] 586 def canon_pointstr(ecname, s): 587 if ecname == 'edwards25519': 588 return s 589 elif ecname == 'edwards448': 590 return s[:-1] + bytes([s[-1] & 0x80]) 591 else: 592 return bytes([(s[0] & 1) | 2]) + s[1:] 594 def gen_point(seed, ecname, ec): 595 for i in range(1, 1000): 596 hval = bighash(seed, i, len(ec.encode())) 597 pointstr = canon_pointstr(ecname, hval) 598 try: 599 p = ec.decode(pointstr) 600 if p != ec.zero_elem() and p * p.l() == ec.zero_elem(): 601 return pointstr, i 602 except Exception: 603 pass 605 Appendix B. Test Vectors 607 This section contains test vectors for SPAKE2+ using the P256-SHA256- 608 HKDF-HMAC and P256-SHA256-HKDF-CMAC ciphersuites. (Choice of PBKDF 609 is omitted and values for w and w0,w1 are provided directly.) All 610 points are encoded using the uncompressed format, i.e., with a 0x04 611 octet prefix, specified in [SEC1] A and B identity strings are 612 provided in the protocol invocation. 614 [Context=b'SPAKE2+-P256-SHA256-HKDF draft-01'] 615 [A=b'client'] 616 [B=b'server'] 617 w0 = 0xe6887cf9bdfb7579c69bf47928a84514b5e355ac034863f7ffaf4390e67d7 618 98c 619 w1 = 0x24b5ae4abda868ec9336ffc3b78ee31c5755bef1759227ef5372ca139b94e 620 512 621 L = 0x0495645cfb74df6e58f9748bb83a86620bab7c82e107f57d6870da8cbcb2ff 622 9f7063a14b6402c62f99afcb9706a4d1a143273259fe76f1c605a3639745a92154b9 623 x = 0x8b0f3f383905cf3a3bb955ef8fb62e24849dd349a05ca79aafb18041d30cbd 624 b6 625 X = 0x04af09987a593d3bac8694b123839422c3cc87e37d6b41c1d630f000dd6498 626 0e537ae704bcede04ea3bec9b7475b32fa2ca3b684be14d11645e38ea6609eb39e7e 627 y = 0x2e0895b0e763d6d5a9564433e64ac3cac74ff897f6c3445247ba1bab40082a 628 91 629 Y = 0x04417592620aebf9fd203616bbb9f121b730c258b286f890c5f19fea833a9c 630 900cbe9057bc549a3e19975be9927f0e7614f08d1f0a108eede5fd7eb5624584a4f4 631 Z = 0x0471a35282d2026f36bf3ceb38fcf87e3112a4452f46e9f7b47fd769cfb570 632 145b62589c76b7aa1eb6080a832e5332c36898426912e29c40ef9e9c742eee82bf30 633 V = 0x046718981bf15bc4db538fc1f1c1d058cb0eececf1dbe1b1ea08a4e25275d3 634 82e82b348c8131d8ed669d169c2e03a858db7cf6ca2853a4071251a39fbe8cfc39bc 635 TT = 0x21000000000000005350414b45322b2d503235362d5348413235362d484b4 636 4462064726166742d30310600000000000000636c69656e740600000000000000736 637 572766572410000000000000004886e2f97ace46e55ba9dd7242579f2993b64e16ef 638 3dcab95afd497333d8fa12f5ff355163e43ce224e0b0e65ff02ac8e5c7be09419c78 639 5e0ca547d55a12e2d20410000000000000004d8bbd6c639c62937b04d997f38c3770 640 719c629d7014d49a24b4f98baa1292b4907d60aa6bfade45008a636337f5168c64d9 641 bd36034808cd564490b1e656edbe7410000000000000004af09987a593d3bac8694b 642 123839422c3cc87e37d6b41c1d630f000dd64980e537ae704bcede04ea3bec9b7475 643 b32fa2ca3b684be14d11645e38ea6609eb39e7e410000000000000004417592620ae 644 bf9fd203616bbb9f121b730c258b286f890c5f19fea833a9c900cbe9057bc549a3e1 645 9975be9927f0e7614f08d1f0a108eede5fd7eb5624584a4f44100000000000000047 646 1a35282d2026f36bf3ceb38fcf87e3112a4452f46e9f7b47fd769cfb570145b62589 647 c76b7aa1eb6080a832e5332c36898426912e29c40ef9e9c742eee82bf30410000000 648 0000000046718981bf15bc4db538fc1f1c1d058cb0eececf1dbe1b1ea08a4e25275d 649 382e82b348c8131d8ed669d169c2e03a858db7cf6ca2853a4071251a39fbe8cfc39b 650 c2000000000000000e6887cf9bdfb7579c69bf47928a84514b5e355ac034863f7ffa 651 f4390e67d798c 652 Ka = 0xf9cab9adcc0ed8e5a4db11a8505914b2 653 Ke = 0x801db297654816eb4f02868129b9dc89 654 KcA = 0x0d248d7d19234f1486b2efba5179c52d 655 KcB = 0x556291df26d705a2caedd6474dd0079b 656 HMAC(KcA, Y) = 0xd4376f2da9c72226dd151b77c2919071155fc22a2068d90b5fa 657 a6c78c11e77dd 658 HMAC(KcB, X) = 0x0660a680663e8c5695956fb22dff298b1d07a526cf3cc591adf 659 ecd1f6ef6e02e 660 CMAC(KcA, Y) = 0xad04419077d806572fd7c8ab6d78656a 661 CMAC(KcB, X) = 0xaa076038a84938018a276e673ee7583e 663 [Context=b'SPAKE2+-P256-SHA256-HKDF draft-01'] 664 [A=b'client'] 665 [B=b''] 666 w0 = 0xe6887cf9bdfb7579c69bf47928a84514b5e355ac034863f7ffaf4390e67d7 667 98c 668 w1 = 0x24b5ae4abda868ec9336ffc3b78ee31c5755bef1759227ef5372ca139b94e 669 512 670 L = 0x0495645cfb74df6e58f9748bb83a86620bab7c82e107f57d6870da8cbcb2ff 671 9f7063a14b6402c62f99afcb9706a4d1a143273259fe76f1c605a3639745a92154b9 672 x = 0xec82d9258337f61239c9cd68e8e532a3a6b83d12d2b1ca5d543f44def17dfb 673 8d 674 X = 0x04230779960824076d3666a7418e4d433e2fa15b06176eabdd572f43a32ecc 675 79a192b243d2624310a7356273b86e5fd9bd627d3ade762baeff1a320d4ad7a4e47f 676 y = 0xeac3f7de4b198d5fe25c443c0cd4963807add767815dd02a6f0133b4bc2c9e 677 b0 678 Y = 0x044558642e71b616b248c9583bd6d7aa1b3952c6df6a9f7492a06035ca5d92 679 522d84443de7aa20a59380fa4de6b7438d925dbfb7f1cfe60d79acf961ee33988c7d 680 Z = 0x04b4e8770f19f58ddf83f9220c3a9305792665e0c60989e6ee9d7fa449c775 681 d6395f6f25f307e3903ac045a013fbb5a676e872a6abfcf4d7bb5aac69efd6140eed 682 V = 0x04141db83bc7d96f41b636622e7a5c552ad83211ff55319ac25ed0a09f0818 683 bd942e8150319bfbfa686183806dc61911183f6a0f5956156023d96e0f93d275bf50 684 TT = 0x21000000000000005350414b45322b2d503235362d5348413235362d484b4 685 4462064726166742d30310600000000000000636c69656e740000000000000000410 686 000000000000004886e2f97ace46e55ba9dd7242579f2993b64e16ef3dcab95afd49 687 7333d8fa12f5ff355163e43ce224e0b0e65ff02ac8e5c7be09419c785e0ca547d55a 688 12e2d20410000000000000004d8bbd6c639c62937b04d997f38c3770719c629d7014 689 d49a24b4f98baa1292b4907d60aa6bfade45008a636337f5168c64d9bd36034808cd 690 564490b1e656edbe7410000000000000004230779960824076d3666a7418e4d433e2 691 fa15b06176eabdd572f43a32ecc79a192b243d2624310a7356273b86e5fd9bd627d3 692 ade762baeff1a320d4ad7a4e47f4100000000000000044558642e71b616b248c9583 693 bd6d7aa1b3952c6df6a9f7492a06035ca5d92522d84443de7aa20a59380fa4de6b74 694 38d925dbfb7f1cfe60d79acf961ee33988c7d410000000000000004b4e8770f19f58 695 ddf83f9220c3a9305792665e0c60989e6ee9d7fa449c775d6395f6f25f307e3903ac 696 045a013fbb5a676e872a6abfcf4d7bb5aac69efd6140eed410000000000000004141 697 db83bc7d96f41b636622e7a5c552ad83211ff55319ac25ed0a09f0818bd942e81503 698 19bfbfa686183806dc61911183f6a0f5956156023d96e0f93d275bf5020000000000 699 00000e6887cf9bdfb7579c69bf47928a84514b5e355ac034863f7ffaf4390e67d798 700 c 701 Ka = 0xe2cbee3ae19a4dbe9f146be6bee9bfa1 702 Ke = 0x6989d8f9177ef7df67da437987f07255 703 KcA = 0x2f9e0bb669d2c22645bce34da04ac16a 704 KcB = 0xeb7a35168759dd8e9ce44e4dc51277ce 705 HMAC(KcA, Y) = 0xe1b9258807ba4750dae1d7f3c3c294f13dc4fa60cde346d5de7 706 d200e2f8fd3fc 707 HMAC(KcB, X) = 0xb9c39dfa49c47757de778d9bedeaca2448b905be19a43b94ee2 708 4b770208135e3 709 CMAC(KcA, Y) = 0xf545e7af21e334de7389ddcf2174e822 710 CMAC(KcB, X) = 0x3fb3055e16b619fd3de0e1b2bd7a9383 712 [Context=b'SPAKE2+-P256-SHA256-HKDF draft-01'] 713 [A=b''] 714 [B=b'server'] 715 w0 = 0xe6887cf9bdfb7579c69bf47928a84514b5e355ac034863f7ffaf4390e67d7 716 98c 717 w1 = 0x24b5ae4abda868ec9336ffc3b78ee31c5755bef1759227ef5372ca139b94e 718 512 719 L = 0x0495645cfb74df6e58f9748bb83a86620bab7c82e107f57d6870da8cbcb2ff 720 9f7063a14b6402c62f99afcb9706a4d1a143273259fe76f1c605a3639745a92154b9 721 x = 0xba0f0f5b78ef23fd07868e46aeca63b51fda519a3420501acbe23d53c29187 722 48 723 X = 0x04c14d28f4370fea20745106cea58bcfb60f2949fa4e131b9aff5ea13fd5aa 724 79d507ae1d229e447e000f15eb78a9a32c2b88652e3411642043c1b2b7992cf2d4de 725 y = 0x39397fbe6db47e9fbd1a263d79f5d0aaa44df26ce755f78e092644b434533a 726 42 727 Y = 0x04d1bee3120fd87e86fe189cb952dc688823080e62524dd2c08dffe3d22a0a 728 8986aa64c9fe0191033cafbc9bcaefc8e2ba8ba860cd127af9efdd7f1c3a41920fe8 729 Z = 0x04aac71cf4c8df8181b867c9ecbee9d0963caf51f1534a823429c26fe52483 730 13ffc5c5e44ea8162161ab6b3d73b87704a45889bf6343d96fa96cd1641efa71607c 731 V = 0x04c7c9505365f7ce57293c92a37f1bbdc68e0322901e61edef59fee7876b17 732 b063e0fa4a126eae0a671b37f1464cf1ccad591c33ae944e3b1f318d76e36fea9966 733 TT = 0x21000000000000005350414b45322b2d503235362d5348413235362d484b4 734 4462064726166742d303100000000000000000600000000000000736572766572410 735 000000000000004886e2f97ace46e55ba9dd7242579f2993b64e16ef3dcab95afd49 736 7333d8fa12f5ff355163e43ce224e0b0e65ff02ac8e5c7be09419c785e0ca547d55a 737 12e2d20410000000000000004d8bbd6c639c62937b04d997f38c3770719c629d7014 738 d49a24b4f98baa1292b4907d60aa6bfade45008a636337f5168c64d9bd36034808cd 739 564490b1e656edbe7410000000000000004c14d28f4370fea20745106cea58bcfb60 740 f2949fa4e131b9aff5ea13fd5aa79d507ae1d229e447e000f15eb78a9a32c2b88652 741 e3411642043c1b2b7992cf2d4de410000000000000004d1bee3120fd87e86fe189cb 742 952dc688823080e62524dd2c08dffe3d22a0a8986aa64c9fe0191033cafbc9bcaefc 743 8e2ba8ba860cd127af9efdd7f1c3a41920fe8410000000000000004aac71cf4c8df8 744 181b867c9ecbee9d0963caf51f1534a823429c26fe5248313ffc5c5e44ea8162161a 745 b6b3d73b87704a45889bf6343d96fa96cd1641efa71607c410000000000000004c7c 746 9505365f7ce57293c92a37f1bbdc68e0322901e61edef59fee7876b17b063e0fa4a1 747 26eae0a671b37f1464cf1ccad591c33ae944e3b1f318d76e36fea996620000000000 748 00000e6887cf9bdfb7579c69bf47928a84514b5e355ac034863f7ffaf4390e67d798 749 c 750 Ka = 0xec8d19b807ffb1d1eea81a93ba35cdfe 751 Ke = 0x2ea40e4badfa5452b5744dc5983e99ba 752 KcA = 0x66de534d9bf1e44e96a53a4b48d6b353 753 KcB = 0x4945c38bb476cb0f347f3222be9b64a2 754 HMAC(KcA, Y) = 0xe564c93b3015efb946dc16d642bbe7d1c8da5be164ed9fc3bae 755 4e0ff86e1bd3c 756 HMAC(KcB, X) = 0x072a94d9a54edc201d8891534c2317cadf3ea3792827f479e87 757 3f93e90f21552 758 CMAC(KcA, Y) = 0x94aacd28128dc2ce1d7f5684119d553c 759 CMAC(KcB, X) = 0xbc6615eb68af10d329b2acb2d4545d97 761 [Context=b'SPAKE2+-P256-SHA256-HKDF draft-01'] 762 [A=b''] 763 [B=b''] 764 w0 = 0xe6887cf9bdfb7579c69bf47928a84514b5e355ac034863f7ffaf4390e67d7 765 98c 766 w1 = 0x24b5ae4abda868ec9336ffc3b78ee31c5755bef1759227ef5372ca139b94e 767 512 768 L = 0x0495645cfb74df6e58f9748bb83a86620bab7c82e107f57d6870da8cbcb2ff 769 9f7063a14b6402c62f99afcb9706a4d1a143273259fe76f1c605a3639745a92154b9 770 x = 0x5b478619804f4938d361fbba3a20648725222f0a54cc4c876139efe7d9a217 771 86 772 X = 0x04a6db23d001723fb01fcfc9d08746c3c2a0a3feff8635d29cad2853e73586 773 23425cf39712e928054561ba71e2dc11f300f1760e71eb177021a8f85e78689071cd 774 y = 0x766770dad8c8eecba936823c0aed044b8c3c4f7655e8beec44a15dcbcaf78e 775 5e 776 Y = 0x04390d29bf185c3abf99f150ae7c13388c82b6be0c07b1b8d90d26853e8437 777 4bbdc82becdb978ca3792f472424106a2578012752c11938fcf60a41df75ff7cf947 778 Z = 0x040a150d9a62f514c9a1fedd782a0240a342721046cefb1111c3adb3be893c 779 e9fcd2ffa137922fcf8a588d0f76ba9c55c85da2af3f1c789ca17976810387fb1d7e 780 V = 0x04f8e247cc263a1846272f5a3b61b68aa60a5a2665d10cd22c89cd6bad05dc 781 0e5e650f21ff017186cc92651a4cd7e66ce88f529299f340ea80fb90a9bad094e1a6 782 TT = 0x21000000000000005350414b45322b2d503235362d5348413235362d484b4 783 4462064726166742d303100000000000000000000000000000000410000000000000 784 004886e2f97ace46e55ba9dd7242579f2993b64e16ef3dcab95afd497333d8fa12f5 785 ff355163e43ce224e0b0e65ff02ac8e5c7be09419c785e0ca547d55a12e2d2041000 786 0000000000004d8bbd6c639c62937b04d997f38c3770719c629d7014d49a24b4f98b 787 aa1292b4907d60aa6bfade45008a636337f5168c64d9bd36034808cd564490b1e656 788 edbe7410000000000000004a6db23d001723fb01fcfc9d08746c3c2a0a3feff8635d 789 29cad2853e7358623425cf39712e928054561ba71e2dc11f300f1760e71eb177021a 790 8f85e78689071cd410000000000000004390d29bf185c3abf99f150ae7c13388c82b 791 6be0c07b1b8d90d26853e84374bbdc82becdb978ca3792f472424106a2578012752c 792 11938fcf60a41df75ff7cf9474100000000000000040a150d9a62f514c9a1fedd782 793 a0240a342721046cefb1111c3adb3be893ce9fcd2ffa137922fcf8a588d0f76ba9c5 794 5c85da2af3f1c789ca17976810387fb1d7e410000000000000004f8e247cc263a184 795 6272f5a3b61b68aa60a5a2665d10cd22c89cd6bad05dc0e5e650f21ff017186cc926 796 51a4cd7e66ce88f529299f340ea80fb90a9bad094e1a62000000000000000e6887cf 797 9bdfb7579c69bf47928a84514b5e355ac034863f7ffaf4390e67d798c 798 Ka = 0x5929a3ce9822c81401bf0f764f69af08 799 Ke = 0xea3276d68334576097e04b19ee5a3a8b 800 KcA = 0x7f84b939d600117256b0c8a6d40cf181 801 KcB = 0xf7d7547ced93f681e8df4c258c4516fd 802 HMAC(KcA, Y) = 0x71d9412779b6c45a2c615c9df3f1fd93dc0aaf63104da8ece4a 803 a1b5a3a415fea 804 HMAC(KcB, X) = 0x095dc0400355cc233fde7437811815b3c1524aae80fd4e6810c 805 f531cf11d20e3 806 CMAC(KcA, Y) = 0xd66386ee8033bf56387db3543691064e 807 CMAC(KcB, X) = 0x391070acb88ecc74dfe079cd0b8b52dc 809 Authors' Addresses 810 Tim Taubert 811 Apple Inc. 812 One Apple Park Way 813 Cupertino, California 95014, 814 United States of America 816 Email: ttaubert@apple.com 818 Christopher A. Wood 820 Email: caw@heapingbits.net