Re: [PATCH 0/8] Implement Curve448 ECDH and Ed448
ni...@lysator.liu.se (Niels Möller) writes: > I think this is complete now (except updating hogweed-benchmark), just > pushed to the ed448 branch. Thanks for the patience. It seems I forgot to add the new files in the first attempt. Ooops. Fixed with a forced update on this branch. Now ubsan fails, it doesn't like calling memcpy with null ptr and zero size. I have to fix that. Not sure what's prettiest, either a conditional, or a function pointer like it was done in the original patch. In the mean time, I've updated hogweed benchmark (not yet committed). This is what I get on my old (x86_64) laptop: name size sign/ms verify/ms ecdsa 1925.21941.7914 ecdsa 2243.22971.1658 ecdsa 2563.11531.0347 ecdsa 3841.43930.4607 ecdsa 5210.72770.2308 eddsa 2556.02431.5598 eddsa 4481.74640.4595 So speedwise, ed25519 is comparable to ecdsa on secp_192r1, and ed448 is comparable to ecdsa on secp_384r1. In both cases, signing is a bit faster (15%-20%), and verify is the same or a bit slower. 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
Re: [PATCH 0/8] Implement Curve448 ECDH and Ed448
Daiki Ueno 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
Re: [PATCH 0/8] Implement Curve448 ECDH and Ed448
Hello Niels,
Thank you very much for all the Curve448/SHAKE256 work for merging (I'm
slowly catching up).
ni...@lysator.liu.se (Niels Möller) writes:
> ni...@lysator.liu.se (Niels Möller) writes:
>
>> Daiki Ueno writes:
>>
>>> For curve25519, q is defined as:
>>>
>>> 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed
>>>
>>> whose bit pattern starts with 0x1000, so r - q * (r>>252) should
>>> work.
>>>
>>> On the other hand, for curve448, q is defined as:
>>>
>>> 2^446 - 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d
>>>
>>> whose bit pattern starts with 0x. In that case the formula (r - q *
>>> (r>>445)) could be incorrect due to the accumulated errors by
>>> multiplication (i.e. q * 0x7FFF...).
>>
>> Good catch! Right, this needs a bit more analysis. Fur curve25519, the
>> subtraction can underflow (unlikely), which is addressed with the
>> conditional addition a few lines down.
>
> For ecc_ah_to_a, this code was deleted, but it's still an issue for
> eddsa_sign. Maybe need special cases for both ed25519 and ed448 for now.
> Or some logic looking at the high limb of q.
>
> 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:
test_one
("0cf87eb094bf46d161bde3b99d1d32856fecfae0142392cd98c091db206d174bbf8ef476a9cf746d94306c565f97ac50796f021eff8d779ca5"
"9addde61f668f2dbc0ac24874adb47a2aa6ad59fa888bdc5d430705ed0796a8c330782b51860785be63fd79b1c7cf58fd728b2bf3d77395100:"
"9addde61f668f2dbc0ac24874adb47a2aa6ad59fa888bdc5d430705ed0796a8c330782b51860785be63fd79b1c7cf58fd728b2bf3d77395100:"
"20202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020544c5320312e332c207365727665722043657274696669636174655665726966790090da2c6178a3019274ed029ba5ad28f25662a78d71e8429c19f96007df39d7a77d7cb80f221c76db5e1c397714f48692:"
"91554b9b85058d3d6885997adf47e1f766ae780018ca26873de854fb12d789f3bf1f85d3ce5b23265d8d8900f62906e2eb4a064887beaf9cea26f0edeff35be1e969df77ab1368ced966beb0c7b6242aa0d8844d773e254cfed823d3a5e53b3ef557e716ce7cc2aaca127e86798f2b00"
"20202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020544c5320312e332c207365727665722043657274696669636174655665726966790090da2c6178a3019274ed029ba5ad28f25662a78d71e8429c19f96007df39d7a77d7cb80f221c76db5e1c397714f48692:");
>> It might make sense to instead add a function pointer to struct
>> ecc_modulo to do canonical reduction; that's needed in a few different
>> places, not only here.
>
> I still think think this makes sense, but it's not clear to me what the
> usage really is.
Regards,
Footnotes:
[1] https://gitlab.com/gnutls/gnutls/merge_requests/984
--
Daiki Ueno
___
nettle-bugs mailing list
nettle-bugs@lists.lysator.liu.se
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
Re: [PATCH 0/8] Implement Curve448 ECDH and Ed448
ni...@lysator.liu.se (Niels Möller) writes: > Daiki Ueno writes: > >> For curve25519, q is defined as: >> >> 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed >> >> whose bit pattern starts with 0x1000, so r - q * (r>>252) should >> work. >> >> On the other hand, for curve448, q is defined as: >> >> 2^446 - 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d >> >> whose bit pattern starts with 0x. In that case the formula (r - q * >> (r>>445)) could be incorrect due to the accumulated errors by >> multiplication (i.e. q * 0x7FFF...). > > Good catch! Right, this needs a bit more analysis. Fur curve25519, the > subtraction can underflow (unlikely), which is addressed with the > conditional addition a few lines down. For ecc_ah_to_a, this code was deleted, but it's still an issue for eddsa_sign. Maybe need special cases for both ed25519 and ed448 for now. Or some logic looking at the high limb of q. These corner cases are a bit hard to test. > It might make sense to instead add a function pointer to struct > ecc_modulo to do canonical reduction; that's needed in a few different > places, not only here. I still think think this makes sense, but it's not clear to me what the usage really is. 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
