idnits 2.17.1 draft-irtf-cfrg-spake2-08.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 : ---------------------------------------------------------------------------- ** There is 1 instance of too long lines in the document, the longest one being 1 character in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 11, 2019) is 1844 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: '-1' is mentioned on line 532, but not defined -- Looks like a reference, but probably isn't: '0' on line 534 == Outdated reference: A later version (-07) exists of draft-ietf-mmusic-sdp-uks-03 Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group W. Ladd 3 Internet-Draft UC Berkeley 4 Intended status: Informational B. Kaduk, Ed. 5 Expires: September 12, 2019 Akamai 6 March 11, 2019 8 SPAKE2, a PAKE 9 draft-irtf-cfrg-spake2-08 11 Abstract 13 This document describes SPAKE2 and its augmented variant SPAKE2+, 14 which are protocols for two parties that share a password to derive a 15 strong shared key with no risk of disclosing the password. This 16 method is compatible with any prime order group, is computationally 17 efficient, and SPAKE2 (but not SPAKE2+) has a security proof. 19 Status of This Memo 21 This Internet-Draft is submitted in full conformance with the 22 provisions of BCP 78 and BCP 79. 24 Internet-Drafts are working documents of the Internet Engineering 25 Task Force (IETF). Note that other groups may also distribute 26 working documents as Internet-Drafts. The list of current Internet- 27 Drafts is at https://datatracker.ietf.org/drafts/current/. 29 Internet-Drafts are draft documents valid for a maximum of six months 30 and may be updated, replaced, or obsoleted by other documents at any 31 time. It is inappropriate to use Internet-Drafts as reference 32 material or to cite them other than as "work in progress." 34 This Internet-Draft will expire on September 12, 2019. 36 Copyright Notice 38 Copyright (c) 2019 IETF Trust and the persons identified as the 39 document authors. All rights reserved. 41 This document is subject to BCP 78 and the IETF Trust's Legal 42 Provisions Relating to IETF Documents 43 (https://trustee.ietf.org/license-info) in effect on the date of 44 publication of this document. Please review these documents 45 carefully, as they describe your rights and restrictions with respect 46 to this document. Code Components extracted from this document must 47 include Simplified BSD License text as described in Section 4.e of 48 the Trust Legal Provisions and are provided without warranty as 49 described in the Simplified BSD License. 51 Table of Contents 53 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 54 2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 2 55 3. Definition of SPAKE2 . . . . . . . . . . . . . . . . . . . . 2 56 4. Key Schedule and Key Confirmation . . . . . . . . . . . . . . 5 57 5. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 6 58 6. Security Considerations . . . . . . . . . . . . . . . . . . . 9 59 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 60 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 9 61 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 62 Appendix A. Algorithm used for Point Generation . . . . . . . . 11 63 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 13 65 1. Introduction 67 This document describes SPAKE2, a means for two parties that share a 68 password to derive a strong shared key with no risk of disclosing the 69 password. This password-based key exchange protocol is compatible 70 with any group (requiring only a scheme to map a random input of 71 fixed length per group to a random group element), is computationally 72 efficient, and has a security proof. Predetermined parameters for a 73 selection of commonly used groups are also provided for use by other 74 protocols. 76 2. Requirements Notation 78 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 79 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 80 "OPTIONAL" in this document are to be interpreted as described in BCP 81 14 [RFC2119] [RFC8174] when, and only when, they appear in all 82 capitals, as shown here. 84 3. Definition of SPAKE2 86 3.1. Setup 88 Let G be a group in which the computational Diffie-Hellman (CDH) 89 problem is hard. Suppose G has order p*h where p is a large prime; h 90 will be called the cofactor. Let I be the unit element in G, e.g., 91 the point at infinity if G is an elliptic curve group. We denote the 92 operations in the group additively. We assume there is a 93 representation of elements of G as byte strings: common choices would 94 be SEC1 compressed [SEC1] for elliptic curve groups or big endian 95 integers of a fixed (per-group) length for prime field DH. We fix 96 two elements M and N in the prime-order subgroup of G as defined in 97 the table in this document for common groups, as well as a generator 98 P of the (large) prime-order subgroup of G. P is specified in the 99 document defining the group, and so we do not repeat it here. 101 || denotes concatenation of strings. We also let len(S) denote the 102 length of a string in bytes, represented as an eight-byte little- 103 endian number. Finally, let nil represent an empty string, i.e., 104 len(nil) = 0. 106 KDF is a key-derivation function that takes as input a salt, 107 intermediate keying material (IKM), info string, and derived key 108 length L to derive a cryptographic key of length L. MAC is a Message 109 Authentication Code algorithm that takes a secret key and message as 110 input to produce an output. Let Hash be a hash function from 111 arbitrary strings to bit strings of a fixed length. Common choices 112 for H are SHA256 or SHA512 [RFC6234]. Let MHF be a memory-hard hash 113 function designed to slow down brute-force attackers. Scrypt 114 [RFC7914] is a common example of this function. The output length of 115 MHF matches that of Hash. Parameter selection for MHF is out of 116 scope for this document. Section 5 specifies variants of KDF, MAC, 117 Hash, and MHF suitable for use with the protocols contained herein. 119 Let A and B be two parties. A and B may also have digital 120 representations of the parties' identities such as Media Access 121 Control addresses or other names (hostnames, usernames, etc). A and 122 B may share Additional Authenticated Data (AAD) of length at most 123 2^16 - 1 bits that is separate from their identities which they may 124 want to include in the protocol execution. One example of AAD is a 125 list of supported protocol versions if SPAKE2(+) were used in a 126 higher-level protocol which negotiates use of a particular PAKE. 127 Including this list would ensure that both parties agree upon the 128 same set of supported protocols and therefore prevent downgrade 129 attacks. We also assume A and B share an integer w; typically w = 130 MHF(pw) mod p, for a user-supplied password pw. Standards such 131 NIST.SP.800-56Ar3 suggest taking mod p of a hash value that is 64 132 bits longer than that needed to represent p to remove statistical 133 bias introduced by the modulation. Protocols using this 134 specification must define the method used to compute w: it may be 135 necessary to carry out various forms of normalization of the password 136 before hashing [RFC8265]. The hashing algorithm SHOULD be a MHF so 137 as to slow down brute-force attackers. 139 We present two protocols below. Note that it is insecure to use the 140 same password with both protocols; passwords MUST NOT be used for 141 both SPAKE2 and SPAKE2+. 143 3.2. SPAKE2 145 To begin, A picks x randomly and uniformly from the integers in 146 [0,p), and calculates X=x*P and T=w*M+X, then transmits T to B. Upon 147 receipt of T, B computes T*h and aborts if the result is equal to I. 148 (This ensures T is in the prime order subgroup of G.) 150 B selects y randomly and uniformly from the integers in [0,p), and 151 calculates Y=y*P, S=w*N+Y, then transmits S to A. Upon receipt of S, 152 A computes S*h and aborts if the result is equal to I. 154 Both A and B calculate a group element K. A calculates it as 155 x*(S-wN), while B calculates it as y*(T-w*M). A knows S because it 156 has received it, and likewise B knows T. A and B multiply protocol 157 messages from each peer by h so as to avoid small subgroup attacks, 158 but the result of the multiplication is not used for operations other 159 than the comparison against I and the non-multiplied value is used in 160 subsequent calculations. 162 K is a shared value, though it MUST NOT be used as a shared secret. 163 Both A and B must derive two shared secrets from K and the protocol 164 transcript. This prevents man-in-the-middle attackers from inserting 165 themselves into the exchange. The transcript TT is encoded as 166 follows: 168 TT = len(A) || A || len(B) || B || len(S) || S || len(T) || T 169 || len(K) || K || len(w) || w 171 If an identity is absent, it is omitted from the transcript entirely. 172 For example, if both A and B are absent, then TT = len(S) || S || 173 len(T) || T || len(K) || K || len(w) || w. Likewise, if only A is 174 absent, TT = len(B) || B || len(S) || S || len(T) || T || len(K) || 175 K || len(w) || w. This must only be done for applications in which 176 identities are implicit. Otherwise, the protocol risks Unknown Key 177 Share attacks (discussion of Unknown Key Share attacks in a specific 178 protocl is given in [I-D.ietf-mmusic-sdp-uks]. 180 Upon completion of this protocol, A and B compute shared secrets Ke, 181 KcA, and KcB as specified in Section 4. A MUST send B a key 182 confirmation message so both parties agree upon these shared secrets. 183 This confirmation message F is computed as a MAC over the protocol 184 transcript TT using KcA, as follows: F = MAC(KcA, TT). Similarly, B 185 MUST send A a confirmation message using a MAC computed equivalently 186 except with the use of KcB. Key confirmation verification requires 187 computing F and checking for equality against that which was 188 received. 190 3.3. SPAKE2+ 192 This protocol appears in [TDH]. We use the same setup as for SPAKE2, 193 except that we have two secrets, w0 and w1, derived by hashing the 194 password pw with the identities of the two participants, A and B. 195 Specifically, w0s || w1s = MHF(len(pw) || pw || len(A) || A || 196 len(B) || B), and then computing w0 = w0s mod p and w1 = w1s mod p. 197 The length of each of w0s and w1s is equal to half of the MHF output, 198 e.g., |w0s| = |w1s| = 128 bits for scrypt. w0 and w1 MUST NOT equal 199 I. If they are, they MUST be iteratively regenerated by computing 200 w0s || w1s = MHF(len(pw) || pw || len(A) || A || len(B) || B || 201 0x0000), where 0x0000 is 16-bit increasing counter. This process 202 must repeat until valid w0 and w1 are produced. B stores L=w1*P and 203 w0. 205 When executing SPAKE2+, A selects x uniformly at random from the 206 numbers in the range [0, p), and lets X=x*P+w0*M, then transmits X to 207 B. Upon receipt of X, A computes h*X and aborts if the result is 208 equal to I. B then selects y uniformly at random from the numbers in 209 [0, p), then computes Y=y*P+w0*N, and transmits Y to A. Upon receipt 210 of Y, A computes Y*h and aborts if the result is equal to I. 212 A computes Z as x*(Y-w0*N), and V as w1*(Y-w0*N). B computes Z as 213 y*(X- w0*M) and V as y*L. Both share Z and V as common keys. It is 214 essential that both Z and V be used in combination with the 215 transcript to derive the keying material. The protocol transcript 216 encoding is shown below. 218 TT = len(A) || A || len(B) || B || len(X) || X || len(Y) || Y 219 || len(Z) || Z || len(V) || V || len(w0) || w0 221 As in Section 3.2, inclusion of A and B in the transcript is optional 222 depending on whether or not the identities are implicit. 224 Upon completion of this protocol, A and B follow the same key 225 derivation and confirmation steps as outlined in Section 3.2. 227 4. Key Schedule and Key Confirmation 229 The protocol transcript TT, as defined in Sections Section 3.3 and 230 Section 3.2, is unique and secret to A and B. Both parties use TT to 231 derive shared symmetric secrets Ke and Ka as Ke || Ka = Hash(TT). 232 The length of each key is equal to half of the digest output, 233 e.g., |Ke| = |Ka| = 128 bits for SHA-256. 235 Both endpoints use Ka to derive subsequent MAC keys for key 236 confirmation messages. Specifically, let KcA and KcB be the MAC keys 237 used by A and B, respectively. A and B compute them as KcA || KcB = 238 KDF(nil, Ka, "ConfirmationKeys" || AAD), where AAD is the associated 239 data each given to each endpoint, or nil if none was provided. The 240 length of each of KcA and KcB is equal to half of the KDF output, 241 e.g., |KcA| = |KcB| = 128 bits for HKDF(SHA256). 243 The resulting key schedule for this protocol, given transcript TT and 244 additional associated data AAD, is as follows. 246 TT -> Hash(TT) = Ke || Ka 247 AAD -> KDF(nil, Ka, "ConfirmationKeys" || AAD) = KcA || KcB 249 A and B output Ke as the shared secret from the protocol. Ka and its 250 derived keys are not used for anything except key confirmation. 252 5. Ciphersuites 254 This section documents SPAKE2 and SPAKE2+ ciphersuite configurations. 255 A ciphersuite indicates a group, cryptographic hash algorithm, and 256 pair of KDF and MAC functions, e.g., SPAKE2-P256-SHA256-HKDF-HMAC. 257 This ciphersuite indicates a SPAKE2 protocol instance over P-256 that 258 uses SHA256 along with HKDF [RFC5869] and HMAC [RFC2104] for G, Hash, 259 KDF, and MAC functions, respectively. 261 +--------------+-----------+-----------+---------------+------------+ 262 | G | Hash | KDF | MAC | MHF | 263 +--------------+-----------+-----------+---------------+------------+ 264 | P-256 | SHA256 | HKDF | HMAC | scrypt | 265 | | [RFC6234] | [RFC5869] | [RFC2104] | [RFC7914] | 266 | | | | | | 267 | P-256 | SHA512 | HKDF | HMAC | scrypt | 268 | | [RFC6234] | [RFC5869] | [RFC2104] | [RFC7914] | 269 | | | | | | 270 | P-384 | SHA256 | HKDF | HMAC | scrypt | 271 | | [RFC6234] | [RFC5869] | [RFC2104] | [RFC7914] | 272 | | | | | | 273 | P-384 | SHA512 | HKDF | HMAC | scrypt | 274 | | [RFC6234] | [RFC5869] | [RFC2104] | [RFC7914] | 275 | | | | | | 276 | P-512 | SHA512 | HKDF | HMAC | scrypt | 277 | | [RFC6234] | [RFC5869] | [RFC2104] | [RFC7914] | 278 | | | | | | 279 | edwards25519 | SHA256 | HKDF | HMAC | scrypt | 280 | [RFC7748] | [RFC6234] | [RFC5869] | [RFC2104] | [RFC7914] | 281 | | | | | | 282 | edwards448 | SHA512 | HKDF | HMAC | scrypt | 283 | [RFC7748] | [RFC6234] | [RFC5869] | [RFC2104] | [RFC7914] | 284 | | | | | | 285 | P-256 | SHA256 | HKDF | CMAC-AES-128 | scrypt | 286 | | [RFC6234] | [RFC5869] | [RFC4493] | [RFC7914] | 287 | | | | | | 288 | P-256 | SHA512 | HKDF | CMAC-AES-128 | scrypt | 289 | | [RFC6234] | [RFC5869] | [RFC4493] | [RFC7914] | 290 +--------------+-----------+-----------+---------------+------------+ 292 Table 1: SPAKE2(+) Ciphersuites 294 The following points represent permissible point generation seeds for 295 the groups listed in the Table Table 1, using the algorithm presented 296 in Appendix A. These bytestrings are compressed points as in [SEC1] 297 for curves from [SEC1]. 299 For P256: 301 M = 302 02886e2f97ace46e55ba9dd7242579f2993b64e16ef3dcab95afd497333d8fa12f 303 seed: 1.2.840.10045.3.1.7 point generation seed (M) 305 N = 306 03d8bbd6c639c62937b04d997f38c3770719c629d7014d49a24b4f98baa1292b49 307 seed: 1.2.840.10045.3.1.7 point generation seed (N) 308 For P384: 310 M = 311 030ff0895ae5ebf6187080a82d82b42e2765e3b2f8749c7e05eba366434b363d3dc 312 36f15314739074d2eb8613fceec2853 313 seed: 1.3.132.0.34 point generation seed (M) 315 N = 316 02c72cf2e390853a1c1c4ad816a62fd15824f56078918f43f922ca21518f9c543bb 317 252c5490214cf9aa3f0baab4b665c10 318 seed: 1.3.132.0.34 point generation seed (N) 320 For P521: 322 M = 323 02003f06f38131b2ba2600791e82488e8d20ab889af753a41806c5db18d37d85608 324 cfae06b82e4a72cd744c719193562a653ea1f119eef9356907edc9b56979962d7aa 325 seed: 1.3.132.0.35 point generation seed (M) 327 N = 328 0200c7924b9ec017f3094562894336a53c50167ba8c5963876880542bc669e494b25 329 32d76c5b53dfb349fdf69154b9e0048c58a42e8ed04cef052a3bc349d95575cd25 330 seed: 1.3.132.0.35 point generation seed (N) 332 For edwards25519: 334 M = 335 d048032c6ea0b6d697ddc2e86bda85a33adac920f1bf18e1b0c6d166a5cecdaf 336 seed: edwards25519 point generation seed (M) 338 N = 339 d3bfb518f44f3430f29d0c92af503865a1ed3281dc69b35dd868ba85f886c4ab 340 seed: edwards25519 point generation seed (N) 342 For edwards448: 344 M = 345 b6221038a775ecd007a4e4dde39fd76ae91d3cf0cc92be8f0c2fa6d6b66f9a12 346 942f5a92646109152292464f3e63d354701c7848d9fc3b8880 347 seed: edwards448 point generation seed (M) 349 N = 350 6034c65b66e4cd7a49b0edec3e3c9ccc4588afd8cf324e29f0a84a072531c4db 351 f97ff9af195ed714a689251f08f8e06e2d1f24a0ffc0146600 352 seed: edwards448 point generation seed (N) 354 6. Security Considerations 356 A security proof of SPAKE2 for prime order groups is found in [REF]. 357 Note that the choice of M and N is critical for the security proof. 358 The generation method specified in this document is designed to 359 eliminate concerns related to knowing discrete logs of M and N. 361 SPAKE2+ appears in [TDH] along with a path to a proof that server 362 compromise does not lead to password compromise under the DH 363 assumption (though the corresponding model excludes precomputation 364 attacks). 366 Elements received from a peer MUST be checked for group membership: 367 failure to properly validate group elements can lead to attacks. 368 Beyond the cofactor multiplication checks to ensure that these 369 elements are in the prime order subgroup of G, it is essential that 370 endpoints verify received points are members of G. 372 The choices of random numbers MUST BE uniform. Randomly generated 373 values (e.g., x and y) MUST NOT be reused; such reuse may permit 374 dictionary attacks on the password. 376 SPAKE2 does not support augmentation. As a result, the server has to 377 store a password equivalent. This is considered a significant 378 drawback, and so SPAKE2+ also appears in this document. 380 7. IANA Considerations 382 No IANA action is required. 384 8. Acknowledgments 386 Special thanks to Nathaniel McCallum and Greg Hudson for generation 387 of test vectors. Thanks to Mike Hamburg for advice on how to deal 388 with cofactors. Greg Hudson also suggested the addition of warnings 389 on the reuse of x and y. Thanks to Fedor Brunner, Adam Langley, and 390 the members of the CFRG for comments and advice. Chris Wood 391 contributed substantial text and reformatting to address the 392 excellent review comments from Kenny Paterson. Trevor Perrin 393 informed me of SPAKE2+. 395 9. References 397 9.1. Normative References 399 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 400 Hashing for Message Authentication", RFC 2104, 401 DOI 10.17487/RFC2104, February 1997, 402 . 404 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 405 Requirement Levels", BCP 14, RFC 2119, 406 DOI 10.17487/RFC2119, March 1997, 407 . 409 [RFC4493] Song, JH., Poovendran, R., Lee, J., and T. Iwata, "The 410 AES-CMAC Algorithm", RFC 4493, DOI 10.17487/RFC4493, June 411 2006, . 413 [RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, 414 "Elliptic Curve Cryptography Subject Public Key 415 Information", RFC 5480, DOI 10.17487/RFC5480, March 2009, 416 . 418 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 419 Key Derivation Function (HKDF)", RFC 5869, 420 DOI 10.17487/RFC5869, May 2010, 421 . 423 [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms 424 (SHA and SHA-based HMAC and HKDF)", RFC 6234, 425 DOI 10.17487/RFC6234, May 2011, 426 . 428 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 429 for Security", RFC 7748, DOI 10.17487/RFC7748, January 430 2016, . 432 [RFC7914] Percival, C. and S. Josefsson, "The scrypt Password-Based 433 Key Derivation Function", RFC 7914, DOI 10.17487/RFC7914, 434 August 2016, . 436 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 437 Signature Algorithm (EdDSA)", RFC 8032, 438 DOI 10.17487/RFC8032, January 2017, 439 . 441 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 442 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 443 May 2017, . 445 [SEC1] SEC, "STANDARDS FOR EFFICIENT CRYPTOGRAPHY, "SEC 1: 446 Elliptic Curve Cryptography", version 2.0", May 2009. 448 9.2. Informative References 450 [I-D.ietf-mmusic-sdp-uks] 451 Thomson, M. and E. Rescorla, "Unknown Key Share Attacks on 452 uses of TLS with the Session Description Protocol (SDP)", 453 draft-ietf-mmusic-sdp-uks-03 (work in progress), January 454 2019. 456 [REF] Abdalla, M. and D. Pointcheval, "Simple Password-Based 457 Encrypted Key Exchange Protocols.", Feb 2005. 459 Appears in A. Menezes, editor. Topics in Cryptography- 460 CT-RSA 2005, Volume 3376 of Lecture Notes in Computer 461 Science, pages 191-208, San Francisco, CA, US. Springer- 462 Verlag, Berlin, Germany. 464 [RFC8265] Saint-Andre, P. and A. Melnikov, "Preparation, 465 Enforcement, and Comparison of Internationalized Strings 466 Representing Usernames and Passwords", RFC 8265, 467 DOI 10.17487/RFC8265, October 2017, 468 . 470 [TDH] Cash, D., Kiltz, E., and V. Shoup, "The Twin-Diffie 471 Hellman Problem and Applications", 2008. 473 EUROCRYPT 2008. Volume 4965 of Lecture notes in Computer 474 Science, pages 127-145. Springer-Verlag, Berlin, Germany. 476 Appendix A. Algorithm used for Point Generation 478 This section describes the algorithm that was used to generate the 479 points (M) and (N) in the table in Section 5. 481 For each curve in the table below, we construct a string using the 482 curve OID from [RFC5480] (as an ASCII string) or its name, combined 483 with the needed constant, for instance "1.3.132.0.35 point generation 484 seed (M)" for P-512. This string is turned into a series of blocks 485 by hashing with SHA256, and hashing that output again to generate the 486 next 32 bytes, and so on. This pattern is repeated for each group 487 and value, with the string modified appropriately. 489 A byte string of length equal to that of an encoded group element is 490 constructed by concatenating as many blocks as are required, starting 491 from the first block, and truncating to the desired length. The byte 492 string is then formatted as required for the group. In the case of 493 Weierstrass curves, we take the desired length as the length for 494 representing a compressed point (section 2.3.4 of [SEC1]), and use 495 the low-order bit of the first byte as the sign bit. In order to 496 obtain the correct format, the value of the first byte is set to 0x02 497 or 0x03 (clearing the first six bits and setting the seventh bit), 498 leaving the sign bit as it was in the byte string constructed by 499 concatenating hash blocks. For the [RFC8032] curves a different 500 procedure is used. For edwards448 the 57-byte input has the least- 501 significant 7 bits of the last byte set to zero, and for edwards25519 502 the 32-byte input is not modified. For both the [RFC8032] curves the 503 (modified) input is then interpreted as the representation of the 504 group element. If this interpretation yields a valid group element 505 with the correct order (p), the (modified) byte string is the output. 506 Otherwise, the initial hash block is discarded and a new byte string 507 constructed from the remaining hash blocks. The procedure of 508 constructing a byte string of the appropriate length, formatting it 509 as required for the curve, and checking if it is a valid point of the 510 correct order, is repeated until a valid element is found. 512 The following python snippet generates the above points, assuming an 513 elliptic curve implementation following the interface of 514 Edwards25519Point.stdbase() and Edwards448Point.stdbase() in 515 Appendix A of [RFC8032]: 517 def iterated_hash(seed, n): 518 h = seed 519 for i in range(n): 520 h = hashlib.sha256(h).digest() 521 return h 523 def bighash(seed, start, sz): 524 n = -(-sz // 32) 525 hashes = [iterated_hash(seed, i) for i in range(start, start + n)] 526 return b''.join(hashes)[:sz] 528 def canon_pointstr(ecname, s): 529 if ecname == 'edwards25519': 530 return s 531 elif ecname == 'edwards448': 532 return s[:-1] + bytes([s[-1] & 0x80]) 533 else: 534 return bytes([(s[0] & 1) | 2]) + s[1:] 536 def gen_point(seed, ecname, ec): 537 for i in range(1, 1000): 538 hval = bighash(seed, i, len(ec.encode())) 539 pointstr = canon_pointstr(ecname, hval) 540 try: 541 p = ec.decode(pointstr) 542 if p != ec.zero_elem() and p * p.l() == ec.zero_elem(): 543 return pointstr, i 544 except Exception: 545 pass 547 Authors' Addresses 549 Watson Ladd 550 UC Berkeley 552 Email: watsonbladd@gmail.com 554 Benjamin Kaduk (editor) 555 Akamai Technologies 557 Email: kaduk@mit.edu