Subject: [Crypto-panel] Request for review: draft-irtf-cfrg-hash-to-curve-08

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Fri, 5 Jun 2020 07:17:53 +0300

Dear Crypto Panel members,

Alexey, Nick and I would like to ask Crypto Review Panel members about the
review(s) of draft-irtf-cfrg-hash-to-curve-08.

The document specifies a number of algorithms for encoding or hashing an
arbitrary string to a point on an elliptic curve.

Can we have any volunteers, please?

Best regards,
Stanislav (on behalf of chairs)

---

From: Thomas Pornin <[email-masked]>
Date: Fri, 5 Jun 2020 11:53:33 +0000

I can do that.

Thomas

From: Crypto-panel <[email-masked]> on behalf of "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Friday, June 5, 2020 at 00:17
To: "[email-masked]" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: EXTERNAL: [Crypto-panel] Request for review: draft-irtf-cfrg-hash-to-curve-08

Alexey, Nick and I would like to ask Crypto Review Panel members about the review(s) of draft-irtf-cfrg-hash-to-curve-08.

The document specifies a number of algorithms for encoding or hashing an arbitrary string to a point on an elliptic curve.

Best regards,

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Fri, 5 Jun 2020 15:10:41 +0300

Great, many thanks, Thomas!

Stanislav (for Chairs)

On Fri, 5 Jun 2020 at 14:53, Thomas Pornin <thomas.pornin=
[email-masked]> wrote:

> I can do that.
>
>
>
> Thomas
>
>
>
> *From: *Crypto-panel <[email-masked]> on behalf of
> "Stanislav V. Smyshlyaev" <[email-masked]>
> *Date: *Friday, June 5, 2020 at 00:17
> *To: *"[email-masked]" <[email-masked]>
> *Cc: *"[email-masked]" <
> [email-masked]>, "[email-masked]" <
> [email-masked]>
> *Subject: *EXTERNAL: [Crypto-panel] Request for review:
> draft-irtf-cfrg-hash-to-curve-08
>
>
>
> _______________________________________________
> Crypto-panel mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/crypto-panel
>

---

From: "Christopher Wood" <[email-masked]>
Date: Fri, 05 Jun 2020 07:47:48 -0700

> Great, many thanks, Thomas!

+1 :-)

Best,
Chris

> Stanislav (for Chairs)
> 
> On Fri, 5 Jun 2020 at 14:53, Thomas Pornin 
> <thomas.pornin=[email-masked]> wrote:
> > I can do that.____
> 
> > __ __
> 
> > Thomas____
> 
> > __ __
> 
> > *From: *Crypto-panel <[email-masked]> on behalf of "Stanislav V. Smyshlyaev" <[email-masked]>
> > *Cc: *"[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
> > *Subject: *EXTERNAL: [Crypto-panel] Request for review: draft-irtf-cfrg-hash-to-curve-08____
> 
> > __ __
> 
> > Dear Crypto Panel members, ____
> 
> > __ __
> 
> > Alexey, Nick and I would like to ask Crypto Review Panel members about the review(s) of draft-irtf-cfrg-hash-to-curve-08.____
> 
> > __ __
> 
> > The document specifies a number of algorithms for encoding or hashing an arbitrary string to a point on an elliptic curve. ____
> 
> > __ __
> 
> > __ __
> 
> > Can we have any volunteers, please?____
> 
> > __ __
> 
> > __ __
> 
> > Best regards,____
> 
> > Stanislav (on behalf of chairs)____
>

---

From: Thomas Pornin <[email-masked]>
Date: Tue, 9 Jun 2020 22:42:36 +0000

Here is my review.

Hashing to Elliptic Curves
draft-irtf-cfrg-hash-to-curve-08

This draft is well-written. I have not verified that all pseudocode
and all test vectors are correct, but I did not see anything obviously
wrong. All proposed constructions make sense to me, from a cryptographic
point of view.
(I can reimplement stuff in Sage and check the results, but it will take
me more time, and I don't have a lot of it at the moment.)

A generic remark: there is not a word about intellectual property
issues. I understand that this is a contentious issue, and that nobody
wants to assert that any specific method is patent-free. But I would
have expected a disclaimer somewhere. Otherwise, it feels weird that
Icart's map is not used as a possible method, since, when p^m = 2 mod 3,
it should be faster than the simplified SWU (it uses one inversion
and one cube root, no extra is_square() or similar).
(Also, I heard some rumours that simplified SWU is also patented,
albeit with a less proactively enforced patent. The same rumours say
that the original Shallue-van de Woestijne method is patent-free. These
are only rumours.)

Some other remarks, in appearance order:

2.1 (page 6): Maybe note that there are multiple choices for the
representation of GF(p^m) as polynomials: any irreducible modulus M (of
degree m) is fine (all finite fields with the same cardinal are
isomorphic to each other), but no M is more canonical than any other.
Choice of M is often driven by implementation performance (some M lead
to faster code).

2.1 (page 6): "elements are those points with coordinates (x, y)
satisfying the curve equation": some curves (in particular Weierstraß
and Montgomery curves) also include a special point-at-infinity which
does not have coordinates (x, y).

