Dmitry Eremin-Solenikov <[email protected]> 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 -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ nettle-bugs mailing list [email protected] http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
