Hello,
SP800-56A (revision 3) section 5.6.2.3.3 now mandates a check that the generated public key (Q) multiplied by the curve order (n) results in an identity element (= an infinity point).
It seem that it is not possible to implement this check with the Nettle's public API. The attached patch naively multiplies Q by n but it causes the valgrind errors below.
As it works with the curve order minus 1, I added the following check instead in my library, though I'm not sure if this satisfies the original requirement:
P = (n - 1) * Q
where P's x-coordinate is the same as Q's, and P also lies on the same curve so that indicates P + Q (= n * Q) is an infinity point, according to the group law.
Is there a better (direct) way to implement the check? Suggestions appreciated.
Conditional jump or move depends on uninitialised value(s) at 0x4880DFB: _nettle_ecc_mul_a (ecc-mul-a.c:145) by 0x48815F8: nettle_ecc_point_mul (ecc-point-mul.c:55) by 0x4012EB: main (ecc-test.c:36)
Conditional jump or move depends on uninitialised value(s) at 0x487D1D9: _nettle_sec_tabselect (sec-tabselect.c:54) by 0x4880E1B: _nettle_ecc_mul_a (ecc-mul-a.c:147) by 0x48815F8: nettle_ecc_point_mul (ecc-point-mul.c:55) by 0x4012EB: main (ecc-test.c:36)
Conditional jump or move depends on uninitialised value(s) at 0x487E0F3: _nettle_ecc_mod_add (ecc-mod-arith.c:53) by 0x487F51B: _nettle_ecc_dup_jj (ecc-dup-jj.c:81) by 0x4880E66: _nettle_ecc_mul_a (ecc-mul-a.c:171) by 0x48815F8: nettle_ecc_point_mul (ecc-point-mul.c:55) by 0x4012EB: main (ecc-test.c:36)
Regards,
Daiki Ueno ueno@gnu.org writes:
It seem that it is not possible to implement this check with the Nettle's public API. The attached patch naively multiplies Q by n but it causes the valgrind errors below.
I think the point multiplication functions were written under the assumption that the scalar should be less than the group order. Docs could perhaps be improved on that.
But I don't known now exactly how it fails. It's good you get the valgrind failures, but line numbers don't quite match my version.
If ecc_mul_a can be made to support this, I take it the output will be a point with z = 0 (mod p) in homogenenous coordinates.
And then the special case z = 0 has to be detected in some way in the conversion to affine coordinates. That's done by ecc_j_to_a, but that assumes a finite input point, since it inverts z without checking for zero.
As it works with the curve order minus 1, I added the following check instead in my library, though I'm not sure if this satisfies the original requirement:
P = (n - 1) * Q
Checking that (n-1) * Q = -Q should be mathematically equivalent. There's a similar test in testsuite/ecc-mul-a-test.c and testsuite/ecc-mul-g-test.c (but testing with the generator rather than with an arbitrary public key).
If the point of the requirements of "SP800-56A (revision 3)" is to check the mathematical properties of the point, rather than testing a particular implementation of the ecc arithmetics, then (n-1) Q = -Q sounds good enough to me. You should first check that Q really lies on the curve (otherwise both left-hand side and right-hand side operations suffer garbage-in-garbage-out), but you probably do that already.
Regards, /Niels
nisse@lysator.liu.se (Niels Möller) writes:
I think the point multiplication functions were written under the assumption that the scalar should be less than the group order. Docs could perhaps be improved on that.
But I don't known now exactly how it fails. It's good you get the valgrind failures, but line numbers don't quite match my version.
I was using the Nettle version installed on the system, sorry. I'm attaching the complete log taken with the git master (d1e45e07f).
If ecc_mul_a can be made to support this, I take it the output will be a point with z = 0 (mod p) in homogenenous coordinates.
And then the special case z = 0 has to be detected in some way in the conversion to affine coordinates. That's done by ecc_j_to_a, but that assumes a finite input point, since it inverts z without checking for zero.
I think it would be nice if it hits an assertion failure.
As it works with the curve order minus 1, I added the following check instead in my library, though I'm not sure if this satisfies the original requirement:
P = (n - 1) * Q
Checking that (n-1) * Q = -Q should be mathematically equivalent. There's a similar test in testsuite/ecc-mul-a-test.c and testsuite/ecc-mul-g-test.c (but testing with the generator rather than with an arbitrary public key).
Thanks for the pointer and the confirmation; I've tightened the check based on testsuite/ecc-mul-a-test.c. For the record, the patch is: https://gitlab.com/gnutls/gnutls/-/merge_requests/1299/diffs?commit_id=23756...
Regards,
nettle-bugs@lists.lysator.liu.se
-
Daiki Ueno -
nisse＠lysator.liu.se