idnits 2.17.1 draft-goldbe-vrf-00.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 -- The document date (March 13, 2017) is 2599 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) -- Looks like a reference, but probably isn't: '2' on line 476 -- Looks like a reference, but probably isn't: '3' on line 476 == Unused Reference: 'CP92' is defined on line 831, but no explicit reference was found in the text ** Downref: Normative reference to an Informational RFC: RFC 8017 ** 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 7748 == Outdated reference: A later version (-08) exists of draft-vcelak-nsec5-04 -- Possible downref: Non-RFC (?) normative reference: ref. 'FIPS-186-3' -- Possible downref: Non-RFC (?) normative reference: ref. 'SECG1' Summary: 5 errors (**), 0 flaws (~~), 3 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group S. Goldberg 3 Internet-Draft Boston University 4 Intended status: Standards Track D. Papadopoulos 5 Expires: September 14, 2017 University of Maryland 6 J. Vcelak 7 NS1 8 March 13, 2017 10 Verifiable Random Functions (VRFs) 11 draft-goldbe-vrf-00 13 Abstract 15 A Verifiable Random Function (VRF) is the public-key version of a 16 keyed cryptographic hash. Only the holder of the private key can 17 compute the hash, but anyone with public key can verify the 18 correctness of the hash. VRFs are useful for preventing enumeration 19 of hash-based data structures. This document specifies several VRF 20 constructions that are secure in the cryptographic random oracle 21 model. One VRF uses RSA and the other VRF uses Eliptic Curves (EC). 23 Status of This Memo 25 This Internet-Draft is submitted in full conformance with the 26 provisions of BCP 78 and BCP 79. 28 Internet-Drafts are working documents of the Internet Engineering 29 Task Force (IETF). Note that other groups may also distribute 30 working documents as Internet-Drafts. The list of current Internet- 31 Drafts is at http://datatracker.ietf.org/drafts/current/. 33 Internet-Drafts are draft documents valid for a maximum of six months 34 and may be updated, replaced, or obsoleted by other documents at any 35 time. It is inappropriate to use Internet-Drafts as reference 36 material or to cite them other than as "work in progress." 38 This Internet-Draft will expire on September 14, 2017. 40 Copyright Notice 42 Copyright (c) 2017 IETF Trust and the persons identified as the 43 document authors. All rights reserved. 45 This document is subject to BCP 78 and the IETF Trust's Legal 46 Provisions Relating to IETF Documents 47 (http://trustee.ietf.org/license-info) in effect on the date of 48 publication of this document. Please review these documents 49 carefully, as they describe your rights and restrictions with respect 50 to this document. Code Components extracted from this document must 51 include Simplified BSD License text as described in Section 4.e of 52 the Trust Legal Provisions and are provided without warranty as 53 described in the Simplified BSD License. 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 58 1.1. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 3 59 1.2. Requirements . . . . . . . . . . . . . . . . . . . . . . 3 60 1.3. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 61 2. VRF Algorithms . . . . . . . . . . . . . . . . . . . . . . . 3 62 3. VRF Security Properties . . . . . . . . . . . . . . . . . . . 4 63 3.1. Full Uniqueness or Trusted Uniqueness . . . . . . . . . . 4 64 3.2. Full Pseudorandomness or Selective Pseudorandomness . . . 5 65 3.3. Full Collison Resistance or Trusted Collision Resistance 5 66 4. RSA Full Domain Hash VRF (RSA-FDH-VRF) . . . . . . . . . . . 6 67 4.1. RSA-FDH-VRF Proving . . . . . . . . . . . . . . . . . . . 7 68 4.2. RSA-FDH-VRF Proof To Hash . . . . . . . . . . . . . . . . 7 69 4.3. RSA-FDH-VRF Verifying . . . . . . . . . . . . . . . . . . 8 70 5. Elliptic Curve VRF (EC-VRF) . . . . . . . . . . . . . . . . . 8 71 5.1. EC-VRF Proving . . . . . . . . . . . . . . . . . . . . . 10 72 5.2. EC-VRF Proof To Hash . . . . . . . . . . . . . . . . . . 10 73 5.3. EC-VRF Verifying . . . . . . . . . . . . . . . . . . . . 11 74 5.4. EC-VRF Auxiliary Functions . . . . . . . . . . . . . . . 11 75 5.4.1. EC-VRF Hash To Curve . . . . . . . . . . . . . . . . 11 76 5.4.2. EC-VRF Hash Points . . . . . . . . . . . . . . . . . 13 77 5.4.3. EC-VRF Decode Proof . . . . . . . . . . . . . . . . . 13 78 5.5. EC-VRF Ciphersuites . . . . . . . . . . . . . . . . . . . 14 79 6. Implementation Status . . . . . . . . . . . . . . . . . . . . 15 80 7. Security Considerations . . . . . . . . . . . . . . . . . . . 15 81 7.1. Key Generation . . . . . . . . . . . . . . . . . . . . . 15 82 7.2. Proper randomness for EC-VRF . . . . . . . . . . . . . . 16 83 7.3. Timing attacks . . . . . . . . . . . . . . . . . . . . . 16 84 7.4. Selective vs Full Pseudorandomness . . . . . . . . . . . 16 85 8. Change Log . . . . . . . . . . . . . . . . . . . . . . . . . 17 86 9. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 17 87 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 17 88 10.1. Normative References . . . . . . . . . . . . . . . . . . 17 89 10.2. Informative References . . . . . . . . . . . . . . . . . 18 90 Appendix A. Open Issues . . . . . . . . . . . . . . . . . . . . 19 91 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 19 93 1. Introduction 95 1.1. Rationale 97 A Verifiable Random Function (VRF) [MRV99] is the public-key version 98 of a keyed cryptographic hash. Only the holder of the private VRF 99 key can compute the hash, but anyone with corresponding public key 100 can verify the correctness of the hash. 102 The main application of the VRF is to protect the privacy of data 103 records stored in a hash-based data structure against a querying 104 adversary. In this application, a prover holds the VRF secret key 105 and uses the VRF hashing to construct a hash-based data structure on 106 the input data. Due to the nature of the VRF hashing, only the 107 prover can answer queries about whether or not some data is stored in 108 the data structure. Anyone who knows the public VRF key can verify 109 that the prover has answered the queries correctly. However no 110 offline inferences (i.e. inferences without querying the prover) can 111 be made about the data stored in the data strucuture. 113 1.2. Requirements 115 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 116 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 117 document are to be interpreted as described in [RFC2119]. 119 1.3. Terminology 121 The following terminology is used through this document: 123 SK: The private key for the VRF. 125 PK: The public key for the VRF. 127 alpha: The input to be hashed by the VRF. 129 beta: The VRF hash output. 131 pi: The VRF proof. 133 2. VRF Algorithms 135 A VRF comes with a key generation algorithm that generates a public 136 VRF key PK and private VRF key SK. 138 A VRF hashes an input alpha using the private VRF key SK to obtain a 139 VRF hash output beta: 141 beta = VRF_hash(SK, alpha) 143 The VRF_hash algorithm MUST be deterministic, in the sense that it 144 will always produce the same output beta given a pair of inputs (SK, 145 alpha). The private key SK is also used to construct a proof pi that 146 beta is the correct hash output 148 pi = VRF_prove(SK, alpha) 150 The VRFs defined in this document allow anyone to deterministically 151 obtain the VRF hash output beta directly from the proof value pi as 153 beta = VRF_proof2hash(pi) 155 Notice that this means that 157 VRF_hash(SK, alpha) = VRF_proof2hash(VRF_prove(SK, alpha)) 159 The proof pi allows anyone holding the public key PK to verify that 160 beta is the correct VRF hash of input alpha under key PK. Thus, the 161 VRF also comes with an algorithm 163 VRF_verify(PK, alpha, pi) 165 that outputs VALID if beta=VRF_proof2hash(pi) is correct VRF hash of 166 alpha under key PK, and outputs INVALID otherwise. 168 3. VRF Security Properties 170 VRFs are designed to ensure the following security properties. 172 3.1. Full Uniqueness or Trusted Uniqueness 174 Uniqueness states that, for any fixed public VRF key and for any 175 input alpha, there is a unique VRF output beta that can be proved to 176 be valid, even for a computationally-bounded adversary that knows the 177 VRF secret key SK. 179 More precisely, full uniqueness states that a computationally bounded 180 adversary cannot choose a VRF public key PK, a VR input alpha, two 181 different VRF hash outputs beta1 and beta2, and two proofs pi1 and 182 pi2 such that VRF_verify(PK, alpha, pi1) and VRF_verify(PK, alpha, 183 pi2) both output VALID. 185 A slightly weaker security property called "trusted uniquness" 186 sufficies for many applications. Trusted uniqueness is the same as 187 full uniqueness, but it must hold only if the VRF keys PK and SK were 188 generated in a trustworthy manner. In otherwords, uniqueness might 189 not hold if keys were generated in an invalid manner. 191 3.2. Full Pseudorandomness or Selective Pseudorandomness 193 Suppose the public and private VRF keys (PK, SK) were generated in a 194 trustworthy manner. 196 Pseudorandomness ensures that the VRF hash output beta (without its 197 corresponding VRF proof pi) on any adversarially-chosen "target" VRF 198 input alpha looks indistinguishable from random for any 199 computationally bounded adversary who does not know the private VRF 200 key SK. This holds even if the adversary also gets to choose other 201 VRF inputs alpha' and observe their corresponding VRF hash outputs 202 beta' and proofs pi'. 204 With "full pseudorandomness", the adversary is allowed to choose the 205 target VRF input alpha at any time, even after it observes VRF 206 outputs beta' and proofs pi' on a variety of chosen inputs alpha'. 208 "Selective pseudorandomness" is a weaker security property which 209 suffices in many applications. Here, the adversary must choose the 210 target VRF input alpha independently of the public VRF key PK, and 211 before it observes VRF outputs beta' and proofs pi' on inputs alpha' 212 of its choice. 214 It is important to remember that the VRF output beta does not look 215 random to a party that knows the private VRF key SK! Such a party 216 can easily distinguish beta from a random value by comparing it to 217 the result of VRF_hash(SK, alpha). 219 Also, the VRF output beta does not look random to any party that 220 knows valid VRF proof pi corresponding to the VRF input alpha, even 221 if this party does not know the private VRF key SK. Such a party can 222 easily distinguish beta from a random value by checking whether 223 VRF_verify(PK, alpha, pi) returns "VALID" and beta = 224 VRF_proof2hash(pi). 226 Finally, the VRF output beta may not look random if VRF key 227 generation was not done in a trustworthy fashion. (For example, if 228 VRF keys were not generated with good randomness.) 230 3.3. Full Collison Resistance or Trusted Collision Resistance 232 Finally, like any cryprographic hash function, VRFs need to be 233 collision resistant. Specifically, it should be computationally 234 infeasible for an adversary to find two distinct VRF inputs alpha1 235 and alpha2 that have the same VRF hash beta, even if that adversary 236 knows the secret VRF key SK. 238 For most applications, a slightly weaker security property called 239 "trusted collision resistance" suffices. Trusted collision 240 resistance is the same as collision resistance, but it holds only if 241 PK and SK were generated in a trustworthy manner. 243 4. RSA Full Domain Hash VRF (RSA-FDH-VRF) 245 The RSA Full Domain Hash VRF (RSA-FDH-VRF) is VRF that satisfies the 246 trusted uniqueness, full pseudorandomness, and trusted collision 247 resistance properties defined in Section 3. Its security follows 248 from the standard RSA assumption in the random oracle model. Formal 249 security proofs are in [nsec5ecc]. 251 The VRF computes the proof pi as a deterministic RSA signature on 252 input alpha using the RSA Full Domain Hash Algorithm [RFC8017] 253 parametrized with the selected hash algorithm. RSA signature 254 verification is used to verify the correctness of the proof. The VRF 255 hash output beta is simply obtained by hashing the proof pi with the 256 selected hash algorithm. 258 The key pair for RSA-FDH-VRF MUST be generated in a way that it 259 satisfies the conditions specified in Section 3 of [RFC8017]. 261 In this document, the notation from [RFC8017] is used. 263 Used parameters: 265 (n, e) - RSA public key 267 K - RSA private key 269 k - length in octets of the RSA modulus n 271 Fixed options: 273 Hash - cryptographic hash function 275 hLen - output length in octets of hash function Hash 277 Options constraints: 279 Cryptographic security of Hash is at least as high as the 280 cryptographic security level of the RSA key 282 Used primitives: 284 I2OSP - Coversion of a nonnegative integer to an octet string as 285 defined in Section 4.1 of [RFC8017] 287 OS2IP - Coversion of an octet string to a nonnegative integer as 288 defined in Section 4.2 of [RFC8017] 290 RSASP1 - RSA signature primitive as defined in Section 5.2.1 of 291 [RFC8017] 293 RSAVP1 - RSA verification primitive as defined in Section 5.2.2 of 294 [RFC8017] 296 MGF1 - Mask Generation Function based on a hash function as 297 defined in Section B.2.1 of [RFC8017] 299 4.1. RSA-FDH-VRF Proving 301 RSAFDHVRF_prove(K, alpha) 303 Input: 305 K - RSA private key 307 alpha - VRF hash input, an octet string 309 Output: 311 pi - proof, an octet string of length k 313 Steps: 315 1. EM = MGF1(alpha, k - 1) 317 2. m = OS2IP(EM) 319 3. s = RSASP1(K, m) 321 4. pi = I2OSP(s, k) 323 5. Output pi 325 4.2. RSA-FDH-VRF Proof To Hash 327 RSAFDHVRF_proof2hash(pi) 329 Input: 331 pi - proof, an octet string of length k 333 Output: 335 beta - VRF hash output, an octet string of length hLen 337 Steps: 339 1. beta = Hash(pi) 341 2. Output beta 343 4.3. RSA-FDH-VRF Verifying 345 RSAFDHVRF_verify((n, e), alpha, pi) 347 Input: 349 (n, e) - RSA public key 351 alpha - VRF hash input, an octet string 353 pi - proof to be verified, an octet string of length n 355 Output: 357 "VALID" or "INVALID" 359 Steps: 361 1. s = OS2IP(pi) 363 2. m = RSAVP1((n, e), s) 365 3. EM = I2OSP(m, k - 1) 367 4. EM' = MGF1(alpha, k - 1) 369 5. If EM and EM' are the same, output "VALID"; else output 370 "INVALID". 372 5. Elliptic Curve VRF (EC-VRF) 374 The Elliptic Curve Verifiable Random Function (EC-VRF) is VRF that 375 satisfies the trusted uniqueness, full pseudorandomness, and trusted 376 collision resistance properties defined in Section 3. The security 377 of this VRF follows from the decisional Diffie-Hellman (DDH) 378 assumption in the cyclic group in the random oracle model. Formal 379 security proofs are in [nsec5ecc]. 381 The key pair generation primitive is specified in Section 3.2.1 of 382 [SECG1]. 384 Fixed options: 386 G - EC group 388 q - prime order of group G 390 g - generator of group G 392 2n - ceil(log2(q)/8); where log2(x) is the binary logarithm of x 393 and ceil(x) is the smallest integer larger than or equal to the 394 real number x. 396 Hash - cryptographic hash function 398 hLen - output length in octets of function Hash 400 Options constraints: 402 Cryptographic security of Hash is at least as high as the 403 cryptographic security of G 405 hLen is equal to 2n 407 Used parameters: 409 g^x - EC public key 411 x - EC private key 413 Used primitives: 415 "" - empty octet string 417 || - octet string concatenation 419 p^k - EC point multiplication 421 p1*p2 - EC point addition 423 h[i] - the i'th octet of octet string h 425 ECP2OS - EC point to octet string conversion with point 426 compression as specified in Section 2.3.3 of [SECG1] 427 OS2ECP - octet string to EC point conversion with point 428 compression as specified in Section 2.3.4 of [SECG1] 430 5.1. EC-VRF Proving 432 ECVRF_prove(g^x, x, alpha) 434 Input: 436 g^x - EC public key 438 x - EC private key 440 alpha - VRF input, octet string 442 Output: 444 pi - VRF proof, octet string of length 5n+1 446 Steps: 448 1. h = ECVRF_hash_to_curve(alpha, g^x) 450 2. gamma = h^x 452 3. choose a random nonce k from [0, q-1] 454 4. c = ECVRF_hash_points(g, h, g^x, h^x, g^k, h^k) 456 5. s = k - c*q mod q 458 6. pi = ECP2OS(gamma) || I2OSP(c, n) || I2OSP(s, 2n) 460 7. Output pi 462 5.2. EC-VRF Proof To Hash 464 ECVRF_proof2hash(pi) 466 Input: 468 pi - VRF proof, octet string of length 5n+1 470 Output: 472 beta - VRF hash output, octet string of length 2n 474 Steps: 476 1. beta = pi[2] || pi[3] || ... pi[2n+1] 478 2. Output beta 480 5.3. EC-VRF Verifying 482 ECVRF_verify(g^x, pi, alpha) 484 Input: 486 g^x - EC public key 488 pi - VRF proof, octet string of length 5n+1 490 alpha - VRF input, octet string 492 Output: 494 "VALID" or "INVALID" 496 Steps: 498 1. gamma, c, s = ECVRF_decode_proof(pi) 500 2. If gamma is not a valid EC point in G, output "INVALID" and stop. 502 3. u = (g^x)^c * g^s 504 4. h = ECVRF_hash_to_curve(alpha, g^x) 506 5. v = gamma^c * h^s 508 6. c' = ECVRF_hash_points(g, h, g^x, gamma, u, v) 510 7. If c and c' are the same, output "VALID"; else output "INVALID". 512 5.4. EC-VRF Auxiliary Functions 514 5.4.1. EC-VRF Hash To Curve 516 The ECVRF_hash_to_curve algorithm takes in an octet string alpha and 517 converts it to h, an EC point in G. 519 5.4.1.1. ECVRF_hash_to_curve1 521 The following ECVRF_hash_to_curve1(alpha, g^x) algorithm implements 522 ECVRF_hash_to_curve in a simple and generic way that works for any 523 elliptic curve that supports point compression. 525 However, this algorithm MUST NOT be used in applications where the 526 VRF input alpha must be kept secret. This is because the running 527 time of the hashing algorithm depends on alpha, and so it is 528 susceptible to timing attacks. That said, the amount of information 529 obtained from such a timing attack is likely to be small, since the 530 algorithm is expected to find a valid curve point after only two 531 attempts (i.e., when ctr=1) on average (see [Icart09]). 533 ECVRF_hash_to_curve1(alpha, g^x) 535 Input: 537 alpha - value to be hashed, an octet string 539 g^x - EC public key 541 Output: 543 h - hashed value, EC point in G 545 Steps: 547 1. ctr = 0 549 2. pk = ECP2OS(g^x) 551 3. Repeat: 553 A. CTR = I2OSP(ctr, 4) 555 B. p = 0x02 || Hash(alpha || pk || CTR) 557 C. Goto step 3 if OS2ECP(p) is valid EC point in G 559 D. p = 0x03 || Hash(alpha || pk || CTR) 561 E. Goto step 3 if OS2ECP(p) is valid EC point in G 563 F. ctr = ctr + 1 565 4. h = OS2ECP(p) 567 5. Output h 569 The initial octet 0x02 in the octet string created in step B 570 represents that the point in compressed form has positive 571 y-coefficient [SECG1]. Similarly, the 0x03 octet in step D 572 represents negative y-coefficient. 574 5.4.1.2. ECVRF_hash_to_curve2 576 For applications where VRF input alpha must be kept secret, the 577 following ECVRF_hash_to_curve algorithm MAY be used to used as 578 generic way to hash an octet string onto any elliptic curve. 580 [TODO: If there interest, we could look into specifying the generic 581 deterministic time hash_to_curve algorithm from [Icart09]. ] 583 5.4.2. EC-VRF Hash Points 585 ECVRF_hash_points(p_1, p_2, ..., p_j) 587 Input: 589 p_i - EC point in G 591 Output: 593 h - hash value, integer between 0 and 2^(8n)-1 595 Steps: 597 1. P = "" 599 2. for p_i in [p_1, p_2, ... p_j]: 600 P = P || ECP2OS(p_i) 602 3. h' = Hash(P) 604 4. h = OS2IP(h'[1] || h'[2] || ... h'[n]) 606 5. Output h 608 5.4.3. EC-VRF Decode Proof 610 ECVRF_decode_proof(pi) 612 Input: 614 pi - VRF proof, octet string (5n+1 octets) 616 Output: 618 gamma - EC point 620 c - integer between 0 and 2^(8n)-1 621 s - integer between 0 and 2^(16n)-1 623 Steps: 625 1. let gamma', c', s' be pi split after (2n+1)-th and (3n+1)-th 626 octet 628 2. gamma = OS2ECP(gamma') 630 3. c = OS2IP(c') 632 4. s = OS2IP(s') 634 5. Output gamma, c, and s 636 5.5. EC-VRF Ciphersuites 638 [Seeking feedback on this section!] 640 This document defines EC-VRF-P256-SHA256 as follows: 642 o The EC group G is the NIST-P256 elliptic curve, with curve 643 parameters as specified in [FIPS-186-3] (Section D.1.2.3) and 644 [RFC5114] (Section 2.6). For this group, the length in octets of 645 a single coordinate of an EC point is 2n = 32. 647 o The hash function Hash is SHA-256 as specified in [RFC6234]. 649 o The ECVRF_hash_to_curve function is ECVRF_hash_to_curve1, as 650 specified in Section 5.4.1.1. 652 This document defines EC-VRF-ED25519-SHA256 as follows: 654 o The EC group G is the Ed25519 elliptic curve with parameters 655 defined in [RFC7748] (Section 4.1). For this group, the length in 656 octets of a single coordinate of an EC point is 2n = 32. 658 o The hash function Hash is SHA-256 as specified in [RFC6234]. 660 o The ECVRF_hash_to_curve function is as specified in 661 Section 5.4.1.1. 663 [TODO: Should we add an EC-VRF-ED25519-SHA256-Elligator ciphersuite 664 where the Elligator hash function is used for ECVRF_hash-to-curve?] 666 [TODO: Add an Ed448 ciphersuite?] 668 6. Implementation Status 670 An implementation of the RSA-FDH-VRF (SHA-256) and EC-VRF-P256-SHA256 671 was developed as a part of the NSEC5 project [I-D.vcelak-nsec5] and 672 is available at . 674 The Key Transparency project at Google uses a VRF implemention that 675 is almost identical to the EC-VRF-P256-SHA256 specified here, with a 676 few minor changes including the use of SHA-512 instead of SHA-256. 677 Its implementation is available 678 681 Open Whisper Systems also uses a VRF very similar to EC-VRF- 682 ED25519-SHA512-Elligator, called VXEdDSA, and specified here: 683 685 7. Security Considerations 687 7.1. Key Generation 689 Applications that use the VRFs defined in this document MUST ensure 690 that that the VRF key is generated correctly, using good randomness. 691 Without good randomness, pseudorandomness properties of the VRF may 692 not hold. Also, trusted uniqueness and trusted collision-resistance 693 may also not hold if the keys are generated adversarially (e.g., the 694 RSA modulus is not a product of two primes for the RSA-FDH-VRF or the 695 public key g^x is not valid point in the prime-order group G for the 696 EC). 698 Full uniqueness and full collision-resistance (as opposed to trusted 699 uniqueness and trusted collision-resistance) are properties that hold 700 even if VRF keys are generated by an adversary. The VRFs defined in 701 this document do not have these properties. However, they may be 702 modifed to have these properties if adversarial key generation is a 703 concern. The modification consists of additional cryptographic 704 proofs that keys have of the correct form. These modifications are 705 left for future specification. 707 Note that for the RSA-FDH-VRF, it might be possible to construct such 708 a proof using the [GQ88] identification protocol made non-interactive 709 using the Fiat-Shamir heuristic in the random oracle model. 711 However, it is not possible to guarantee pseudorandomness in the face 712 of adversarially generated VRF keys. This is because an adversary 713 can always use bad randomness to generate the VRF keys, and thus, the 714 VRF output may not be pseudorandom. 716 7.2. Proper randomness for EC-VRF 718 Applications that use the EC-VRF defined in this document MUST ensure 719 that the random nonce k used in the ECVRF_prove algorithm is chosen 720 with proper randomness. Otherwise, an adversary may be able to 721 recover the private VRF key x (and thus break pseudorandomness of the 722 VRF) after observing several valid VRF proofs pi. 724 7.3. Timing attacks 726 The EC-VRF_hash_to_curve algorithm defined in Section 5.4.1.1 should 727 not be used in applications where the VRF input alpha is secret and 728 is hashed by the VRF on-the-fly. This is because the EC- 729 VRF_hash_to_curve algorithm's running time depends on the VRF input 730 alpha, and thus creates a timing channel that can be used to learn 731 information about alpha. 733 7.4. Selective vs Full Pseudorandomness 735 [nsec5ecc] presents cryptographic reductions to an underlying hard 736 problem (e.g. Decisional Diffie Hellman, or the standard RSA 737 assumption) that prove the VRFs specificied in this document possess 738 full pseudorandomness as well as selective pseudorandomness. 739 However, the cryptographic reductions are tighter for selective 740 pseudorandomness than for full pseudorandomness. This means the the 741 VRFs have quantitavely stronger security guarentees for selective 742 pseudorandomness. 744 Applications that are concerned about tightness of cryptographic 745 reductions therefor have two options. 747 o They may choose to ensure that selective pseudorandomness is 748 sufficient for the application. That is, that pseudorandomness of 749 outputs matters only for inputs that are chosen independently of 750 the VRF key. 752 o If full pseudorandomness is required for the application, the 753 application may increase security parameters to make up for the 754 loose security reduction. For RSA-FDH-VRF, this means increasing 755 the RSA key length. For EC-VRF, this means increasing the 756 cryptographic strength of the EC group G. For both RSA-FDH-VRF 757 and EC-VRF the cryptographic strength of the hash function Hash 758 may also potentially need to be increased. 760 8. Change Log 762 Note to RFC Editor: if this document does not obsolete an existing 763 RFC, please remove this appendix before publication as an RFC. 765 00 - Forked this document from draft-vcelak-nsec5-04. Cleaned up 766 the definitions of VRF algorithms. Added security definitions for 767 VRF and security considerations. Parameterized EC-VRF so it could 768 support curves other than P-256 and Ed25519. 770 9. Contributors 772 Leonid Reyzin (Boston University) made major contributions to this 773 document. This document also would not be possible without the work 774 of Moni Naor (Weizmann Institute), Sachin Vasant (Cisco Systems), and 775 Asaf Ziv (Facebook). Shumon Huque (Salesforce) and David C. 776 Lawerence (Akamai) provided valuable input to this draft. 778 10. References 780 10.1. Normative References 782 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 783 Requirement Levels", BCP 14, RFC 2119, 784 DOI 10.17487/RFC2119, March 1997, 785 . 787 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, 788 "PKCS #1: RSA Cryptography Specifications Version 2.2", 789 RFC 8017, DOI 10.17487/RFC8017, November 2016, 790 . 792 [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman 793 Groups for Use with IETF Standards", RFC 5114, 794 DOI 10.17487/RFC5114, January 2008, 795 . 797 [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms 798 (SHA and SHA-based HMAC and HKDF)", RFC 6234, 799 DOI 10.17487/RFC6234, May 2011, 800 . 802 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 803 for Security", RFC 7748, DOI 10.17487/RFC7748, January 804 2016, . 806 [I-D.vcelak-nsec5] 807 Vcelak, J., Goldberg, S., Papadopoulos, D., Huque, S., and 808 D. Lawrence, "NSEC5, DNSSEC Authenticated Denial of 809 Existence", draft-vcelak-nsec5-04 (work in progress), 810 March 2017. 812 [FIPS-186-3] 813 National Institute for Standards and Technology, "Digital 814 Signature Standard (DSS)", FIPS PUB 186-3, June 2009. 816 [SECG1] Standards for Efficient Cryptography Group (SECG), "SEC 1: 817 Elliptic Curve Cryptography", Version 2.0, May 2009, 818 . 820 10.2. Informative References 822 [nsec5ecc] 823 Papadopoulos, D., Wessels, D., Huque, S., Vcelak, J., 824 Naor, M., Reyzin, L., and S. Goldberg, "NSEC5 from 825 Elliptic Curves", in ePrint Cryptology Archive 2017/099, 826 February 2017, . 828 [MRV99] Michali, S., Rabin, M., and S. Vadhan, "Verifiable Random 829 Functions", in FOCS, 1999. 831 [CP92] Chaum, D. and C. Pederson, "Wallet databases with 832 observers", in FOCS, 1992. 834 [Icart09] Icart, T., "How to Hash into Elliptic Curves", in CRYPTO, 835 2009. 837 [GQ88] Guillou, L. and JJ. Quisquater, "A Practical Zero- 838 Knowledge Protocol Fitted to Security Microprocessor 839 Minimizing Both Transmission and Memory", in Advances in 840 Cryptology - EUROCRYPT '88, 1988. 842 Appendix A. Open Issues 844 Note to RFC Editor: please remove this appendix before publication as 845 an RFC. 847 1. Open issues 849 Authors' Addresses 851 Sharon Goldberg 852 Boston University 853 111 Cummington St, MCS135 854 Boston, MA 02215 855 USA 857 EMail: goldbe@cs.bu.edu 859 Dimitrios Papadopoulos 860 University of Maryland 861 8223 Paint Branch Dr 862 College Park, MD 20740 863 USA 865 EMail: dipapado@bu.edu 867 Jan Vcelak 868 NS1 869 16 Beaver St 870 New York, NY 10004 871 USA 873 EMail: jvcelak@ns1.com