Daiki Ueno <u...@gnu.org> writes: > Thank you very much for all the Curve448/SHAKE256 work for merging (I'm > slowly catching up).
I think this is complete now (except updating hogweed-benchmark), just pushed to the ed448 branch. Thanks for the patience. >> These corner cases are a bit hard to test. > > For what it's worth, the original issue was reliably reproducible with > the GnuTLS port[1] against the OpenSSL client. Here is a test vector > extracted from the interaction: I'm afraid this doesn't exercise the corner cases. The thing is, we have q close to 2^k (k = 2^252 for ed25519, k = 446 for ed448). Then we want to reduce r = hi 2^k + lo modulo q, canonically. If we set r' = r - hi * q then it's highly likely that 0 <= r' < q, but not certain. For ed25519, q > 2^k, so we are guaranteed that r' < 2^k < q, but we may get r' < 0. For ed448, q < 2^k, so we are guaranteed that r' > 0, and we may instead get r' >= q. For now, I've added the following logic to _eddsa_sign: if (ecc->p.bit_size == 255) { /* FIXME: Special code duplicated in ecc_25519_modq Define a suitable method for canonical reduction? */ /* q is slightly larger than 2^252, underflow from below mpn_submul_1 is unlikely. */ unsigned shift = 252 - GMP_NUMB_BITS * (ecc->p.size - 1); q = sp[ecc->p.size-1] >> shift; } else { unsigned shift; assert (ecc->p.bit_size == 448); /* q is slightly smaller than 2^446 */ shift = 446 - GMP_NUMB_BITS * (ecc->p.size - 1); /* Add one, then it's possible but unlikely that below mpn_submul_1 does *not* underflow. */ q = (sp[ecc->p.size-1] >> shift) + 1; } cy = mpn_submul_1 (sp, ecc->q.m, ecc->p.size, q); assert (cy < 2); cy -= cnd_add_n (cy, sp, ecc->q.m, ecc->p.size); assert (cy == 0); I think that's correct, but it seems tricky to find inputs to _eddsa_sign that will hit the corner cases. I've added some debug printouts to verify that mpn_submul_1 returns 0 for the ed25519 testcases, and 1 for all the ed448 testcases. If it's taken out to a separate function/method, then it gets easier to unit test. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ nettle-bugs mailing list nettle-bugs@lists.lysator.liu.se http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs