Dmitry Eremin-Solenikov dbaryshkov@gmail.com writes:
Is it the condition b < B^size / p that is not valid for the GOST curves? What are the problematic values of b and p?
I did not try debugging maths part of this issue. Basically you can apply first two patches and then observe asserts failing when running ecc-benchmark example. Problematic module looks like 80000.......something. Bmodp then looks like 7fffffff.....something.
Any help at this point is appreciated.
If p is close to B^size / 2, then I think a reduction like
r <-- r - 2 * hi * p
will get you close. I.e.,
hi -= mpn_submul_1(..., 2*hi)
should almost cancel the most significant limb. After this, the common case is hi == 0, with possible error case being hi == -1 if p starts with 8000..., or hi == +1 if p starts with 7ffff...
It might be useful to precompute |2p - B^size|.
For the larger reductions, does p have form suitable for redc, ending with ...00001 of ...fffff? Current non-redc reduction code probably won't support p close to B^size / 2.
To keep the ecc code side-channel silent, there must be no conditional jumps depending on hi (except for asserts, since they always branch the same way in a non-crashing program). The adjustmenst can only do unconditional calls to functions like mpn_add_mul_1 and cnd_add_1.
Yes, thus I've tried adding a loop which should nearly always terminate with just single compare after cnd_add_1.
Unfortunately, "nearly always" isn't enough; it means that some inputs will result in a value of hi making the code branch differently, and that information then leaks through cache and/or timing. If it's likely to be exploitable, I can't say, but current ecc code is written to avoid that risk.
Regards, /Niels