Subject: Re: [CFRG] IRTF Chair review of draft-irtf-cfrg-hash-to-curve-13

From: Colin Perkins <[email-masked]>
Date: Fri, 4 Mar 2022 19:54:41 +0000

Thanks,  I confirm that this addresses my comments. 

Chairs – if you can please confirm you’re okay with this progressing, then I’ll move it to IRSG review.

Colin

> On 18 Feb 2022, at 22:03, Christopher Wood <[email-masked]> wrote:
> 
> Thanks for the review, Colin! We believe we adequately addressed your comments in the latest version of the draft (which includes some other changes beyond your review, including a ciphersuite change). You can view the diff here:
> 
>   https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-hash-to-curve-14.txt
> 
> Please see inline below for followup responses to each of your comments.
> 
>> On Feb 14, 2022, at 4:22 PM, Colin Perkins <[email-masked]> wrote:
>> 
>> The CFRG chairs have requested that draft-irtf-cfrg-hash-to-curve-13 be published as an RFC on the IRTF stream. The IRTF publication process is described in RFC 5743, and comprises a review by the IRSG to ensure technical and editorial quality, followed by a check by the IESG to ensure the work does not conflict with IETF standards activities.
>> 
>> As IRTF Chair, I perform an initial review of all drafts submitted for publication on the IRTF stream before sending them for detailed review by the IRSG. This note provides my review comments for discussion.
>> 
>> 
>> Result: Ready with nits
>> 
>> RFC 5743 compliance: The draft follows the guidelines in RFC 5743
>> 
>> 
>> Comments
>> 
>> The draft looks to be well written and is clearly motivated. The specification is generally clear and well structured, and does a good job of signposting what parts of the draft relate to the various different curves and when the use the various functions. I don't have a background in cryptography, so I can’t check the detail, but it seems clear to me what I would need to implement in various cases.
>> 
>> 
>> I have a number of nits and questions where I found the text not entirely clear:
>> 
>> * In the description of hash_to_field in Section 3, the prose description is clear, but the terminology “{0, 1}^* x {1, 2, ...} -> (F, F, …)” is not. Is this correct?
> 
> Yes, this is correct. This is shorthand for the Cartesian product between the sets {0,1}^* and the natural numbers, yielding an output set of field (F) elements. That said, I don't think the terminology was offering anything that the description was not, so we removed it. See [this commit](https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/1babed904e58e5093c58d47a822b9a5cfc4264d6).
> 
>> 
>> * The prose description of hash_to_field in Section 3 says it takes an arbitrary byte string as input, but the description of encode_to_curve() later in that section, and the description in Section 5, both take a byte string and a count.
> 
> The descriptions say that it maps arbitrary inputs to one or more field elements, which isn't incorrect. It simply doesn't say that the number of outputs is also an input parameter. We think it would be less clear if we were to rewrite the description this was, so we left the text as-is.
> 
>> 
>> * The descriptions of the encode_to_curve() and hash_to_curve() algorithms in Section 3, are explicit about the input, output, and steps, which is good. It would help to describe hash_to_field, map_to_curve, and clear_cofactor in a similar way. For example:
>> 
>>     hash_to_field(msg, count)
>> 
>>     Input: msg, an arbitrary-length byte string
>>            count, ...
>>     Output: (u_0, ..., u_(count - 1)), a list of field elements
>> 
>>     Steps:
>>     (See Section 5)
> 
> This is a sound improvement given that we removed the terminology as noted above. We made the change in [this commit](https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/1ff7687b36ae94a3ef4e28d81da16bbb9b67cdbf).
> 
>> 
>> * Section 3: “As an example, consider a fictional application named Quux that defines several different ciphersuites” - presumably that also only uses a single random oracle?
> 
> We didn't mention this in contrast to the second example since, in the latter, the key point is that the application requires two _independent_ random oracles, and it forces them to be independent by using the same suite for the same curve but with a different tag. That said, we can clarify that in the original example there's no need for multiple random oracles targeting the same curve. See [this commit](https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/f4834e86a3b0d0293945779fe5fccc072a422e88).
> 
>> 
>> * “The example tags given above are assumed to be ASCII-encoded byte strings without null termination, which is the RECOMMENDED format” - presumably the rationale for avoiding UTF-8 is that there are sometime ambiguous encodings for particular strings in UTF-8? If so, this seems like a common gotcha, so might be worth calling out explicitly. 
> 
> We think this is covered by the following sentence: "Other encodings can be used, but in all cases the encoding as a sequence of bytes MUST be specified unambiguously."
> 
>> 
>> * In Section 4.1, the terminology sign_i presumably represents the i’th element of sign. It might be helpful to explicitly explain the terminology, since it’s used throughout the draft and isn’t common syntax. Further, the “_” character is used in some places as a separator in the middle of variable names, and in other places to indicate an index. This may be confusing. 
> 
> This isn't quite right. In Section 4.1, sign_i is a variable that stores the sign of the i-th element: 
> 
>   sign_i = x_i mod 2
> 
> It's not meant to be short-hand for the index operator. 
> 
>> 
>> * In Section 5.3, the expand_message parameter says “(see discussion above)”; should it say “(see Section 5.4)”?
> 
> Yep, good catch. Fixed in [this commit](https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/d7ef3736a2c6b7fb234c1268406b6a503beb6ab8).
> 
>> 
>> * In Section 5.4.1, should the phrase “For security, H must meet the following requirements” be rather “...H MUST meet...”?
> 
> Yep. Fixed in [this commit](https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/6b63e2c5dfc3d11e23b18d5e2b34706e3051323e).
> 
>> 
>> * In Section 5.4.1, would “Note that the string Z_pad is prefixed to msg when computing b_0 (step 7)” be clearer as “Note that the string Z_pad is prefixed to msg (step 6) prior to computing b_0 (step 7)” ?
> 
> That's a fine improvement. See [this commit](https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/8d3eaff345884ae5739f4f0cd4a2d603c4d6a2ef).
> 
>> 
>> * In Section 5.4.2, should the phrase “For security, H must meet the following criteria” be rather “...H MUST meet...”?
> 
> As above, yep. Fixed in [this commit](https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/b018d08e126a53b99b48efe43ec9fd87aace9a50).
> 
>> * In Section 6.2, the definition of a generic interface for map_to_curve() is appropriate. The later sections of the draft define specific implementations of that interface (e.g., map_to_curve_simple_swu() in Section 6.6.2). The definitions of these variants are less clearly stated. Would it make sense to expand the definitions in Sections 6.6 and 6.7 to be explicit about the interface being defined? For example, in section 6.6.2, the text would change to:
>> 
>>     and Boneh [WB19] generalize and optimize this mapping.
>> 
>>     The following procedure implements map_to_curve_simple_swu(u).
>> 
>>     (x, y) = map_to_curve_simple_swu(u)
>> 
>>     Preconditions: ...
>> 
> 
> These aren't meant to be implemented as-is, so we don't think expanding the definitions would be helpful. Instead, the straightline implementations later in the document are meant to be implemented.
> 
>> 
>> * In Section 6.6.1, I was surprised the operations say “tv1 = 1 - tv1” on line 3, rather than assigning a new tv_ value. Similarly, rather than “set y = -y” on line 15, I was surprised it didn’t try to avoid reassigning y. There are similar issues in other operations in the draft. This doesn’t matter as such, but the mix of single-assignment and mutable programming styles is a little unexpected. (The cost of changing the draft to address this is likely not worth the benefit)
> 
> Indeed -- good eye. However, at this point, given that we've carefully gone through the pseudocode to make sure it matches the reference code in Sage, we don't think changes to improve style would be helpful. Compilers will likely optimize the code for variable reuse where appropriate anyway. 
> 
>> 
>> * (I have only briefly skimmed the appendices)
>> 
>> Finally, I note that there are many numeric constants and pseudo-code algorithms in the draft. Is there a test suite to help demonstrate correctness or are parts of the draft derived from running code? I believe the draft has been reviewed carefully, but there is a lot detail where it is easy to make a mistake. There is Sage code in https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve - is this somehow verified to match the draft?
> 
> We have run all tests on code that (literally) matches the pseudocode, so we have high confidence in its correctness. It's also seen substantial review from other implementers and reviewers in the past.
> 
> Thanks again,
> Chris, on behalf of the authors

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Sat, 5 Mar 2022 03:38:26 +0300

