сб, 11 мая 2019 г. в 12:53, Niels Möller <[email protected]>: > > 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
Yes, it is. As an overflow happens in low level code, do you suggest duplicating ecc-dup-jj/ecc-add-jja/ecc-add-jjj for GOST curves? > 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? No, it does not. p is 80.....0c99 for 256-bit curve and 800...06f for 512-bit curve. Another problem might be another 256-bit curve, where p is semi-random (9b9f605f5a858107ab1ec85e6b41c8aacf846e86789051d37998f7b9022d759b). > 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. -- With best wishes Dmitry _______________________________________________ nettle-bugs mailing list [email protected] http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
