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

["Riad S. Wahby" <[e-mail]>]

Hello Filippo,

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

Filippo Valsorda <[e-mail]> 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