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

[Christopher Wood <[e-mail]>]

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 <[e-mail]> 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*
>
> 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?
>

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 "/"?
> Would it be clearer to represent these divisions as multiplications of the
> multiplicative inverse computed over p?
>

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