[Cfrg] [CFRG] [hash2curve-05] Suggestions regarding modifications of the "external API"

[Björn Haase <[e-mail]>]

Hello hash2curve team,

I am currently reviewing the current draft-irtf-cfrg-hash-to-curve-05 in
the context of a "user" of the operations that you specify. After trying
to re-use the definitions as-is for the CPace and AuCPace RFC that I am
currently writing, I would like to come up with two suggestions.

As a first general remark, I would like to give the feedback that it is
written very clearly (IMO). Also I am now convinced that the patent
pitfalls are avoided also for SSWU!

Suggestions:

1.) Don't make the co-factor clearing mandatory for encode_to_curve

I noticed some diffculty coming with the currently specified API for
non-prime-order curves such as Curve25519 or Ed448.

Currently, two different "public APIs" are suggested, one for returing a
point in the (secure) cryptographic subgroup of the curve
(encode_to_curve) and one for true hashing onto the curve involving one
additional point additions (hash2curve). As a final step both currently
mandatorily involve co-factor clearing.

While I agree that co-factor-clearing is mandatory in most applications,
specifying this as mandatory on the encode_to_curve level makes problems
for me. Note that protocols designed for non-prime-order curves, such as
X25519 already include co-factor clearing themselves by the "scalar
clamping" operation that precedes any scalar multiplication.

The problem with co-factor clearing is that unlike for Elligator 2 the
co-factor clearing algorithm returns the result in projective coordinates.

Consider the case of a point generated by encode_to_point as a secret
generator used in CPace for Diffie-Hellman using X25519 on Curve25519.
One of the most efficient X25519 Diffie-Hellman implementations that use
a x-coordinate-only Montgomery ladder requires an *affine* base-point as
input. The alternative addition formulas that take a projective point as
an input require ~256 additional field multiplications in comparison
with an algorithm taking an *affine* base point input. Using a
projective input point is, thus, more costly than using an inversion
(~256 field squarings) and an affine base point.

In order to input the output of encode_to_curve() for CPace as it is
defined currently, you need a superflous field inversion to be run on
the output of the co-factor-clearing algorithm, accounting for an
computational overhead of roughly 20%.

Elligator2 -> Result in affine coordinates
Co-Factor-CLearing -> Result in projective coordinates
Inversion -> Conversion to affine coordinates
X25519-> Scalarmultiplication which itself clears the co-factor a second
time

In order to circumvent this problem for the CPace definition, I will not refer to encode_to_curve but only use the
hash_to_base and map_to_curve definitions.

I would like to suggest to remove the clear_cofactor step from encode to
point.

encode_to_curve(alpha)

    Input: alpha, an arbitrary-length bit string.
    Output: P, a point in G.

    Steps:
    1. u = hash_to_base(alpha, 2)
    2. Q = map_to_curve(u)
    // remove 3. P = clear_cofactor(Q)
    // remove 4. return P
    3. return Q


This also would simplify the hash_to_curve definition by refering to encode_to_curve.

hash_to_curve(alpha)

    Input: alpha, an arbitrary-length bit string.
    Output: P, a point in G.

    Steps:
    1. Q0 = encode_to_curve(alpha, 0)
    2. Q1 = encode_to_curve(alpha, 1)
    3. R = Q0 + Q1 // Point addition
    4. P = clear_cofactor(R)
    5. return P


2.) Use SHA512 as "natural" choice for the hash function for Curve25519

Usually, a hash function and elliptic curve are used in conjunction with
the same "security bit level". E.g. for P-256 one would usually use
SHA-256 and for Brainpool-512, SHA-512. Both, signature algorithm and
Diffie-Hellman operations will likely use the "128-bit security" hash.

However, in the case of Curve25519, in my opinion the "natural" choice
would be SHA-512, because the default signature algorithm Ed25519, will
not use SHA-256 but rather SHA-512. Note that SHA-512 is not
significantly more expensive than SHA-256 on constrained small targets
according to my implementation study on an ARM Cortex M0. Assume a
constrained device that uses Ed25519 as efficient algorithm for
verifying firmware signatures and another protocol that uses mappings.
In this case, the designer would rather like to use SHA-512.

I would therefore like to suggest to add a cipher suite for
encode_to_point for Curve25519 based on SHA-512.

This will also allow for a more efficient version of hash_to_base for
the case of Curve25519, since we dont mandatorily need the
"HKDF-extract"/"HKDF-expand" sequence. Here one could just use the
sufficiently long result of a single SHA-512 (H) invokation, interpret
the 512 bit result as un-reduced fe25519 field element and reduce the
output to 255 bits in order to remove any statistical bias.

Thus, my suggestion for map_to_base would be to use
HDKF-extract/HKDF-expand only when the hash output is not sufficiently
long for the required output of the current HKDF-expand operation. In
case that the base-line hash function H output is already sufficiently
long, I'd recommend to use it's hash output as-is.

(Note that, while typically using HKDF should not be considered of
negligible cost in comparison to a single hash function invokation,
there might be applications where this is not the case. E.g. for the
mapping used in CPace I have suggested in the submitted documents to
CFRG for PAKE to use a masked side-channel-protected implementation
based on SHA-3 if SPA/Faults become relevant. When considering masking
for DPA protection, the hash operation could rapidly turn out to be a
*very* complex part, specifically, when considering ARX-constructions
such as SHA-256. Such masking operation might actually be particularly
important on smallest/constrained devices that are often more exposed to
invasive side-channel attacks than typical desktops/laptops.)

Yours,

Björn.