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

[Christopher Wood <[e-mail]>]

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:
> 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.

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