Re: [CFRG] thoughts on clearing the cofactor in hash to curve

[Loup Vaillant-David <[e-mail]>]

On Mon, 2021-04-12 at 15:50 -0700, Armando Faz wrote:
> > "Hao, Feng" <[e-mail]>
> > I asked for clarification on whether the small subgroup points can
> > be removed from map-to-curve by design. The replies from the hash-
> > to-curve authors indicated no: because 1) too much hassle; 2) not
> > worth it for the negligible probability. I think the rationale is
> > clear.
> 
> There were several comments about why clear-cofactor helps to map
> low-order points to the identity, and why this might or might not be
> an issue in higher protocols.
> However, few comments addressed the problem of devising a map-to-
> curve algorithm that always returns points of a given order. I
> consider this is still an open problem in general, (which is another
> reason why the draft takes a simpler  approach, namely clear-
> cofactor).
> Also note that a similar function will be useful for CSIDH, which
> needs to sample points in a desired torsion group. If I am not wrong,
> CSIDH also uses the clear-cofactor technique to achieve this task.
> Happy to hear more comments about this specific problem, (which is a
> different  discussion from the implications of not having such a
> map).

Hi,

If we separate the map/hash to curve step from the higher-level
protocol that uses it, it is generally simpler to clear the cofactor
before the high-level protocol sees anything. (This ease of use is why
I wouldn't dare object to clearing the cofactor in the context of the
hash-to-curve RFC.)

On the other hand, there might be a small performance benefits in *not*
clearing the cofactor. Curve25519's cofactor for instance is 8 (2^3),
and requires 3 point doublings to clear. Depending on the context, this
could be considered a significant overhead, or a negligible one:

- Elligator2 based Map to Curve requires a single exponentiation.
  Adding 3 point doubling on top of that will likely add about 10%
  of overhead.
- If we're performing a scalar multiplication after clearing the
  cofactor (OPRF does), then the overhead drops down to 1% or so.

(The overhead for Curve448 are even lower: the curve is bigger, and
 requires only 2 points doubling to clear the cofactor.)

Negligible or no, the overhead is measurable, so there's the temptation
to skip it. And in many cases, we can: it turns out that regular X25519
(and X448) scalar multiplications ignore the cofactor to begin with.
They do this by clearing the 3 (or 2) least significant bit of the
scalar, thus making sure that the scalar is a multiple of the cofactor.

To sum it up, if cofactor clearing happens as a natural side effect of
the higher level protocol (such as scalar multiplication, where the
scalar is tweaked to clear the cofactor), then we can save a few cycles
and omit it. On the other hand, you really have to know what you're
doing.

---

Another reason not to clear the cofactor is when you also want to
provide the reverse map. Reverse map facilitate steganography and other
forms of meta-data hiding: if you map a random point on the curve, the
representative is indistinguishable from random. So when you send it
over the network, it looks random, without the statistical biases
associated with raw public keys.

The problem with the reverse mapping is that we need to pick a random
point over the *whole* curve, not just the prime order group (let's
ignore the fact that half of the points do not map at all). If we
restricted ourselves to the prime order group, the attacker could just
map it back and notice that by some amazing "coincidence", they always
get a point on the prime order group.

So the representative we send over the network for attackers to
eavesdrop must map to a point whose cofactor is *not* cleared. To do
that, it makes sense for a low-level cryptographic library to expose an
interface that does not clear the cofactors. One can then implement
Hash-To-Curve (which does clear the cofactor) on top of it.

---

Speaking of which, I found rather unfortunate incompatibilities between
the RFC's map-to-point step, and existing Elligator2 implementations
over Curve25519 I was referring to when I added Elligator2 to
Monocypher last year. I believe Mike Hamburg asked about them then.

As one can guess, I'm rather found of the reverse map, and what it
enables. In the specific case of Curve25519, mapping a point to a
representative will yield a 255-bit number. Note however that
representatives and their opposite (modulo 2^255-19) map to the same
curve point, so I always chose the positive representative. (The one
between 0 and p-2. I could instead discriminate with parity instead
like Ed25519 does, but the Elligator2 paper suggested otherwise).

The result is a 254-bit number. I can then just pad the two other bits
with random noise, and the decoding step will have to ignore those
bits. If I recall correctly, the Hash-To-Curve RFC however does not
ignore those two bit:

- Bit 256 is used to flip the sign of the mapped curve point, instead
  of just being ignored.
- The representative is encoded in 255 bits instead of 254 bits, which
  are enough for positive representatives.

Both of these incompatibilities are fairly easily worked around: we
don't care about the sign of the point to begin with if its purpose is
to use it in X-only ladders (and in many cases, it is), and
representatives are easily negated if need be. I also understand why
representatives use 255 bits: that's how existing decoding functions
work.

What I don't get is the rationale behind using bit 256 to flip the sign
of the curve point. It doesn't do anything that I can tell: if a point
can be mapped, then so can its opposite, so we won't even cover more
points that way. Unless perhaps as a way of highlighting implementation
errors?

---

Anyway, my thoughts.
Loup.