Subject: [Cfrg] Comments regarding draft-sullivan-cfrg-hash-to-curve

From: "Jason Resch" <[email-masked]>
Date: Tue, 20 Mar 2018 00:31:26 +0000

I recently read and implemented the draft "draft-sullivan-cfrg-hash-to-curve" Nick Sullivan and Christopher Wood:

Sullivan & Wood         Expires September 6, 2018              [Page 17]
Internet-Draft                hash-to-curve                   March 2018

Available at: https://datatracker.ietf.org/doc/draft-sullivan-cfrg-hash-to-curve/?include_text=1

And had some feedback I wished to make available to the authors and the list.

First, I wanted to thank the authors for organizing this draft; I think standards on hashing to EC points are sorely needed and this is an excellent collection of recommendations that simplify things for implementors such as myself.

Comment 1: Algorithm Recommendations Table

Is there any reason not to include recommendations be made for other common curves, such as NIST P-521, Curve1174, or Koblitz curves such as secp256k1?

Comment 2: Icart vs. SWU Simplified

Both of these are listed as having performance of "O(log^3 q)". Given this, is there a significant advantage to using Icart for P-384?  Implementation simplicity might motivate using SWU Simplified for all curves, for example, as opposed to special casing NIST P-384.

Comment 3: Algorithm description of SWU Simplified

I did not understand this line:

"5. Output (-g * alpha) * (g * beta)"

- g was not defined here, except above as a function of x, but here it is being used in a multiplication.
- g might be confused with the generator point for the curve
- The output should be in the form of a point with coordinates x and y, should it not?

Steps "19" and "20" use "//" presumably to denote division, but "//" is also used later to represent comments.  Is there any difference here between "//" and "/"?
Would it be clearer to represent these divisions as multiplications of the multiplicative inverse computed over p?

Step "21" indicates an equality comparison.  Unless implemented specially, these could lead to side-channel attacks as an equality check of equal values takes longer than one where the values are unequal. It might be more secure to separately compute both comparisons, i.e. also compute "e_2 = (y2 ^ 2 == h3)" as a mitigation strategy or alternative to implementing constant time equality checks, which might not be readily available in different BigInteger libraries/languages.

Comment 4: Definition of HashToBase

An example is given that this can be any cryptographic hash function, such as SHA-256.  However, I think it would be better if this is defined as a method supporting variable length outputs.  For example, HKDF (Hmac Key Derivation Function).  The justification being that some elliptic curves operate on fields that are too large, even for SHA-512 (e.g. NIST P-521), and naive attempts at extending the length of a hash may otherwise be designed insecurely.

If the function is specified as HKDF (which operates on bytes rather than bits) there should be clarification as to which bits of the output are to be used (e.g. the left-most bits output by HKDF).

There should be some security recommendation as well, in terms of selecting hash functions with security properties appropriately matched for the security of the curve.

Comment 5: Clarification for supported curves

The draft indicates that Simplified SWU works for all curves where: p == 3 % 4

However, the Koblitz curve secp256k1 has a p such that p == 3 % 4, yet it does not seem to work with Simplified SWU. The problem is that it's "a" coefficient is defined as zero. Thus it isn't possible to compute (-b / a) which is required and used in the Simplified SWU method.  Is there a means around this?

Those are all the comments that I had.

Best Regards,

Jason Resch

---

From: Christopher Wood <[email-masked]>
Date: Mon, 26 Mar 2018 13:45:47 +0000

Hi Jason,

Thanks for the review and feedback. Please see inline below for comments.

On Mon, Mar 19, 2018 at 5:35 PM Jason Resch <[email-masked]> wrote:

> *Comment 1: Algorithm Recommendations Table*
>
> Is there any reason not to include recommendations be made for other
> common curves, such as NIST P-521, Curve1174, or Koblitz curves such as
> secp256k1?
>

No. We didn't have an immediate use for them. That said, we should be
inclusive to all curves and provide appropriate recommendations. I filed:

https://github.com/chris-wood/draft-sullivan-cfrg-hash-to-curve/issues/9

>
> *Comment 2: Icart vs. SWU Simplified*
>
> Both of these are listed as having performance of "O(log^3 q)". Given
> this, is there a significant advantage to using Icart for P-384?
> Implementation simplicity might motivate using SWU Simplified for all
> curves, for example, as opposed to special casing NIST P-384.
>

That may well be the case. We are still working on the analysis and cost
comparison. I suspect we will prune the list of algorithms specified (in
the main body) in the future. If and when that happens, we may move all
other algorithms to the appendix.

>
> *Comment 3: Algorithm description of SWU Simplified*
>

This is a bug in that description. I'll clean this up in the next revision.

>
> Steps "19" and "20" use "//" presumably to denote division, but "//" is
> also used later to represent comments.  Is there any difference here
> between "//" and "/"?

Good point. There is no difference as written. I will clarify this notation.

>
> Step "21" indicates an equality comparison.  Unless implemented specially,
> these could lead to side-channel attacks as an equality check of equal
> values takes longer than one where the values are unequal. It might be more
> secure to separately compute both comparisons, i.e. also compute "e_2 = (y2
> ^ 2 == h3)" as a mitigation strategy or alternative to implementing
> constant time equality checks, which might not be readily available in
> different BigInteger libraries/languages.
>

Another good point. I will make sure these are written to be constant-time
comparisons.

>
> *Comment 4: Definition of HashToBase*
>
> An example is given that this can be any cryptographic hash function, such
> as SHA-256.  However, I think it would be better if this is defined as a
> method supporting variable length outputs.  For example, HKDF (Hmac Key
> Derivation Function).  The justification being that some elliptic curves
> operate on fields that are too large, even for SHA-512 (e.g. NIST P-521),
> and naive attempts at extending the length of a hash may otherwise be
> designed insecurely.
>

This does in fact seem better. I'll see if we can integrate it.

>
> If the function is specified as HKDF (which operates on bytes rather than
> bits) there should be clarification as to which bits of the output are to
> be used (e.g. the left-most bits output by HKDF).
>
> There should be some security recommendation as well, in terms of
> selecting hash functions with security properties appropriately matched for
> the security of the curve.
>

Agreed. We will add this missing information.

>
>
>
> *Comment 5: Clarification for supported curves*The draft indicates that
> Simplified SWU works for all curves where: p == 3 % 4
>
> However, the Koblitz curve secp256k1 has a p such that p == 3 % 4, yet it
> does not seem to work with Simplified SWU. The problem is that it's "a"
> coefficient is defined as zero. Thus it isn't possible to compute (-b / a)
> which is required and used in the Simplified SWU method.  Is there a means
> around this?
>

Thanks for pointing this out. I'm not sure off hand and will investigate
more.

Thanks again for your very thorough feedback. I will circle back with you
when the next revision is made.

Best,
Chris