Subject: [Cfrg] Some comments on draft-irtf-cfrg-hash-to-curve-01

From: Richard Barnes <[email-masked]>
Date: Sat, 21 Jul 2018 13:00:27 -0400

Hey all,

On the plane back from the IETF meeting, I set about implementing
draft-irtf-cfrg-hash-to-curve for hashing to P-256 (as a prelude to
implementing draft-krawczyk-cfrg-opaque).  A few comments (not a complete
review):

* The section describing HashToBase could be more explicit about the how
the octet string H(x) is to be interpreted as a field element.  Since we're
only talking about prime fields, you might do something like the following:
  * Interpret H(x) as a big-endian integer h
  * Reduce h mod 2^(log2(p) + 1)
  * Reduce h mod p

* The encoding algorithms are obviously the most complicated thing here.
For debugging, it would be helpful to have test vectors that show all of
the steps in the encoding algorithms for some curve.  In case it's helpful,
I've pasted below a Python implementation of map2curve_simple_swu for
P-256, with print statements that produce the required test vectors.

* In the description of the simplified SWU method, the variable name
"alpha" is re-used for the input and an internal variable, which is extra
confusing because these values have different types (octet string vs. field
element).  It would be clearer for the encoding algorithms to take a field
element as input, since the only thing they do with their octet string
inputs is hash them to a field element.

* In the section describing FFSTV13, it's not clear whether the 0/1 values
prepended to alpha are bits or bytes.  If it's all the same
cryptographically, it would probably be more implementer-friendly to make
them bytes.

Other than that, I found the doc pretty readable, and clear about what
algorithms you should be implementing (at least in the use case I'm focused
on right now).

--Richard

-----BEGIN h2c.py-----
#!/usr/bin/env python

from random import randint

# https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.186-4.pdf
p256 =
115792089210356248762697446949407573530086143415290314195533631308867097853951
a256 = p256 - 3
b256 = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b

Gx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
Gy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5

def on_curve(x, y):
    lhs = (y * y) % p256
    rhs = ((x * x * x) + (a256 * x) + b256) % p256
    return lhs == rhs

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a):
    g, x, y = egcd(a, p256)
    return x % p256

def map_to_curve_swu(t):
    p4 = (p256 + 1) // 4

    alpha = (t * t) % p256
    print " 2", alpha

    alpha = p256 - alpha
    print " 3", alpha

    right = (alpha * alpha + alpha) % p256
    print " 4", right

    right = modinv(right)
    print " 5", right

    right = (right + 1) % p256
    print " 6", right

    left = p256 - b256
    print " 7", left

    left = (left * modinv(a256)) % p256
    print " 8", left

    x2 = (left * right) % p256
    print " 9", x2

    x3 = (alpha * x2) % p256
    print "10", x3

    h2 = (x2 * x2 * x2) % p256
    print "11", h2

    i2 = (x2 * a256) % p256
    print "12", i2

    i2 = (i2 + b256) % p256
    print "13", i2

    h2 = (h2 + i2) % p256
    print "14", h2

    h3 = (x3 * x3 * x3) % p256
    print "15", h3

    i3 = (x3 * a256) % p256
    print "16", i3

    i3 = (i3 + b256) % p256
    print "17", i3

    h3 = (h3 + i3) % p256
    print "18", h3

    y1 = pow(h2, p4, p256)
    print "19", y1

    y2 = pow(h3, p4, p256)
    print "20", y2

    if pow(y1, 2, p256) == h2:
        return (x2, y1)
    else:
        return (x3, y2)

def test():
    print on_curve(Gx, Gy)
    print (modinv(2) * 2) % p256 == 1

    t = randint(2, p256-2)
    print " t", t
    x, y = map_to_curve_swu(t)
    print " x", x
    print " y", y
    print on_curve(x, y)

test()
-----END h2c.py-----

---

From: Richard Barnes <[email-masked]>
Date: Mon, 23 Jul 2018 14:08:11 -0400

On Mon, Jul 23, 2018 at 1:52 PM Jason Resch <[email-masked]> wrote:

> Hi Richard,
>
> Thank you for the code below.  If it helps establish confidence, I wanted
> to report that in my tests your implementation yielded the same points as
> my own independent implementation did.  That is, for a given "t" as input
> to "map_to_curve_swu", my implementation returned the same points.
>

Signs of interop are always good to hear :)

