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

["Jason Resch" <[e-mail]>]

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" target="_blank" rel="nofollow">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