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

From: Leonid Reyzin <[email-masked]>
Date: Tue, 18 Jan 2022 17:16:28 -0500

Dear Burt,

Thank you for your detailed and thoughtful comments. We have addressed them
all and feel that the draft has improved as a result. The new version is
here https://github.com/cfrg/draft-irtf-cfrg-vrf.

Details on how we have addressed the specific comments are below.

To others who have submitted comments that we have not yet addressed: we
are working through them and will respond shortly. Thank you!

Sincerely,

 Leo

> Technical Comments

> T1. General: The specification frequently computes one-octet constants as
an explicit algorithm step, e.g., "one_string = 0x01 = I2OSP(1, 1), a
single octet with value 1".  Suggest defining the notation "0x" as in
[RFC8017] and then using constants such as 0x01 directly in the algorithms
rather than computing them, to avoid the superfluous steps. (The ECVRF
algorithms use int_to_string which is suite-specific, but the single-octet
output is the same for all suites.)

Done [in this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/ee5fd0eb353d5d53c09bc274bbd796fd0de762d5
)

> T2. Sec. 4, "Parameters used:" / "K - RSA private key": Suggest to add
note that representation of K is implementation-dependent

Done [in this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/7d6cf6e49277db5c546e0179e3f36da4b38f02c9
)

> T3. Sec. 4.3, step 2: Suggest adding error handling for the case that s
>= n, in which case RSAVP1 will return "signature representative out of
range" and the algorithm should output "INVALID"

 Done [in this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/7d6cf6e49277db5c546e0179e3f36da4b38f02c9
)

> T4. Sec. 4.3, step 3: Suggest adding error handling for the case that m
>= 2^(8(k-1)), in which case I2OSP will return "integer too large" and the
algorithm should output "INVALID".  Alternatively, instead of computing EM
from m and comparing EM to EM', compute m' from EM' (as m' = OS2IP(EM'))
and compare m to m'

Done [in this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/7d6cf6e49277db5c546e0179e3f36da4b38f02c9
)

> T5. Sec. 5, "Fixed options" / "2n": Suggest adding an explanation why n
is introduced this way. Based on the security analysis in [PWHVNRG17], n
appears to correspond to the security level $\ell$, as both are the lengths
of the challenge c (in octets vs. bits). It's not clear why the parameter n
is defined here in terms of the length of a field element, rather than the
size of group G. Although the security level is affected by the size of the
field, it is not necessarily related to the length in octets of a field
element (if this is understood to be the length if the octet string
representing the field element, which may be implementation-defined). Also,
the choice of field is not discussed outside this section of the document,
although it is implied by the selection of curve parameters elsewhere.
Suggest instead to introduce a new parameter such as cLen for the length in
octets of the challenge c, and then in the security considerations, comment
on the relationship between cLen, qLen, hash function output sizes, and
security levels, much as is done in [PWHVNRG17].

Introduced appropriate length parameters and included a discussion of
security levels [in this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/ef6e178af4fa088ad7b2ce3c5aac685236e835de
)

> T6. Sec. 5, "Fixed options:": Suggest adding ECVRF_hash_points as another
fixed option after ECVRF_nonce_generation. (See comment below regarding the
name of this technique.)

Agree with renaming this technique (see below, T11). Decided not to list as
a fixed option, because fixed options are specified in a ciphersuite, but
there is no reason to specify it as part of the ciphersuite. Just like
ECVRF_prove and ECVRF_verify, it calls functions that are specified as part
of the ciphersuite, but it itself does not need to be specified as part of
the ciphersuite.

> T7. Sec. 5.4.1.1, "Fixed option:" / "arbitrary_string_to_point" (and
elsewhere):  The term "arbitrary" is a misnomer in that it is applied to a
string that has already been hashed. Moreover, one of the two options
supported for this function in Sec. 5.5 requires the string to be exactly
32 octets, and the other requires it to be at least 32 octets (in a suite
that uses SHA-512, so the string will be exactly 64 octets). This contrasts
with [PWHVNRG17]'s idea in Appendix A of "a hash function H1 that maps
arbitrary-length strings to points on an elliptic curve". Indeed, the "hash
to curve" functions in the document are the actual "arbitrary string to
point" mappings. One possible solution would be to replace
"arbitrary_string_to_point" with a newly defined "encode", following the
model given by 5.4.1.2. "string_to_hash" would be computed as "suite_string
|| one_string || PK_string || alpha_string || ctr_string || zero_string",
i.e., step 6B without the hashing, and passed to "encode". Instantiations
of the "encode" option would be defined in Sec. 5.5.
>
> An instantiation would include both the hashing and the existing
conversion of the hash value to an elliptic curve point.

 Renamed "arbitrary_string_to_point" to "interpret_hash_value_as_a_point"
[in this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/577972f341bf530330915eb0b8838f953a6fa9e6
)

 > T8. Sec. 5.4.2: After "not compatible with each other", suggest adding
"and are intended for specific suite(s)".

 Rephrased [in this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/577972f341bf530330915eb0b8838f953a6fa9e6
)

> T9. Sec. 5.4.2.1 (also 5.4.2.2), "Output:" / "k": Suggest adding "nonce"
before "an integer" to clarify purpose of k.

Done [in this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/577972f341bf530330915eb0b8838f953a6fa9e6
)

> T10. Sec. 5.4.2.1, next to last para: Suggest adding a note that qlen,
the length in bits of q in RFC6979, is not to be confused with qLen, the
length in octets of q in this document.

 Done [in this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/577972f341bf530330915eb0b8838f953a6fa9e6
)

> T11. Sec. 5.4.3 (and elsewhere): Suggest redefining "ECVRF_hash_points"
as "ECVRF_challenge_generation", limiting to four inputs (H, Gamma, U, and
V), and labeling output as "challenge value" rather than "hash value".
Rationale: ECVRF_hash_points is only used in this document for mapping the
four specified inputs to the challenge c, so it is similar to
ECVRF_nonce_generation in its limited purpose. The suggested change does
not affect the value computed by the function on the specified inputs, only
the way the function is specified.  The benefit of the change is that it
simplifies implementation. In particular, implementations only need to be
able to handle four points, not an arbitrary number M. Calls to the
algorithm would need to be updated similarly. (If the function is not
redefined as suggested here, then a note should be added to indicate that
implementations MUST be able to handle the case M = 4; other cases are
optional.)

Done [in this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/577972f341bf530330915eb0b8838f953a6fa9e6
)

> T12. Sec. 7.6: Suggest moving the final sentence to its own section,
titled "Dependence of challenge on generator and public key". The sentence
explains why the challenge c still depends on all six points (B, H, Y,
Gamma, U, and V) as per the formal specification in [PWHVNRG17], rather
than just the four points input to ECVRF_hash_points. This discussion is
important from a security proof perspective and it is separate from the
prehashing considerations. Suggest adding "via the point H" to the end of
the sentence.

Done [in this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/577972f341bf530330915eb0b8838f953a6fa9e6
)

> Editorial Comments

> E1. Sec. 1.1, para 1, line 3: "with corresponding" --> "with the
corresponding"

Done in [this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/07a2008bc94c7372b0fe28236ba6462c40f31fff
)

> E2. Sec. 1.1, para 2, line 2: "on data" --> "of data"?

Changed to make more sense in [this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/07a2008bc94c7372b0fe28236ba6462c40f31fff
)

> E3. Sec. 2, last para, line 3: "the VRF also comes" --> "the VRFs defined
in this document also come" (to match the model discussed in the prior
paras where beta can be derived from pi, and to recognize that there are
multiple VRFs in the document)

