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

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

Hi,


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

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.


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

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.


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

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.