Subject: Re: [CFRG] Last call for draft-irtf-cfrg-vrf-09

From: "Christopher Wood" <[email-masked]>
Date: Fri, 05 Nov 2021 06:41:30 -0700

I read the document and think it's ready to publish. I implemented ECVRF-P256-SHA256-SSWU and validated that the test vectors match. I left my review comments at the top of that implementation:

   https://github.com/chris-wood/vrf-poc/blob/main/vrf.sage

I hope this helps.

Best,
Chris

On Mon, Oct 25, 2021, at 12:07 PM, Nick Sullivan wrote:
> Dear CFRG participants,
>
> The VRF draft has received significant reviews from the RG and the 
> crypto panel and is ready for a second last call. This email commences 
> a last call for this document that will end on the last day of IETF 112 
> Online (12 Nov 2021):
>
> https://datatracker.ietf.org/doc/draft-irtf-cfrg-vrf/
>
> If you've read the document by the end of this period and think that it 
> is ready (or not ready) for publication as an RFC, please send a 
> message in reply to this email. Detailed comments would be helpful. You 
> can reach out directly to CFRG chairs ([email-masked]) if you 
> have questions about the process.
>
> Thank you,
> Nick, Stanislav & Alexey
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Leonid Reyzin <[email-masked]>
Date: Tue, 9 Nov 2021 11:22:03 -0500

Thank you very much, Chris, for the detailed reading. I address your
comments point-by-point below.

- Section 3: Many of the security properties have "weaker" versions
(trusted
  uniqueness, trusted collision resistance, etc) and claims that these are
  sufficient for many applications. It is not clear under what conditions
  applications require stronger variants. Perhaps this should be added to
  the security considerations?

There is some language already there -- for example "Trusted uniqueness is
the same as full uniqueness, but it must hold only if the VRF keys PK and
SK were generated in a trustworthy manner" -- and more language in Section
7, where these issues are discussed with respect to the specific VRFs
defined. In response to your comment, we have edited the document to ensure
a tighter integration between these two sections. See
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/91b83b6d68d84b04963dd89e8afa42424ecaae98

- Section 3.4: Do we have proofs that the schemes in this document satisfy
  the RO-like property, or is this merely intuitively true? If the former,
  perhaps we should note that this analysis remains to be done?

I don't believe anyone wrote down and published these proofs for these very
specific variants, but they follow easily because the output is equal to an
application of RO followed by a fixed permutation (and by uniqueness no
other output will be accepted). Appendix C of
https://eprint.iacr.org/2017/573.pdf does this proof for a very similar
variant of the ECVRF, and the proof for FDH is even simpler. To say
"analysis remains to be done" would be a bit too strong.

- Section 4/5: Unless I'm missing something, neither the RSA-baed VRF has no
  variant for achieving "full" security, unlike the ECVRF, which depends on
the
  procedures in Section 5.6. Should this inconsistency be noted in the
introduction?

It is noted in detail in Security Considerations (7.1.1). We have edited
the introduction to security properties (Section 3, to be exact) to point
to 7.1.1 as part of the response to the first comment.

- Section 5. "Note that with certain software libraries (for big integer and
      elliptic curve arithmetic), the int_to_string and point_to_string
      conversions are not needed" --> it seems worth clarifying that this is
  is true iff the libraries return strings that are encoded in the same way
  as required by the corresponding ciphersuites, for interoperability
reasons.

Thanks, fixed. See
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/ba0d8b30d656825e9f03cc834bc1638dee7b5f05#diff-382a26a0bcccb52bc8c6ab7c862ed0ee8848df81772776e9fae86b36e5b1be11R858

- Section 5.3. It might be worth noting that the verification check does not
  need to be done in constant time as it's a public operation. (The
comparison
  check at the end might lead one to ask whether or not it needs to be
constant
  time, so calling it out early would clarify.)

Thanks, added a discusion to 7.4, where side channels are discussed. See
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/ba0d8b30d656825e9f03cc834bc1638dee7b5f05#diff-382a26a0bcccb52bc8c6ab7c862ed0ee8848df81772776e9fae86b36e5b1be11R1339

- Section 5.4.4. Remove "let" in "let <variable> = ..." statements, as this
  is not done in other functions where variables are declared and
initialized.

Thanks, fixed. See
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/ba0d8b30d656825e9f03cc834bc1638dee7b5f05#diff-382a26a0bcccb52bc8c6ab7c862ed0ee8848df81772776e9fae86b36e5b1be11R1174

- Section 5.6. It's noted that the procedure in this section does not work
if either
  the curve or generator are untrusted, but aren't these both fixed for the
suites
  in this document? If so, I might remove this paragraph.

We prefer to mitigate against the risk that someone codes it in a way that
has the basepoint transferred from an untrusted source rather than
hardwired. We have added a clarification to that effect. See
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/ba0d8b30d656825e9f03cc834bc1638dee7b5f05#diff-382a26a0bcccb52bc8c6ab7c862ed0ee8848df81772776e9fae86b36e5b1be11R1242

- Section 5.6.1. Do implementations for curves with small cofactors perform
validation
  by checking against known points? I don't know! If this isn't common, I
would simply
  remove the variant for ed25519, as it just seems simpler to clear the
cofactor and
  check against the identity element. Conversely, the hash-to-curve
document has specific
  cofactor clearing suggestions for each curve, and it seems reasonable to
be opinionated in
  this document, too. One might even just re-use the methods in
draft-irtf-cfrg-hash-to-curve
  for P-256 and ed25519.

Yes, other implementations seem to -- we got this idea from another
implementation. It's faster and quite simple.

- Section 7.1. Recommendations for randomness generation can probably be
cribbed
  from https://datatracker.ietf.org/doc/html/rfc8446#appendix-C.1.

Generation of secrets is an active R&D area and putting it in the standard
now seems premature.

# General comments
- Can we remove try-and-increment entirely from this specification? The
security
  relevant discussion in 7.4 can be easily skipped by applications looking
to implement
  one of the options in either 5.4.1.1 or 5.4.1.2.

It requires a more complex set of libraries to implement the other options.
There are people who want to use try-and-increment, and in most cases
there's no harm, because the side channel attack that it enables is only
against the VRF input, which is not a secret.

- In some places the public key is denoted as Y (Section 7.1.1), but in
others it's
  denoted as PK. Perhaps these should be consistent?

PK is a generic public key, while Y is the EC point specific to the ECVRF
(much like (n,e) is the PK specific to the RSAVRF). I went through to
ensure we use that consistently, and corrected a couple of places.

Best,

 Leo

On Fri, Nov 5, 2021 at 9:42 AM Christopher Wood <[email-masked]> wrote:

> I read the document and think it's ready to publish. I implemented
> ECVRF-P256-SHA256-SSWU and validated that the test vectors match. I left my
> review comments at the top of that implementation:
>

---

From: "Christopher Wood" <[email-masked]>
Date: Wed, 10 Nov 2021 04:27:00 -0800

Thanks for the response, Leo. All of your comments seem quite reasonable to me. Please see inline below for one followup comment.

On Tue, Nov 9, 2021, at 8:22 AM, Leonid Reyzin wrote:
> - Section 3: Many of the security properties have "weaker" versions (trusted 
> There is some language already there -- for example "Trusted uniqueness 
> is the same as full uniqueness, but it must hold only if the VRF keys 
> PK and SK were generated in a trustworthy manner" -- and more language 
> in Section 7, where these issues are discussed with respect to the 
> specific VRFs defined. In response to your comment, we have edited the 
> document to ensure a tighter integration between these two sections. 
> See 
> I don't believe anyone wrote down and published these proofs for these 
> very specific variants, but they follow easily because the output is 
> equal to an application of RO followed by a fixed permutation (and by 
> uniqueness no other output will be accepted). Appendix C of 
>   variant for achieving "full" security, unlike the ECVRF, which 
> depends on the
> It is noted in detail in Security Considerations (7.1.1). We have 
> edited the introduction to security properties (Section 3, to be exact) 
> to point to 7.1.1 as part of the response to the first comment.
>
>   as required by the corresponding ciphersuites, for interoperability reasons.
>  
> Thanks, fixed. See 
>   need to be done in constant time as it's a public operation. (The comparison
>   check at the end might lead one to ask whether or not it needs to be constant
>   is not done in other functions where variables are declared and initialized.
>  
> Thanks, fixed. See 
> - Section 5.6. It's noted that the procedure in this section does not 
> work if either
>   the curve or generator are untrusted, but aren't these both fixed for 
> the suites
> We prefer to mitigate against the risk that someone codes it in a way 
> that has the basepoint transferred from an untrusted source rather than 
> - Section 5.6.1. Do implementations for curves with small cofactors 
> perform validation
>   by checking against known points? I don't know! If this isn't common, 
> I would simply 
>   cofactor clearing suggestions for each curve, and it seems reasonable 
> to be opinionated in
> - Section 7.1. Recommendations for randomness generation can probably be cribbed
> Generation of secrets is an active R&D area and putting it in the 
> standard now seems premature.
>  
> # General comments
>   relevant discussion in 7.4 can be easily skipped by applications 
> looking to implement
> It requires a more complex set of libraries to implement the other 
> options. There are people who want to use try-and-increment, and in 
> most cases there's no harm, because the side channel attack that it 
> enables is only against the VRF input, which is not a secret.

I agree that it's simpler, and that's why it gives me pause. The temptation to use it for efficiency reasons is arguably quite high. The only text describing when it should be avoided seems somewhat hidden in 5.4.1.1:

   However, because the running time of algorithm depends on
   alpha_string, this algorithm SHOULD be avoided in applications where
   it is important that the VRF input alpha remain secret.

Minimally, I would promote this text to 5.4.1, and probably even add something to the security considerations elaborating on use cases where try-and-increment is not appropriate. 

Thanks again for your work on this document!

Best,
Chris

---

From: Leonid Reyzin <[email-masked]>
Date: Tue, 16 Nov 2021 21:37:36 -0500

Thanks to everyone who chimed in on the last call. Particular thanks to
Chris Peikert, Jiayu Xu, Riad Wahby, Chris Wood, Burt Kaliski, Antonio
Marcedone, and Brian Chen for the detailed reading and comments! We have
responded to some comments already; we will work through the rest and
produce an updated draft shortly.

Best,

 Leo

On Mon, Oct 25, 2021 at 3:11 PM Nick Sullivan <nick=
[email-masked]> wrote:

> Dear CFRG participants,
>
> The VRF draft has received significant reviews from the RG and the crypto
> panel and is ready for a second last call. This email commences a
> last call for this document that will end on the last day of IETF 112
> Online (12 Nov 2021):
>
> If you've read the document by the end of this period and think that it is
> ready (or not ready) for publication as an RFC, please send a message in
> reply to this email. Detailed comments would be helpful. You can reach out
> directly to CFRG chairs ([email-masked]) if you have questions
> about the process.
>
> Thank you,
> Nick, Stanislav & Alexey