>
> I would like to add that as far as standardizing on a method that takes
> arbitrary octet strings as inputs and maps them to "t" values, that such a
> function should support arbitrarily large output sizes.  This is because to
> support curves like NIST P-521, that function must output at least 521 bits
> (but there are no well supported hash functions with outputs this large).
> I think HKDF (https://tools.ietf.org/html/rfc5869) is a reasonable
> candidate for this purpose, as it supports outputs up to 256*MAC_Length
> bytes in size.
>
> The standard would need to specify whether to to use the left-most or
> right-most bits of HKDF, and what to do if those bits happen to be larger
> than the prime modulus of the field (i.e., should one try again to
> eliminate bias and hash again with a different input, or take the modulo
> and keep the bias, or generate a number much longer than p (say 80-bits
> longer) and take the modulo to ensure that bias, while always present is
> minimized). HKDF permits a rather straight-forward  way of generating other
> candidate t values which are hopefully less than p, and this approach would
> be be completely free of bias.
>
> The idea is, the HKDF method takes an arbitrary "info" in addition to a
> key length.  By treating the "info" as a counter, we can iterate to
> generate other candidate t values in the event that (t >= p).
>

I agree that certain cases will require longer ouptut lengths, but I'm not
sure this doc needs to wire to specific functions.  Rather, it seems to me
that the HashToCurve() function as having two parameters in addition to the
input octet string, namely (1) a PRF and (2) a curve.  ISTM the only real
requirement this document has is that the output length of the PRF is at
least as big as the bit-length of the characteristic of the field over
which the curve is defined.

You could obviously use HKDF in many cases, but it seems like overkill for
cases like P-256 or Curve25519 (where SHA256 works fine), P-384 (SHA384),
or Curve448 (SHA512).  It's really only P-521 where there's a problem.
Even if you wanted to use a common construction for all sizes (and even
then you'd probably still want to vary the hash), it would still be good to
keep the agility to swap in, say, SHAKE for HKDF.

--Richard

>
> Jason
>
>
> ----- Original message -----
> From: Richard Barnes <[email-masked]>
> Sent by: "Cfrg" <[email-masked]>
> To: CFRG <[email-masked]>
> Cc:
> Subject: [Cfrg] Some comments on draft-irtf-cfrg-hash-to-curve-01
> Date: Sat, Jul 21, 2018 12:01 PM
>
> Hey all,
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>
>
>

---

From: "Jason Resch" <[email-masked]>
Date: Mon, 23 Jul 2018 17:52:09 +0000

Hi Richard,

Thank you for the code below.  If it helps establish confidence, I wanted to report that in my tests your implementation yielded the same points as my own independent implementation did.  That is, for a given "t" as input to "map_to_curve_swu", my implementation returned the same points.

I would like to add that as far as standardizing on a method that takes arbitrary octet strings as inputs and maps them to "t" values, that such a function should support arbitrarily large output sizes.  This is because to support curves like NIST P-521, that function must output at least 521 bits (but there are no well supported hash functions with outputs this large).  I think HKDF (https://tools.ietf.org/html/rfc5869) is a reasonable candidate for this purpose, as it supports outputs up to 256*MAC_Length bytes in size.

The standard would need to specify whether to to use the left-most or right-most bits of HKDF, and what to do if those bits happen to be larger than the prime modulus of the field (i.e., should one try again to eliminate bias and hash again with a different input, or take the modulo and keep the bias, or generate a number much longer than p (say 80-bits longer) and take the modulo to ensure that bias, while always present is minimized). HKDF permits a rather straight-forward  way of generating other candidate t values which are hopefully less than p, and this approach would be be completely free of bias.

The idea is, the HKDF method takes an arbitrary "info" in addition to a key length.  By treating the "info" as a counter, we can iterate to generate other candidate t values in the event that (t >= p).

Jason

----- Original message -----
From: Richard Barnes <[email-masked]>
Sent by: "Cfrg" <[email-masked]>
To: CFRG <[email-masked]>
Cc:
Subject: [Cfrg] Some comments on draft-irtf-cfrg-hash-to-curve-01
Date: Sat, Jul 21, 2018 12:01 PM

Hey all,

On the plane back from the IETF meeting, I set about implementing draft-irtf-cfrg-hash-to-curve for hashing to P-256 (as a prelude to implementing draft-krawczyk-cfrg-opaque).  A few comments (not a complete review):

* The section describing HashToBase could be more explicit about the how the octet string H(x) is to be interpreted as a field element.  Since we're only talking about prime fields, you might do something like the following:
* Interpret H(x) as a big-endian integer h
* Reduce h mod 2^(log2(p) + 1)
* Reduce h mod p

* The encoding algorithms are obviously the most complicated thing here.  For debugging, it would be helpful to have test vectors that show all of the steps in the encoding algorithms for some curve.  In case it's helpful, I've pasted below a Python implementation of map2curve_simple_swu for P-256, with print statements that produce the required test vectors.

* In the description of the simplified SWU method, the variable name "alpha" is re-used for the input and an internal variable, which is extra confusing because these values have different types (octet string vs. field element).  It would be clearer for the encoding algorithms to take a field element as input, since the only thing they do with their octet string inputs is hash them to a field element.

* In the section describing FFSTV13, it's not clear whether the 0/1 values prepended to alpha are bits or bytes.  If it's all the same cryptographically, it would probably be more implementer-friendly to make them bytes.

Other than that, I found the doc pretty readable, and clear about what algorithms you should be implementing (at least in the use case I'm focused on right now).

--Richard

-----BEGIN h2c.py-----
#!/usr/bin/env python

# https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.186-4.pdf
p256 = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a256 = p256 - 3
b256 = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b

def on_curve(x, y):
lhs = (y * y) % p256

def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)

def modinv(a):
g, x, y = egcd(a, p256)
return x % p256

def map_to_curve_swu(t):
p4 = (p256 + 1) // 4

alpha = (t * t) % p256
print " 2", alpha

alpha = p256 - alpha
print " 3", alpha

right = modinv(right)
print " 5", right

left = p256 - b256
print " 7", left

x3 = (alpha * x2) % p256
print "10", x3

i2 = (x2 * a256) % p256
print "12", i2

i2 = (i2 + b256) % p256
print "13", i2

h2 = (h2 + i2) % p256
print "14", h2

i3 = (x3 * a256) % p256
print "16", i3

i3 = (i3 + b256) % p256
print "17", i3

h3 = (h3 + i3) % p256
print "18", h3

y1 = pow(h2, p4, p256)
print "19", y1

y2 = pow(h3, p4, p256)
print "20", y2

def test():
print on_curve(Gx, Gy)

t = randint(2, p256-2)
print " t", t

test()

---

From: Martin Thomson <[email-masked]>
Date: Tue, 24 Jul 2018 11:42:24 +1000

On Tue, Jul 24, 2018 at 4:08 AM Richard Barnes <[email-masked]> wrote:
> You could obviously use HKDF in many cases, but it seems like overkill for cases like P-256 or Curve25519 (where SHA256 works fine), P-384 (SHA384), or Curve448 (SHA512).  It's really only P-521 where there's a problem.  Even if you wanted to use a common construction for all sizes (and even then you'd probably still want to vary the hash), it would still be good to keep the agility to swap in, say, SHAKE for HKDF.

This sounds great in theory, but I'd like to continue to encourage
this group to produce primitives that have fewer tuning knobs.  In
this case, each curve could be paired with precisely one KDF.  That
is, rather than write code that accepts two arguments, the function
accepts one, then consults a lookup table for the other.

That means picking, and picking is hard, but it's better that way.

---

From: Richard Barnes <[email-masked]>
Date: Mon, 23 Jul 2018 21:52:38 -0400

On Mon, Jul 23, 2018, 21:42 Martin Thomson <[email-masked]> wrote:

> > You could obviously use HKDF in many cases, but it seems like overkill
> for cases like P-256 or Curve25519 (where SHA256 works fine), P-384
> (SHA384), or Curve448 (SHA512).  It's really only P-521 where there's a
> problem.  Even if you wanted to use a common construction for all sizes
> (and even then you'd probably still want to vary the hash), it would still
> be good to keep the agility to swap in, say, SHAKE for HKDF.
>

I don't think these positions are inconsistent.   Let's described the thing
with the joints in the natural places, even if we nail the joints in place
for now.

--RLB

---

From: Christopher Wood <[email-masked]>
Date: Tue, 24 Jul 2018 20:19:27 -0700

Hi Richard,

Thanks for the feedback. Please see inline below.

>   * Reduce h mod 2^(log2(p) + 1)

Your proposal is effectively what we implement (not in the doc, as
that's currently omitted, but elsewhere). I filed the following issue
to address this:

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

> * The encoding algorithms are obviously the most complicated thing here.  For debugging, it would be helpful to have test vectors that show all of the steps in the encoding algorithms for some curv…

Yes, we are planning on adding test vectors soon. Thanks for providing
the implementation. I will use it to check with our implementation.

> * In the description of the simplified SWU method, the variable name "alpha" is re-used for the input and an internal variable, which is extra confusing because these values have different types (o…

Indeed, someone pointed that out after the meeting. I'll fix it:

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

> * In the section describing FFSTV13, it's not clear whether the 0/1 values prepended to alpha are bits or bytes.  If it's all the same cryptographically, it would probably be more implementer-frien…

It is all the same cryptographically, so I'll make it clear that it's a byte:

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

> Other than that, I found the doc pretty readable, and clear about what algorithms you should be implementing (at least in the use case I'm focused on right now).

Great to hear!

Best,
Chris

---

From: Christopher Wood <[email-masked]>
Date: Tue, 24 Jul 2018 20:22:11 -0700

On Mon, Jul 23, 2018 at 6:53 PM Richard Barnes <[email-masked]> wrote:
> I don't think these positions are inconsistent.   Let's described the thing with the joints in the natural places, even if we nail the joints in place for now.

For what it's worth, I think this is the right approach.

Best,
Chris