Done in [this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/07a2008bc94c7372b0fe28236ba6462c40f31fff
)

> E4. Sec. 3.1, para 3, line 3: "it must only hold if" --> "it is only
required to hold if" (see next)

Rephrased (slightly differently) in response to comments from Chris Wood,
[here](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/91b83b6d68d84b04963dd89e8afa42424ecaae98#diff-382a26a0bcccb52bc8c6ab7c862ed0ee8848df81772776e9fae86b36e5b1be11R670
)

> E5. Sec. 3.2, para 3, line 3: "it holds only if" --> "it is only required
to hold if" (to clarify that the property may also hold if the condition is
not met)

Rephrased (slightly differently) in response to comments from Chris Wood
[here](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/91b83b6d68d84b04963dd89e8afa42424ecaae98#diff-382a26a0bcccb52bc8c6ab7c862ed0ee8848df81772776e9fae86b36e5b1be11R677
)

> E6. Sec. 3.3, next to last para, line 2: "knows the valid VRF proof" -->
"knows a valid VRF proof" (ECVRF has multiple valid proofs, one for each k)

 Done in [this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/07a2008bc94c7372b0fe28236ba6462c40f31fff
)

> E7. Sec. 4, para 2, line 3: "parametrized" --> "parameterized"

I will appeal to the authority of the Merriam-Webster and American Heritage
Dictionaries, which [allow](
https://www.merriam-webster.com/dictionary/parameterize) [both](
https://www.ahdictionary.com/word/search.html?q=parameterize).

> E8. Sec. 4, "Primitives used:" / "RSASP1": "secret key" --> "private
key", "secret RSA exponent" --> "private RSA exponent" (to match "RSA
private key" parameter and terminology in [RFC8017])

Done [in this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/7d6cf6e49277db5c546e0179e3f36da4b38f02c9
)

> E9. Sec. 4.3, "Input:" / "pi_string": "length k" --> "length n"

I think you mean "length n" --> "length k". Fixed. [in this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/7d6cf6e49277db5c546e0179e3f36da4b38f02c9
)

> E10. Sec. 5.3: Reverse order of "pi_string", "alpha_string" in
ECVRF_verify function call and "Input:" list (to match API in Sec. 2)

Done in [this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/07a2008bc94c7372b0fe28236ba6462c40f31fff
)

> E11. Sec. 5.6.1, step 14: "bad_pk[0]...bad_pk[6]" --> "[bad_pk[0],
...,bad_pk[6]] (to use set notation rather than concatenation -- compare
with step 3 in Sec. 5.4.3)

Done  in [this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/07a2008bc94c7372b0fe28236ba6462c40f31fff
)

> E12. Sec. 7.5, line 5: "Initialized" --> "Initialize"

Done in [this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/07a2008bc94c7372b0fe28236ba6462c40f31fff
)

> E13. Sec. 7.7, next to last para: "RSA VRF" --> "RSA-FDH-VRF"

Done in [this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/07a2008bc94c7372b0fe28236ba6462c40f31fff
)

> E14. Sec. 7.7, last para, "elliptic curve VRF" --> "ECVRF"

Done  in [this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/07a2008bc94c7372b0fe28236ba6462c40f31fff
)