Subject: [CFRG] hash_to_field requires implementing a new 25519 field op

From: "Filippo Valsorda" <[email-masked]>
Date: Wed, 21 Jul 2021 19:09:22 +0200

Yawning Angel noticed that the current hash-to-curve draft requires implementing a new 25519 base field operation: wide reduction from 384-bit (or larger) inputs for hash_to_field. https://github.com/FiloSottile/edwards25519/issues/17

This is unfortunate, because most Curve25519 implementations probably don't already provide it, since simply reducing 255 random bits will have a chance of bias of less than 2⁻²⁵⁰, well within the security bounds of the curve.

There are two ways this can go: Curve25519 implementations will all have to implement and expose a new field operation (like https://git.io/JlU6L) which will be only used for h2c, meaning it will not be well tested or maintained, or h2c implementations will have to roll their own, probably in variable time.

Why is a 384-bit integer reduced in hash_to_field for Curve25519 instead of the regular 255 bits?

---

From: "Riad S. Wahby" <[email-masked]>
Date: Wed, 21 Jul 2021 15:11:23 -0400

Hello Filippo,

Thanks for your thoughts on this! Answers and comments below.

Filippo Valsorda <[email-masked]> wrote:
> simply reducing 255 random bits will have a chance of bias of less
> than 2⁻²⁵⁰, well within the security bounds of the curve.

As you say, for the case of p = 2^255-19 one gets a nearly unbiased
result when reducing a 256-bit integer mod p. So you're right: it's
safe in this specific case to use 256 (or even 255) bits.

But (as you know) in general it is not safe to reduce ceil(log2(p))
bits mod p, since this can give significant bias for general p. The
goal in the draft is to specify a hash-to-field method that is safe
for any p without requiring any parameter except the security level
in bits, k, and which gives bias roughly 2^-k. Adding parameters is
dangerous in the sense that incorrectly choosing parameters gives a
hash-to-field function that looks OK but is subtly broken.

So there's a tension here. On the one hand, we might say that it is
not good to require a wide modular reduction; on the other hand, we
might say that it is not good to open the door to subtle brokenness
in the suite specs (especially when there is a strong temptation to
introduce that brokenness for the sake of performance!).

In my mind the second is the much more convincing argument, because
every EC-relevant field library that I'm aware of implements a wide
reduction already, inside the multiplication routine (which gives a
p^2-size intermediate result).

So this

> Curve25519 implementations will all have to implement and expose
> a new field operation (like https://git.io/JlU6L) which will be only
> used for h2c, meaning it will not be well tested or maintained,
> or h2c implementations will have to roll their own, probably
> in variable time.

isn't really true. If one exposes the ceil(log2(p^2)) bit reduction
that's already implemented for multiplication, then there's no need
for extra code, and maybe even no need for extra tests.

I know this isn't a perfect answer, and I'm sure that some folks do
not agree that it's better than the alternative (namely, adding the
extra parameter to hash-to-field and asking folks to figure out for
themselves the "safe" number of bits). But I would rather bet on J.
Arthur Random Programmer to de-dup their code than to grok a subtle
specification issue that could have potentially disastrous security
consequences.

Would it partially allay your concerns if the hash-to-field section
explicitly pointed out that it's possible to use the multiplication
routine (or, well, half of it) for the wide modular reduction?

Thanks as always for your thoughts! and best regards,

-=rsw

---

From: "Filippo Valsorda" <[email-masked]>
Date: Wed, 21 Jul 2021 23:17:32 +0200

> Thanks for your thoughts on this! Answers and comments below.

Hi Riad! Replies inline.

> introduce that brokenness for the sake of performance!).

Agreed there's a general tension here.

I think it helps to think in terms of abstractions. Is the h2c spec supposed to expose a safe, universal hash_to_field function, or is it just a component of higher-level functions? Are developers expected to swap in arbitrary curves into the spec, or are they supposed to use specific instantiations? Is an h2c library expected to work with all possible curves, or is h2c one of the features of a curve-specific library?

If the former, then maybe your hands are tied, but I also question whether this is trying to be too general. If the latter I feel like you could outright special-case p = 2^255-19 and I don't see how that could lead to mistakes.

Myself, I believe elliptic curves are not a safe abstraction (as opposed to prime order groups, as you might have expected ;-), which I believe should include a fixed-length-string-to-element map as part of the abstraction, solving the issue) so I wouldn't try to write something that generalizes over arbitrary elliptic curves, and instead would take advantage of the ability to target specific curves individually to lead to better tailored algorithms.

> for extra code, and maybe even no need for extra tests.

That's not true for unsaturated limbs like the popular 51-bit limb schedule used by most 64-bit implementations of Curve25519. Reduction in multiplication is carried out simultaneously with multiplication, and it yields double-wide _limbs_, which are carried very differently from a wide reduction. https://git.io/JlTG0

Both libsodium and filippo.io/edwards25519 have ex-novo code for this draft specifically.

---

From: Loup Vaillant-David <[email-masked]>
Date: Wed, 21 Jul 2021 23:42:49 +0200

Hi,

> hash-to-field function that looks OK but is subtly broken.

