Daiki Ueno ueno@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