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

["Stanislav V. Smyshlyaev" <[e-mail]>]

Dear Thomas,

Thanks a lot for your review!

Kind regards,
Stanislav

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

> 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 <[e-mail]> on behalf of
> "Stanislav V. Smyshlyaev" <[e-mail]>
> Date: Friday, June 5, 2020 at 08:11
> To: Thomas Pornin <thomas.pornin=[e-mail]>
> Cc: "[e-mail]" <[e-mail]>, "
> [e-mail]" <
> [e-mail]>, "[e-mail]" <
> [e-mail]>
> Subject: Re: [Crypto-panel] EXTERNAL: Request for review:
> draft-irtf-cfrg-hash-to-curve-08
>
> Great, many thanks, Thomas!
>
> Stanislav (for Chairs)
>
> On Fri, 5 Jun 2020 at 14:53, Thomas Pornin <thomas.pornin=mailto:
> [e-mail]> wrote:
> I can do that.
>
> Thomas
>
> From: Crypto-panel <mailto:[e-mail]> on behalf of
> "Stanislav V. Smyshlyaev" <mailto:[e-mail]>
> Date: Friday, June 5, 2020 at 00:17
> To: "mailto:[e-mail]" <mailto:[e-mail]>
> Cc: "mailto:[e-mail]" <mailto:
> [e-mail]>, "mailto:
> [e-mail]" <mailto:[e-mail]>
> 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)
> _______________________________________________
> Crypto-panel mailing list
> mailto:[e-mail]
> https://www.irtf.org/mailman/listinfo/crypto-panel
>
>