From d0933a5e495b74dae8f23ff5dbaed1780ca878e2 Mon Sep 17 00:00:00 2001 From: Loup Vaillant Date: Sat, 4 Aug 2018 15:30:54 +0200 Subject: [PATCH] All field element constants have the proper invariants A number of pre-computed constant didn't follow the ideal invariants set forth by the carry propagation logic. This increased the risk of limb overflow. Now all such constants are generated with fe_frombytes(), which guarantees they can withstand the same number of additions and subtraction before needing carry propagation. This reduces the risks, and simplifies the analysis of code using field arithmetic. --- src/monocypher.c | 160 +++++++++++++++++++++++------------------------ 1 file changed, 79 insertions(+), 81 deletions(-) diff --git a/src/monocypher.c b/src/monocypher.c index 142d645..a8934e6 100644 --- a/src/monocypher.c +++ b/src/monocypher.c @@ -1440,8 +1440,8 @@ static int ge_frombytes_neg_vartime(ge *h, const u8 s[32]) static void ge_cache(ge_cached *c, const ge *p) { static const fe D2 = { // - 2 * 121665 / 121666 - 0x2b2f159, 0x1a6e509, 0x22add7a, 0x0d4141d, 0x0038052, - 0x0f3d130, 0x3407977, 0x19ce331, 0x1c56dff, 0x0901b67 + -21827239, -5839606, -30745221, 13898782, 229458, + 15978800, -12551817, -6495438, 29715968, 9444199 }; fe_add (c->Yp, p->Y, p->X); fe_sub (c->Ym, p->Y, p->X); @@ -1548,85 +1548,83 @@ static void ge_precompute(ge_cached lut[8], const ge *P1) } static const fe base_comb [32] = { - {0x0000000, 0x0000000, 0x0000000, 0x0000000, 0x0000000, - 0x0000000, 0x0000000, 0x0000000, 0x0000000, 0x0000000}, - {0x0000001, 0x0000000, 0x0000000, 0x0000000, 0x0000000, - 0x0000000, 0x0000000, 0x0000000, 0x0000000, 0x0000000}, - - {0x325d51a, 0x18b5823, 0x0f6592a, 0x104a92d, 0x1a4b31d, - 0x1d6dc5c, 0x27118fe, 0x07fd814, 0x13cd6e5, 0x085a4db}, - {0x2666658, 0x1999999, 0x0cccccc, 0x1333333, 0x1999999, - 0x0666666, 0x3333333, 0x0cccccc, 0x2666666, 0x1999999}, - - {0x0eda202, 0x0dae3fd, 0x2bd67c1, 0x1f6a8d1, 0x001e36d, - 0x0a08a96, 0x1b067da, 0x13aba89, 0x08bf2df, 0x1888af6}, - {0x2e45313, 0x1be95e0, 0x160d1e3, 0x045d481, 0x15042d8, - 0x01b7c4f, 0x1ed7693, 0x004bbad, 0x02ea4ed, 0x00c96ed}, - - {0x1ccfba2, 0x00199d8, 0x318834e, 0x197f9d3, 0x0b37588, - 0x11950ab, 0x2cdf91d, 0x1ffb70f, 0x279c294, 0x03aea46}, - {0x2515e46, 0x16fc77f, 0x2b37cbc, 0x1c3386c, 0x16ad747, - 0x12c93a1, 0x3876f61, 0x1e5b0b2, 0x3eabea7, 0x060c11c}, - - {0x0b7e824, 0x011eb98, 0x07cbf90, 0x04e1739, 0x2639a17, - 0x14e29a0, 0x29cc270, 0x06592a5, 0x3f3c45f, 0x1309ebf}, - {0x3f5a66b, 0x0af4452, 0x093cb77, 0x0f28d26, 0x24342f8, - 0x0c29c3a, 0x08f5b13, 0x10fb2be, 0x26526dc, 0x17cb267}, - - {0x00c969a, 0x0bf4a5a, 0x39cdf7c, 0x0418f65, 0x2c39bb0, - 0x0c36053, 0x1e0df46, 0x091f156, 0x152b88e, 0x1b99395}, - {0x3afd09b, 0x14a991e, 0x24204a6, 0x0c4f62a, 0x0d8e445, - 0x1b85145, 0x2fe499c, 0x117cd53, 0x0fa4cb5, 0x0e0f144}, - - {0x3abca05, 0x0c398d0, 0x0c8317e, 0x09cdfc5, 0x14e01c1, - 0x18f5e86, 0x006e1f1, 0x0897903, 0x1dd81f3, 0x1b7caf0}, - {0x3be3a34, 0x0fdb677, 0x034313e, 0x0ecfca7, 0x3a57531, - 0x19249a1, 0x0a98777, 0x0eb1130, 0x3137a68, 0x1818b77}, - - {0xff9d5a63, 0xff71a307, 0xfe1d4a50, 0xff0b504c, 0x1cfcccc, - 0xff071f21, 0x0cdbe3e, 0x0781b09, 0xfef7225f, 0x0c7b676}, - {0x0363667, 0x0649015, 0x1023cce, 0x09d6889, 0x1ee14ca, - 0xff3bb73e, 0xff8e09a5, 0x065d601, 0xffdfdaa9, 0x0f51ca4}, - - {0x3dad28d, 0x0b59131, 0x3a4db6f, 0x10dc0eb, 0x1ea777b, - 0x07e177d, 0x2821b8e, 0x1cf85b1, 0x1e38185, 0x06f1ebc}, - {0x0314833, 0x0bd9640, 0x0e1f95e, 0x09318d9, 0x07409f8, - 0x15dc049, 0x377c3bc, 0x1e5ef4b, 0x1855661, 0x1876427}, - - {0x3b06838, 0x13f28c1, 0x3e210b9, 0x12b2a63, 0x3ebeacd, - 0x16f53a5, 0x3263a6d, 0x04068ca, 0x297ad5e, 0x00b1870}, - {0x0f259bc, 0x018dd41, 0x005f098, 0x1b338e3, 0x2198ff5, - 0x0bffaf3, 0x016e96e, 0x077b232, 0x26e5a93, 0x10b6831}, - - {0xfef4ca3a, 0x0bb309a, 0x0cae292, 0x06e8318, 0xffac1855, - 0xff4f586a, 0xffc5e2bc, 0xffb1de19, 0xff3a064f, 0xffc598f3}, - {0xfeda2dd9, 0x03f8343, 0xff0c84ee, 0xffb7d140, 0xfe94c180, - 0x0da6c0e, 0x02f3179, 0x0da68ef, 0xffd1c006, 0xff747d5c}, - - {0x0f46f3f, 0x1bf7613, 0x39924e1, 0x005e15a, 0x08f9e93, - 0x19f0229, 0x3f4eb18, 0x01e92da, 0x0e0b5ee, 0x0f3b84c}, - {0x1f2ed09, 0x0e45d8f, 0x1d2f498, 0x0843ea5, 0x063d977, - 0x11d1f47, 0x1e7f933, 0x0f2340c, 0x0593f82, 0x0fc8dd5}, - - {0x3adf1d1, 0x0d93748, 0x20832d2, 0x1afbbfb, 0x28a26a7, - 0x18db034, 0x28cd70d, 0x06b0922, 0x15876d2, 0x1da053c}, - {0x2b523fb, 0x12b33fa, 0x049d1aa, 0x07f597a, 0x1a36d8c, - 0x1cfa837, 0x27ad5c5, 0x152cdd4, 0x3ed6b22, 0x036f67a}, - - {0xffa942c7, 0x0a0c074, 0xfec8e2f1, 0x01e3624, 0x02e5412, - 0x0c911fc, 0xff065c31, 0xff3b308f, 0xffcfa37c, 0xffb709f4}, - {0x0b33e6b, 0xffe32ec1, 0xfe378912, 0xffce613d, 0x0648ae0, - 0xff092e83, 0xfe6cb95b, 0x029a38b, 0xff10beaa, 0xffc8231c}, - - {0x27a8746, 0x095a01b, 0x3b81141, 0x0b3588e, 0x37d1f77, - 0x0d8d910, 0x3d83e75, 0x1c00071, 0x048fc12, 0x0c34ea1}, - {0x1a28906, 0x12b4d3e, 0x1b0a07b, 0x0153a8f, 0x1779e72, - 0x00c9352, 0x0adcd19, 0x119555c, 0x3a6d02b, 0x0eac750}, - - {0x1be5ff0, 0x0c4036d, 0x186470d, 0x1ec03b5, 0x1c6532a, - 0x1c9f27a, 0x3ef151a, 0x1092853, 0x3cab011, 0x191f3be}, - {0x23d583f, 0x0f6d664, 0x1cb1b62, 0x1bf0053, 0x0212a46, - 0x02ed620, 0x1e4a29e, 0x0ef22f1, 0x1990c7e, 0x09460ea}, + {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, + {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, + + {-14297830, -7645148, 16144683, -16471763, 27570974, + -2696100, -26142465, 8378389, 20764389, 8758491}, + {-26843541, -6710886, 13421773, -13421773, 26843546, + 6710886, -13421773, 13421773, -26843546, -6710886}, + + {15573525, 14345213, -21141567, -612142, 123758, + 10521238, 28338138, -12928375, 9171680, -7828746}, + {-18590957, -4287007, 23122404, 4576385, 22037208, + 1801295, 32339603, 310189, 3056877, 825069}, + + {30210978, 104920, -15170738, -6817324, 11761033, + -15118165, -20055778, -18672, -25574763, 3861063}, + {-28221882, -9451648, -21791555, -3983251, 23779144, + -13855839, -7901342, -1724237, -1392984, 6340893}, + + {12052535, 1174424, 8175504, 5117753, -27026921, + -11654751, -23281039, 6656678, -801697, -13590848}, + {-678274, 11486291, 9685879, 15895846, -29146376, + 12753979, 9394963, -15748418, -26925347, -8605080}, + + {825005, 12536410, -6496388, 4296550, -20735056, + 12804180, 31514438, 9564502, 22198414, -4615275}, + {-5255013, -11888353, -29227865, 12908075, 14214213, + -4697787, -16889443, -15217324, 16403638, 14741828}, + + {-5518824, 12818641, 13119870, 10280901, 21889473, + -7381370, 451058, 9009411, 31293939, -4732176}, + {-4310457, 16627320, 3420478, 15531175, -5933775, + -7190110, 11110264, 15405360, -15500696, -8287368}, + + {-6464925, -9329913, -31634864, -16035764, 30395596, + -16310495, 13483582, 7871241, -17358241, 13088374}, + {3552871, 6590485, 16923854, 10315913, 32380106, + -12863682, -7468635, 6673921, -2106711, 16063652}, + + {-2436467, 11899186, -5973137, -15875860, 32143228, + 8263549, -25027698, -3177038, 31687046, 7282364}, + {3229766, 12424768, 14809438, 9640153, 7604728, + -10633143, -8928323, -1708212, 25515618, -7904217}, + + {-5216200, -12638014, -1961798, -13948316, -1316146, + -9481306, -14271890, 4221131, -23614114, 727153}, + {15882703, 1629505, 389272, -5031709, -31879178, + 12581620, 1501550, 7844402, -26322285, -16029646}, + + {-17511878, 12267674, 13296274, 7242520, -5498795, + -11577238, -3808580, -5120487, -12974513, -3827469}, + {-19255847, 4162371, -15956754, -4730560, -23805568, + 14314510, 3092857, 14313711, -3031034, -9142948}, + + {16019263, -4229613, -6740766, 385371, 9412243, + -6356439, -726247, 2003675, 14726638, 15972428}, + {32697609, 14966159, 30602392, 8666789, 6543735, + -14868665, 31979828, 15873036, 5848962, 16551381}, + + {-5377564, 14235465, -33017134, -5260292, -24500568, + -7491531, -24324338, 7014691, 22574802, -2489028}, + {-21683205, -13945861, 4837803, 8345978, 27487628, + -3168201, -25504314, -11350571, -1217757, 3602043}, + + {-5684537, 10535028, -20389135, 1979940, 3036178, + 13177340, -16360399, -12898161, -3169412, -4781580}, + {11746923, -1888575, -29914862, -3251907, 6589152, + -16175485, -26429093, 2728843, -15679830, -3661028}, + + {-25524410, 9805852, -4714175, 11753615, -8577161, + 14211345, -2605451, -4194190, 4783123, 12799649}, + {27429126, -13939394, 28352636, 1391247, 24616562, + 824146, 11390233, -15116964, -5844948, 15386449}, + + {29253635, 12845933, 25577229, -1309771, 29774635, + -3542406, -1108709, -16177068, -3493870, -7212097}, + {-29534145, 16176741, 30088034, -4259757, 2173511, + 3069472, 31761054, 15672049, 26807422, 9724138}, }; // Variable time! P, sP, and sB must not be secret! -- 2.47.3