Daiki Ueno <[email protected]> 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
[email protected]
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