Dear Colin and Chris,

I confirm that I am completely fine with this progressing (as a document
shepherd and one of the CFRG chairs).

Best regards,
Stanislav

On Fri, 4 Mar 2022 at 22:54, Colin Perkins <[email-masked]> wrote:

> > Thanks for the review, Colin! We believe we adequately addressed your
> comments in the latest version of the draft (which includes some other
> changes beyond your review, including a ciphersuite change). You can view
> the diff here:
> >
> >> The CFRG chairs have requested that draft-irtf-cfrg-hash-to-curve-13 be
> published as an RFC on the IRTF stream. The IRTF publication process is
> described in RFC 5743, and comprises a review by the IRSG to ensure
> technical and editorial quality, followed by a check by the IESG to ensure
> the work does not conflict with IETF standards activities.
> >>
> >> As IRTF Chair, I perform an initial review of all drafts submitted for
> publication on the IRTF stream before sending them for detailed review by
> the IRSG. This note provides my review comments for discussion.
> >>
> >>
> >> Result: Ready with nits
> >>
> >> The draft looks to be well written and is clearly motivated. The
> specification is generally clear and well structured, and does a good job
> of signposting what parts of the draft relate to the various different
> curves and when the use the various functions. I don't have a background in
> cryptography, so I can’t check the detail, but it seems clear to me what I
> would need to implement in various cases.
> >>
> >>
> >> * In the description of hash_to_field in Section 3, the prose
> description is clear, but the terminology “{0, 1}^* x {1, 2, ...} -> (F, F,
> …)” is not. Is this correct?
> >
> > Yes, this is correct. This is shorthand for the Cartesian product
> between the sets {0,1}^* and the natural numbers, yielding an output set of
> field (F) elements. That said, I don't think the terminology was offering
> anything that the description was not, so we removed it. See [this commit](
> https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/1babed904e58e5093c58d47a822b9a5cfc4264d6
> ).
> >
> >>
> >> * The prose description of hash_to_field in Section 3 says it takes an
> arbitrary byte string as input, but the description of encode_to_curve()
> later in that section, and the description in Section 5, both take a byte
> string and a count.
> >
> > The descriptions say that it maps arbitrary inputs to one or more field
> elements, which isn't incorrect. It simply doesn't say that the number of
> outputs is also an input parameter. We think it would be less clear if we
> were to rewrite the description this was, so we left the text as-is.
> >
> >>
> >> * The descriptions of the encode_to_curve() and hash_to_curve()
> algorithms in Section 3, are explicit about the input, output, and steps,
> which is good. It would help to describe hash_to_field, map_to_curve, and
> clear_cofactor in a similar way. For example:
> >>
> > This is a sound improvement given that we removed the terminology as
> noted above. We made the change in [this commit](
> https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/1ff7687b36ae94a3ef4e28d81da16bbb9b67cdbf
> ).
> >
> >>
> >> * Section 3: “As an example, consider a fictional application named
> Quux that defines several different ciphersuites” - presumably that also
> only uses a single random oracle?
> >
> > We didn't mention this in contrast to the second example since, in the
> latter, the key point is that the application requires two _independent_
> random oracles, and it forces them to be independent by using the same
> suite for the same curve but with a different tag. That said, we can
> clarify that in the original example there's no need for multiple random
> oracles targeting the same curve. See [this commit](
> https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/f4834e86a3b0d0293945779fe5fccc072a422e88
> ).
> >
> >>
> >> * “The example tags given above are assumed to be ASCII-encoded byte
> strings without null termination, which is the RECOMMENDED format” -
> presumably the rationale for avoiding UTF-8 is that there are sometime
> ambiguous encodings for particular strings in UTF-8? If so, this seems like
> a common gotcha, so might be worth calling out explicitly.
> >
> > We think this is covered by the following sentence: "Other encodings can
> be used, but in all cases the encoding as a sequence of bytes MUST be
> specified unambiguously."
> >
> >>
> >> * In Section 4.1, the terminology sign_i presumably represents the i’th
> element of sign. It might be helpful to explicitly explain the terminology,
> since it’s used throughout the draft and isn’t common syntax. Further, the
> “_” character is used in some places as a separator in the middle of
> variable names, and in other places to indicate an index. This may be
> confusing.
> >
> >> * In Section 5.3, the expand_message parameter says “(see discussion
> above)”; should it say “(see Section 5.4)”?
> >
> > Yep, good catch. Fixed in [this commit](
> https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/d7ef3736a2c6b7fb234c1268406b6a503beb6ab8
> ).
> >
> >>
> >> * In Section 5.4.1, should the phrase “For security, H must meet the
> following requirements” be rather “...H MUST meet...”?
> >
> > Yep. Fixed in [this commit](
> https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/6b63e2c5dfc3d11e23b18d5e2b34706e3051323e
> ).
> >
> >>
> >> * In Section 5.4.1, would “Note that the string Z_pad is prefixed to
> msg when computing b_0 (step 7)” be clearer as “Note that the string Z_pad
> is prefixed to msg (step 6) prior to computing b_0 (step 7)” ?
> >
> > That's a fine improvement. See [this commit](
> https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/8d3eaff345884ae5739f4f0cd4a2d603c4d6a2ef
> ).
> >
> >>
> >> * In Section 5.4.2, should the phrase “For security, H must meet the
> following criteria” be rather “...H MUST meet...”?
> >
> > As above, yep. Fixed in [this commit](
> https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/b018d08e126a53b99b48efe43ec9fd87aace9a50
> ).
> >
> >> * In Section 6.2, the definition of a generic interface for
> map_to_curve() is appropriate. The later sections of the draft define
> specific implementations of that interface (e.g., map_to_curve_simple_swu()
> in Section 6.6.2). The definitions of these variants are less clearly
> stated. Would it make sense to expand the definitions in Sections 6.6 and
> 6.7 to be explicit about the interface being defined? For example, in
> section 6.6.2, the text would change to:
> >>
> > These aren't meant to be implemented as-is, so we don't think expanding
> the definitions would be helpful. Instead, the straightline implementations
> later in the document are meant to be implemented.
> >
> >>
> >> * In Section 6.6.1, I was surprised the operations say “tv1 = 1 - tv1”
> on line 3, rather than assigning a new tv_ value. Similarly, rather than
> “set y = -y” on line 15, I was surprised it didn’t try to avoid reassigning
> y. There are similar issues in other operations in the draft. This doesn’t
> matter as such, but the mix of single-assignment and mutable programming
> styles is a little unexpected. (The cost of changing the draft to address
> this is likely not worth the benefit)
> >
> > Indeed -- good eye. However, at this point, given that we've carefully
> gone through the pseudocode to make sure it matches the reference code in
> Sage, we don't think changes to improve style would be helpful. Compilers
> will likely optimize the code for variable reuse where appropriate anyway.
> >
> >>
> >> Finally, I note that there are many numeric constants and pseudo-code
> algorithms in the draft. Is there a test suite to help demonstrate
> correctness or are parts of the draft derived from running code? I believe
> the draft has been reviewed carefully, but there is a lot detail where it
> is easy to make a mistake. There is Sage code in
> https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve - is this somehow
> verified to match the draft?
> >
> > We have run all tests on code that (literally) matches the pseudocode,
> so we have high confidence in its correctness. It's also seen substantial
> review from other implementers and reviewers in the past.
> >
> > Thanks again,

