idnits 2.17.1 draft-irtf-cfrg-vrf-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: However, if the ECVRF uses keys that could be generated adversarially, then the the Verfier MUST first perform the validation procedure ECVRF_validate_key(PK) (specified in Section 5.6) upon receipt of the public key PK as an octet string. If the validation procedure outputs "INVALID", then the public key MUST not be used. Otherwise, the procedure will output a valid public key y, and the ECVRF with public key y satisfies the "full uniqueness" and "full collision resistance" properties. -- The document date (June 28, 2018) is 2128 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. 'FIPS-186-3' ** Downref: Normative reference to an Informational RFC: RFC 5114 ** Downref: Normative reference to an Informational RFC: RFC 6234 ** Downref: Normative reference to an Informational RFC: RFC 6979 ** Downref: Normative reference to an Informational RFC: RFC 8017 ** Downref: Normative reference to an Informational RFC: RFC 8032 -- Possible downref: Non-RFC (?) normative reference: ref. 'SECG1' == Outdated reference: A later version (-08) exists of draft-vcelak-nsec5-07 Summary: 6 errors (**), 0 flaws (~~), 3 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CFRG S. Goldberg 3 Internet-Draft L. Reyzin 4 Intended status: Standards Track Boston University 5 Expires: December 30, 2018 D. Papadopoulos 6 Hong Kong University of Science and Techology 7 J. Vcelak 8 NS1 9 June 28, 2018 11 Verifiable Random Functions (VRFs) 12 draft-irtf-cfrg-vrf-02 14 Abstract 16 A Verifiable Random Function (VRF) is the public-key version of a 17 keyed cryptographic hash. Only the holder of the private key can 18 compute the hash, but anyone with public key can verify the 19 correctness of the hash. VRFs are useful for preventing enumeration 20 of hash-based data structures. This document specifies several VRF 21 constructions that are secure in the cryptographic random oracle 22 model. One VRF uses RSA and the other VRF uses Eliptic Curves (EC). 24 Status of This Memo 26 This Internet-Draft is submitted in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF). Note that other groups may also distribute 31 working documents as Internet-Drafts. The list of current Internet- 32 Drafts is at https://datatracker.ietf.org/drafts/current/. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 This Internet-Draft will expire on December 30, 2018. 41 Copyright Notice 43 Copyright (c) 2018 IETF Trust and the persons identified as the 44 document authors. All rights reserved. 46 This document is subject to BCP 78 and the IETF Trust's Legal 47 Provisions Relating to IETF Documents 48 (https://trustee.ietf.org/license-info) in effect on the date of 49 publication of this document. Please review these documents 50 carefully, as they describe your rights and restrictions with respect 51 to this document. Code Components extracted from this document must 52 include Simplified BSD License text as described in Section 4.e of 53 the Trust Legal Provisions and are provided without warranty as 54 described in the Simplified BSD License. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 59 1.1. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 3 60 1.2. Requirements . . . . . . . . . . . . . . . . . . . . . . 3 61 1.3. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 62 2. VRF Algorithms . . . . . . . . . . . . . . . . . . . . . . . 4 63 3. VRF Security Properties . . . . . . . . . . . . . . . . . . . 4 64 3.1. Full Uniqueness or Trusted Uniqueness . . . . . . . . . . 5 65 3.2. Full Collison Resistance or Trusted Collision Resistance 5 66 3.3. Full Pseudorandomness or Selective Pseudorandomness . . . 5 67 3.4. An additional pseudorandomness property . . . . . . . . . 6 68 4. RSA Full Domain Hash VRF (RSA-FDH-VRF) . . . . . . . . . . . 7 69 4.1. RSA-FDH-VRF Proving . . . . . . . . . . . . . . . . . . . 8 70 4.2. RSA-FDH-VRF Proof To Hash . . . . . . . . . . . . . . . . 8 71 4.3. RSA-FDH-VRF Verifying . . . . . . . . . . . . . . . . . . 9 72 5. Elliptic Curve VRF (ECVRF) . . . . . . . . . . . . . . . . . 9 73 5.1. ECVRF Proving . . . . . . . . . . . . . . . . . . . . . . 11 74 5.2. ECVRF Proof To Hash . . . . . . . . . . . . . . . . . . . 12 75 5.3. ECVRF Verifying . . . . . . . . . . . . . . . . . . . . . 13 76 5.4. ECVRF Auxiliary Functions . . . . . . . . . . . . . . . . 13 77 5.4.1. ECVRF Hash To Curve . . . . . . . . . . . . . . . . . 13 78 5.4.2. ECVRF Hash Points . . . . . . . . . . . . . . . . . . 17 79 5.4.3. ECVRF Decode Proof . . . . . . . . . . . . . . . . . 17 80 5.5. ECVRF Ciphersuites . . . . . . . . . . . . . . . . . . . 18 81 5.6. When the ECVRF Keys are Untrusted . . . . . . . . . . . . 19 82 5.6.1. ECVRF Validate Key . . . . . . . . . . . . . . . . . 20 83 6. Implementation Status . . . . . . . . . . . . . . . . . . . . 20 84 7. Security Considerations . . . . . . . . . . . . . . . . . . . 21 85 7.1. Key Generation . . . . . . . . . . . . . . . . . . . . . 21 86 7.1.1. Uniqueness and collision resistance with untrusted 87 keys . . . . . . . . . . . . . . . . . . . . . . . . 21 88 7.1.2. Pseudorandomness with untrusted keys . . . . . . . . 22 89 7.2. Selective vs Full Pseudorandomness . . . . . . . . . . . 22 90 7.3. Proper pseudorandom nonce for ECVRF . . . . . . . . . . . 22 91 7.4. Timing attacks . . . . . . . . . . . . . . . . . . . . . 23 92 7.5. Proofs Provide No Secrecy for VRF Input . . . . . . . . . 23 93 7.6. Prehashing . . . . . . . . . . . . . . . . . . . . . . . 23 94 7.7. Hash function domain separation and future-proofing . . . 24 95 8. Change Log . . . . . . . . . . . . . . . . . . . . . . . . . 24 96 9. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 25 97 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 25 98 10.1. Normative References . . . . . . . . . . . . . . . . . . 25 99 10.2. Informative References . . . . . . . . . . . . . . . . . 26 100 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 27 102 1. Introduction 104 1.1. Rationale 106 A Verifiable Random Function (VRF) [MRV99] is the public-key version 107 of a keyed cryptographic hash. Only the holder of the private VRF 108 key can compute the hash, but anyone with corresponding public key 109 can verify the correctness of the hash. 111 A key application of the VRF is to provide privacy against offline 112 enumeration (e.g. dictionary attacks) on data stored in a hash-based 113 data structure. In this application, a Prover holds the VRF private 114 key and uses the VRF hashing to construct a hash-based data structure 115 on the input data. Due to the nature of the VRF, only the Prover can 116 answer queries about whether or not some data is stored in the data 117 structure. Anyone who knows the public VRF key can verify that the 118 Prover has answered the queries correctly. However no offline 119 inferences (i.e. inferences without querying the Prover) can be made 120 about the data stored in the data strucuture. 122 1.2. Requirements 124 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 125 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 126 document are to be interpreted as described in [RFC2119]. 128 1.3. Terminology 130 The following terminology is used through this document: 132 SK: The private key for the VRF. 134 PK: The public key for the VRF. 136 alpha: The input to be hashed by the VRF. 138 beta: The VRF hash output. 140 pi: The VRF proof. 142 Prover: The Prover holds the private VRF key SK and public VRF key 143 PK. 145 Verifier: The Verifier holds the public VRF key PK. 147 2. VRF Algorithms 149 A VRF comes with a key generation algorithm that generates a public 150 VRF key PK and private VRF key SK. 152 The prover hashes an input alpha using the private VRF key SK to 153 obtain a VRF hash output beta 155 beta = VRF_hash(SK, alpha) 157 The VRF_hash algorithm is deterministic, in the sense that it always 158 produces the same output beta given a pair of inputs (SK, alpha). 159 The prover also uses the private key SK to construct a proof pi that 160 beta is the correct hash output 162 pi = VRF_prove(SK, alpha) 164 The VRFs defined in this document allow anyone to deterministically 165 obtain the VRF hash output beta directly from the proof value pi as 167 beta = VRF_proof2hash(pi) 169 Notice that this means that 171 VRF_hash(SK, alpha) = VRF_proof2hash(VRF_prove(SK, alpha)) 173 and thus this document will specify VRF_prove and VRF_proof2hash 174 rather than VRF_hash. 176 The proof pi allows a Verifier holding the public key PK to verify 177 that beta is the correct VRF hash of input alpha under key PK. Thus, 178 the VRF also comes with an algorithm 180 VRF_verify(PK, alpha, pi) 182 that outputs VALID if beta=VRF_proof2hash(pi) is the correct VRF hash 183 of alpha under key PK, and outputs INVALID otherwise. 185 3. VRF Security Properties 187 VRFs are designed to ensure the following security properties. 189 3.1. Full Uniqueness or Trusted Uniqueness 191 Uniqueness means that, for any fixed public VRF key and for any input 192 alpha, there is a unique VRF output beta that can be proved to be 193 valid. Uniqueness must hold even for an adversarial Prover that 194 knows the VRF private key SK. 196 More percisely, "full uniqueness" states that a computationally- 197 bounded adversary cannot choose a VRF public key PK, a VRF input 198 alpha, two different VRF hash outputs beta1 and beta2, and two proofs 199 pi1 and pi2 such that VRF_verify(PK, alpha, pi1) and VRF_verify(PK, 200 alpha, pi2) both output VALID. 202 A slightly weaker security property called "trusted uniquness" 203 sufficies for many applications. Trusted uniqueness is the same as 204 full uniqueness, but it must hold only if the VRF keys PK and SK were 205 generated in a trustworthy manner. In other words, uniqueness might 206 not hold if keys were generated in an invalid manner or with bad 207 randomness. 209 3.2. Full Collison Resistance or Trusted Collision Resistance 211 Like any cryprographic hash function, VRFs need to be collision 212 resistant. Collison resistance must hold even for an adversarial 213 Prover that knows the VRF private key SK. 215 More percisely, "full collision resistance" states that it should be 216 computationally infeasible for an adversary to find two distinct VRF 217 inputs alpha1 and alpha2 that have the same VRF hash beta, even if 218 that adversary knows the private VRF key SK. 220 For most applications, a slightly weaker security property called 221 "trusted collision resistance" suffices. Trusted collision 222 resistance is the same as collision resistance, but it holds only if 223 PK and SK were generated in a trustworthy manner. 225 3.3. Full Pseudorandomness or Selective Pseudorandomness 227 Pseudorandomness ensures that when an adversarial Verifier sees a VRF 228 hash output beta without its corresponding VRF proof pi, then beta is 229 indistinguishable from a random value. 231 More percisely, suppose the public and private VRF keys (PK, SK) were 232 generated in a trustworthy manner. Pseudorandomness ensures that the 233 VRF hash output beta (without its corresponding VRF proof pi) on any 234 adversarially-chosen "target" VRF input alpha looks indistinguishable 235 from random for any computationally bounded adversary who does not 236 know the private VRF key SK. This holds even if the adversary also 237 gets to choose other VRF inputs alpha' and observe their 238 corresponding VRF hash outputs beta' and proofs pi'. 240 With "full pseudorandomness", the adversary is allowed to choose the 241 "target" VRF input alpha at any time, even after it observes VRF 242 outputs beta' and proofs pi' on a variety of chosen inputs alpha'. 244 "Selective pseudorandomness" is a weaker security property which 245 suffices in many applications. Here, the adversary must choose the 246 target VRF input alpha independently of the public VRF key PK, and 247 before it observes VRF outputs beta' and proofs pi' on inputs alpha' 248 of its choice. 250 It is important to remember that the VRF output beta does not look 251 random to the Prover, or to any other party that knows the private 252 VRF key SK! Such a party can easily distinguish beta from a random 253 value by comparing beta to the result of VRF_hash(SK, alpha). 255 Also, the VRF output beta does not look random to any party that 256 knows valid VRF proof pi corresponding to the VRF input alpha, even 257 if this party does not know the private VRF key SK. Such a party can 258 easily distinguish beta from a random value by checking whether 259 VRF_verify(PK, alpha, pi) returns "VALID" and beta = 260 VRF_proof2hash(pi). 262 Also, the VRF output beta may not look random if VRF key generation 263 was not done in a trustworthy fashion. (For example, if VRF keys 264 were generated with bad randomness.) 266 3.4. An additional pseudorandomness property 268 [TODO: This property is not needed for applications that use VRFs to 269 prevent enumeration of hash-based data structures. However, we 270 noticed that some other applications of VRF (e.g. Algorand, 271 Oroborus) rely on this property. We are waiting on a formal 272 definition of this property in the literature, and a proof that our 273 ECVRF scheme can satisfy this property. Preliminary analysis 274 suggests that acheiving this property requires ECVRF verifiers to run 275 an VRF_validate_key() key function upon receipt of VRF public keys 276 and the proof2hash function to be modified to take in (gamma, beta, 277 pk) rather than just gamma.] 279 Pseudorandomness, as defined in Section 3.3, does not hold if the VRF 280 keys were generated adversarially. 282 There is, however, a different type of pseudorandomness that could 283 hold even if the VRF keys are generated adversarially, as long as the 284 VRF input alpha is unpredictable. This property is similar to the 285 pseudorandomness achieved by an (ordinary, unkeyed) cryptographic 286 hash function. 288 [TODO: Formal definition here.] 290 4. RSA Full Domain Hash VRF (RSA-FDH-VRF) 292 The RSA Full Domain Hash VRF (RSA-FDH-VRF) is a VRF that satisfies 293 the "trusted uniqueness", "trusted collision resistance", and "full 294 pseudorandomness" properties defined in Section 3. Its security 295 follows from the standard RSA assumption in the random oracle model. 296 Formal security proofs are in [nsec5ecc]. 298 The VRF computes the proof pi as a deterministic RSA signature on 299 input alpha using the RSA Full Domain Hash Algorithm [RFC8017] 300 parametrized with the selected hash algorithm. RSA signature 301 verification is used to verify the correctness of the proof. The VRF 302 hash output beta is simply obtained by hashing the proof pi with the 303 selected hash algorithm. 305 The key pair for RSA-FDH-VRF MUST be generated in a way that it 306 satisfies the conditions specified in Section 3 of [RFC8017]. 308 In this document, the notation from [RFC8017] is used. 310 Parameters used: 312 (n, e) - RSA public key 314 K - RSA private key 316 k - length in octets of the RSA modulus n 318 Fixed options: 320 Hash - cryptographic hash function 322 hLen - output length in octets of hash function Hash 324 Constraints on options: 326 Cryptographic security of Hash is at least as high as the 327 cryptographic security level of the RSA key. 329 Primitives used: 331 I2OSP - Coversion of a nonnegative integer to an octet string as 332 defined in Section 4.1 of [RFC8017] 333 OS2IP - Coversion of an octet string to a nonnegative integer as 334 defined in Section 4.2 of [RFC8017] 336 RSASP1 - RSA signature primitive as defined in Section 5.2.1 of 337 [RFC8017] 339 RSAVP1 - RSA verification primitive as defined in Section 5.2.2 of 340 [RFC8017] 342 MGF1 - Mask Generation Function based on a hash function as 343 defined in Section B.2.1 of [RFC8017] 345 4.1. RSA-FDH-VRF Proving 347 RSAFDHVRF_prove(K, alpha) 349 Input: 351 K - RSA private key 353 alpha - VRF hash input, an octet string 355 Output: 357 pi - proof, an octet string of length k 359 Steps: 361 1. EM = MGF1(alpha, k - 1) 363 2. m = OS2IP(EM) 365 3. s = RSASP1(K, m) 367 4. pi = I2OSP(s, k) 369 5. Output pi 371 4.2. RSA-FDH-VRF Proof To Hash 373 RSAFDHVRF_proof2hash(pi) 375 Input: 377 pi - proof, an octet string of length k 379 Output: 381 beta - VRF hash output, an octet string of length hLen 383 Steps: 385 1. beta = Hash(pi) 387 2. Output beta 389 4.3. RSA-FDH-VRF Verifying 391 RSAFDHVRF_verify((n, e), alpha, pi) 393 Input: 395 (n, e) - RSA public key 397 alpha - VRF hash input, an octet string 399 pi - proof to be verified, an octet string of length n 401 Output: 403 "VALID" or "INVALID" 405 Steps: 407 1. s = OS2IP(pi) 409 2. m = RSAVP1((n, e), s) 411 3. EM = I2OSP(m, k - 1) 413 4. EM' = MGF1(alpha, k - 1) 415 5. If EM and EM' are equal, output "VALID"; else output "INVALID". 417 5. Elliptic Curve VRF (ECVRF) 419 The Elliptic Curve Verifiable Random Function (ECVRF) is a VRF that 420 satisfies the trusted uniqueness, trusted collision resistance, and 421 full pseudorandomness properties defined in Section 3. The security 422 of this VRF follows from the decisional Diffie-Hellman (DDH) 423 assumption in the random oracle model. Formal security proofs are in 424 [nsec5ecc]. 426 To additionally satisfy "full uniqueness" and "full collision 427 resistance", the Verifier MUST additionally perform the validation 428 procedure specified in Section 5.6 upon receipt of the public VRF 429 key. 431 Fixed options (specified in Section 5.5): 433 F - finite field 435 2n - length, in octets, of a field element in F; must be even 437 E - elliptic curve (EC) defined over F 439 m - length, in octets, of an EC point encoded as an octet string 441 G - subgroup of E of large prime order 443 q - prime order of group G; must be less than 2^{2n} 445 cofactor - number of points on E divided by q 447 g - generator of group G 449 Hash - cryptographic hash function 451 hLen - output length in octets of Hash; must be at least 2n 453 suite - a single nonzero octet specifying the ECVRF ciphersuite, 454 which determines the above options 456 Notation and primitives used: 458 p^k - When p is an EC point: point multiplication, i.e. k 459 repetitions of the EC group operation applied to the EC point p. 460 When p is an integer: exponentiation 462 || - octet string concatenation 464 I2OSP - nonnegative integer conversion to octet string as defined 465 in Section 4.1 of [RFC8017] 467 OS2IP - Coversion of an octet string to a nonnegative integer as 468 defined in Section 4.2 of [RFC8017] 470 EC2OSP - conversion of EC point to an m-octet string as specified 471 in Section 5.5 473 OS2ECP - conversion of an m-octet string to EC point as specified 474 in Section 5.5. OS2ECP returns INVALID if the octet string does 475 not convert to a valid EC point. 477 RS2ECP - conversion of a random 2n-octet string to an EC point as 478 specified in Section 5.5 480 ECVRF_hash_to_curve - collision resistant hash of strings to an EC 481 point; options described in Section 5.4.1 and specified in 482 Section 5.5. 484 ECVRF_nonce_generation - derives a pseudorandom nonce from SK and 485 the input as part of ECVRF proving. Specified in Section 5.5 487 ECVRF_hash_points - collision resistant hash of EC points to an 488 n-octet string. Specified in Section 5.4.2. 490 Parameters used (the generation of these parameters is specified in 491 Section 5.5): 493 SK - VRF private key 495 x - VRF secret scalar, an integer 497 Note: depending on the ciphersuite used, the VRF secret scalar 498 may be equal to SK; else, it is derived from SK 500 y = g^x - VRF public key, an EC point 502 5.1. ECVRF Proving 504 Note: this function must have the VRF private key SK as input. Below 505 we make it more efficient by supplying it also with the secret scalar 506 x and the public key y as additional inputs; however, each of these 507 can be computed from SK if desired. 509 ECVRF_prove(y, x, alpha) 511 Input: 513 SK - VRF private key 515 x - VRF secret scalar 517 y = g^x - VRF public key 519 Output: 521 pi - VRF proof, octet string of length m+3n 523 Steps: 525 1. h = ECVRF_hash_to_curve(suite, y, alpha) 527 2. h1 = EC2OSP(h) 529 3. gamma = h^x 531 4. k = ECVRF_nonce_generation(SK, h1) 533 5. c = ECVRF_hash_points(h, gamma, g^k, h^k) 535 6. s = (k + c*x) mod q (where * denotes integer multiplication) 537 7. pi = EC2OSP(gamma) || I2OSP(c, n) || I2OSP(s, 2n) 539 8. Output pi 541 5.2. ECVRF Proof To Hash 543 ECVRF_proof2hash(pi) 545 Input: 547 pi - VRF proof, octet string of length m+3n 549 Output: 551 "INVALID", or 553 beta - VRF hash output, octet string of length 2n 555 Steps: 557 1. D = ECVRF_decode_proof(pi) 559 2. If D is "INVALID", output "INVALID" and stop 561 3. (gamma, c, s) = D 563 4. three = 0x03 = I2OSP(3, 1), a single octet with value 3 565 5. preBeta = Hash(suite || three || EC2OSP(gamma^cofactor)) 567 6. beta = first 2n octets of preBeta 569 7. Output beta 571 5.3. ECVRF Verifying 573 ECVRF_verify(y, pi, alpha) 575 Input: 577 y - public key, an EC point 579 pi - VRF proof, octet string of length 5n+1 581 alpha - VRF input, octet string 583 Output: 585 "VALID" or "INVALID" 587 Steps: 589 1. D = ECVRF_decode_proof(pi) 591 2. If D is "INVALID", output "INVALID" and stop 593 3. (gamma, c, s) = D 595 4. u = g^s / y^c (where / denotes EC point subtraction, i.e. the 596 group operation applied to g^s and the inverse of y^c) 598 5. h = ECVRF_hash_to_curve(suite, y, alpha) 600 6. v = h^s / gamma^c (where / again denotes EC point subtraction) 602 7. c' = ECVRF_hash_points(h, gamma, u, v) 604 8. If c and c' are equal, output "VALID"; else output "INVALID" 606 5.4. ECVRF Auxiliary Functions 608 5.4.1. ECVRF Hash To Curve 610 The ECVRF_hash_to_curve algorithm takes in the VRF input alpha and 611 converts it to h, an EC point in G. This algorithm is the only place 612 alpha is used in the proving and verfying. See Section 7.6 for 613 further discussion. 615 The algorithms in this section are not compatible with each other; 616 the choice of algorithm is made in Section 5.5. 618 5.4.1.1. ECVRF_hash_to_curve_try_and_increment 620 The following ECVRF_hash_to_curve_try_and_increment(suite, y, alpha) 621 algorithm implements ECVRF_hash_to_curve in a simple and generic way 622 that works for any elliptic curve. 624 The running time of this algorithm depends on alpha. For the 625 ciphersuites specified in Section 5.5, this algorithm is expected to 626 find a valid curve point after approximately two attempts (i.e., when 627 ctr=1) on average. See also [Icart09]. 629 However, because the running time of algorithm depends on alpha, this 630 algorithm SHOULD be avoided in applications where it is important 631 that the VRF input alpha remain secret. 633 ECVRF_hash_to_try_and_increment(suite, y, alpha) 635 Input: 637 suite - a single octet specifying ECVRF ciphersuite. 639 y - public key, an EC point 641 alpha - value to be hashed, an octet string 643 Output: 645 h - hashed value, a finite EC point in G 647 Steps: 649 1. ctr = 0 651 2. pk = EC2OSP(y) 653 3. one = 0x01 = I2OSP(1, 1), a single octet with value 1 655 4. h = "INVALID" 657 5. While h is "INVALID" or h is EC point at infinity: 659 A. CTR = I2OSP(ctr, 4) 661 B. ctr = ctr + 1 663 C. hash = Hash(suite || one || pk || alpha || CTR) 665 D. attempted_hash = first 2n bits of hash 666 E. h = RS2ECP(attempted_hash) 668 F. If h is not "INVALID" and cofactor > 1, set h = h^cofactor 670 6. Output h 672 5.4.1.2. ECVRF_hash_to_curve_elligator2_25519 674 The following ECVRF__hash_to_curve_elligator2_25519(suite, y, alpha) 675 algorithm implements ECVRF_hash_to_curve using the elligator2 676 algorithm exclusively for Curve25519. 678 ECVRF_hash_to_curve_elligator2_25519(y, alpha) 680 Input: 682 alpha - value to be hashed, an octet string 684 y - public key, an EC point 686 suite = a single octet specifying ECVRF ciphersuite. 688 Output: 690 h - hashed value, a finite EC point in G per the encoding in 691 RFC8032 Section 5.1.2 [RFC8032] 693 Fixed options: 695 p = 2^255-19, the size of the finite field F, a prime, for 696 Curve25519 698 A = 486662, Montgomery curve constant for Curve25519 700 cofactor = 8 , the cofactor for Curve25519 702 * denotes integer multiplication 704 Constraints on options: 706 output length of Hash is at least 16n + 1 bits (i.e. greater than 707 2n octets) 709 Steps: 711 1. pk = EC2OSP(y) 713 2. one = 0x01 = I2OSP(1, 1), a single octet with value 1 714 3. hash = Hash(suite || one || pk || alpha ) 716 4. r = first 2n octets of hash 718 5. x_0 = next unused bit of hash 720 6. u = - A / (1 + 2*(r^2) ) mod p 722 7. v = u * (u^2 + A*u + 1) mod p 724 8. Let e equal the Legendre symbol of v modulo p 726 9. If e is equal to 1 then finalu = u; else finalu = (-A - u) mod p 728 10. y = (finalu - 1) / (finalu + 1) mod p 730 11. let h = (x_0,y), an EC point per the encoding in Section 5.1.2 731 of [RFC8032] 733 12. h = h^cofactor 735 In order to make this algorithm run in time that is (almost) 736 independent of the input (so-called "constant-time"), implementers 737 should pay particular attention to Steps 7 and 8 above. These steps 738 can be implemented using the following approach: 740 e = v ^ ((p-1)/2) mod p 742 finalu = (e*u + (e-1) * (A/2)) mod p 744 The first step will produce a value e that is either 1 or p-1. The 745 second step is so fast compared to the first that that its dependence 746 on e is likely to not matter; implementers can also ensure that it 747 runs in the same amount of time regardless of e. 749 If having this algorithm run in constant time is not important, then 750 there are much faster algorithms to compute the Legendre symbol 751 (which is the same as the Jacobi symbol because p is a prime). See, 752 for example, Section 12.3 of [ntb]. 754 5.4.1.3. ECVRF_hash_to_curve_other? 756 [TODO: In addition to Elligator, it would be nice to have a generic 757 ECVRF_hash_to_curve algorithm that runs in constant time and provides 758 a generic way to hash an octet string onto any elliptic curve. There 759 is an an upcoming draft that deals with this [SW18]. Some other 760 useful algorithms include [Icart09], and Shallue-Woestijne-Ulas 761 algorithm from [BCIMRT10].] 763 5.4.2. ECVRF Hash Points 765 ECVRF_hash_points(p_1, p_2, ..., p_j) 767 Input: 769 p_i - EC point in G 771 Output: 773 c - hash value, integer between 0 and 2^(8n)-1 775 Steps: 777 1. two = 0x02 = I2OSP(2, 1), a single octet with value 2 779 2. Initialize str = suite || two 781 3. for p_i in [p_1, p_2, ... p_j]: 782 str = str || EC2OSP(p_i) 784 4. c1 = Hash(str) 786 5. c2 = first n octets of c1 788 6. c = OS2IP(c2) 790 7. Output c 792 5.4.3. ECVRF Decode Proof 794 ECVRF_decode_proof(pi) 796 Input: 798 pi - VRF proof, octet string (m+3n octets) 800 Output: 802 "INVALID", or 804 gamma - EC point 806 c - integer between 0 and 2^(8n)-1 808 s - integer between 0 and 2^(16n)-1 810 Steps: 812 1. let gamma', c', s' be pi split after m-th and m+n-th octet 814 2. gamma = OS2ECP(gamma') 816 3. if gamma = "INVALID" output "INVALID" and stop. 818 4. c = OS2IP(c') 820 5. s = OS2IP(s') 822 6. Output gamma, c, and s 824 5.5. ECVRF Ciphersuites 826 This document defines ECVRF-P256-SHA256 as follows: 828 o suite = 0x01 = I2OSP(1, 1). 830 o The EC group G is the NIST-P256 elliptic curve, with curve 831 parameters as specified in [FIPS-186-3] (Section D.1.2.3) and 832 [RFC5114] (Section 2.6). For this group, 2n = 32 and cofactor = 833 1. 835 o The key pair generation primitive is specified in Section 3.2.1 of 836 [SECG1] (q, g, SK, and PK in this document correspond to in n, G, 837 d, and Q in Section 3.2.1 of [SECG1]). In this ciphersuite, the 838 secret scalar x is equal to the private key SK. 840 o The ECVRF_nonce_generation function is as specified in [RFC6979] 841 Section 3.2 Steps b-h (omitting Step a and using h1 that is 842 provided as input to ECVRF_nonce_generation), with the hash 843 function SHA-256 as specified in [RFC6234] 845 o EC2OSP is specified in Section 2.3.3 of [SECG1] with point 846 compression on. This implies m = 2n + 1 = 33. 848 o OS2ECP is specified in Section 2.3.4 of [SECG1]. 850 o RS2ECP(h) = OS2ECP(0x02 || h) (where 0x02 is a single octet with 851 value 2, 0x02=I2OSP(2, 1)). The input h is a 32-octet string and 852 the output is either an EC point or "INVALID". 854 o The hash function Hash is SHA-256 as specified in [RFC6234]. 856 o The ECVRF_hash_to_curve function is as specified in 857 Section 5.4.1.1. 859 This document defines ECVRF-ED25519-SHA512 as follows: 861 o suite = 0x02 = I2OSP(2, 1). 863 o The EC group G is the Ed25519 elliptic curve with parameters 864 defined in Table 1 of [RFC8032]. For this group, 2n = 32 and 865 cofactor = 8. 867 o The private key and generation of the secret scalar and the public 868 key are specified in Section 5.1.5 of [RFC8032] 870 o The ECVRF_nonce_generation function is as specified in [RFC8032] 871 Section 5.1.6 Steps 1-2, with dom2(F, C) equal to the empty string 872 and PH(M) equal to h1. 874 o EC2OSP is specified in Section 5.1.2 of [RFC8032]. This implies m 875 = 2n = 32. 877 o OS2ECP is specified in Section 5.1.3 of [RFC8032]. 879 o RS2ECP is equivalent to OS2ECP. 881 o The hash function Hash is SHA-512 as specified in [RFC6234]. 883 o The ECVRF_hash_to_curve function is as specified in 884 Section 5.4.1.1. 886 This document defines ECVRF-ED25519-SHA512-Elligator2 as follows: 888 o This ciphersuite is identical to ECVRF-ED25519-SHA512 except that 889 the ECVRF_hash_to_curve function is as specified in 890 Section 5.4.1.2 and suite = 0x03 = I2OSP(3, 1). 892 5.6. When the ECVRF Keys are Untrusted 894 The ECVRF as specified above is a VRF that satisfies the "trusted 895 uniqueness", "trusted collision resistance", and "full 896 pseudorandomness" properties defined in Section 3. In order to 897 obtain "full uniqueness" and "full collision resistance" (which 898 provide protection against a malicious VRF public key), the Verifier 899 MUST perform the following additional validation procedure upon 900 receipt of the public VRF key. The public VRF key MUST NOT be used 901 if this procedure returns "INVALID". 903 Note that this procedure is not sufficient if the elliptic curve E or 904 the point g, the generator of group G, is untrusted. If the prover 905 is untrusted, the Verifier MUST obtain E and g from a trusted source, 906 such as a ciphersuite specification, rather than from the prover. 908 This procedure supposes that the public key provided to the Verifier 909 is an octet string. The procedure returns "INVALID" if the public 910 key in invalid. Otherwise, it returns y, the public key as an EC 911 point. 913 5.6.1. ECVRF Validate Key 915 ECVRF_validate_key(PK) 917 Input: 919 PK - public key, an octet string 921 Output: 923 "INVALID", or 925 y - public key, an EC point 927 Steps: 929 1. y = OS2ECP(PK) 931 2. If y is "INVALID", output "INVALID" and stop 933 3. If y^cofactor is the EC point at infinty, output "INVALID" and 934 stop 936 4. Output y 938 6. Implementation Status 940 An implementation of the RSA-FDH-VRF (SHA-256) and ECVRF-P256-SHA256 941 was first developed as a part of the NSEC5 project [I-D.vcelak-nsec5] 942 and is available at . The 943 ECVRF implementation may be out of date as this spec has evolved. 945 The Key Transparency project at Google uses a VRF implemention that 946 is similar to the ECVRF-P256-SHA256, with a few minor changes 947 including the use of SHA-512 instead of SHA-256. Its implementation 948 is available 949 952 An implementation by Yahoo! similar to the ECVRF is available at 953 . 955 An implementation similar to ECVRF is available as part of the CONIKS 956 implementation in Golang at . 959 Open Whisper Systems also uses a VRF very similar to ECVRF- 960 ED25519-SHA512-Elligator, called VXEdDSA, and specified here: 961 963 7. Security Considerations 965 7.1. Key Generation 967 Applications that use the VRFs defined in this document MUST ensure 968 that that the VRF key is generated correctly, using good randomness. 970 7.1.1. Uniqueness and collision resistance with untrusted keys 972 The ECVRF as specified in Section 5.1-Section 5.5 statisfies the 973 "trusted uniqueness" and "trusted collision resistance" properties as 974 long as the VRF keys are generated correctly, with good randomness. 975 If the Verifier trusts the VRF keys are generated correctly, it MAY 976 use the public key y as is. 978 However, if the ECVRF uses keys that could be generated 979 adversarially, then the the Verfier MUST first perform the validation 980 procedure ECVRF_validate_key(PK) (specified in Section 5.6) upon 981 receipt of the public key PK as an octet string. If the validation 982 procedure outputs "INVALID", then the public key MUST not be used. 983 Otherwise, the procedure will output a valid public key y, and the 984 ECVRF with public key y satisfies the "full uniqueness" and "full 985 collision resistance" properties. 987 The RSA-FDH-VRF statisfies the "trusted uniqueness" and "trusted 988 collision resistance" properties as long as the VRF keys are 989 generated correctly, with good randomness. These properties may not 990 hold if the keys are generated adversarially (e.g., if RSA is not 991 permutation). Meanwhile, the "full uniqueness" and "full collision 992 resistance" are properties that hold even if VRF keys are generated 993 by an adversary. The RSA-FDH-VRF defined in this document does not 994 have these properties. However, if adversarial key generation is a 995 concern, the RSA-FDH-VRF may be modifed to have these properties by 996 adding additional cryptographic checks that its public key has the 997 right form. These modifications are left for future specification. 999 7.1.2. Pseudorandomness with untrusted keys 1001 Without good randomness, the "pseudorandomness" properties of the VRF 1002 may not hold. Note that it is not possible to guarantee 1003 pseudorandomness in the face of adversarially generated VRF keys. 1004 This is because an adversary can always use bad randomness to 1005 generate the VRF keys, and thus, the VRF output may not be 1006 pseudorandom. 1008 7.2. Selective vs Full Pseudorandomness 1010 [nsec5ecc] presents cryptographic reductions to an underlying hard 1011 problem (e.g. Decisional Diffie Hellman for the ECVRF, or the 1012 standard RSA assumption for RSA-FDH-VRF) that prove the VRFs 1013 specificied in this document possess full pseudorandomness as well as 1014 selective pseudorandomness. However, the cryptographic reductions 1015 are tighter for selective pseudorandomness than for full 1016 pseudorandomness. This means the the VRFs have quantitavely stronger 1017 security guarentees for selective pseudorandomness. 1019 Applications that are concerned about tightness of cryptographic 1020 reductions therefore have two options. 1022 o They may choose to ensure that selective pseudorandomness is 1023 sufficient for the application. That is, that pseudorandomness of 1024 outputs matters only for inputs that are chosen independently of 1025 the VRF key. 1027 o If full pseudorandomness is required for the application, the 1028 application may increase security parameters to make up for the 1029 loose security reduction. For RSA-FDH-VRF, this means increasing 1030 the RSA key length. For ECVRF, this means increasing the 1031 cryptographic strength of the EC group G. For both RSA-FDH-VRF 1032 and ECVRF the cryptographic strength of the hash function Hash may 1033 also potentially need to be increased. 1035 7.3. Proper pseudorandom nonce for ECVRF 1037 The security of the ECVRF defined in this document relies on the fact 1038 that nonce k used in the ECVRF_prove algorithm is chosen uniformly 1039 and pseudorandomly modulo q, and is unknown to the advesrary. 1040 Otherwise, an adversary may be able to recover the private VRF key x 1041 (and thus break pseudorandomness of the VRF) after observing several 1042 valid VRF proofs pi. The nonce generation methods specified in the 1043 ECVRF ciphersuites of Section 5.5 are designed with this requirement 1044 in mind. 1046 7.4. Timing attacks 1048 The ECVRF_hash_to_curve_try_and_increment algorithm defined in 1049 Section 5.4.1.1 SHOULD NOT be used in applications where the VRF 1050 input alpha is secret and is hashed by the VRF on-the-fly. This is 1051 because the algorithm's running time depends on the VRF input alpha, 1052 and thus creates a timing channel that can be used to learn 1053 information about alpha. That said, for most inputs the amount of 1054 information obtained from such a timing attack is likely to be small 1055 (1 bit, on average), since the algorithm is expected to find a valid 1056 curve point after only two attempts. However, there might be inputs 1057 which cause the algorithm to make many attempts before it finds a 1058 valid curve point; for such inputs, the information leaked in a 1059 timing attack will be more than 1 bit. 1061 Meanwhile, ECVRF-ED25519-SHA512-Elligator2 runs in constant time if 1062 the implementation of the ECVRF_hash_to_curve function specified in 1063 Section 5.4.1.2 also runs in constant time. 1065 7.5. Proofs Provide No Secrecy for VRF Input 1067 The VRF proof pi is not designed to provide secrecy and, in general, 1068 may reveal the VRF input alpha. Anyone who knows PK and pi is able 1069 to perform an offline dictionary attack to search for alpha, by 1070 verifying guesses for alpha using VRF_verify. This is in contrast to 1071 the VRF hash output beta which, without the proof, is pseudorandom 1072 and thus is designed to reveal no information about alpha. 1074 7.6. Prehashing 1076 The VRFs specified in this document allow for read-once access to the 1077 input alpha for both signing and verifying. Thus, additional 1078 prehashing of alpha (as specified, for example, in [RFC8032] for 1079 EdDSA signatures) is not needed, even for applications that need to 1080 handle long alpha or to support the Initialized-Update-Finalize (IUF) 1081 interface (in such an interface, alpha is not supplied all at once, 1082 but rather in pieces by a sequence of calls to Update). The ECVRF, 1083 in particular, uses alpha only in ECVRF_hash_to_curve. The curve 1084 point h becomes the representative of alpha thereafter. Note that 1085 the suite octet and the public key are hashed together with alpha in 1086 ECVRF_hash_to_curve, which ensures that the curve (including the 1087 generator g) and the public key are included indirectly into 1088 subsequent hashes. 1090 7.7. Hash function domain separation and future-proofing 1092 Hashing is used for four different purposes in ECVRF (namely, in 1093 hash_to_curve, nonce_generation, hash_points, and proof2hash). The 1094 theoretical analysis assumes each of these four functions is a 1095 separate random oracle. This analysis still holds even if the same 1096 hash function is used, as long as the four queries made to the hash 1097 function for a given SK and alpha are overwhelmingly unlikely to 1098 equal each other or to any queries made to the hash function for the 1099 same SK and different alpha. This is indeed the case for the ECVRF 1100 ciphersuites defined in this document, because: 1102 o inputs to the hash function used during nonce_generation are 1103 unlikely to equal to inputs given to hash_to_curve, proof2hash, 1104 and hash_points. This follows since nonce_generation inputs a 1105 secret to the hash function that is not used by honest parties as 1106 input to any other hash function, and is not available to the 1107 adversary 1109 o the second octet of the input to the hash function used in 1110 hash_to_curve, proof2hash, and hash_points are all different 1112 If future designs need to specify variants (e.g., additional 1113 ciphersuites) of the design in this document, then, to avoid the 1114 possibility that an adversary can obtain a VRF output under one 1115 variant, and then claim it was obtained under another variant, they 1116 should specify a different suite constant. This way, the inputs to 1117 the hash_to_curve hash function used in producing h are guaranteed to 1118 be different; since all the other hashing done by the prover depends 1119 on h, inputs all the hash functions used by the prover will also be 1120 different as long as hash_to_curve is collision resistant. 1122 8. Change Log 1124 Note to RFC Editor: if this document does not obsolete an existing 1125 RFC, please remove this appendix before publication as an RFC. 1127 00 - Forked this document from draft-goldbe-vrf-01. 1129 01 - Minor updates, mostly highlighting TODO items. 1131 02 - Added specification of elligator2 for Curve25519, along with 1132 ciphersuites for ECVRF-ED25519-SHA512-Elligator. Changed ECVRF- 1133 ED25519-SHA256 suite to ECVRF-ED25519-SHA512. (This change made 1134 because Ed25519 in [RFC8032] signatures use SHA512 and not 1135 SHA256.) Made ECVRF nonce generation a separate component, so 1136 that nonces are determinsitic. In ECVRF proving, changed + to - 1137 (and made corresponding verification changes) in order to be 1138 consistent with EdDSA and ECDSA. Highlighted that 1139 ECVRF_hash_to_curve acts like a prehash. Added "suites" variable 1140 to ECVRF for future-proofing. Ensured domain separation for hash 1141 functions by modifying hash_points and added discussion about 1142 domain separation. Updated todos in the "additional 1143 pseudorandomness property" section. Added an discussion of 1144 secrecy into security considerations. Removed g and PK=y from 1145 ECVRF_hash_points because they are already present via h, which is 1146 computed via hash_to_curve using the suite (which identifies g) 1147 and y. 1149 9. Contributors 1151 This document also would not be possible without the work of Moni 1152 Naor (Weizmann Institute), Sachin Vasant (Cisco Systems), and Asaf 1153 Ziv (Facebook). Shumon Huque (Salesforce), David C. Lawerence 1154 (Akamai), and Trevor Perrin provided valuable input to this draft. 1156 10. References 1158 10.1. Normative References 1160 [FIPS-186-3] 1161 National Institute for Standards and Technology, "Digital 1162 Signature Standard (DSS)", FIPS PUB 186-3, June 2009. 1164 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1165 Requirement Levels", BCP 14, RFC 2119, 1166 DOI 10.17487/RFC2119, March 1997, 1167 . 1169 [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman 1170 Groups for Use with IETF Standards", RFC 5114, 1171 DOI 10.17487/RFC5114, January 2008, 1172 . 1174 [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms 1175 (SHA and SHA-based HMAC and HKDF)", RFC 6234, 1176 DOI 10.17487/RFC6234, May 2011, 1177 . 1179 [RFC6979] Pornin, T., "Deterministic Usage of the Digital Signature 1180 Algorithm (DSA) and Elliptic Curve Digital Signature 1181 Algorithm (ECDSA)", RFC 6979, DOI 10.17487/RFC6979, August 1182 2013, . 1184 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, 1185 "PKCS #1: RSA Cryptography Specifications Version 2.2", 1186 RFC 8017, DOI 10.17487/RFC8017, November 2016, 1187 . 1189 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 1190 Signature Algorithm (EdDSA)", RFC 8032, 1191 DOI 10.17487/RFC8032, January 2017, 1192 . 1194 [SECG1] Standards for Efficient Cryptography Group (SECG), "SEC 1: 1195 Elliptic Curve Cryptography", Version 2.0, May 2009, 1196 . 1198 10.2. Informative References 1200 [BCIMRT10] 1201 Brier, E., Coron, J., Icart, T., Madore, D., Randriam, H., 1202 and M. Tibouchi, "Efficient Indifferentiable Hashing into 1203 Ordinary Elliptic Curves", in CRYPTO, 2010. 1205 [I-D.vcelak-nsec5] 1206 Vcelak, J., Goldberg, S., Papadopoulos, D., Huque, S., and 1207 D. Lawrence, "NSEC5, DNSSEC Authenticated Denial of 1208 Existence", draft-vcelak-nsec5-07 (work in progress), June 1209 2018. 1211 [Icart09] Icart, T., "How to Hash into Elliptic Curves", in CRYPTO, 1212 2009. 1214 [MRV99] Michali, S., Rabin, M., and S. Vadhan, "Verifiable Random 1215 Functions", in FOCS, 1999. 1217 [nsec5ecc] 1218 Papadopoulos, D., Wessels, D., Huque, S., Vcelak, J., 1219 Naor, M., Reyzin, L., and S. Goldberg, "Making NSEC5 1220 Practical for DNSSEC", in ePrint Cryptology Archive 1221 2017/099, February 2017, 1222 . 1224 [ntb] Shoup, V., "A Computational Introduction to Number Theory 1225 and Algebra", 2008, . 1227 [SW18] Sullivan, E. and C. Wood, "Hashing to Elliptic Curves", 1228 2018. 1230 Authors' Addresses 1232 Sharon Goldberg 1233 Boston University 1234 111 Cummington St, MCS135 1235 Boston, MA 02215 1236 USA 1238 EMail: goldbe@cs.bu.edu 1240 Leonid Reyzin 1241 Boston University 1242 111 Cummington St, MCS135 1243 Boston, MA 02215 1244 USA 1246 EMail: reyzin@bu.edu 1248 Dimitrios Papadopoulos 1249 Hong Kong University of Science and Techology 1250 Clearwater Bay 1251 Hong Kong 1253 EMail: dipapado@cse.ust.hkbu.edu 1255 Jan Vcelak 1256 NS1 1257 16 Beaver St 1258 New York, NY 10004 1259 USA 1261 EMail: jvcelak@ns1.com