idnits 2.17.00 (12 Aug 2021) /tmp/idnits10578/draft-irtf-cfrg-vrf-11.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 document date (6 February 2022) is 97 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: '32' on line 957 -- Looks like a reference, but probably isn't: '63' on line 957 == Missing Reference: 'P1' is mentioned on line 982, but not defined == Missing Reference: 'P2' is mentioned on line 982, but not defined == Missing Reference: 'P3' is mentioned on line 982, but not defined == Missing Reference: 'P4' is mentioned on line 982, but not defined == Missing Reference: 'P5' is mentioned on line 982, but not defined -- Looks like a reference, but probably isn't: '0' on line 1215 -- Looks like a reference, but probably isn't: '31' on line 1215 -- Looks like a reference, but probably isn't: '1' on line 1103 -- Looks like a reference, but probably isn't: '2' on line 1098 -- Looks like a reference, but probably isn't: '3' on line 1098 -- Looks like a reference, but probably isn't: '4' on line 1101 -- Looks like a reference, but probably isn't: '5' on line 1102 -- Looks like a reference, but probably isn't: '6' on line 1102 ** 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 8032 ** Downref: Normative reference to an Informational RFC: RFC 6979 == Outdated reference: A later version (-14) exists of draft-irtf-cfrg-hash-to-curve-13 ** Downref: Normative reference to an Informational draft: draft-irtf-cfrg-hash-to-curve (ref. 'I-D.irtf-cfrg-hash-to-curve') -- Possible downref: Non-RFC (?) normative reference: ref. 'FIPS-186-4' -- Possible downref: Non-RFC (?) normative reference: ref. 'SECG1' Summary: 7 errors (**), 0 flaws (~~), 6 warnings (==), 13 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CFRG S. Goldberg 3 Internet-Draft Boston University 4 Intended status: Standards Track L. Reyzin 5 Expires: 10 August 2022 Boston University and Algorand 6 D. Papadopoulos 7 Hong Kong University of Science and Technology 8 J. Vcelak 9 NS1 10 6 February 2022 12 Verifiable Random Functions (VRFs) 13 draft-irtf-cfrg-vrf-11 15 Abstract 17 A Verifiable Random Function (VRF) is the public-key version of a 18 keyed cryptographic hash. Only the holder of the private key can 19 compute the hash, but anyone with the public key can verify the 20 correctness of the hash. VRFs are useful for preventing enumeration 21 of hash-based data structures. This document specifies several VRF 22 constructions based on RSA and Elliptic Curves that are secure in the 23 cryptographic random oracle model. 25 Status of This Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at https://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on 10 August 2022. 42 Copyright Notice 44 Copyright (c) 2022 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 49 license-info) in effect on the date of publication of this document. 50 Please review these documents carefully, as they describe your rights 51 and restrictions with respect to this document. Code Components 52 extracted from this document must include Revised BSD License text as 53 described in Section 4.e of the Trust Legal Provisions and are 54 provided without warranty as described in the Revised BSD License. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 59 1.1. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 3 60 1.2. Requirements . . . . . . . . . . . . . . . . . . . . . . 3 61 1.3. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 62 2. VRF Algorithms . . . . . . . . . . . . . . . . . . . . . . . 4 63 3. VRF Security Properties . . . . . . . . . . . . . . . . . . . 5 64 3.1. Full Uniqueness or Trusted Uniqueness . . . . . . . . . . 5 65 3.2. Full Collison Resistance or Trusted Collision 66 Resistance . . . . . . . . . . . . . . . . . . . . . . . 5 67 3.3. Full Pseudorandomness or Selective Pseudorandomness . . . 6 68 3.4. Some VRFs: Unpredictability Under Malicious Key 69 Generation . . . . . . . . . . . . . . . . . . . . . . . 7 70 4. RSA Full Domain Hash VRF (RSA-FDH-VRF) . . . . . . . . . . . 7 71 4.1. RSA-FDH-VRF Proving . . . . . . . . . . . . . . . . . . . 9 72 4.2. RSA-FDH-VRF Proof to Hash . . . . . . . . . . . . . . . . 9 73 4.3. RSA-FDH-VRF Verifying . . . . . . . . . . . . . . . . . . 10 74 4.4. RSA-FDH-VRF Ciphersuites . . . . . . . . . . . . . . . . 11 75 5. Elliptic Curve VRF (ECVRF) . . . . . . . . . . . . . . . . . 11 76 5.1. ECVRF Proving . . . . . . . . . . . . . . . . . . . . . . 14 77 5.2. ECVRF Proof to Hash . . . . . . . . . . . . . . . . . . . 15 78 5.3. ECVRF Verifying . . . . . . . . . . . . . . . . . . . . . 15 79 5.4. ECVRF Auxiliary Functions . . . . . . . . . . . . . . . . 17 80 5.4.1. ECVRF Encode to Curve . . . . . . . . . . . . . . . . 17 81 5.4.2. ECVRF Nonce Generation . . . . . . . . . . . . . . . 19 82 5.4.3. ECVRF Challenge Generation . . . . . . . . . . . . . 21 83 5.4.4. ECVRF Decode Proof . . . . . . . . . . . . . . . . . 21 84 5.4.5. ECVRF Validate Key . . . . . . . . . . . . . . . . . 22 85 5.5. ECVRF Ciphersuites . . . . . . . . . . . . . . . . . . . 24 86 6. Implementation Status . . . . . . . . . . . . . . . . . . . . 26 87 7. Security Considerations . . . . . . . . . . . . . . . . . . . 27 88 7.1. Key Generation . . . . . . . . . . . . . . . . . . . . . 28 89 7.1.1. Uniqueness and collision resistance with untrusted 90 keys . . . . . . . . . . . . . . . . . . . . . . . . 28 91 7.1.2. Pseudorandomness with untrusted keys . . . . . . . . 28 92 7.2. Security Levels . . . . . . . . . . . . . . . . . . . . . 28 93 7.3. Selective vs. Full Pseudorandomness . . . . . . . . . . . 29 94 7.4. Proper pseudorandom nonce for ECVRF . . . . . . . . . . . 30 95 7.5. Side-channel attacks . . . . . . . . . . . . . . . . . . 30 96 7.6. Proofs provide no secrecy for the VRF input . . . . . . . 31 97 7.7. Prehashing . . . . . . . . . . . . . . . . . . . . . . . 31 98 7.8. Hash function domain separation . . . . . . . . . . . . . 31 99 7.9. Hash function salting . . . . . . . . . . . . . . . . . . 32 100 7.10. Futureproofing . . . . . . . . . . . . . . . . . . . . . 32 101 8. Change Log . . . . . . . . . . . . . . . . . . . . . . . . . 33 102 9. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 34 103 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 34 104 10.1. Normative References . . . . . . . . . . . . . . . . . . 34 105 10.2. Informative References . . . . . . . . . . . . . . . . . 36 106 Appendix A. Test Vectors for the ECVRFs . . . . . . . . . . . . 37 107 A.1. ECVRF-P256-SHA256-TAI . . . . . . . . . . . . . . . . . . 37 108 A.2. ECVRF-P256-SHA256-SSWU . . . . . . . . . . . . . . . . . 38 109 A.3. ECVRF-EDWARDS25519-SHA512-TAI . . . . . . . . . . . . . . 40 110 A.4. ECVRF-EDWARDS25519-SHA512-ELL2 . . . . . . . . . . . . . 42 111 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 44 113 1. Introduction 115 1.1. Rationale 117 A Verifiable Random Function (VRF) [MRV99] is the public-key version 118 of a keyed cryptographic hash. Only the holder of the private VRF 119 key can compute the hash, but anyone with the corresponding public 120 key can verify the correctness of the hash. 122 A key application of the VRF is to provide privacy against offline 123 dictionary attacks (also known as enumeration attacks) on data stored 124 in a hash-based data structure. In this application, a Prover holds 125 the VRF private key and uses the VRF hashing to construct a hash- 126 based data structure on the input data. Due to the nature of the 127 VRF, only the Prover can answer queries about whether or not some 128 data is stored in the data structure. Anyone who knows the public 129 VRF key can verify that the Prover has answered the queries 130 correctly. However, no offline inferences (i.e. inferences without 131 querying the Prover) can be made about the data stored in the data 132 structure. 134 1.2. Requirements 136 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 137 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 138 document are to be interpreted as described in [RFC2119]. 140 1.3. Terminology 142 The following terminology is used through this document: 144 SK: The private key for the VRF. 146 PK: The public key for the VRF. 148 alpha or alpha_string: The input to be hashed by the VRF. 150 beta or beta_string: The VRF hash output. 152 pi or pi_string: The VRF proof. 154 Prover: The Prover holds the private VRF key SK and public VRF key 155 PK. 157 Verifier: The Verifier holds the public VRF key PK. 159 2. VRF Algorithms 161 A VRF comes with a key generation algorithm that generates a public 162 VRF key PK and private VRF key SK. 164 The prover hashes an input alpha using the private VRF key SK to 165 obtain a VRF hash output beta 167 beta = VRF_hash(SK, alpha) 169 The VRF_hash algorithm is deterministic, in the sense that it always 170 produces the same output beta given the same pair of inputs (SK, 171 alpha). The prover also uses the private key SK to construct a proof 172 pi that beta is the correct hash output 174 pi = VRF_prove(SK, alpha) 176 The VRFs defined in this document allow anyone to deterministically 177 obtain the VRF hash output beta directly from the proof value pi by 178 using the function VRF_proof_to_hash: 180 beta = VRF_proof_to_hash(pi) 182 Thus, for VRFs defined in this document, VRF_hash is defined as 184 VRF_hash(SK, alpha) = VRF_proof_to_hash(VRF_prove(SK, alpha)), 186 and therefore this document will specify VRF_prove and 187 VRF_proof_to_hash rather than VRF_hash. 189 The proof pi allows a Verifier holding the public key PK to verify 190 that beta is the correct VRF hash of input alpha under key PK. Thus, 191 the VRFs defined in this document also come with an algorithm 193 VRF_verify(PK, alpha, pi) 195 that outputs (VALID, beta = VRF_proof_to_hash(pi)) if pi is valid, 196 and INVALID otherwise. 198 3. VRF Security Properties 200 VRFs are designed to ensure the following security properties. 202 3.1. Full Uniqueness or Trusted Uniqueness 204 Uniqueness means that, for any fixed public VRF key and for any input 205 alpha, there is a unique VRF output beta that can be proved to be 206 valid. Uniqueness must hold even for an adversarial Prover that 207 knows the VRF private key SK. 209 More precisely, "full uniqueness" states that a computationally- 210 bounded adversary cannot choose a VRF public key PK, a VRF input 211 alpha, and two proofs pi1 and pi2 such that VRF_verify(PK, alpha, 212 pi1) outputs (VALID, beta1), VRF_verify(PK, alpha, pi2) outputs 213 (VALID, beta2), and beta1 is not equal to beta2. 215 For many applications, a slightly weaker security property called 216 "trusted uniqueness" suffices. Trusted uniqueness is the same as 217 full uniqueness, but it is guaranteed to hold only if the VRF keys PK 218 and SK were generated in a trustworthy manner. 220 As further discussed in Section 7.1.1, some VRFs specified in this 221 document satisfy only trusted uniqueness, while others satisfy full 222 uniqueness. VRFs in this document that satisfy only trusted 223 uniqueness but not full uniqueness MUST NOT be used if the key 224 generation process cannot be trusted. 226 3.2. Full Collison Resistance or Trusted Collision Resistance 228 Like any cryptographic hash function, VRFs need to be collision 229 resistant. Collison resistance must hold even for an adversarial 230 Prover that knows the VRF private key SK. 232 More precisely, "full collision resistance" states that it should be 233 computationally infeasible for an adversary to find two distinct VRF 234 inputs alpha1 and alpha2 that have the same VRF hash beta, even if 235 that adversary knows the private VRF key SK. 237 For many applications, a slightly weaker security property called 238 "trusted collision resistance" suffices. Trusted collision 239 resistance is the same as collision resistance, but it is guaranteed 240 to hold only if the VRF keys PK and SK were generated in a 241 trustworthy manner. 243 As further discussed in Section 7.1.1, some VRFs specified in this 244 document satisfy only trusted collision resistance, while others 245 satisfy full collision resistance. VRFs in this document that 246 satisfy only trusted collision resistance but not full collision 247 resistance MUST NOT be used if the key generation process cannot be 248 trusted. 250 3.3. Full Pseudorandomness or Selective Pseudorandomness 252 Pseudorandomness ensures that when an adversarial Verifier sees a VRF 253 hash output beta without its corresponding VRF proof pi, then beta is 254 indistinguishable from a random value. 256 More precisely, suppose the public and private VRF keys (PK, SK) were 257 generated in a trustworthy manner. Pseudorandomness ensures that the 258 VRF hash output beta (without its corresponding VRF proof pi) on any 259 adversarially-chosen "target" VRF input alpha looks indistinguishable 260 from random for any computationally bounded adversary who does not 261 know the private VRF key SK. This holds even if the adversary also 262 gets to choose other VRF inputs alpha' and observe their 263 corresponding VRF hash outputs beta' and proofs pi'. 265 With "full pseudorandomness", the adversary is allowed to choose the 266 "target" VRF input alpha at any time, even after it observes VRF 267 outputs beta' and proofs pi' on a variety of chosen inputs alpha'. 269 "Selective pseudorandomness" is a weaker security property which 270 suffices in many applications. Here, the adversary must choose the 271 target VRF input alpha independently of the public VRF key PK, and 272 before it observes VRF outputs beta' and proofs pi' on inputs alpha' 273 of its choice. 275 As further discussed in Section 7.3, VRFs specified in this document 276 satisfy both full pseudorandomness and selective pseudorandomness, 277 but their quantitative security against the selective 278 pseudorandomness attack is stronger. 280 It is important to remember that the VRF output beta does not look 281 random to the Prover, or to any other party that knows the private 282 VRF key SK! Such a party can easily distinguish beta from a random 283 value by comparing beta to the result of VRF_hash(SK, alpha). 285 Also, the VRF output beta does not look random to any party that 286 knows a valid VRF proof pi corresponding to the VRF input alpha, even 287 if this party does not know the private VRF key SK. Such a party can 288 easily distinguish beta from a random value by checking whether 289 VRF_verify(PK, alpha, pi) returns (VALID, beta). 291 Also, the VRF output beta may not look random if VRF key generation 292 was not done in a trustworthy fashion. (For example, if VRF keys 293 were generated with bad randomness.) 295 3.4. Some VRFs: Unpredictability Under Malicious Key Generation 297 As explained in Section 3.3, pseudorandomness is guaranteed only if 298 the VRF keys were generated in a trustworthy fashion. For instance, 299 if an adversary outputs VRF keys that are deterministically generated 300 (or hard-coded and publicly known), then the outputs are easily 301 derived by anyone and are therefore not pseudorandom. 303 There is, however, a different type of unpredictability that is 304 desirable in certain VRF applications (such as leader selection in 305 the consensus protocols of [GHMVZ17] and [DGKR18]), called 306 "unpredictability under malicious key generation". This property is 307 similar to the unpredictability achieved by an (ordinary, unkeyed) 308 cryptographic hash function: if the input has enough entropy (i.e., 309 cannot be predicted), then the correct output is indistinguishable 310 from uniform, no matter how the VRF keys are generated. 312 A formal definition of this property appears in Section 3.2 of 313 [DGKR18]. The RSA-FDH-VRF presented in this document does not 314 satisfy this property. The ECVRF presented in this document 315 satisfies this property if validate_key parameter given to the 316 ECVRF_verify is TRUE. 318 4. RSA Full Domain Hash VRF (RSA-FDH-VRF) 320 The RSA Full Domain Hash VRF (RSA-FDH-VRF) is a VRF that, for 321 suitable key lengths, satisfies the "trusted uniqueness", "trusted 322 collision resistance", and "full pseudorandomness" properties defined 323 in Section 3, as further discussed in Section 7. Its security 324 follows from the standard RSA assumption in the random oracle model. 325 Formal security proofs are in [PWHVNRG17]. 327 The VRF computes the proof pi as a deterministic RSA signature on 328 input alpha using the RSA Full Domain Hash Algorithm [RFC8017] 329 parametrized with the selected hash algorithm. RSA signature 330 verification is used to verify the correctness of the proof. The VRF 331 hash output beta is simply obtained by hashing the proof pi with the 332 selected hash algorithm. 334 The key pair for RSA-FDH-VRF MUST be generated in a way that it 335 satisfies the conditions specified in Section 3 of [RFC8017]. 337 In this section, the notation from [RFC8017] is used. 339 Parameters used: 341 (n, e) - RSA public key 343 K - RSA private key (its representation is implementation- 344 dependent) 346 k - length in octets of the RSA modulus n (k must be less than 347 2^32) 349 Fixed options (specified in Section 4.4): 351 Hash - cryptographic hash function 353 hLen - output length in octets of hash function Hash 355 suite_string - an octet string specifying the RSA-FDH-VRF 356 ciphersuite, which determines the above options 358 Primitives used: 360 I2OSP - Conversion of a nonnegative integer to an octet string as 361 defined in Section 4.1 of [RFC8017] (given an integer and a length 362 in octets, produces a big-endian representation of the integer, 363 zero-padded to the desired length) 365 OS2IP - Conversion of an octet string to a nonnegative integer as 366 defined in Section 4.2 of [RFC8017] (given a big-endian encoding 367 of an integer, produces the integer) 369 RSASP1 - RSA signature primitive as defined in Section 5.2.1 of 370 [RFC8017] (given a private key and an input, raises the input to 371 the private RSA exponent modulo n) 373 RSAVP1 - RSA verification primitive as defined in Section 5.2.2 of 374 [RFC8017] (given a public key and an input, raises the input to 375 the public RSA exponent modulo n) 377 MGF1 - Mask Generation Function based on the hash function Hash as 378 defined in Section B.2.1 of [RFC8017] (given an input, produces a 379 random-oracle-like output of desired length) 381 || - octet string concatenation 383 4.1. RSA-FDH-VRF Proving 385 RSAFDHVRF_prove(K, alpha_string[, MGF_salt]) 387 Input: 389 K - RSA private key 391 alpha_string - VRF hash input, an octet string 393 Optional Input: 395 MGF_salt - a public octet string used as a hash function salt; 396 this input is not used when MGF_salt is specified as part of the 397 ciphersuite 399 Output: 401 pi_string - proof, an octet string of length k 403 Steps: 405 1. mgf_domain_separator = 0x01 407 2. EM = MGF1(suite_string || mgf_domain_separator || MGF_salt || 408 alpha_string, k - 1) 410 3. m = OS2IP(EM) 412 4. s = RSASP1(K, m) 414 5. pi_string = I2OSP(s, k) 416 6. Output pi_string 418 4.2. RSA-FDH-VRF Proof to Hash 420 RSAFDHVRF_proof_to_hash(pi_string) 422 Input: 424 pi_string - proof, an octet string of length k 426 Output: 428 beta_string - VRF hash output, an octet string of length hLen 430 Important note: 432 RSAFDHVRF_proof_to_hash should be run only on pi_string that is 433 known to have been produced by RSAFDHVRF_prove, or from within 434 RSAFDHVRF_verify as specified in Section 4.3. 436 Steps: 438 1. proof_to_hash_domain_separator = 0x02 440 2. beta_string = Hash(suite_string || 441 proof_to_hash_domain_separator || pi_string) 443 3. Output beta_string 445 4.3. RSA-FDH-VRF Verifying 447 RSAFDHVRF_verify((n, e), alpha_string, pi_string[, MGF_salt]) 449 Input: 451 (n, e) - RSA public key 453 alpha_string - VRF hash input, an octet string 455 pi_string - proof to be verified, an octet string of length k 457 Optional Input: 459 MGF_salt - a public octet string used as a hash function salt; 460 this input is not used when MGF_salt is specified as part of the 461 ciphersuite 463 Output: 465 Output: 467 ("VALID", beta_string), where beta_string is the VRF hash output, 468 an octet string of length hLen; or 470 "INVALID" 472 Steps: 474 1. s = OS2IP(pi_string) 476 2. m = RSAVP1((n, e), s); if RSAVP1 returns "signature 477 representative out of range", output "INVALID" and stop. 479 3. mgf_domain_separator = 0x01 480 4. EM' = MGF1(suite_string || mgf_domain_separator || MGF_salt || 481 alpha_string, k - 1) 483 5. m' = OS2IP(EM') 485 6. If m and m' are equal, output ("VALID", 486 RSAFDHVRF_proof_to_hash(pi_string)); else output "INVALID". 488 4.4. RSA-FDH-VRF Ciphersuites 490 This document defines RSA-FDH-VRF-SHA256 as follows: 492 * suite_string = 0x01 494 * The hash function Hash is SHA-256 as specified in [RFC6234], with 495 hLen = 32 497 * MGF_salt = I2OSP(k, 4) || I2OSP(n, k) 499 This document defines RSA-FDH-VRF-SHA384 as follows: 501 * suite_string = 0x02 503 * The hash function Hash is SHA-384 as specified in [RFC6234], with 504 hLen = 48 506 * MGF_salt = I2OSP(k, 4) || I2OSP(n, k) 508 This document defines RSA-FDH-VRF-SHA512 as follows: 510 * suite_string = 0x03 512 * The hash function Hash is SHA-512 as specified in [RFC6234], with 513 hLen = 64 515 * MGF_salt = I2OSP(k, 4) || I2OSP(n, k) 517 5. Elliptic Curve VRF (ECVRF) 519 The Elliptic Curve Verifiable Random Function (ECVRF) is a VRF that, 520 for suitable parameter choices, satisfies the "full uniqueness", 521 "trusted collision resistance", and "full pseudorandomness 522 properties" defined in Section 3. If validate_key parameter given to 523 the ECVRF_verify is TRUE, then the ECVRF additionally satisfies "full 524 collision resistance" and "unpredictability under malicious key 525 generation". See Section 7 for further discussion. Formal security 526 proofs are in [PWHVNRG17]. 528 Notation used: 530 Elliptic curve operations are written in additive notation, with 531 P+Q denoting point addition and x*P denoting scalar multiplication 532 of a point P by a scalar x 534 x^y - x raised to the power y 536 x*y - x multiplied by y 538 s || t - concatenation of octet strings s and t 540 0xMN (where M and N are hexadecimal digits) - a single octet with 541 value M*16+N; equivalently, int_to_string(M*16+N, 1), where 542 int_to_string is as defined below. 544 Fixed options (specified in Section 5.5): 546 F - finite field 548 fLen - length, in octets, of an element in F encoded as an octet 549 string 551 E - elliptic curve (EC) defined over F 553 ptLen - length, in octets, of a point on E encoded as an octet 554 string 556 G - subgroup of E of large prime order 558 q - prime order of group G 560 qLen - length of q in octets, i.e., smallest integer such that 561 2^(8qLen)>q 563 cLen - length, in octets, of a challenge value used by the VRF 564 (note that in the typical case, cLen is qLen/2 or close to it) 566 cofactor - number of points on E divided by q 568 B - generator of group G 570 Hash - cryptographic hash function 572 hLen - output length in octets of Hash (hLen must be at least 573 cLen; in the typical case, it is at least qLen) 574 ECVRF_encode_to_curve - a function that hashes strings to points 575 on E. 577 ECVRF_nonce_generation - a function that derives a pseudorandom 578 nonce from SK and the input as part of ECVRF proving. 580 suite_string - an octet string specifying the ECVRF ciphersuite, 581 which determines the above options as well as type conversions and 582 parameter generation 584 Type conversions (specified in Section 5.5): 586 int_to_string(a, len) - conversion of nonnegative integer a to 587 octet string of length len 589 string_to_int(a_string) - conversion of an octet string a_string 590 to a nonnegative integer 592 point_to_string - conversion of a point on E to an ptLen-octet 593 string 595 string_to_point - conversion of an ptLen-octet string to a point 596 on E. string_to_point returns INVALID if the octet string does 597 not convert to a valid EC point on the curve E. 599 Note that with certain software libraries (for big integer and 600 elliptic curve arithmetic), the int_to_string and point_to_string 601 conversions are not needed, when the libraries encode integers and 602 EC points in the same way as required by the ciphersuites. For 603 example, in some implementations, EC point operations will take 604 octet strings as inputs and produce octet strings as outputs, 605 without introducing a separate elliptic curve point type. 607 Parameters used (the generation of these parameters is specified in 608 Section 5.5): 610 SK - VRF private key 612 x - VRF secret scalar, an integer. Note: depending on the 613 ciphersuite used, the VRF secret scalar may be equal to SK; else, 614 it is derived from SK 616 Y = x*B - VRF public key, an point on E 618 PK_string = point_to_string(Y) - VRF public key represented as an 619 octet string 621 encode_to_curve_salt - a public value used as a hash function salt 623 5.1. ECVRF Proving 625 ECVRF_prove(SK, alpha_string[, encode_to_curve_salt]) 627 Input: 629 SK - VRF private key 631 alpha_string - input alpha, an octet string 633 Optional input: 635 encode_to_curve_salt - a public salt value, an octet string; this 636 input is not used when encode_to_curve_salt is specified as part 637 of the ciphersuite 639 Output: 641 pi_string - VRF proof, octet string of length ptLen+cLen+qLen 643 Steps: 645 1. Use SK to derive the VRF secret scalar x and the VRF public key Y 646 = x*B 648 (this derivation depends on the ciphersuite, as per Section 5.5; 650 these values can be cached, for example, after key generation, 651 and need not be rederived each time) 653 2. H = ECVRF_encode_to_curve(encode_to_curve_salt, alpha_string) 654 (see Section 5.4.1) 656 3. h_string = point_to_string(H) 658 4. Gamma = x*H 660 5. k = ECVRF_nonce_generation(SK, h_string) (see Section 5.4.2) 662 6. c = ECVRF_challenge_generation(Y, H, Gamma, k*B, k*H) (see 663 Section 5.4.3) 665 7. s = (k + c*x) mod q 667 8. pi_string = point_to_string(Gamma) || int_to_string(c, cLen) || 668 int_to_string(s, qLen) 670 9. Output pi_string 672 5.2. ECVRF Proof to Hash 674 ECVRF_proof_to_hash(pi_string) 676 Input: 678 pi_string - VRF proof, octet string of length ptLen+cLen+qLen 680 Output: 682 "INVALID", or 684 beta_string - VRF hash output, octet string of length hLen 686 Important note: 688 ECVRF_proof_to_hash should be run only on pi_string that is known 689 to have been produced by ECVRF_prove, or from within ECVRF_verify 690 as specified in Section 5.3. 692 Steps: 694 1. D = ECVRF_decode_proof(pi_string) (see Section 5.4.4) 696 2. If D is "INVALID", output "INVALID" and stop 698 3. (Gamma, c, s) = D 700 4. proof_to_hash_domain_separator_front = 0x03 702 5. proof_to_hash_domain_separator_back = 0x00 704 6. beta_string = Hash(suite_string || 705 proof_to_hash_domain_separator_front || point_to_string(cofactor 706 * Gamma) || proof_to_hash_domain_separator_back) 708 7. Output beta_string 710 5.3. ECVRF Verifying 712 ECVRF_verify(PK_string, alpha_string, pi_string[, 713 encode_to_curve_salt, validate_key]) 715 Input: 717 PK_string - public key, an octet string 719 alpha_string - VRF input, octet string 720 pi_string - VRF proof, octet string of length ptLen+cLen+qLen 722 Optional input: 724 encode_to_curve_salt - a public salt value, an octet string; this 725 input is not used when encode_to_curve_salt is specified as part 726 of the ciphersuite 728 validate_key - a boolean. An implementation MAY support only the 729 option of validate_key = TRUE, or only the option of validate_key 730 = FALSE, in which case this input is not needed. If an 731 implementation supports only one option, it MUST specify which 732 option is supports. 734 Output: 736 ("VALID", beta_string), where beta_string is the VRF hash output, 737 octet string of length hLen; or 739 "INVALID" 741 Steps: 743 1. Y = string_to_point(PK_string) 745 2. If Y is "INVALID", output "INVALID" and stop 747 3. If validate_key, run ECVRF_validate_key(Y) (Section 5.4.5); if 748 it outputs "INVALID", output "INVALID" and stop 750 4. D = ECVRF_decode_proof(pi_string) (see Section 5.4.4) 752 5. If D is "INVALID", output "INVALID" and stop 754 6. (Gamma, c, s) = D 756 7. H = ECVRF_encode_to_curve(encode_to_curve_salt, alpha_string) 757 (see Section 5.4.1) 759 8. U = s*B - c*Y 761 9. V = s*H - c*Gamma 763 10. c' = ECVRF_challenge_generation(Y, H, Gamma, U, V) (see 764 Section 5.4.3) 766 11. If c and c' are equal, output ("VALID", 767 ECVRF_proof_to_hash(pi_string)); else output "INVALID" 769 Note that the first three steps need to be performed only once for a 770 given public key. 772 5.4. ECVRF Auxiliary Functions 774 5.4.1. ECVRF Encode to Curve 776 The ECVRF_encode_to_curve algorithm takes a public salt (see 777 Section 7.9) and the VRF input alpha and converts it to H, an EC 778 point in G. This algorithm is the only place the VRF input alpha is 779 used for proving and verifying. See Section 7.7 for further 780 discussion. 782 This section specifies a number of such algorithms, which are not 783 compatible with each other and are intended to use with various 784 ciphersuites specified in Section 5.5. 786 Input: 788 encode_to_curve_salt - public salt value, an octet string 790 alpha_string - value to be hashed, an octet string 792 Output: 794 H - hashed value, a point in G 796 5.4.1.1. ECVRF_encode_to_curve_try_and_increment 798 The following 799 ECVRF_encode_to_curve_try_and_increment(encode_to_curve_salt, 800 alpha_string) algorithm implements ECVRF_encode_to_curve in a simple 801 and generic way that works for any elliptic curve. To use this 802 algorithm, hLen MUST be at least fLen. 804 The running time of this algorithm depends on alpha_string. For the 805 ciphersuites specified in Section 5.5, this algorithm is expected to 806 find a valid curve point after approximately two attempts (i.e., when 807 ctr=1) on average. 809 However, because the running time of algorithm depends on 810 alpha_string, this algorithm SHOULD be avoided in applications where 811 it is important that the VRF input alpha remain secret. 813 ECVRF_encode_to_curve_try_and_increment(encode_to_curve_salt, 814 alpha_string) 816 Fixed option (specified in Section 5.5): 818 interpret_hash_value_as_a_point - a function that attempts to 819 convert a cryptographic hash value to a point on E; may output 820 INVALID. 822 Steps: 824 1. ctr = 0 826 2. encode_to_curve_domain_separator_front = 0x01 828 3. encode_to_curve_domain_separator_back = 0x00 830 4. H = "INVALID" 832 5. While H is "INVALID" or H is the identity element of the elliptic 833 curve group: 835 a. ctr_string = int_to_string(ctr, 1) 837 b. hash_string = Hash(suite_string || 838 encode_to_curve_domain_separator_front || 839 encode_to_curve_salt || alpha_string || ctr_string || 840 encode_to_curve_domain_separator_back) 842 c. H = interpret_hash_value_as_a_point(hash_string) 844 d. If H is not "INVALID" and cofactor > 1, set H = cofactor * H 846 e. ctr = ctr + 1 848 6. Output H 850 Note even though the loop is infinite as written, and 851 int_to_string(ctr,1) may fail when ctr reaches 256, 852 interpret_hash_value_as_a_point functions specified in Section 5.5 853 will succeed on roughly half hash_string values. Thus the loop is 854 expected to stop after two iterations, and ctr is overwhelmingly 855 unlikely (probability about 2^-256) to reach 256. 857 5.4.1.2. ECVRF_encode_to_curve_h2c_suite 859 The ECVRF_encode_to_curve_h2c_suite(encode_to_curve_salt, 860 alpha_string) algorithm implements ECVRF_encode_to_curve using one of 861 the several hash-to-curve options defined in 862 [I-D.irtf-cfrg-hash-to-curve]. The specific choice of the hash-to- 863 curve option (called Suite ID in [I-D.irtf-cfrg-hash-to-curve]) is 864 given by the h2c_suite_ID_string parameter. 866 ECVRF_encode_to_curve_h2c_suite(encode_to_curve_salt, alpha_string) 868 Fixed option (specified in Section 5.5): 870 h2c_suite_ID_string - a hash-to-curve suite ID, encoded in ASCII 871 (see discussion below) 873 Steps: 875 1. string_to_be_hashed = encode_to_curve_salt || alpha_string 877 2. H = encode(string_to_be_hashed) 879 (the encode function is discussed below) 881 3. Output H 883 The encode function is provided by the hash-to-curve suite whose ID 884 is h2c_suite_ID_string, as specified in 885 [I-D.irtf-cfrg-hash-to-curve], Section 8. The domain separation tag 886 DST, a parameter to the hash-to-curve suite, SHALL be set to 888 "ECVRF_" || h2c_suite_ID_string || suite_string 890 where "ECVRF_" is represented as a 6-byte ASCII encoding (in 891 hexadecimal, octets 45 43 56 52 46 5F). 893 5.4.2. ECVRF Nonce Generation 895 The following algorithms generate the nonce value k in a 896 deterministic pseudorandom fashion. This section specifies a number 897 of such algorithms, which are not compatible with each other. The 898 choice of a particular algorithm from the options specified in this 899 section depends on the ciphersuite, as specified in Section 5.5. 901 5.4.2.1. ECVRF Nonce Generation from RFC 6979 903 ECVRF_nonce_generation_RFC6979(SK, h_string) 905 Input: 907 SK - an ECVRF secret key 909 h_string - an octet string 911 Output: 913 k - an integer nonce between 1 and q-1 915 The ECVRF_nonce_generation function is as specified in [RFC6979] 916 Section 3.2 where 918 Input m is set equal to h_string 920 The "suitable for DSA or ECDSA" check in step h.3 is omitted 922 The hash function H is Hash and its output length hlen (in bits) 923 is set as hLen*8 925 The secret key x is set equal to the VRF secret scalar x 927 The prime q is the same as in this specification 929 qlen is the binary length of q, i.e., the smallest integer such 930 that 2^qlen > q (this qlen is not to be confused with qLen in this 931 document, which is the length of q in octets) 933 All the other values and primitives as defined in [RFC6979] 935 5.4.2.2. ECVRF Nonce Generation from RFC 8032 937 The following is from Steps 2-3 of Section 5.1.6 in [RFC8032]. To 938 use this algorithm, hLen MUST be at least 64. 940 ECVRF_nonce_generation_RFC8032(SK, h_string) 942 Input: 944 SK - an ECVRF secret key 946 h_string - an octet string 948 Output: 950 k - an integer nonce between 0 and q-1 952 Steps: 954 1. hashed_sk_string = Hash(SK) 956 2. truncated_hashed_sk_string = 957 hashed_sk_string[32]...hashed_sk_string[63] 959 3. k_string = Hash(truncated_hashed_sk_string || h_string) 961 4. k = string_to_int(k_string) mod q 963 5.4.3. ECVRF Challenge Generation 965 ECVRF_challenge_generation(P1, P2, P3, P4, P5) 967 Input: 969 P1, P2, P3, P4, P5 - EC points 971 Output: 973 c - challenge value, integer between 0 and 2^(8*cLen)-1 975 Steps: 977 1. challenge_generation_domain_separator_front = 0x02 979 2. Initialize str = suite_string || 980 challenge_generation_domain_separator_front 982 3. for PJ in [P1, P2, P3, P4, P5]: 984 str = str || point_to_string(PJ) 986 4. challenge_generation_domain_separator_back = 0x00 988 5. str = str || challenge_generation_domain_separator_back 990 6. c_string = Hash(str) 992 7. truncated_c_string = c_string[0]...c_string[cLen-1] 994 8. c = string_to_int(truncated_c_string) 996 9. Output c 998 5.4.4. ECVRF Decode Proof 1000 ECVRF_decode_proof(pi_string) 1002 Input: 1004 pi_string - VRF proof, octet string (ptLen+cLen+qLen octets) 1006 Output: 1008 "INVALID", or 1010 Gamma - a point on E 1011 c - integer between 0 and 2^(8*cLen)-1 1013 s - integer between 0 and q-1 1015 Steps: 1017 1. gamma_string = pi_string[0]...pi_string[ptLen-1] 1019 2. c_string = pi_string[ptLen]...pi_string[ptLen+cLen-1] 1021 3. s_string = pi_string[ptLen+cLen]...pi_string[ptLen+cLen+qLen-1] 1023 4. Gamma = string_to_point(gamma_string) 1025 5. if Gamma = "INVALID" output "INVALID" and stop 1027 6. c = string_to_int(c_string) 1029 7. s = string_to_int(s_string) 1031 8. if s >= q output "INVALID" and stop 1033 9. Output Gamma, c, and s 1035 5.4.5. ECVRF Validate Key 1037 ECVRF_validate_key(Y) 1039 Input: 1041 Y - public key, a point on E 1043 Output: 1045 "VALID" or "INVALID" 1047 Important note: the public key Y given to this procedure MUST be a 1048 valid point on E. 1050 Steps: 1052 1. Let Y' = cofactor*Y 1054 2. If Y' is the identity element of the elliptic curve group, output 1055 "INVALID" and stop 1057 3. Output "VALID" 1058 Note that if the cofactor = 1, then Step 1 simply sets Y'=Y. In 1059 particular, for the P-256 curve, ECVRF_validate_key simply ensures 1060 that Y is not the point at infinity. 1062 Also note that if the cofactor is small, the total number of Y values 1063 that could cause Step 2 to output "INVALID" may be small, and it may 1064 be more efficient to simply check Y against a fixed list of such 1065 points. For example, the following algorithm can be used for the 1066 edwards25519 curve: 1068 1. PK_string = point_to_string(Y) 1070 2. oneTwentySeven_string = 0x7F 1072 3. y_string[31] = y_string[31] & oneTwentySeven_string 1074 (this step clears the high-order bit of octet 31) 1076 4. bad_pk[0] = int_to_string(0, 32) 1078 5. bad_pk[1] = int_to_string(1, 32) 1080 6. bad_y2 = 2707385501144840649318225287225658788936804267575313519 1081 463743609750303402022 1083 7. bad_pk[2] = int_to_string(bad_y2, 32) 1085 8. bad_pk[3] = int_to_string(p-bad_y2, 32) 1087 9. bad_pk[4] = int_to_string(p-1, 32) 1089 10. bad_pk[5] = int_to_string(p, 32) 1091 11. bad_pk[6] = int_to_string(p+1, 32) 1093 12. If y_string is in the list [bad_pk[0],...,bad_pk[6]], output 1094 "INVALID" and stop 1096 13. Output Y 1098 (bad_pk[0], bad_pk[2], bad_pk[3] each match two bad public keys, 1099 depending on the sign of the x-coordinate, which was cleared in step 1100 5, in order to make sure that it does not affect the comparison. 1101 bad_pk[1] and bad_pk[4] each match one bad public key, because 1102 x-coordinate is 0 for these two public keys. bad_pk[5] and bad_pk[6] 1103 are simply bad_pk[0] and bad_pk[1] shifted by p, in case the 1104 y-coordinate had not been modular reduced by p. There is no need to 1105 shift the other bad_pk values by p, because they will exceed 2^255. 1107 These bad keys, which represent all points of order 1, 2, 4, and 8, 1108 have been obtained by converting the points specified in [X25519] to 1109 Edwards coordinates.) 1111 5.5. ECVRF Ciphersuites 1113 This document defines ECVRF-P256-SHA256-TAI as follows: 1115 * suite_string = 0x01. 1117 * The EC group G is the NIST P-256 elliptic curve, with curve 1118 parameters as specified in [FIPS-186-4] (Section D.1.2.3) and 1119 [RFC5114] (Section 2.6). For this group, fLen = qLen = 32 and 1120 cofactor = 1. 1122 * cLen = 16. 1124 * The key pair generation primitive is specified in Section 3.2.1 of 1125 [SECG1] (q, B, SK, and Y in this document correspond to n, G, d, 1126 and Q in Section 3.2.1 of [SECG1]). In this ciphersuite, the 1127 secret scalar x is equal to the private key SK. 1129 * encode_to_curve_salt = PK_string 1131 * The ECVRF_nonce_generation function is as specified in 1132 Section 5.4.2.1. 1134 * The int_to_string function is the I2OSP function specified in 1135 Section 4.1 of [RFC8017]. (This is big-endian representation.) 1137 * The string_to_int function is the OS2IP function specified in 1138 Section 4.2 of [RFC8017]. (This is big-endian representation.) 1140 * The point_to_string function converts a point on E to an octet 1141 string according to the encoding specified in Section 2.3.3 of 1142 [SECG1] with point compression on. This implies ptLen = fLen + 1 1143 = 33. (Note that certain software implementations do not 1144 introduce a separate elliptic curve point type and instead 1145 directly treat the EC point as an octet string per above encoding. 1146 When using such an implementation, the point_to_string function 1147 can be treated as the identity function.) 1149 * The string_to_point function converts an octet string to an a 1150 point on E according to the encoding specified in Section 2.3.4 of 1151 [SECG1]. This function MUST output INVALID if the octet string 1152 does not decode to a point on the curve E. 1154 * The hash function Hash is SHA-256 as specified in [RFC6234], with 1155 hLen = 32. 1157 * The ECVRF_encode_to_curve function is as specified in 1158 Section 5.4.1.1, with interpret_hash_value_as_a_point(s) = 1159 string_to_point(0x02 || s). 1161 This document defines ECVRF-P256-SHA256-SSWU as identical to ECVRF- 1162 P256-SHA256-TAI, except that: 1164 * suite_string = 0x02. 1166 * the ECVRF_encode_to_curve function is as specified in 1167 Section 5.4.1.2 with h2c_suite_ID_string = P256_XMD:SHA- 1168 256_SSWU_NU_ (the suite is defined in 1169 [I-D.irtf-cfrg-hash-to-curve] Section 8.2) 1171 This document defines ECVRF-EDWARDS25519-SHA512-TAI as follows: 1173 * suite_string = 0x03. 1175 * The EC group G is the edwards25519 elliptic curve with parameters 1176 defined in Table 1 of [RFC8032]. For this group, fLen = qLen = 32 1177 and cofactor = 8. 1179 * cLen = 16. 1181 * The private key and generation of the secret scalar and the public 1182 key are specified in Section 5.1.5 of [RFC8032]. 1184 * encode_to_curve_salt = PK_string 1186 * The ECVRF_nonce_generation function is as specified in 1187 Section 5.4.2.2. 1189 * The int_to_string function as specified in the first paragraph of 1190 Section 5.1.2 of [RFC8032]. (This is little-endian 1191 representation.) 1193 * The string_to_int function interprets the string as an integer in 1194 little-endian representation. 1196 * The point_to_string function converts an point on E to an octet 1197 string according to the encoding specified in Section 5.1.2 of 1198 [RFC8032]. This implies ptLen = fLen = 32. (Note that certain 1199 software implementations do not introduce a separate elliptic 1200 curve point type and instead directly treat the EC point as an 1201 octet string per above encoding. When using such and 1202 implementation, the point_to_string function can be treated as the 1203 identity function.) 1205 * The string_to_point function converts an octet string to a point 1206 on E according to the encoding specified in Section 5.1.3 of 1207 [RFC8032]. This function MUST output INVALID if the octet string 1208 does not decode to a point on the curve E. 1210 * The hash function Hash is SHA-512 as specified in [RFC6234], with 1211 hLen = 64. 1213 * The ECVRF_encode_to_curve function is as specified in 1214 Section 5.4.1.1, with interpret_hash_value_as_a_point(s) = 1215 string_to_point(s[0]...s[31]). 1217 This document defines ECVRF-EDWARDS25519-SHA512-ELL2 as identical to 1218 ECVRF-EDWARDS25519-SHA512-TAI, except: 1220 * suite_string = 0x04. 1222 * the ECVRF_encode_to_curve function is as specified in 1223 Section 5.4.1.2 with h2c_suite_ID_string = edwards25519_XMD:SHA- 1224 512_ELL2_NU_ (the suite is defined in 1225 [I-D.irtf-cfrg-hash-to-curve] Section 8.5). 1227 6. Implementation Status 1229 Note to RFC editor: Remove before publication 1231 A reference C++ implementation of ECVRF-P256-SHA256-TAI, ECVRF- 1232 P256-SHA256-SSWU, ECVRF-EDWARDS25519-SHA512-TAI, and ECVRF- 1233 EDWARDS25519-SHA512-ELL2 is available at https://github.com/reyzin/ 1234 ecvrf. This implementation is neither secure nor especially 1235 efficient, but can be used to generate test vectors. 1237 A Python implementation of an older version of ECVRF- 1238 EDWARDS25519-SHA512-ELL2 from the -05 version of this draft is 1239 available at https://github.com/integritychain/draft-irtf-cfrg-vrf- 1240 05. 1242 A C implementation of an older version of ECVRF- 1243 EDWARDS25519-SHA512-ELL2 from the -03 version of this draft is 1244 available at https://github.com/algorand/libsodium/tree/draft-irtf- 1245 cfrg-vrf-03/src/libsodium/crypto_vrf/ietfdraft03. 1247 A Rust implementation of an older version of ECVRF-P256-SHA256-TAI 1248 from the -05 version of this draft, as well as variants for the 1249 sect163k1 and secp256k1 curves, is available at 1250 https://crates.io/crates/vrf. 1252 A C implementation of a variant of ECVRF-P256-SHA256-TAI from the -05 1253 version of this draft adapted for the secp256k1 curve is available at 1254 https://github.com/aergoio/secp256k1-vrf. 1256 An implementation of an earlier version of RSA-FDH-VRF (SHA-256) and 1257 ECVRF-P256-SHA256-TAI was first developed as a part of the NSEC5 1258 project [I-D.vcelak-nsec5] and is available at 1259 http://github.com/fcelda/nsec5-crypto. 1261 The Key Transparency project at Google uses a VRF implementation that 1262 is similar to the ECVRF-P256-SHA256-TAI, with a few changes including 1263 the use of SHA-512 instead of SHA-256. Its implementation is 1264 available at 1265 https://github.com/google/keytransparency/blob/master/core/crypto/ 1266 vrf/ 1268 An implementation by Ryuji Ishiguro following an older version of 1269 ECVRF-EDWARDS25519-SHA512-TAI from the -00 version of this draft is 1270 available at https://github.com/r2ishiguro/vrf. 1272 An implementation similar to ECVRF-EDWARDS25519-SHA512-ELL2 (with 1273 some changes, including the use of SHA-3) is available as part of the 1274 CONIKS implementation in Golang at https://github.com/coniks-sys/ 1275 coniks-go/tree/master/crypto/vrf. 1277 Open Whisper Systems also uses a VRF similar to ECVRF- 1278 EDWARDS25519-SHA512-ELL2, called VXEdDSA, and specified here 1279 https://whispersystems.org/docs/specifications/xeddsa/ and here 1280 https://moderncrypto.org/mail-archive/curves/2017/000925.html. 1281 Implementations in C and Java are available at 1282 https://github.com/signalapp/curve25519-java and 1283 https://github.com/wavesplatform/curve25519-java. 1285 7. Security Considerations 1286 7.1. Key Generation 1288 Applications that use the VRFs defined in this document MUST ensure 1289 that the VRF key is generated correctly, using good randomness. 1291 7.1.1. Uniqueness and collision resistance with untrusted keys 1293 The RSA-FDH-VRF satisfies the "trusted uniqueness" (see Section 3.1) 1294 and "trusted collision resistance" (see Section 3.2) properties as 1295 long as the VRF keys are generated correctly. Uniqueness and 1296 collision resistance may not hold if the keys are generated 1297 adversarially (specifically, if the RSA function specified in the 1298 public key is not bijective because the modulus n or the exponent e 1299 are chosen not in compliance with the stadnard); thus, RSA-FDH-VRF 1300 defined in this document does not have "full uniqueness" and "full 1301 collision resistance". Therefore, if adversarial key generation is a 1302 concern, the RSA-FDH-VRF has to be enhanced by additional 1303 cryptographic checks that its public key has the right form. These 1304 enhacements are left for future specification. 1306 For the ECVRF, the Verifier MUST obtain E and B from a trusted 1307 source, such as a ciphersuite specification, rather than from the 1308 prover. If the verifier does so, then the ECVRF satisfies the "full 1309 uniqueness" (see Section 3.1) and "trusted collision resistance" (see 1310 Section 3.2) properties. It additonally satisfies "full collision 1311 resistance" if validate_key parameter given to the ECVRF_verify is 1312 TRUE. 1314 7.1.2. Pseudorandomness with untrusted keys 1316 Without good randomness, the "pseudorandomness" properties of the VRF 1317 may not hold. Note that it is not possible to guarantee 1318 pseudorandomness in the face of adversarially generated VRF keys. 1319 This is because an adversary can always use bad randomness to 1320 generate the VRF keys, and thus, the VRF output may not be 1321 pseudorandom. 1323 7.2. Security Levels 1325 As shown in [PWHVNRG17], RSA-FDH-VRF satifies the trusted uniqueness 1326 property unconditionally. The security level of the RSA-FDH-VRF, 1327 measured in bits, for the other two properties is as follows (in the 1328 random oracle model for the functions MGF1 and Hash): 1330 * For trusted collision resistance: approximately 8*min(k/2, hLen/2) 1331 (as shown in [PWHVNRG17]). 1333 * For selective pseudorandomness: approximately as strong as the 1334 security, in bits, of the RSA problem for the key (n, e) (as shown 1335 in [GNPRVZ15]). 1337 As shown in [PWHVNRG17], the security level of the ECVRF, measured in 1338 bits, is as follows (in the random oracle model for the functions 1339 Hash and ECVRF_encode_to_curve): 1341 * For trusted uniqueness: approximately 8*min(qLen, cLen). 1343 * For collision resistance (trusted or full, depending on whether 1344 validation is performed as explained in Section 7.1.1): 1345 approximately 8*min(qLen/2, hLen/2). 1347 * For the selective pseudorandomness property: approximately as 1348 strong as the security, in bits, of the decisional Diffie-Hellman 1349 problem in the group G (which is at most 8*qLen/2). 1351 See Section 3 for the definitions of these security properties. See 1352 Section 7.3 for the discussion of full pseudorandomness. 1354 7.3. Selective vs. Full Pseudorandomness 1356 [PWHVNRG17] presents cryptographic reductions to an underlying hard 1357 problem (namely, the RSA problem for RSA-FDH-VRF and the Decisional 1358 Diffie-Hellman problem for the ECVRF) to prove that the VRFs 1359 specified in this document possess not only selective 1360 pseudorandomness, but also full pseudorandomness (see Section 3.3 for 1361 an explanation of these notions). However, the cryptographic 1362 reductions are tighter for selective pseudorandomness than for full 1363 pseudorandomness. Specifically, the approximate provable security 1364 level, measured in bits, for full pseudorandomness may be obtained 1365 from the provable security level for selective pseudorandomness 1366 (given in Section 7.2) by subtracting the binary logarithm of the 1367 number of proofs produced for a given secret key. This holds for 1368 both the RSA-FDH-VRF and the ECVRF. 1370 While no known attacks against full pseudorandomness are stronger 1371 than similar attacks against selective pseudorandomness, some 1372 applications may be concerned about tightness of cryptographic 1373 reductions. Such applications may consider the following two 1374 options: 1376 * They may choose to ensure that selective pseudorandomness is 1377 sufficient for the application. That is, that pseudorandomness of 1378 outputs matters only for inputs that are chosen independently of 1379 the VRF key. 1381 * They may increase security parameters to make up for the loose 1382 security reduction. For RSA-FDH-VRF, this means increasing the 1383 RSA key length. For ECVRF, this means increasing the 1384 cryptographic strength of the EC group G by specifying a new 1385 ciphersuite. 1387 7.4. Proper pseudorandom nonce for ECVRF 1389 The security of the ECVRF defined in this document relies on the fact 1390 that the nonce k used in the ECVRF_prove algorithm is chosen 1391 uniformly and pseudorandomly modulo q, and is unknown to the 1392 adversary. Otherwise, an adversary may be able to recover the 1393 private VRF key x (and thus break pseudorandomness of the VRF) after 1394 observing several valid VRF proofs pi. The nonce generation methods 1395 specified in the ECVRF ciphersuites of Section 5.5 are designed with 1396 this requirement in mind. 1398 7.5. Side-channel attacks 1400 Side channel attacks on cryptographic primitives are an important 1401 issue. Implementers should take care to avoid side-channel attacks 1402 that leak information about the VRF private key SK (and the nonce k 1403 used in the ECVRF), which is used in VRF_prove. In most 1404 applications, VRF_proof_to_hash and VRF_verify algorithms take only 1405 inputs that are public, and thus side channel attacks are typically 1406 not a concern for these algorithms. 1408 The VRF input alpha may be also a sensitive input to VRF_prove and 1409 may need to be protected against side channel attacks. Below we 1410 discuss one particular class of such attacks: timing attacks that can 1411 be used to leak information about the VRF input alpha. 1413 The ECVRF_encode_to_curve_try_and_increment algorithm defined in 1414 Section 5.4.1.1 SHOULD NOT be used in applications where the VRF 1415 input alpha is secret and is hashed by the VRF on-the-fly. This is 1416 because the algorithm's running time depends on the VRF input alpha, 1417 and thus creates a timing channel that can be used to learn 1418 information about alpha. That said, for most inputs the amount of 1419 information obtained from such a timing attack is likely to be small 1420 (1 bit, on average), since the algorithm is expected to find a valid 1421 curve point after only two attempts. However, there might be inputs 1422 which cause the algorithm to make many attempts before it finds a 1423 valid curve point; for such inputs, the information leaked in a 1424 timing attack will be more than 1 bit. 1426 ECVRF-P256-SHA256-SSWU and ECVRF-EDWARDS25519-SHA512-ELL2 can be made 1427 to run in time independent of alpha, following recommendations in 1428 [I-D.irtf-cfrg-hash-to-curve]. 1430 7.6. Proofs provide no secrecy for the VRF input 1432 The VRF proof pi is not designed to provide secrecy and, in general, 1433 may reveal the VRF input alpha. Anyone who knows PK and pi is able 1434 to perform an offline dictionary attack to search for alpha, by 1435 verifying guesses for alpha using VRF_verify. This is in contrast to 1436 the VRF hash output beta which, without the proof, is pseudorandom 1437 and thus is designed to reveal no information about alpha. 1439 7.7. Prehashing 1441 The VRFs specified in this document allow for read-once access to the 1442 input alpha for both signing and verifying. Thus, additional 1443 prehashing of alpha (as specified, for example, in [RFC8032] for 1444 EdDSA signatures) is not needed, even for applications that need to 1445 handle long alpha or to support the Initialize-Update-Finalize (IUF) 1446 interface (in such an interface, alpha is not supplied all at once, 1447 but rather in pieces by a sequence of calls to Update). The ECVRF, 1448 in particular, uses alpha only in ECVRF_encode_to_curve. The curve 1449 point H becomes the representative of alpha thereafter. 1451 7.8. Hash function domain separation 1453 Hashing is used for different purposes in the two VRFs (namely, in 1454 the RSA-FDH-VRF, in MGF1 and in proof_to_hash; in the ECVRF, in 1455 encode_to_curve, nonce_generation, challenge_generation, and 1456 proof_to_hash). The theoretical analysis treats each of these 1457 functions as a separate hash function, modeled as a random oracle. 1458 This analysis still holds even if the same hash function is used, as 1459 long as the four queries made to the hash function for a given SK and 1460 alpha are overwhelmingly unlikely to equal each other or to any 1461 queries made to the hash function for the same SK and different 1462 alpha. This is indeed the case for the RSA-FDH-VRF defined in this 1463 document, because the second octets of the input to the hash function 1464 used in MGF1 and in proof_to_hash are different. 1466 This is also the case for the ECVRF ciphersuites defined in this 1467 document, because: 1469 * inputs to the hash function used during nonce_generation are 1470 unlikely to equal inputs used in encode_to_curve, proof_to_hash, 1471 and challenge_generation. This follows since nonce_generation 1472 inputs a secret to the hash function that is not used by honest 1473 parties as input to any other hash function, and is not available 1474 to the adversary. 1476 * the second octets of the inputs to the hash function used in 1477 proof_to_hash, challenge_generation, and 1478 encode_to_curve_try_and_increment are all different. 1480 * the last octet of the input to the hash function used in 1481 proof_to_hash, challenge_generation, and 1482 encode_to_curve_try_and_increment is always zero, and therefore 1483 different from the last octet of the input to the hash function 1484 used in ECVRF_encode_to_curve_h2c_suite, which is set equal to the 1485 nonzero length of the domain separation tag by 1486 [I-D.irtf-cfrg-hash-to-curve]. 1488 7.9. Hash function salting 1490 In case a hash collision is found, in order to make it more difficult 1491 for the adversary to exploit such a collision, the MGF1 function for 1492 the RSA-FDH-VRF and ECVRF_encode_to_curve function for the ECVRF use 1493 a public value in addition to alpha (as a so-called salt). This 1494 value is determined by the ciphersuite. For the ciphersuites defined 1495 in this document, it is set equal to the string representation of the 1496 RSA modulus and EC public key, respectively. Implementations that do 1497 not use one of the ciphersuites (see Section 7.10) MAY use a 1498 different salt. For example, if a group of public keys to share the 1499 same salt, then the hash of the VRF input alpha will be the same for 1500 the entire group of public keys, which may aid in some protocol that 1501 uses the VRF. 1503 7.10. Futureproofing 1505 if future designs need to specify variants (e.g., additional 1506 ciphersuites) of the RSA-FDH-VRF or the ECVRF in this document, then, 1507 to avoid the possibility that an adversary can obtain a VRF output 1508 under one variant, and then claim it was obtained under another 1509 variant, they should specify a different suite_string constant. The 1510 suite_string constants in this document are all single octets; if a 1511 future suite_string constant is longer than one octet, then it should 1512 start with a different octet than the suite_string constants in this 1513 document. Then, for the RSA-FDH-VRF, the inputs to the hash function 1514 used in MGF1 and proof_to_hash will be different from other 1515 ciphersuites. For the ECVRF, the inputs ECVRF_encode_to_curve hash 1516 function used in producing H are then guaranteed to be different from 1517 other ciphersuites; since all the other hashing done by the prover 1518 depends on H, inputs to all the hash functions used by the prover 1519 will also be different from other ciphersuites as long as 1520 ECVRF_encode_to_curve is collision resistant. 1522 8. Change Log 1524 Note to RFC Editor: if this document does not obsolete an existing 1525 RFC, please remove this appendix before publication as an RFC. 1527 00 - Forked this document from draft-goldbe-vrf-01. 1529 01 - Minor updates, mostly highlighting TODO items. 1531 02 - Added specification of elligator2 for Curve25519, along with 1532 ciphersuites for ECVRF-ED25519-SHA512-Elligator. Changed ECVRF- 1533 ED25519-SHA256 suite_string to ECVRF-ED25519-SHA512. (This change 1534 made because Ed25519 in [RFC8032] signatures use SHA512 and not 1535 SHA256.) Made ECVRF nonce generation a separate component, so 1536 that nonces are deterministic. In ECVRF proving, changed + to - 1537 (and made corresponding verification changes) in order to be 1538 consistent with EdDSA and ECDSA. Highlighted that 1539 ECVRF_hash_to_curve acts like a prehash. Added "suites" variable 1540 to ECVRF for futureproofing. Ensured domain separation for hash 1541 functions by modifying hash_points and added discussion about 1542 domain separation. Updated todos in the "additional 1543 pseudorandomness property" section. Added a discussion of secrecy 1544 into security considerations. Removed B and PK=Y from 1545 ECVRF_hash_points because they are already present via H, which is 1546 computed via hash_to_curve using the suite_string (which 1547 identifies B) and Y. 1549 03 - Changed Ed25519 conversions to little-endian, to match RFC 1550 8032; added simple key validation for Ed25519; added Simple SWU 1551 cipher suite; clarified Elligator and removed the extra x0 bit, to 1552 make Montgomery and Edwards Elligator the same; added domain 1553 separation for RSA VRF; improved notation throughout; added nonce 1554 generation as a section; changed counter in try-and-increment from 1555 four bytes to one, to avoid endian issues; renamed try-and- 1556 increment ciphersuites to -TAI; added qLen as a separate 1557 parameter; changed output length to hLen for ECVRF, to match 1558 RSAVRF; made Verify return beta so unverified proofs don't end up 1559 in proof_to_hash; added test vectors. 1561 04 - Clarified handling of optional arguments x and PK in 1562 ECVRF_prove. Edited implementation status to bring it up to date. 1564 05 - Renamed ed25519 into the more commonly used edwards25519. 1565 Corrected ECVRF_nonce_generation_RFC6979 (thanks to Gorka Irazoqui 1566 Apecechea and Mario Cao Cueto for finding the problem) and 1567 corresponding test vectors for the P256 suites. Added a reference 1568 to the Rust implementation. 1570 06 - Made some variable names more descriptive. Added a few 1571 implementation references. 1573 07 - Incorporated hash-to-curve draft by reference to replace our 1574 own Elligator2 and Simple SWU. Clarified discussion of EC 1575 parameters and functions. Added a 0 octet to all hashing to 1576 enforce domain separation from hashing done inside hash-to-curve. 1578 08 - Incorporated suggestions from crypto panel review by Chloe 1579 Martindale. Changed Reyzin's affiliation. Updated references. 1581 09 - Added a note to remove the implementation page before 1582 publication. 1584 10 - Added a check in ECVRF_decode_proof to ensure that s is 1585 reduced mod q. Connected security properties (Section 3) and 1586 security considerations (Section 7) with more cross-references. 1588 11 - Processed last call comments. Clarified various notation, 1589 including lengths of various parameters for ECVRF; added error 1590 handling to RSA-FDH-VRF; added security levels section; clarified 1591 full vs trusted uniqueness and full vs selective pseudorandomness; 1592 added RSA ciphersuites; made key validation clearer; renamed 1593 hash_to_curve to encode_to_curve to be consistent with the 1594 hash_to_curve draft; allowed a more general salt in hashing, added 1595 the public key as input to ECVRF_challenge_generation, and added 1596 an explanation about the salt. 1598 9. Contributors 1600 This document also would not be possible without the work of Moni 1601 Naor, Sachin Vasant, and Asaf Ziv. Chloe Martindale provided a 1602 thorough cryptographer's review. Liliya Akhmetzyanova, Tony Arcieri, 1603 Gary Belvin, Mario Cao Cueto, Brian Chen, Sergey Gorbunov, Shumon 1604 Huque, Gorka Irazoqui Apecechea, Marek Jankowski, Burt Kaliski, David 1605 C. Lawerence, Derek Ting-Haye Leung, Antonio Marcedone, Piotr 1606 Nojszewski, Chris Peikert, Trevor Perrin, Sam Scott, Stanislav 1607 Smyshlyaev, Adam Suhl, Nick Sullivan, Christopher Wood, Jiayu Xu, and 1608 Annie Yousar provided valuable input to this draft. Riad Wahby 1609 helped this document align with draft-irtf-cfrg-hash-to-curve. 1611 10. References 1613 10.1. Normative References 1615 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1616 Requirement Levels", BCP 14, RFC 2119, 1617 DOI 10.17487/RFC2119, March 1997, 1618 . 1620 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, 1621 "PKCS #1: RSA Cryptography Specifications Version 2.2", 1622 RFC 8017, DOI 10.17487/RFC8017, November 2016, 1623 . 1625 [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman 1626 Groups for Use with IETF Standards", RFC 5114, 1627 DOI 10.17487/RFC5114, January 2008, 1628 . 1630 [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms 1631 (SHA and SHA-based HMAC and HKDF)", RFC 6234, 1632 DOI 10.17487/RFC6234, May 2011, 1633 . 1635 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 1636 Signature Algorithm (EdDSA)", RFC 8032, 1637 DOI 10.17487/RFC8032, January 2017, 1638 . 1640 [RFC6979] Pornin, T., "Deterministic Usage of the Digital Signature 1641 Algorithm (DSA) and Elliptic Curve Digital Signature 1642 Algorithm (ECDSA)", RFC 6979, DOI 10.17487/RFC6979, August 1643 2013, . 1645 [I-D.irtf-cfrg-hash-to-curve] 1646 Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R. S., 1647 and C. A. Wood, "Hashing to Elliptic Curves", Work in 1648 Progress, Internet-Draft, draft-irtf-cfrg-hash-to-curve- 1649 13, 10 November 2021, 1650 . 1653 [FIPS-186-4] 1654 National Institute for Standards and Technology, "Digital 1655 Signature Standard (DSS)", FIPS PUB 186-4, July 2013, 1656 . 1659 [SECG1] Standards for Efficient Cryptography Group (SECG), "SEC 1: 1660 Elliptic Curve Cryptography", Version 2.0, May 2009, 1661 . 1663 10.2. Informative References 1665 [ANSI.X9-62-2005] 1666 "Public Key Cryptography for the Financial Services 1667 Industry: The Elliptic Curve Digital Signature Algorithm 1668 (ECDSA)", ANSI X9.62, 2005. 1670 [DGKR18] David, B., Gazi, P., Kiayias, A., and A. Russell, 1671 "Ouroboros Praos: An adaptively-secure, semi-synchronous 1672 proof-of-stake protocol", in Advances in Cryptology - 1673 EUROCRYPT, 2018, . 1675 [GHMVZ17] Gilad, Y., Hemo, R., Micali, Y., Vlachos, Y., and Y. 1676 Zeldovich, "Algorand: Scaling Byzantine Agreements for 1677 Cryptocurrencies", in Proceedings of the 26th Symposium on 1678 Operating Systems Principles (SOSP), 2017, 1679 . 1681 [GNPRVZ15] Goldberg, S., Naor, M., Papadopoulos, D., Reyzin, L., 1682 Vasant, S., and A. Ziv, "NSEC5: Provably Preventing DNSSEC 1683 Zone Enumeration", in NDSS, 2015, 1684 . 1686 [I-D.vcelak-nsec5] 1687 Vcelak, J., Goldberg, S., Papadopoulos, D., Huque, S., and 1688 D. C. Lawrence, "NSEC5, DNSSEC Authenticated Denial of 1689 Existence", Work in Progress, Internet-Draft, draft- 1690 vcelak-nsec5-08, 29 December 2018, 1691 . 1694 [MRV99] Micali, S., Rabin, M., and S. Vadhan, "Verifiable Random 1695 Functions", in FOCS, 1999, 1696 . 1698 [PWHVNRG17] 1699 Papadopoulos, D., Wessels, D., Huque, S., Vcelak, J., 1700 Naor, M., Reyzin, L., and S. Goldberg, "Making NSEC5 1701 Practical for DNSSEC", in ePrint Cryptology Archive 1702 2017/099, February 2017, 1703 . 1705 [X25519] Bernstein, D.J., "How do I validate Curve25519 public 1706 keys?", 2006, . 1708 Appendix A. Test Vectors for the ECVRFs 1710 The test vectors in this section were generated using the reference 1711 implementation at https://github.com/reyzin/ecvrf. 1713 A.1. ECVRF-P256-SHA256-TAI 1715 The example secret keys and messages in Examples 1 and 2 are taken 1716 from Appendix A.2.5 of [RFC6979]. 1718 Example 1: 1720 SK = x = 1721 c9afa9d845ba75166b5c215767b1d6934e50c3db36e89b127b8a622b120f6721 1722 PK = 1723 0360fed4ba255a9d31c961eb74c6356d68c049b8923b61fa6ce669622e60f29fb6 1724 alpha = 73616d706c65 (ASCII "sample") 1725 try_and_increment succeeded on ctr = 1 1726 H = 1727 0272a877532e9ac193aff4401234266f59900a4a9e3fc3cfc6a4b7e467a15d06d4 1728 k = 1729 0d90591273453d2dc67312d39914e3a93e194ab47a58cd598886897076986f77 1730 U = k*B = 1731 02bb6a034f67643c6183c10f8b41dc4babf88bff154b674e377d90bde009c21672 1732 V = k*H = 1733 02893ebee7af9a0faa6da810da8a91f9d50e1dc071240c9706726820ff919e8394 1734 pi = 035b5c726e8c0e2c488a107c600578ee75cb702343c153cb1eb8dec77f4b5 1735 071b4a53f0a46f018bc2c56e58d383f2305e0975972c26feea0eb122fe7893c15a 1736 f376b33edf7de17c6ea056d4d82de6bc02f 1737 beta = 1738 a3ad7b0ef73d8fc6655053ea22f9bede8c743f08bbed3d38821f0e16474b505e 1740 Example 2: 1742 SK = x = 1743 c9afa9d845ba75166b5c215767b1d6934e50c3db36e89b127b8a622b120f6721 1744 PK = 1745 0360fed4ba255a9d31c961eb74c6356d68c049b8923b61fa6ce669622e60f29fb6 1746 alpha = 74657374 (ASCII "test") 1747 try_and_increment succeeded on ctr = 3 1748 H = 1749 02173119b4fff5e6f8afed4868a29fe8920f1b54c2cf89cc7b301d0d473de6b974 1750 k = 1751 5852353a868bdce26938cde1826723e58bf8cb06dd2fed475213ea6f3b12e961 1752 U = k*B = 1753 022779a2cafcb65414c4a04a4b4d2adf4c50395f57995e89e6de823250d91bc48e 1754 V = k*H = 1755 033b4a14731672e82339f03b45ff6b5b13dee7ada38c9bf1d6f8f61e2ce5921119 1756 pi = 034dac60aba508ba0c01aa9be80377ebd7562c4a52d74722e0abae7dc3080 1757 ddb56c19e067b15a8a8174905b13617804534214f935b94c2287f797e393eb0816 1758 969d864f37625b443f30f1a5a33f2b3c854 1759 beta = 1760 a284f94ceec2ff4b3794629da7cbafa49121972671b466cab4ce170aa365f26d 1762 The example secret key in Example 3 is taken from Appendix L.4.2 of 1763 [ANSI.X9-62-2005]. 1765 Example 3: 1767 SK = x = 1768 2ca1411a41b17b24cc8c3b089cfd033f1920202a6c0de8abb97df1498d50d2c8 1769 PK = 1770 03596375e6ce57e0f20294fc46bdfcfd19a39f8161b58695b3ec5b3d16427c274d 1771 alpha = 4578616d706c65207573696e67204543445341206b65792066726f6d20 1772 417070656e646978204c2e342e32206f6620414e53492e58392d36322d32303035 1773 (ASCII "Example using ECDSA key from Appendix L.4.2 of 1774 ANSI.X9-62-2005") 1775 try_and_increment succeeded on ctr = 1 1776 H = 1777 0258055c26c4b01d01c00fb57567955f7d39cd6f6e85fd37c58f696cc6b7aa761d 1778 k = 1779 5689e2e08e1110b4dda293ac21667eac6db5de4a46a519c73d533f69be2f4da3 1780 U = k*B = 1781 020f465cd0ec74d2e23af0abde4c07e866ae4e5138bded5dd1196b8843f380db84 1782 V = k*H = 1783 036cb6f811428fc4904370b86c488f60c280fa5b496d2f34ff8772f60ed24b2d1d 1784 pi = 03d03398bf53aa23831d7d1b2937e005fb0062cbefa06796579f2a1fc7e7b 1785 8c667d091c00b0f5c3619d10ecea44363b5a599cadc5b2957e223fec62e81f7b48 1786 25fc799a771a3d7334b9186bdbee87316b1 1787 beta = 1788 90871e06da5caa39a3c61578ebb844de8635e27ac0b13e829997d0d95dd98c19 1790 A.2. ECVRF-P256-SHA256-SSWU 1792 The example secret keys and messages in Examples 4 and 5 are taken 1793 from Appendix A.2.5 of [RFC6979]. 1795 Example 4: 1797 SK = x = 1798 c9afa9d845ba75166b5c215767b1d6934e50c3db36e89b127b8a622b120f6721 1799 PK = 1800 0360fed4ba255a9d31c961eb74c6356d68c049b8923b61fa6ce669622e60f29fb6 1801 alpha = 73616d706c65 (ASCII "sample") 1802 In SSWU: uniform_bytes = 5024e98d6067dec313af09ff0cbe78218324a645c 1803 2a4b0aae2453f6fe91aa3bd9471f7b4a5fbf128e4b53f0c59603f7e 1804 In SSWU: u = 1805 df565615a2372e8b31b8771f7503bafc144e48b05688b97958cc27ce29a8d810 1806 In SSWU: x1 = 1807 e7e39eb8a4c982426fcff629e55a3e13516cfeb62c02c369b1e750316f5e94eb 1808 In SSWU: gx1 is a nonsquare 1809 H = 1810 02b31973e872d4a097e2cfae9f37af9f9d73428fde74ac537dda93b5f18dbc5842 1811 k = 1812 e92820035a0a8afe132826c6312662b6ea733fc1a0d33737945016de54d02dd8 1813 U = k*B = 1814 031490f49d0355ffcdf66e40df788bee93861917ee713acff79be40d20cc91a30a 1815 V = k*H = 1816 03701df0228138fa3d16612c0d720389326b3265151bc7ac696ea4d0591cd053e3 1817 pi = 0331d984ca8fece9cbb9a144c0d53df3c4c7a33080c1e02ddb1a96a365394 1818 c7888782fffde7b842c38c20c08de6ec6c2e7027a97000f2c9fa4425d5c03e639f 1819 b48fde58114d755985498d7eb234cf4aed9 1820 beta = 1821 21e66dc9747430f17ed9efeda054cf4a264b097b9e8956a1787526ed00dc664b 1823 Example 5: 1825 SK = x = 1826 c9afa9d845ba75166b5c215767b1d6934e50c3db36e89b127b8a622b120f6721 1827 PK = 1828 0360fed4ba255a9d31c961eb74c6356d68c049b8923b61fa6ce669622e60f29fb6 1829 alpha = 74657374 (ASCII "test") 1830 In SSWU: uniform_bytes = 910cc66d84a57985a1d15843dad83fd9138a109af 1831 b243b7fa5d64d766ec9ca3894fdcf46ebeb21a3972eb452a4232fd3 1832 In SSWU: u = 1833 d8b0107f7e7aa36390240d834852f8703a6dc407019d6196bda5861b8fc00181 1834 In SSWU: x1 = 1835 ccc747fa7318b9486ce4044adbbecaa084c27be6eda88eb7b7f3d688fd0968c7 1836 In SSWU: gx1 is a square 1837 H = 1838 03ccc747fa7318b9486ce4044adbbecaa084c27be6eda88eb7b7f3d688fd0968c7 1839 k = 1840 febc3451ea7639fde2cf41ffd03f463124ecb3b5a79913db1ed069147c8a7dea 1841 U = k*B = 1842 031200f9900e96f811d1247d353573f47e0d9da601fc992566234fc1a5b37749ae 1843 V = k*H = 1844 02d3715dcfee136c7ae50e95ffca76f4ca6c29ddfb92a39c31a0d48e75c6605cd1 1845 pi = 03f814c0455d32dbc75ad3aea08c7e2db31748e12802db23640203aebf1fa 1846 8db2743aad348a3006dc1caad7da28687320740bf7dd78fe13c298867321ce3b36 1847 b79ec3093b7083ac5e4daf3465f9f43c627 1848 beta = 1849 8e7185d2b420e4f4681f44ce313a26d05613323837da09a69f00491a83ad25dd 1851 The example secret key in Example 6 is taken from Appendix L.4.2 of 1852 [ANSI.X9-62-2005]. 1854 Example 6: 1856 SK = x = 1857 2ca1411a41b17b24cc8c3b089cfd033f1920202a6c0de8abb97df1498d50d2c8 1858 PK = 1859 03596375e6ce57e0f20294fc46bdfcfd19a39f8161b58695b3ec5b3d16427c274d 1860 alpha = 4578616d706c65207573696e67204543445341206b65792066726f6d20 1861 417070656e646978204c2e342e32206f6620414e53492e58392d36322d32303035 1862 (ASCII "Example using ECDSA key from Appendix L.4.2 of 1863 ANSI.X9-62-2005") 1864 In SSWU: uniform_bytes = 9b81d55a242d3e8438d3bcfb1bee985a87fd14480 1865 2c9268cf9adeee160e6e9ff765569797a0f701cb4316018de2e7dd4 1866 In SSWU: u = 1867 e43c98c2ae06d13839fedb0303e5ee815896beda39be83fb11325b97976efdce 1868 In SSWU: x1 = 1869 be9e195a50f175d3563aed8dc2d9f513a5536c1e9aee1757d86c08d32d582a86 1870 In SSWU: gx1 is a nonsquare 1871 H = 1872 022dd5150e5a2a24c66feab2f68532be1486e28e07f1b9a055cf38ccc16f6595ff 1873 k = 1874 8e29221f33564f3f66f858ba2b0c14766e1057adbd422c3e7d0d99d5e142b613 1875 U = k*B = 1876 03a8823ff9fd16bf879261c740b9c7792b77fee0830f21314117e441784667958d 1877 V = k*H = 1878 02d48fbb45921c755b73b25be2f23379e3ce69294f6cee9279815f57f4b422659d 1879 pi = 039f8d9cdc162c89be2871cbcb1435144739431db7fab437ab7bc4e2651a9 1880 e99d5488405a11a6c7fc8defddd9e1573a563b7333aab4effe73ae9803274174c6 1881 59269fd39b53e133dcd9e0d24f01288de9 1882 beta = 1883 4fbadf33b42a5f42f23a6f89952d2e634a6e3810f15878b46ef1bb85a04fe95a 1885 A.3. ECVRF-EDWARDS25519-SHA512-TAI 1887 The example secret keys and messages in Examples 7, 8, and 9 are 1888 taken from Section 7.1 of [RFC8032]. 1890 Example 7: 1892 SK = 1893 9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60 1894 PK = 1895 d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a 1896 alpha = (the empty string) 1897 x = 1898 307c83864f2833cb427a2ef1c00a013cfdff2768d980c0a3a520f006904de94f 1899 try_and_increment succeeded on ctr = 0 1900 H = 1901 91bbed02a99461df1ad4c6564a5f5d829d0b90cfc7903e7a5797bd658abf3318 1902 k = 7100f3d9eadb6dc4743b029736ff283f5be494128df128df2817106f345b85 1903 94b6d6da2d6fb0b4c0257eb337675d96eab49cf39e66cc2c9547c2bf8b2a6afae4 1904 U = k*B = 1905 aef27c725be964c6a9bf4c45ca8e35df258c1878b838f37d9975523f09034071 1906 V = k*H = 1907 5016572f71466c646c119443455d6cb9b952f07d060ec8286d678615d55f954f 1908 pi = 8657106690b5526245a92b003bb079ccd1a92130477671f6fc01ad16f26f7 1909 23f26f8a57ccaed74ee1b190bed1f479d9727d2d0f9b005a6e456a35d4fb0daab1 1910 268a1b0db10836d9826a528ca76567805 1911 beta = 90cf1df3b703cce59e2a35b925d411164068269d7b2d29f3301c03dd757 1912 876ff66b71dda49d2de59d03450451af026798e8f81cd2e333de5cdf4f3e140fdd 1913 8ae 1915 Example 8: 1917 SK = 1918 4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb 1919 PK = 1920 3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c 1921 alpha = 72 (1 byte) 1922 x = 1923 68bd9ed75882d52815a97585caf4790a7f6c6b3b7f821c5e259a24b02e502e51 1924 try_and_increment succeeded on ctr = 1 1925 H = 1926 5b659fc3d4e9263fd9a4ed1d022d75eaacc20df5e09f9ea937502396598dc551 1927 k = 42589bbf0c485c3c91c1621bb4bfe04aed7be76ee48f9b00793b2342acb9c1 1928 67cab856f9f9d4febc311330c20b0a8afd3743d05433e8be8d32522ecdc16cc5ce 1929 U = k*B = 1930 1dcb0a4821a2c48bf53548228b7f170962988f6d12f5439f31987ef41f034ab3 1931 V = k*H = 1932 fd03c0bf498c752161bae4719105a074630a2aa5f200ff7b3995f7bfb1513423 1933 pi = f3141cd382dc42909d19ec5110469e4feae18300e94f304590abdced48aed 1934 5933bf0864a62558b3ed7f2fea45c92a465301b3bbf5e3e54ddf2d935be3b67926 1935 da3ef39226bbc355bdc9850112c8f4b02 1936 beta = eb4440665d3891d668e7e0fcaf587f1b4bd7fbfe99d0eb2211ccec90496 1937 310eb5e33821bc613efb94db5e5b54c70a848a0bef4553a41befc57663b56373a5 1938 031 1940 Example 9: 1942 SK = 1943 c5aa8df43f9f837bedb7442f31dcb7b166d38535076f094b85ce3a2e0b4458f7 1944 PK = 1945 fc51cd8e6218a1a38da47ed00230f0580816ed13ba3303ac5deb911548908025 1946 alpha = af82 (2 bytes) 1947 x = 1948 909a8b755ed902849023a55b15c23d11ba4d7f4ec5c2f51b1325a181991ea95c 1949 try_and_increment succeeded on ctr = 0 1950 H = 1951 bf4339376f5542811de615e3313d2b36f6f53c0acfebb482159711201192576a 1952 k = 38b868c335ccda94a088428cbf3ec8bc7955bfaffe1f3bd2aa2c59fc31a0fe 1953 bc59d0e1af3715773ce11b3bbdd7aba8e3505d4b9de6f7e4a96e67e0d6bb6d6c3a 1954 U = k*B = 1955 2bae73e15a64042fcebf062abe7e432b2eca6744f3e8265bc38e009cd577ecd5 1956 V = k*H = 1957 88cba1cb0d4f9b649d9a86026b69de076724a93a65c349c988954f0961c5d506 1958 pi = 9bc0f79119cc5604bf02d23b4caede71393cedfbb191434dd016d30177ccb 1959 f8096bb474e53895c362d8628ee9f9ea3c0e52c7a5c691b6c18c9979866568add7 1960 a2d41b00b05081ed0f58ee5e31b3a970e 1961 beta = 645427e5d00c62a23fb703732fa5d892940935942101e456ecca7bb217c 1962 61c452118fec1219202a0edcf038bb6373241578be7217ba85a2687f7a0310b2df 1963 19f 1965 A.4. ECVRF-EDWARDS25519-SHA512-ELL2 1967 The example secret keys and messages in Examples 10, 11, and 12 are 1968 taken from Section 7.1 of [RFC8032]. 1970 Example 10: 1972 SK = 1973 9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60 1974 PK = 1975 d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a 1976 alpha = (the empty string) 1977 x = 1978 307c83864f2833cb427a2ef1c00a013cfdff2768d980c0a3a520f006904de94f 1979 In Elligator2: uniform_bytes = d620782a206d9de584b74e23ae5ee1db5ca 1980 5298b3fc527c4867f049dee6dd419b3674967bd614890f621c128d72269ae 1981 In Elligator2: u = 1982 30f037b9745a57a9a2b8a68da81f397c39d46dee9d047f86c427c53f8b29a55c 1983 In Elligator2: gx1 = 1984 8cb66318fb2cea01672d6c27a5ab662ae33220961607f69276080a56477b4a08 1985 In Elligator2: gx1 is a square 1986 H = 1987 b8066ebbb706c72b64390324e4a3276f129569eab100c26b9f05011200c1bad9 1988 k = b5682049fee54fe2d519c9afff73bbfad724e69a82d5051496a42458f817be 1989 d7a386f96b1a78e5736756192aeb1818a20efb336a205ffede351cfe88dab8d41c 1990 U = k*B = 1991 762f5c178b68f0cddcc1157918edf45ec334ac8e8286601a3256c3bbf858edd9 1992 V = k*H = 1993 4652eba1c4612e6fce762977a59420b451e12964adbe4fbecd58a7aeff5860af 1994 pi = 7d9c633ffeee27349264cf5c667579fc583b4bda63ab71d001f89c10003ab 1995 46f14adf9a3cd8b8412d9038531e865c341cafa73589b023d14311c331a9ad15ff 1996 2fb37831e00f0acaa6d73bc9997b06501 1997 beta = 9d574bf9b8302ec0fc1e21c3ec5368269527b87b462ce36dab2d14ccf80 1998 c53cccf6758f058c5b1c856b116388152bbe509ee3b9ecfe63d93c3b4346c1fbc6 1999 c54 2001 Example 11: 2003 SK = 2004 4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb 2005 PK = 2006 3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c 2007 alpha = 72 (1 byte) 2008 x = 2009 68bd9ed75882d52815a97585caf4790a7f6c6b3b7f821c5e259a24b02e502e51 2010 In Elligator2: uniform_bytes = 04ae20a9ad2a2330fb33318e376a2448bd7 2011 7bb99e81d126f47952b156590444a9225b84128b66a2f15b41294fa2f2f6d 2012 In Elligator2: u = 2013 3092f033b16d4d5f74a3f7dc7091fe434b449065152b95476f121de899bb773d 2014 In Elligator2: gx1 = 2015 25d7fe7f82456e7078e99fdb24ef2582b4608357cdba9c39a8d535a3fd98464d 2016 In Elligator2: gx1 is a nonsquare 2017 H = 2018 76ac3ccb86158a9104dff819b1ca293426d305fd76b39b13c9356d9b58c08e57 2019 k = 88bf479281fd29a6cbdffd67e2c5ec0024d92f14eaed58f43f22f37c4c37f1 2020 d41e65c036fbf01f9fba11d554c07494d0c02e7e5c9d64be88ef78cab7544e444d 2021 U = k*B = 2022 8ec26e77b8cb3114dd2265fe1564a4efb40d109aa3312536d93dfe3d8d80a061 2023 V = k*H = 2024 fe799eb5770b4e3a5a27d22518bb631db183c8316bb552155f442c62a47d1c8b 2025 pi = 47b327393ff2dd81336f8a2ef10339112401253b3c714eeda879f12c50907 2026 2ef055b48372bb82efbdce8e10c8cb9a2f9d60e93908f93df1623ad78a86a028d6 2027 bc064dbfc75a6a57379ef855dc6733801 2028 beta = 38561d6b77b71d30eb97a062168ae12b667ce5c28caccdf76bc88e093e4 2029 635987cd96814ce55b4689b3dd2947f80e59aac7b7675f8083865b46c89b2ce9cc 2030 735 2032 Example 12: 2034 SK = 2035 c5aa8df43f9f837bedb7442f31dcb7b166d38535076f094b85ce3a2e0b4458f7 2036 PK = 2037 fc51cd8e6218a1a38da47ed00230f0580816ed13ba3303ac5deb911548908025 2038 alpha = af82 (2 bytes) 2039 x = 2040 909a8b755ed902849023a55b15c23d11ba4d7f4ec5c2f51b1325a181991ea95c 2041 In Elligator2: uniform_bytes = be0aed556e36cdfddf8f1eeddbb7356a24f 2042 ad64cf95a922a098038f215588b216beabbfe6acf20256188e883292b7a3a 2043 In Elligator2: u = 2044 f6675dc6d17fc790d4b3f1c6acf689a13d8b5815f23880092a925af94cd6fa24 2045 In Elligator2: gx1 = 2046 a63d48e3247c903e22fdfb88fd9295e396712a5fe576af335dbe16f99f0af26c 2047 In Elligator2: gx1 is a square 2048 H = 2049 13d2a8b5ca32db7e98094a61f656a08c6c964344e058879a386a947a4e189ed1 2050 k = a7ddd74a3a7d165d511b02fa268710ddbb3b939282d276fa2efcfa5aaf79cf 2051 576087299ca9234aacd7cd674d912deba00f4e291733ef189a51e36c861b3d683b 2052 U = k*B = 2053 a012f35433df219a88ab0f9481f4e0065d00422c3285f3d34a8b0202f20bac60 2054 V = k*H = 2055 fb613986d171b3e98319c7ca4dc44c5dd8314a6e5616c1a4f16ce72bd7a0c25a 2056 pi = 926e895d308f5e328e7aa159c06eddbe56d06846abf5d98c2512235eaa57f 2057 dce35b46edfc655bc828d44ad09d1150f31374e7ef73027e14760d42e77341fe05 2058 467bb286cc2c9d7fde29120a0b2320d04 2059 beta = 121b7f9b9aaaa29099fc04a94ba52784d44eac976dd1a3cca458733be5c 2060 d090a7b5fbd148444f17f8daf1fb55cb04b1ae85a626e30a54b4b0f8abf4a43314 2061 a58 2063 Authors' Addresses 2065 Sharon Goldberg 2066 Boston University 2067 111 Cummington Mall 2068 Boston, MA 02215 2069 United States of America 2071 Email: goldbe@cs.bu.edu 2073 Leonid Reyzin 2074 Boston University and Algorand 2075 111 Cummington Mall 2076 Boston, MA 02215 2077 United States of America 2079 Email: reyzin@bu.edu 2081 Dimitrios Papadopoulos 2082 Hong Kong University of Science and Technology 2083 Clearwater Bay 2084 Hong Kong 2086 Email: dipapado@cse.ust.hk 2087 Jan Vcelak 2088 NS1 2089 16 Beaver St 2090 New York, NY 10004 2091 United States of America 2093 Email: jvcelak@ns1.com