The three primes I know of are pretty clear cut. Two are clearly safe,
the other clearly is not.

1. 2^255 - 2^4 - 2^1 - 1               (Curve25519)
2. 2^448 - 2^224 - 1                   (Curve448)
3. 2^256 - 2^224 + 2^96 + 2^192 - 1    (P-256)

The first  has a bias of about 2^-(255-4)   == 2^-252. => Safe
The second has a bias of about 2^-(448-224) == 2^-224. => Safe
The third  has a bias of about 2^-(256-224) == 2^-32.  => Unsafe

So, Curve25519 and Curve448 have biases well below 2^-128, and as such
are virtually undetectable (you need about 2^128 samples, which you are
not going to get). P-256's bias however can be detected with as little
as a few billion samples, and as such is easily detected in realistic
settings.

Yes, having yet another parameter is a bummer, but as long as we don't
use primes with a bias close to 2^-128, choosing an acceptable
threshold (like 2^-128) should not be too much of a problem.

> for extra code, and maybe even no need for extra tests.

Wait a minute, that reduction is not *nearly* as large as you make it
out to be.  Let's take a look at Curve25519's ref10 implementation on
SUPERCOP. You would think that because the result of the multiplication
(before carry propagation) is stored in 10 64-bit signed integers, the
number they represent easily exceeds 2^512, or even approaches 2^640.

Nope.

In fact, that number those wide limbs represent does not even exceed
2^293. That's because the limbs overlap: even though they're 63-bit
wide, they're only 25 or 26 bits apart.

How then can we compute the multiplication *at all*, would you say?
I've explained it on https://loup-vaillant.fr/tutorials/poly1305-design
Search for "Cheating at modular arithmetic".

The trick is to perform part of the modular reduction by taking
advantage of the fact that you're dealing with a pseudo Mersene prime.
See, when you work modulo 2^255-19, multiplying 2^255 is the same as
multiplying by 19. So you can just shift numbers to the right 255 bits,
and multiply by 19 to compensate. That's why field multiplication has
those *19 all over the place: instead of representing the number over
twenty limbs, we just shift directly to one of the ten least
significant limbs, and multiply by 19 to compensate.

Long story short, your trick won't work. We will need to implement a
separate reduction routine.

---

And before someone is tempted to point out that EdDSA involves the
reduction of a 512-bit modulo the prime order of the curve that we
could reuse, hold your horses: while TweetNaCl and Monocypher uses a
fairly generic algorithm that can easily be adapted by changing a
single constant, I've seen ref10 use a highly optimised reduction where
the value of the order of the curve is deeply embedded in the
algorithm. I personally could not even make sense of it, so I don't
think it can be adapted.

Moreover, keep in mind that 2^255-19 is a pseudo Mersene prime, and as
such can use a much faster reduction algorithm: just shift the most
significant bits to the right, multiply by 19, and add it to the least
significant bits. You'll get a full reduction in a couple iterations
(less if you're clever). Still, implementing this is not for Arthur
Random Programmer. I personally would test it quite extensively, and
write a proof of correctness on top.

> routine (or, well, half of it) for the wide modular reduction?

Since to my knowledge it is *not* possible, it would actually make me
very worried: either I missed something big (and I want to know), or
the RFC writers did (and it needs to be pointed out).

Loup.

---

From: Rene Struik <[email-masked]>
Date: Wed, 21 Jul 2021 18:22:31 -0400

Hi Loup, Filippo:

I do not see the modular reduction implementation issue:

if x=x0+x1*2^m and N=2^m-alpha, x (mod N) = (x0 +alpha*x1) (mod N) = 
ZNadd(x0,ZNmul(alpha,x1)), where ZNadd and ZNmul are operators on the 
set ZN=[0..N-1). This may not be the most efficient, but using two 
invocations of a binary operator to implement a single modular reduction 
should work for "Arthur Random Programmer" (whoever that new [to me] 
creature is). For p=2^255-19, one could take m=255 and and alpha=19 
(i.e., N=p) or m=256 and alpha=38 (i.e., N=2*p), depending on libary 
details. The above also works for NIST prime curves, Brainpool curves, 
Gost curves, secp256k1 (all with negligible relative incremental cost).

I do not think a specification needs to spell out all implementation 
details, as long as it is plausible that effective implementations are 
possible.

This all being said, the suitability of curve maps (including detailed 
steps) depends on the application(s) one wishes to cater to. {I do not 
recall having seen such discussion, e.g., related to password schemes 
and pairing-based applications.}

Rene

On 2021-07-21 5:42 p.m., Loup Vaillant-David wrote:
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867

---

From: "Riad S. Wahby" <[email-masked]>
Date: Wed, 21 Jul 2021 18:30:12 -0400

Hey again Filippo,

Filippo Valsorda <[email-masked]> wrote:
> Is the h2c spec supposed to expose a safe, universal hash_to_field
> function, or is it just a component of higher-level functions? Are
> developers expected to swap in arbitrary curves into the spec,
> or are they supposed to use specific instantiations? Is an h2c
> library expected to work with all possible curves, or is h2c one
> of the features of a curve-specific library?

These are great questions. I don't have any particular opinion on the
third one, but with respect to the first two my opinion is that there
are really two separate roles here. One is a developer who implements
an existing suite. The other is an application designer, who needs to
hash to some curve in their application that we (the h2c authors) did
not anticipate. For the second role it should be easy to start with a
curve spec and end up with a secure hash-to-curve suite.

> Myself, I believe elliptic curves are not a safe abstraction (as
> opposed to prime order groups, as you might have expected ;-),
> which I believe should include a fixed-length-string-to-element
> map as part of the abstraction, solving the issue) so I wouldn't
> try to write something that generalizes over arbitrary elliptic curves

