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

From: "Jason Resch" <[email-masked]>
Date: Thu, 5 Apr 2018 03:56:35 +0000

Christopher,

Thank you for your responses. I am glad that my feedback was helpful.

I recently wrote some reference implementations of my suggestion below for implementing HashToBase() for any given input string and curve.  It uses the left-most bits of HKDF applied to the input, where the number of total bits selected is determined by the size of the prime field.  I have ensured consistency via some test vectors I defined and are included in this sample code.  I tested both NIST P-256, and NIST P-521. Note that these examples only implement "Simplified SWU", but this can be easily extended to support the other algorithms.

I have attached a Python3 implementation to this e-mail, I also have a Java implementation I can send if it would be of value. Both produce consistent results as far as I have been able to test.

Also, I found something interesting in regards to supporting Koblitz curves, or other curves where a = 0 (such as BN-254).  By accident, I discovered that it didn't seem to matter whether I used "(-b / a)" or any other number.  The Simplified SWU algorithm appeared to always map to a valid point.  Does this make sense?  Is there a special motivation for using (-b / a) as opposed to some other constant?

Best,

Jason

----- Original message -----
From: Christopher Wood <[email-masked]>
To: [email-masked]
Cc: [email-masked]
Subject: Re: [Cfrg] Comments regarding draft-sullivan-cfrg-hash-to-curve
Date: Mon, Mar 26, 2018 8:46 AM

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

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

---

From: Christopher Wood <[email-masked]>
Date: Mon, 09 Apr 2018 04:30:02 +0000

Hi Jason,

Please see inline below.

On Tue, Apr 3, 2018 at 9:36 PM Jason Resch <[email-masked]> wrote:

>
> I recently wrote some reference implementations of my suggestion below for
> implementing HashToBase() for any given input string and curve.  It uses
> the left-most bits of HKDF applied to the input, where the number of total
> bits selected is determined by the size of the prime field.  I have ensured
> consistency via some test vectors I defined and are included in this sample
> code.  I tested both NIST P-256, and NIST P-521. Note that these examples
> only implement "Simplified SWU", but this can be easily extended to support
> the other algorithms.
>
> I have attached the Python and Java implementations to this e-mail, the
> python one is a bit more concise and is self contained in one file, while
> the Java one is implemented across several files (in the zip file), but
> both produce consistent results as far as I have been able to test.
>

Thanks for sharing the code. We're currently working to port all the
algorithms to hacspec. This routine will certainly be part of that effort.
When the time comes, I will use it to test against our own implementation.

>
> Also, I found something interesting in regards to supporting Koblitz
> curves, or other curves where a = 0 (such as BN-254).  By accident, I
> discovered that it didn't seem to matter whether I used "(-b / a)" or any
> other number.  The Simplified SWU algorithm appeared to always map to a
> valid point.  Does this make sense?  Is there a special motivation for
> using (-b / a) as opposed to some other constant?
>

Interesting. I don't know off hand. I'll have to investigate and get back
to you.

Best,
Chris

---

From: "Jason Resch" <[email-masked]>
Date: Mon, 9 Apr 2018 17:27:53 +0000

Christopher,

That's excellent. I am glad this code is useful and can contribute towards the implementation of hacspec.

Please reach out to me if you have any questions, comments, concerns or issues regarding the code.

Best,

Jason Resch

----- Original message -----
From: Christopher Wood <[email-masked]>
To: [email-masked]
Cc: [email-masked]
Subject: Re: [Cfrg] Comments regarding draft-sullivan-cfrg-hash-to-curve
Date: Sun, Apr 8, 2018 11:30 PM

Hi Jason,

Please see inline below.

I have attached the Python and Java implementations to this e-mail, the python one is a bit more concise and is self contained in one file, while the Java one is implemented across several files (in the zip file), but both produce consistent results as far as I have been able to test.

Thanks for sharing the code. We're currently working to port all the algorithms to hacspec. This routine will certainly be part of that effort. When the time comes, I will use it to test against our own implementation.

Interesting. I don't know off hand. I'll have to investigate and get back to you.

Best,

Chris