---

From: Colin Perkins <[email-masked]>
Date: Mon, 7 Mar 2022 18:45:33 +0000

Thanks – I have requested the IRSG review this draft.
Colin

> On 5 Mar 2022, at 00:38, Stanislav V. Smyshlyaev <[email-masked]> wrote:
> 
> Dear Colin and Chris,
> 
> I confirm that I am completely fine with this progressing (as a document shepherd and one of the CFRG chairs). 
> 
> Best regards,
> Stanislav
> 
> On Fri, 4 Mar 2022 at 22:54, Colin Perkins <[email-masked] <mailto:[email-masked]>> wrote:
> > On 18 Feb 2022, at 22:03, Christopher Wood <[email-masked] <mailto:[email-masked]>> wrote:
> > 
> >   https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-hash-to-curve-14.txt <https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-hash-to-curve-14.txt>
> > 
> >> On Feb 14, 2022, at 4:22 PM, Colin Perkins <[email-masked] <mailto:[email-masked]>> wrote:
> >> 
> > Yes, this is correct. This is shorthand for the Cartesian product between the sets {0,1}^* and the natural numbers, yielding an output set of field (F) elements. That said, I don't think the terminology was offering anything that the description was not, so we removed it. See [this commit](https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/1babed904e58e5093c58d47a822b9a5cfc4264d6 <https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/1babed904e58e5093c58d47a822b9a5cfc4264d6>).
> > 
> >> 
> > This is a sound improvement given that we removed the terminology as noted above. We made the change in [this commit](https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/1ff7687b36ae94a3ef4e28d81da16bbb9b67cdbf <https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/1ff7687b36ae94a3ef4e28d81da16bbb9b67cdbf>).
> > 
> >> 
> > We didn't mention this in contrast to the second example since, in the latter, the key point is that the application requires two _independent_ random oracles, and it forces them to be independent by using the same suite for the same curve but with a different tag. That said, we can clarify that in the original example there's no need for multiple random oracles targeting the same curve. See [this commit](https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/f4834e86a3b0d0293945779fe5fccc072a422e88 <https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/f4834e86a3b0d0293945779fe5fccc072a422e88>).
> > 
> >> 
> > Yep, good catch. Fixed in [this commit](https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/d7ef3736a2c6b7fb234c1268406b6a503beb6ab8 <https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/d7ef3736a2c6b7fb234c1268406b6a503beb6ab8>).
> > 
> >> 
> > Yep. Fixed in [this commit](https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/6b63e2c5dfc3d11e23b18d5e2b34706e3051323e <https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/6b63e2c5dfc3d11e23b18d5e2b34706e3051323e>).
> > 
> >> 
> > That's a fine improvement. See [this commit](https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/8d3eaff345884ae5739f4f0cd4a2d603c4d6a2ef <https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/8d3eaff345884ae5739f4f0cd4a2d603c4d6a2ef>).
> > 
> >> 
> > As above, yep. Fixed in [this commit](https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/b018d08e126a53b99b48efe43ec9fd87aace9a50 <https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/commit/b018d08e126a53b99b48efe43ec9fd87aace9a50>).
> > 
> >> Finally, I note that there are many numeric constants and pseudo-code algorithms in the draft. Is there a test suite to help demonstrate correctness or are parts of the draft derived from running code? I believe the draft has been reviewed carefully, but there is a lot detail where it is easy to make a mistake. There is Sage code in https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve <https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve> - is this somehow verified to match the draft?
> >