2.2.2 (page 8): "Section 10 discusses further." -> This lacks a
complement. Maybe: "See section 10 for further discussion."?

2.2.5 (page 9): Concatenation can be ambiguous, i.e.
   "RO10" || x == "RO1" || ("0" || x)
The actual usage (in section 5.3) uses explicit length bytes, and
also puts the tag _after_ the message, not before. It might be worth
mentioning here that the "concatenation" operation must be an
injective encoding of the tag and input x, with a forward reference
to section 5.3 for details (especially 5.3.4).

3.1 (page 12): The text fluidly and implicitly equates character strings
and byte strings. Java and C#/.NET developers might take issue with
that. This might be worth an explicit sentence here; otherwise, some
developer somewhere will use UTF-16 (and calling it "Unicode" in pure
Microsoft fashion), others will add a terminating zero, or use
big-endian, or add a BOM, or any combination thereof, and much confusion
and interoperability sorrow will ensue.

4 (page 12): "SHOULD be constant time" -> "SHOULD be constant-time".

Also, the traditional acception of "constant-time" covers more than
independence of the execution time with regard to the input values:

  - It really is independence with regard to all secret values, including
    intermediate values and outputs, not just inputs.

  - Constant-time code should not leave any trace that can be leveraged
    with time-based measurements. For instance, in a flush+reload
    attack, the victim's execution time is independent of the secret
    values; the timing measurement is on a reload operation performed by
    the attacker themselves, _after_ the victim has finished. Code which
    is vulnerable to a flush+reload attack may still be "constant-time"
    in the sense described by section 4, but would not be
    "constant-time" in the usual sense.

I think a more generic definition of "constant-time" is needed here. I
suggest the following: "For security, implementations of these functions
SHOULD be constant-time, i.e. none of the possible timing measurements
that can be effected by an adversary should depend on secret values. In
particular, execution time but also memory access patterns should be
independent of any secret input, output or intermediate value."

4 (page 13): "there exist two roots of x in the field F whenever x is
square." -> except when x = 0. Zero has a unique square root in F.

