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

[Rene Struik <[e-mail]>]

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:
> 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.
>
>
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]