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

[Filippo Valsorda <[e-mail]>]

2021-07-21 21:11 GMT+02:00 Riad S. Wahby <[e-mail]>:
> Hello Filippo,
> 
> Thanks for your thoughts on this! Answers and comments below.

Hi Riad! Replies inline.

> 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!).

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.

> 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.

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.

> 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
>