Network Working Group N. Sullivan Internet-Draft Cloudflare Intended status: Informational C. Wood Expires: September 24, 2018 Apple Inc. March 23, 2018 Hashing to Elliptic Curves draft-irtf-cfrg-hash-to-curve-00 Abstract This document specifies a number of algorithms that may be used to hash arbitrary strings to Elliptic Curves. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on September 24, 2018. Copyright Notice Copyright (c) 2018 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Sullivan & Wood Expires September 24, 2018 [Page 1] Internet-Draft hash-to-curve March 2018 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1. Requirements . . . . . . . . . . . . . . . . . . . . . . 3 2. Algorithm Recommendations . . . . . . . . . . . . . . . . . . 3 3. Generic Interface . . . . . . . . . . . . . . . . . . . . . . 4 3.1. Utility Functions . . . . . . . . . . . . . . . . . . . . 4 4. Hashing Variants . . . . . . . . . . . . . . . . . . . . . . 5 4.1. Icart Method . . . . . . . . . . . . . . . . . . . . . . 5 4.2. Shallue-Woestijne-Ulas Method . . . . . . . . . . . . . . 6 4.3. Simplified SWU Method . . . . . . . . . . . . . . . . . . 6 4.4. Elligator2 Method . . . . . . . . . . . . . . . . . . . . 8 5. Curve Transformations . . . . . . . . . . . . . . . . . . . . 10 6. Cost Comparison . . . . . . . . . . . . . . . . . . . . . . . 10 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 8. Security Considerations . . . . . . . . . . . . . . . . . . . 11 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11 10. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 11 11. Normative References . . . . . . . . . . . . . . . . . . . . 11 Appendix A. Try-and-Increment Method . . . . . . . . . . . . . . 13 Appendix B. Sample Code . . . . . . . . . . . . . . . . . . . . 13 B.1. Icart Method . . . . . . . . . . . . . . . . . . . . . . 13 B.2. Shallue-Woestijne-Ulas Method . . . . . . . . . . . . . . 14 B.3. Simplified SWU Method . . . . . . . . . . . . . . . . . . 15 B.4. Elligator2 Method . . . . . . . . . . . . . . . . . . . . 16 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 17 1. Introduction Many cryptographic protocols require a procedure which maps arbitrary input, e.g., passwords, to points on an elliptic curve (EC). Prominent examples include Simple Password Exponential Key Exchange [Jablon96], Password Authenticated Key Exchange [BMP00], and Boneh- Lynn-Shacham signatures [BLS01]. Let E be an elliptic curve over base field GF(p). In practice, efficient (polynomial-time) functions that hash arbitrary input to E can be constructed by composing a cryptographically secure hash function F1 : {0,1}^* ->GF(p) and an injection F2 : GF(p) -> E, i.e., Hash(m) = F2(F1(m)). Probabilistic constructions of Hash, e.g., the MapToGroup function described by Boneh et al. [BLS01]. Their algorithm fails with probability 2^I, where I is a tunable parameter that one can control. Another variant, dubbed the "Try and Increment" approach, was described by Boneh et al. [BLS01]. This function works by hashing input m using a standard hash function, e.g., SHA256, and then checking to see if the resulting point E(m, f(m)), for curve function f, belongs on E. This algorithm is expected to find a valid curve point after approximately two Sullivan & Wood Expires September 24, 2018 [Page 2] Internet-Draft hash-to-curve March 2018 attempts, i.e., when ctr=1, on average. (See Appendix Appendix A for a more detailed description of this algorithm.) Since the running time of the algorithm depends on m, this algorithm is NOT safe for cases sensitive to timing side channel attacks. Deterministic algorithms are needed in such cases where failures are undesirable. Shallue and Woestijne [SWU] first introduced a deterministic algorithm that maps elements in F_{q} to an EC in time O(log^4 q), where q = p^n for some prime p, and time O(log^3 q) when q = 3 mod 4. Icart introduced yet another deterministic algorithm which maps F_{q} to any EC where q = 2 mod 3 in time O(log^3 q) [Icart09]. Elligator (2) [Elligator2] is yet another deterministic algorithm for any odd- characteristic EC that has a point of order 2. Elligator2 can be applied to Curve25519 and Curve448, which are both CFRG-recommended curves [RFC7748]. This document specifies several algorithms for deterministically hashing onto a curve with varying properties: Icart, SWU, Simplified SWU, and Elligator2. Each algorithm conforms to a common interface, i.e., it maps an element from a base field F to a curve E. For each variant, we describe the requirements for F and E to make it work. Sample code for each variant is presented in the appendix. Unless otherwise stated, all elliptic curve points are assumed to be represented as affine coordinates, i.e., (x, y) points on a curve. 1.1. Requirements The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. 2. Algorithm Recommendations The following table lists recommended algorithms to use for specific curves. +------------+------------------------+ | Curve | Algorithm | +------------+------------------------+ | P-256 | SWU Section 4.3 | | | | | P-384 | Icart Section 4.1 | | | | | Curve25519 | Elligator2 Section 4.4 | | | | | Curve448 | Elligator2 Section 4.4 | +------------+------------------------+ Sullivan & Wood Expires September 24, 2018 [Page 3] Internet-Draft hash-to-curve March 2018 The SWU variant from Section Section 4.2 applies to any curve. As such, this algorithm SHOULD be used if no other better alternative is known. More efficient variants and their curve requirements are shown in the table below. These MAY be used if the target curve meets the listed criteria. +--------------------+----------------------------------------------+ | Algorithm | Requirement | +--------------------+----------------------------------------------+ | Icart Section 4.1 | p = 2 mod 3 | | | | | SWU Section 4.2 | None | | | | | Simplified SWU | p = 3 mod 4 | | Section 4.3 | | | | | | Elligator2 Section | p is large and there is a point of order two | | 4.4 | and j-invariant != 1728 | +--------------------+----------------------------------------------+ 3. Generic Interface The generic interface for hashing to elliptic curves is as follows: hash_to_curve(alpha) where alpha is a message to hash onto a curve. 3.1. Utility Functions Algorithms in this document make use of utility functions described below. o HashToBase(x): H(x)[0:log2(p) + 1], i.e., hash-truncate-reduce, where H is a cryptographic hash function, such as SHA256, and p is the prime order of base field Fp. o CMOV(a, b, c): If c = 1, return a, else return b. Note: We assume that HashToBase maps its input to the base field uniformly. In practice, there may be inherent biases in p, e.g., p = 2^k - 1 will have non-negligible bias in higher bits. ((TODO: expand on this problem)) Sullivan & Wood Expires September 24, 2018 [Page 4] Internet-Draft hash-to-curve March 2018 4. Hashing Variants 4.1. Icart Method The following hash_to_curve_icart(alpha) implements the Icart method from [Icart09]. This algorithm works for any curve over F_{p^n}, where p^n = 2 mod 3 (or p = 2 mod 3 and for odd n), including: o P384 o Curve1174 o Curve448 Unsupported curves include: P224, P256, P521, and Curve25519 since, for each, p = 1 mod 3. Mathematically, given input alpha, and A and B from E, the Icart method works as follows: u = HashToBase(alpha) x = (v^2 - b - (u^6 / 27))^(1/3) + (u^2 / 3) y = ux + v where v = ((3A - u^4) / 6u). The following procedure implements this algorithm in a straight-line fashion. It requires knowledge of A and B, the constants from the curve Weierstrass form. It outputs a point with affine coordinates. Sullivan & Wood Expires September 24, 2018 [Page 5] Internet-Draft hash-to-curve March 2018 hash_to_curve_icart(alpha) Input: alpha - value to be hashed, an octet string Output: (x, y) - a point in E Steps: 1. u = HashToBase(alpha) // {0,1}^* -> Fp 2. u2 = u^2 (mod p) // u^2 3. t2 = u2^2 (mod p) // u^4 4. v1 = 3 * A (mod p) // 3A 5. v1 = v1 - t2 (mod p) // 3A - u^4 6. t1 = 6 * u (mod p) // 6u 7. t3 = t1 ^ (-1) (mod p) // modular inverse 8. v = v1 * t3 (mod p) // (3A - u^4)/(6u) 9. x = v^2 (mod p) // v^2 10. x = x - B (mod p) // v^2 - b 11. t1 = 27 ^ (-1) (mod p) // 1/27 12. t1 = t1 * u2 (mod p) // u^4 / 27 13. t1 = t1 * t2 (mod p) // u^6 / 27 14. x = x - t1 (mod p) // v^2 - b - u^6/27 15. t1 = (2 * p) - 1 (mod p) // 2p - 1 16. t1 = t1 / 3 (mod p) // (2p - 1)/3 17. x = x^t1 (mod p) // (v^2 - b - u^6/27) ^ (1/3) 18. t2 = u2 / 3 (mod p) // u^2 / 3 19. x = x + t2 (mod p) // (v^2 - b - u^6/27) ^ (1/3) + (u^2 / 3) 20. y = u * x (mod p) // ux 21. y = y + v (mod p) // ux + v 22. Output (x, y) 4.2. Shallue-Woestijne-Ulas Method ((TODO: write this section)) 4.3. Simplified SWU Method The following hash_to_curve_simple_swu(alpha) implements the simplfied Shallue-Woestijne-Ulas algorithm from [SimpleSWU]. This algorithm works for any curve over F_{p^n}, where p = 3 mod 4, including: o P256 Sullivan & Wood Expires September 24, 2018 [Page 6] Internet-Draft hash-to-curve March 2018 o ... Given curve equation g(x) = x^3 + Ax + B, this algorithm works as follows: 1. t = HashToBase(alpha) 2. alpha = (-b / a) * (1 + (1 / (t^4 + t^2))) 3. beta = -t^2 * alpha 4. z = t^3 * g(alpha) 5. Output (-g * alpha) * (g * beta) The following procedure implements this algorithm. It outputs a point with affine coordinates. Sullivan & Wood Expires September 24, 2018 [Page 7] Internet-Draft hash-to-curve March 2018 hash_to_curve_simple_swu(alpha) Input: alpha - value to be hashed, an octet string Output: (x, y) - a point in E Steps: 1. t = HashToBase(alpha) 2. alpha = t^2 (mod p) 3. alpha = alpha * -1 (mod p) 4. right = alpha^2 + alpha (mod p) 5. right = right^(-1) (mod p) 6. right = right + 1 (mod p) 7. left = B * -1 (mod p) 8. left = left / A (mod p) 9. x2 = left * right (mod p) 10. x3 = alpha * x2 (mod p) 11. h2 = x2 ^ 3 (mod p) 12. i2 = x2 * A (mod p) 13. i2 = i2 + B (mod p) 14. h2 = h2 + i2 (mod p) 15. h3 = x3 ^ 3 (mod p) 16. i3 = x3 * A (mod p) 17. i3 = i3 + B (mod p) 18. h3 = h3 + i3 (mod p) 19. y1 = h2 ^ ((p + 1) // 4) (mod p) 20. y2 = h3 ^ ((p + 1) // 4) (mod p) 21. e = (y1 ^ 2 == h2) 22. x = CMOV(x2, x3, e) // If e = 1, choose x2, else choose x3 23. y = CMOV(y1, y2, e) // If e = 1, choose y1, else choose y2 24. Output (x, y) 4.4. Elligator2 Method The following hash_to_curve_elligator2(alpha) implements the Elligator2 method from [Elligator2]. This algorithm works for any curve with a point of order 2 and j-invariant != 1728. Given curve equation f(x) = y^2 = x(x^2 + Ax + B), i.e., a Montgomery form with the point of order 2 at (0,0), this algorithm works as shown below. (Note that any curve with a point of order 2 is isomorphic to this representation.) Sullivan & Wood Expires September 24, 2018 [Page 8] Internet-Draft hash-to-curve March 2018 1. r = HashToBase(alpha) 2. If f(-A/(1+ur^2)) is square, then output f(-A/(1+ur^2))^(1/2) 3. Else, output f(-Aur^2/(1+ur^2))^(1/2) Another way to express this algorithm is as follows: 1. r = HashToBase(alpha) 2. d = -A / (1 + ur^2) 3. e = f(d)^((p-1)/2) 4. u = ed - (1 - e)A/u Here, e is the Legendre symbol of y = (d^3 + Ad^2 + d), which will be 1 if y is a quadratic residue (square) mod p, and -1 otherwise. (Note that raising y to ((p -1) / 2) is a common way to compute the Legendre symbol.) The following procedure implements this algorithm. Sullivan & Wood Expires September 24, 2018 [Page 9] Internet-Draft hash-to-curve March 2018 hash_to_curve_elligator2(alpha) Input: alpha - value to be hashed, an octet string u - fixed non-square value in Fp. f() - Curve function Output: (x, y) - a point in E Steps: 1. r = HashToBase(alpha) 2. r = r^2 (mod p) 3. nu = r * u (mod p) 4. r = nu 5. r = r + 1 (mod p) 6. r = r^(-1) (mod p) 7. v = A * r (mod p) 8. v = v * -1 (mod p) // -A / (1 + ur^2) 9. v2 = v^2 (mod p) 10. v3 = v * v2 (mod p) 11. e = v3 * v (mod p) 12. v2 = v2 * A (mod p) 13. e = v2 * e (mod p) 14. e = e^((p - 1) / 2) // Legendre symbol 15. nv = v * -1 (mod p) 16. v = CMOV(v, nv, e) // If e = 1, choose v, else choose nv 17. v2 = CMOV(0, A, e) // If e = 1, choose 0, else choose A 18. u = v - v2 (mod p) 19. Output (u, f(u)) Elligator2 can be simplified with projective coordinates. ((TODO: write this variant)) 5. Curve Transformations ((TODO: write this section)) 6. Cost Comparison The following table summarizes the cost of each hash_to_curve variant. We express this cost in terms of additions (A), multiplications (M), squares (SQ), and square roots (SR). Sullivan & Wood Expires September 24, 2018 [Page 10] Internet-Draft hash-to-curve March 2018 ((TODO: finish this section)) +--------------------------+-------------------+ | Algorithm | Cost (Operations) | +--------------------------+-------------------+ | hash_to_curve_icart | TODO | | | | | hash_to_curve_swu | TODO | | | | | hash_to_curve_simple_swu | TODO | | | | | hash_to_curve_elligator2 | TODO | +--------------------------+-------------------+ 7. IANA Considerations This document has no IANA actions. 8. Security Considerations Each hash function variant accepts arbitrary input and maps it to a pseudorandom point on the curve. Points are close to indistinguishable from randomly chosen elements on the curve. Some variants variants are not full-domain hashes. Elligator2, for example, only maps strings to "about half of all curve points," whereas Icart's method only covers about 5/8 of the points. 9. Acknowledgements The authors would like to thank Adam Langley for this detailed writeup up Elligator2 with Curve25519 [ElligatorAGL]. We also thank Sean Devlin and Thomas Icart for feedback on earlier versions of this document. 10. Contributors o Sharon Goldberg Boston University goldbe@cs.bu.edu 11. Normative References [BLS01] "Short signatures from the Weil pairing", n.d., . [BMP00] "Provably secure password-authenticated key exchange using diffie-hellman", n.d.. Sullivan & Wood Expires September 24, 2018 [Page 11] Internet-Draft hash-to-curve March 2018 [ECOPRF] "EC-OPRF - Oblivious Pseudorandom Functions using Elliptic Curves", n.d.. [Elligator2] "Elligator -- Elliptic-curve points indistinguishable from uniform random strings", n.d., . [ElligatorAGL] "Implementing Elligator for Curve25519", n.d., . [Icart09] "How to Hash into Elliptic Curves", n.d., . [Jablon96] "Strong password-only authenticated key exchange", n.d.. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, January 2016, . [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI 10.17487/RFC8017, November 2016, . [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital Signature Algorithm (EdDSA)", RFC 8032, DOI 10.17487/RFC8032, January 2017, . [SECG1] "SEC 1 -- Elliptic Curve Cryptography", n.d., . [SimpleSWU] "Efficient Indifferentiable Hashing into Ordinary Elliptic Curves", n.d.. [SWU] "Rational points on certain hyperelliptic curves over finite fields", n.d., . Sullivan & Wood Expires September 24, 2018 [Page 12] Internet-Draft hash-to-curve March 2018 Appendix A. Try-and-Increment Method In cases where constant time execution is not required, the so-called try-and-increment method may be appropriate. As discussion in Section Section 1, this variant works by hashing input m using a standard hash function ("Hash"), e.g., SHA256, and then checking to see if the resulting point E(m, f(m)), for curve function f, belongs on E. This is detailed below. 1. ctr = 0 3. h = "INVALID" 4. While h is "INVALID" or h is EC point at infinity: A. CTR = I2OSP(ctr, 4) B. ctr = ctr + 1 C. attempted_hash = Hash(m || CTR) D. h = RS2ECP(attempted_hash) E. If h is not "INVALID" and cofactor > 1, set h = h^cofactor 5. Output h I2OSP is a function that converts a nonnegative integer to octet string as defined in Section 4.1 of [RFC8017], and RS2ECP is a function that converts of a random 2n-octet string to an EC point as specified in Section 5.1.3 of [RFC8032]. Appendix B. Sample Code B.1. Icart Method The following Sage program implements hash_to_curve_icart(alpha) for P-384. p = 394020061963944792122790401001436138050797392704654466679482934042 \ 45721771496870329047266088258938001861606973112319 F = GF(p) A = p - 3 B = 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875a \ c656398d8a2ed19d2a85c8edd3ec2aef q = 394020061963944792122790401001436138050797392704654466679469052796 \ 27659399113263569398956308152294913554433653942643 E = EllipticCurve([F(A), F(B)]) g = E(0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a \ 385502f25dbf55296c3a545e3872760ab7, \ 0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c0 \ 0a60b1ce1d7e819d7a431d7c90ea0e5f) E.set_order(q) def icart(u): u = F(u) Sullivan & Wood Expires September 24, 2018 [Page 13] Internet-Draft hash-to-curve March 2018 v = (3*A - u^4)//(6*u) x = (v^2 - B - u^6/27)^((2*p-1)//3) + u^2/3 y = u*x + v return E(x, y) def icart_straight(u): u = F(u) u2 = u ^ 2 t2 = u2 ^ 2 assert t2 == u^4 v1 = 3 * A v1 = v1 - t2 t1 = 6 * u t3 = t1 ^ (-1) v = v1 * t3 assert v == (3 * A - u^4) // (6 * u) x = v ^ 2 x = x - B assert x == (v^2 - B) t1 = F(27) ^ (-1) t1 = t1 * u2 t1 = t1 * t2 assert t1 == ((u^6) / 27) x = x - t1 t1 = (2 * p) - 1 t1 = t1 / 3 assert t1 == ((2*p) - 1) / 3 x = x ^ t1 t2 = u2 / 3 x = x + t2 y = u * x y = y + v return E(x, y) B.2. Shallue-Woestijne-Ulas Method ((TODO: write this section)) Sullivan & Wood Expires September 24, 2018 [Page 14] Internet-Draft hash-to-curve March 2018 B.3. Simplified SWU Method The following Sage program implements hash_to_curve_swu(alpha) for P-256. p = 115792089210356248762697446949407573530086143415290314195533631308 \ 867097853951 F = GF(p) A = F(p - 3) B = F(ZZ("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2 \ 604b", 16)) E = EllipticCurve([A, B]) def simple_swu(alpha): t = F(alpha) alpha = -(t^2) frac = (1 / (alpha^2 + alpha)) x2 = (-B / A) * (1 + frac) x3 = alpha * x2 h2 = x2^3 + A * x2 + B h3 = x3^3 + A * x3 + B if is_square(h2): return E(x2, h2^((p + 1) // 4)) else: return E(x3, h3^((p + 1) // 4)) def simple_swu_straight(alpha): t = F(alpha) alpha = t^2 alpha = alpha * -1 right = alpha^2 + alpha right = right^(-1) right = right + 1 left = B * -1 left = left / A x2 = left * right x3 = alpha * x2 h2 = x2 ^ 3 i2 = x2 * A i2 = i2 + B Sullivan & Wood Expires September 24, 2018 [Page 15] Internet-Draft hash-to-curve March 2018 h2 = h2 + i2 h3 = x3 ^ 3 i3 = x3 * A i3 = i3 + B h3 = h3 + i3 y1 = h2^((p + 1) // 4) y2 = h3^((p + 1) // 4) # Is it square? e = y1^2 == h2 x = x2 if e != 1: x = x3 y = y1 if e != 1: y = y2 return E(x, y) B.4. Elligator2 Method The following Sage program implements hash_to_curve_elligator2(alpha) for Curve25519. p = 2**255 - 19 F = GF(p) A = 486662 B = 1 E = EllipticCurve(F, [0, A, 0, 1, 0]) def curve25519(x): return x^3 + (A * x^2) + x def elligator2(alpha): r = F(alpha) # u is a fixed nonsquare value, eg -1 if p==3 mod 4. u = F(2) # F(2) assert(not u.is_square()) # If f(-A/(1+ur^2)) is square, return its square root. # Else, return the square root of f(-Aur^2/(1+ur^2)). x = -A / (1 + (u * r^2)) Sullivan & Wood Expires September 24, 2018 [Page 16] Internet-Draft hash-to-curve March 2018 y = curve25519(x) if y.is_square(): # is this point square? y = y.square_root() else: x = (-A * u * r^2) / (1 + (u * r^2)) y = curve25519(x).square_root() return (x, curve25519(x)) def elligator2_straight(alpha): r = F(alpha) r = r^2 r = r * 2 r = r + 1 r = r^(-1) v = A * r v = v * -1 # d v2 = v^2 v3 = v * v2 e = v3 + v v2 = v2 * A e = v2 + e # Legendre symbol e = e^((p - 1) / 2) nv = v * -1 if e != 1: v = nv v2 = 0 if e != 1: v2 = A u = v - v2 return (u, curve25519(u)) Authors' Addresses Sullivan & Wood Expires September 24, 2018 [Page 17] Internet-Draft hash-to-curve March 2018 Nick Sullivan Cloudflare 101 Townsend St San Francisco United States of America Email: nick@cloudflare.com Christopher A. Wood Apple Inc. One Apple Park Way Cupertino, California 95014 United States of America Email: cawood@apple.com Sullivan & Wood Expires September 24, 2018 [Page 18]