Totally agreed that elliptic curves have plenty of sharp edges! But I
am not convinced that hash-to-curve is the culprit here---mostly it's
protocols that are designed assuming "elliptic curve" == "prime-order
group," whereas h2c explicitly deals with composite order. And in any
case, I cannot stop anyone from using a composite-order group, but at
least h2c can help them get one tricky part right!

(Moreover, one of h2c's main users is pairing-friendly curves. Do any
nice composite-order abstractions exist for these? I do not know any.
But they *do* seem to be a moving target! which suggests that we have
to assume the suites in h2c won't suffice forever...)

> That's not true for unsaturated limbs like the popular 51-bit limb
> schedule used by most 64-bit implementations of Curve25519. Reduction
> in multiplication is carried out simultaneously with multiplication,
> and it yields double-wide _limbs_, which are carried very differently
> from a wide reduction. https://git.io/JlTG0

Surely there is nothing magic about unsaturated limbs! It's true that
the code you linked would need an "adapter" morally equivalent to the
code on lines 79--117; but after writing that adapter, lines 146--162
could be shared with the wide reduction routine.

So it is not true that we could get away without new tests, contra my
prior email's claim---mea culpa!---but certainly the adapter would be 
much simpler than either lines 79--117 or lines 146--162: split a 384
bit number into 8 * 51 bits with some shifts and masks; call addMul64
three times; continue at line 146. Is that 10 lines of code? 20?

I freely admit that this is just one point of view and that there are
good arguments in the other direction. And talk is cheap for me since
I don't have to maintain those 20 lines of code! :) But I don't think
those lines suffice to justify dramatically increasing the likelihood
that an application designer gets confused and specifies a broken h2c
suite for next year's shiny new elliptic curve...

Best regards,

-=rsw

---

From: "Riad S. Wahby" <[email-masked]>
Date: Wed, 21 Jul 2021 18:41:13 -0400

Hello Loup,

> number they represent easily exceeds 2^512, or even approaches 2^640.

Our messages crossed, but in general the product of two residues mod p
will be as large as p^2 - 2p + 1, which is roughly log2(p^2) bits as I
claimed. The code you link does some of that reduction implicitly, but
the same trick can be used on a 384-bit number. See my message from ~5
minutes ago to Filippo.

Or, as Rene points out in parallel, if we do not demand absolutely the
fastest reduction we can implement it using field operations directly,
which is what I did in the pairing-plus crate, for example:
    https://github.com/algorand/pairing-plus/blob/master/src/bls12_381/fq.rs#L471

Cheers,

-=rsw

---

From: "Riad S. Wahby" <[email-masked]>
Date: Wed, 21 Jul 2021 18:45:36 -0400

Ugh, self-replying because me dumb:

"Riad S. Wahby" <[email-masked]> wrote:
> claimed.

"The product of two integers less than p," obviously. Apologies.

-=rsw

---

From: Loup Vaillant-David <[email-masked]>
Date: Thu, 22 Jul 2021 01:10:39 +0200

Hi Rene,

Something similar could indeed work (untested code below):

    void reduce(uint8_t r[32], uint8_t w[64])
    {
        fe low, high;
        fe_frombytes(low , w);
        fe_frombytes(high, w + 32);
        fe_mul_small(high, high, 19);
        fe_add      (low , low, high);
        fe_tobytes(r, low);
        // maybe wipe low and high
    }

There's a little problem though: this reduction ignores *two* bits from
the input, one of which is right in the middle. As much as I love how
it makes the implementation easy, you might hate how it makes the
specification weird.

Or I could use the same trick to read the two missing bits, and have a
full, clean, wide reduction. Let's see (untested code):

    void reduce(uint8_t r[32], uint8_t w[64])
    {
        fe low, high;
        fe_frombytes(low , w);
        fe_frombytes(high, w + 32);
        fe_mul_small(high, high, 38);
        fe_add      (low , low, high);
        low[0] += (w[31] >> 7) * 19;
        low[0] += (w[63] >> 7) * 19
* 38; // may be omited
        fe_tobytes(r, low);
        // maybe wipe low and high
    }

What do you know, that's much less ugly than I anticipated. Nice.
Slower than a dedicated reduction, but if I'm being honest the
performance difference probably never matters.

Thanks for the tip,
Loup.

On Wed, 2021-07-21 at 18:22 -0400, Rene Struik wrote:
> > I've explained it on 
> > https://loup-vaillant.fr/tutorials/poly1305-design