4 (page 13): "To implement inv0 in constant time, compute inv0(x) :=
x^(q-2)" -> Depending on the field, there may be (much) faster ways, in
particular in field extensions (e.g. in Curve9767, inversion cost is
about 6M, while Fermat's Little Theorem would bring it to about 300M!).
Even in prime fields, a constant-time extended binary GCD will typically
have cost between 40M and 100M for inversion (but some specific care is
required to ensure that inv0(0) = 0). However, it must be said that the
exponentiation is a simple to implement in constant-time if
constant-time multiplication is available (and it should, otherwise the
whole thing is hopeless).

4 (page 13): It may be worth mentioning that I2OSP and OS2IP, as defined
in PKCS#1 (aka RFC 8017), are big-endian. In particular, most of the
curve25519/edwards25519 ecosystem tends to be little-endian, so that's a
plausible source of mistakes.

5 (page 5): The draft uses "SHAKE-128" as the name of SHAKE with a
128-bit output, but the NIST specification (FIPS 202) defines "SHAKE128"
without the dash. This impacts the use of the name in IDs (e.g. in
section 8.10, page 43).

5.2 (page 17): Maybe note somewhere that implementation of "mod p" with
constant-time code is not completely obvious. Using Euclidean division
is not constant-time. Most constant-time implementations use Barrett
reduction, although some use Montgomery instead.

5.2 (page 17): When mapping to a field GF(p^m) with a relatively small p
(e.g. less 32 bits), then the proposed hash_to_field() is rather
wasteful in hash output. For such fields, generating k+log2(p^m) bits
and then repeatedly dividing that big integer by p will be faster,
especially when working on embedded systems. On an ARM Cortex M0+, with
field GF(9767^19), I can get a map_to_field() in about 20000 cycles,
while each invocation of the SHAKE internal function costs 34000 cycles
and the proposed method would require three invocations of that internal
function to get enough bytes.

5.3.1 (page 18): I needed to verify, but "Damgaard" is indeed the
correct ASCII-compatible alternative spelling of "Damgård". Nice job!

5.3.1 (page 19): Definition of b_in_bytes uses ceil(), i.e. accounts for
the possibility that H outputs something else than an integral number
of bytes. But if that is the case, the "uniform_bytes" are not uniform!
It would be better to make it an explicit requirement that the output
length of H, in bits, MUST be a multiple of 8.

5.3.1 (page 19): r_in_bytes is said to be the "block size" of a hash
function, but that notion has not been defined. Generally speaking, some
hash functions do not have a well-defined "block size". You may fall
back here on HMAC, since HMAC also needs a "block size"; for instance,
FIPS 202 defines the block size of SHA3-256 to be 136 bytes.

5.3.4 (page 21): "prepended or appended" -> technically, "prepended" is
an actual English word, but not with that meaning. It means something
like "premeditate". I suggest: "an encoding of DST MUST be added either
as a prefix or suffix to the input to each invocation of H (a suffix is
the RECOMMENDED approach)."

6.6.1 (page 25): It may be worth mentioning that some of the computed
values are actually constants, e.g. tv4 (step 5) or -4*g(Z)/(3*Z^2+4*A)
(used in step 10) (this is applied in appendix D.1). In effect, the
"expensive" operations in this algorithm that cannot be precomputed are
1 inv0(), 2 is_square(), and 1 sqrt(). This makes it apparent that the
speed advantage of the simplified SWU map is that it saves 1 is_square()
call, i.e. about 25% of the overall cost if inv0(), is_square() and
sqrt() are implemented with modular exponentiations.

10 (page 45): for password hashing, discussion points to PBKDF2 and
Scrypt. It might be worth mentioning Argon2, for which there is an
in-progress draft:
   https://datatracker.ietf.org/doc/draft-irtf-cfrg-argon2/

10 (page 45): "the nature of the leakage and the appropriate defense
depends on the application." -> should be "depend" here.

E.1 (page 75): It may be worth mentioning here that the random oracle
mapping requires doing two map_to_curve() and adding the results
together, and this is, in itself, enough to make projective coordinates
useful. In particular, when using a Weierstraß curve, you must take into
account the (remote) possibility that the two points may be the same,
therefore requiring a constant-time generic point addition routine;
there are complete formulas for Weierstraß curves in homogenous
projective coordinates.

G.5 (page 96): "Other optimizations of this type are possible in other
even-order extension fields" -> You can also have similar optimizations
in any extension field. In general, for an odd p and an arbitrary m > 1:

      (p-1)/2 = ((p-1)/2)*(1+p+p^2+...+p^(m-1))

Thus, if we call r = 1+p+p^2+...+p^(m-1), we have:

      x^((p-1)/2) = (x^r)^((p-1)/2)

This can be computed very efficiently because:

  - x^r is an element of GF(p) (indeed, (x^r)^(p-1) = 1 for any x != 0,
    and only elements of GF(p) are roots of the polynomial X^(p-1)-1 in
    GF(p^m)[X]), so the final exponentiation by (p-1)/2 can be done with
    only values in the small field GF(p).

  - x^r can be computed in log(m) multiplications and log(m) applications
    of the Frobenius operator:

      t1 = x * x^p = x^(1+p)
      t2 = t1 * t1^(p^2) = x^(1+p+p^2+p^3)
      t3 = t2 * t2^(p^4) = x^(1+p+p^2+p^3+p^4+p^5+p^6+p^7)
      ...

    The Frobenius operator itself is typically as efficient, or even
    faster, as a multiplication, since it is a linear transform over the
    source polynomial (seen as a vector in a space of dimension m over
    GF(p)). If GF(p^m) was defined modulo M = X^m-c for some constant c,
    then the Frobenius operator is a simple per-coefficient
    multiplication, i.e. a cost close to that of an addition in GF(p^m).

The algorithm in appendix G.5 is a simple sub-case of this, when m = 2.

Thomas

----------------------------------------------------------------------------------------------------
From: Crypto-panel <[email-masked]> on behalf of "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Friday, June 5, 2020 at 08:11
To: Thomas Pornin <thomas.pornin=[email-masked]>
Cc: "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: Re: [Crypto-panel] EXTERNAL: Request for review: draft-irtf-cfrg-hash-to-curve-08

Stanislav (for Chairs)

On Fri, 5 Jun 2020 at 14:53, Thomas Pornin <thomas.pornin=mailto:[email-masked]> wrote:
I can do that.
 
Thomas
 
From: Crypto-panel <mailto:[email-masked]> on behalf of "Stanislav V. Smyshlyaev" <mailto:[email-masked]>
Date: Friday, June 5, 2020 at 00:17
To: "mailto:[email-masked]" <mailto:[email-masked]>
Cc: "mailto:[email-masked]" <mailto:[email-masked]>, "mailto:[email-masked]" <mailto:[email-masked]>
Subject: EXTERNAL: [Crypto-panel] Request for review: draft-irtf-cfrg-hash-to-curve-08

 

Best regards,
mailto:[email-masked]

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 10 Jun 2020 08:26:53 +0300

Dear Thomas,

Thanks a lot for your review!

Kind regards,
Stanislav

ср, 10 июня 2020 г. в 01:42, Thomas Pornin <[email-masked]>:

> From: Crypto-panel <[email-masked]> on behalf of
> Cc: "[email-masked]" <[email-masked]>, "
> [email-masked]" <
> From: Crypto-panel <mailto:[email-masked]> on behalf of
> "Stanislav V. Smyshlyaev" <mailto:[email-masked]>
> Cc: "mailto:[email-masked]" <mailto:
> [email-masked]>, "mailto:
> [email-masked]" <mailto:[email-masked]>