diff options
| -rw-r--r-- | ChangeLog | 18 | ||||
| -rw-r--r-- | Makefile.in | 2 | ||||
| -rw-r--r-- | ecc-ecdsa-verify.c | 22 | ||||
| -rw-r--r-- | ecc-gostdsa-verify.c | 7 | ||||
| -rw-r--r-- | ecc-internal.h | 9 | ||||
| -rw-r--r-- | ecc-nonsec-add-jjj.c | 162 | ||||
| -rw-r--r-- | testsuite/ecc-add-test.c | 44 | ||||
| -rw-r--r-- | testsuite/ecdsa-sign-test.c | 12 | ||||
| -rw-r--r-- | testsuite/ecdsa-verify-test.c | 15 |
9 files changed, 255 insertions, 36 deletions
@@ -43,6 +43,24 @@ * testsuite/balloon-test.c: New tests. * testsuite/Makefile.in (TS_NETTLE_SOURCES): Add balloon-test.c. +2022-09-14 Niels Möller <nisse@lysator.liu.se> + + * ecc-nonsec-add-jjj.c (ecc_nonsec_add_jjj): New file and + function. + * ecc-internal.h: Declare it. + * Makefile.in (hogweed_SOURCES): Add ecc-nonsec-add-jjj.c. + * testsuite/ecc-add-test.c (test_main): Add tests for ecc_nonsec_add_jjj. + + * ecc-ecdsa-verify.c (ecc_ecdsa_verify): Use ecc_nonsec_add_jjj, + to produce correct result in a corner case where point addition + needs to use point duplication. Also use ecc_j_to_a rather than + ecc->h_to_a, since ecdsa supports only weierstrass curves. + * ecc-gostdsa-verify.c (ecc_gostdsa_verify): Analogous change. + + * testsuite/ecdsa-verify-test.c (test_main): Add corresponding test. + * testsuite/ecdsa-sign-test.c (test_main): And a test producing + the problematic signature. + 2022-09-08 Niels Möller <nisse@lysator.liu.se> * eccdata.c (string_toupper): New utility function. diff --git a/Makefile.in b/Makefile.in index b9e39581..73e25323 100644 --- a/Makefile.in +++ b/Makefile.in @@ -203,7 +203,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \ ecc-secp192r1.c ecc-secp224r1.c ecc-secp256r1.c \ ecc-secp384r1.c ecc-secp521r1.c \ ecc-size.c ecc-j-to-a.c ecc-a-to-j.c \ - ecc-dup-jj.c ecc-add-jja.c ecc-add-jjj.c \ + ecc-dup-jj.c ecc-add-jja.c ecc-add-jjj.c ecc-nonsec-add-jjj.c \ ecc-eh-to-a.c \ ecc-dup-eh.c ecc-add-eh.c ecc-add-ehh.c \ ecc-dup-th.c ecc-add-th.c ecc-add-thh.c \ diff --git a/ecc-ecdsa-verify.c b/ecc-ecdsa-verify.c index f3b112b0..4c6284af 100644 --- a/ecc-ecdsa-verify.c +++ b/ecc-ecdsa-verify.c @@ -117,25 +117,13 @@ ecc_ecdsa_verify (const struct ecc_curve *ecc, /* Total storage: 7*ecc->p.size + ecc->mul_g_itch (ecc->p.size) */ ecc->mul_g (ecc, P1, u1, P1 + 3*ecc->p.size); - /* NOTE: ecc_add_jjj and/or ecc_j_to_a will produce garbage in - case u1 G = +/- u2 V. However, anyone who gets his or her - hands on a signature where this happens during verification, - can also get the private key as z = +/- u1 / u_2 (mod q). And - then it doesn't matter very much if verification of - signatures with that key succeeds or fails. - - u1 G = - u2 V can never happen for a correctly generated - signature, since it implies k = 0. - - u1 G = u2 V is possible, if we are unlucky enough to get h / - s_1 = z. Hitting that is about as unlikely as finding the - private key by guessing. - */ - /* Total storage: 6*ecc->p.size + ecc->add_hhh_itch */ - ecc->add_hhh (ecc, P2, P2, P1, P1 + 3*ecc->p.size); + /* Total storage: 6*ecc->p.size + ECC_ADD_JJJ_ITCH(size) */ + if (!ecc_nonsec_add_jjj (ecc, P2, P2, P1, P1 + 3*ecc->p.size)) + /* Infinity point, not a valid signature. */ + return 0; } /* x coordinate only, modulo q */ - ecc->h_to_a (ecc, 2, P1, P2, P1 + 3*ecc->p.size); + ecc_j_to_a (ecc, 2, P1, P2, P1 + 3*ecc->p.size); return (mpn_cmp (rp, P1, ecc->p.size) == 0); #undef P2 diff --git a/ecc-gostdsa-verify.c b/ecc-gostdsa-verify.c index fcdd4644..a835ba71 100644 --- a/ecc-gostdsa-verify.c +++ b/ecc-gostdsa-verify.c @@ -114,11 +114,12 @@ ecc_gostdsa_verify (const struct ecc_curve *ecc, /* Total storage: 7*ecc->p.size + ecc->mul_g_itch (ecc->p.size) */ ecc->mul_g (ecc, P1, z1, P1 + 3*ecc->p.size); - /* Total storage: 6*ecc->p.size + ecc->add_hhh_itch */ - ecc->add_hhh (ecc, P1, P1, P2, P1 + 3*ecc->p.size); + /* Total storage: 6*ecc->p.size + ECC_ADD_JJJ_ITCH(size) */ + if (!ecc_nonsec_add_jjj (ecc, P1, P1, P2, P1 + 3*ecc->p.size)) + return 0; /* x coordinate only, modulo q */ - ecc->h_to_a (ecc, 2, P2, P1, P1 + 3*ecc->p.size); + ecc_j_to_a (ecc, 2, P2, P1, P1 + 3*ecc->p.size); return (mpn_cmp (rp, P2, ecc->p.size) == 0); #undef P2 diff --git a/ecc-internal.h b/ecc-internal.h index b04d80ce..6201bf05 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -66,6 +66,7 @@ #define ecc_dup_jj _nettle_ecc_dup_jj #define ecc_add_jja _nettle_ecc_add_jja #define ecc_add_jjj _nettle_ecc_add_jjj +#define ecc_nonsec_add_jjj _nettle_ecc_nonsec_add_jjj #define ecc_dup_eh _nettle_ecc_dup_eh #define ecc_add_eh _nettle_ecc_add_eh #define ecc_add_ehh _nettle_ecc_add_ehh @@ -390,6 +391,14 @@ ecc_add_jjj (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, mp_limb_t *scratch); +/* Variant that handles the checks for the special cases P = ±Q. + Returns 1 on success, 0 if result is infinite. Not side-channel + silent, so must not be used with secret inputs. */ +int +ecc_nonsec_add_jjj (const struct ecc_curve *ecc, + mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, + mp_limb_t *scratch); + /* Point doubling on a twisted Edwards curve, with homogeneous cooordinates. */ void diff --git a/ecc-nonsec-add-jjj.c b/ecc-nonsec-add-jjj.c new file mode 100644 index 00000000..439c0a52 --- /dev/null +++ b/ecc-nonsec-add-jjj.c @@ -0,0 +1,162 @@ +/* ecc-non-sec-add-jjj.c + + Copyright (C) 2013, 2022 Niels Möller + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include "ecc.h" +#include "ecc-internal.h" + +/* Similar to ecc_add_jjj, but checks if x coordinates are equal (H = + 0) below, and if so, performs doubling if also y coordinates are + equal, or returns 0 (failure) indicating that the result is the + infinity point. */ +int +ecc_nonsec_add_jjj (const struct ecc_curve *ecc, + mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, + mp_limb_t *scratch) +{ +#define x1 p +#define y1 (p + ecc->p.size) +#define z1 (p + 2*ecc->p.size) + +#define x2 q +#define y2 (q + ecc->p.size) +#define z2 (q + 2*ecc->p.size) + +#define x3 r +#define y3 (r + ecc->p.size) +#define z3 (r + 2*ecc->p.size) + /* Formulas, from djb, + http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-bl: + + Computation Operation Live variables + + Z1Z1 = Z1^2 sqr Z1Z1 + Z2Z2 = Z2^2 sqr Z1Z1, Z2Z2 + U1 = X1*Z2Z2 mul Z1Z1, Z2Z2, U1 + U2 = X2*Z1Z1 mul Z1Z1, Z2Z2, U1, U2 + H = U2-U1 Z1Z1, Z2Z2, U1, H + Z3 = ((Z1+Z2)^2-Z1Z1-Z2Z2)*H sqr, mul Z1Z1, Z2Z2, U1, H + S1 = Y1*Z2*Z2Z2 mul, mul Z1Z1, U1, H, S1 + S2 = Y2*Z1*Z1Z1 mul, mul U1, H, S1, S2 + W = 2*(S2-S1) (djb: r) U1, H, S1, W + I = (2*H)^2 sqr U1, H, S1, W, I + J = H*I mul U1, S1, W, J, V + V = U1*I mul S1, W, J, V + X3 = W^2-J-2*V sqr S1, W, J, V + Y3 = W*(V-X3)-2*S1*J mul, mul + */ + +#define h scratch +#define z1z1 (scratch + ecc->p.size) +#define z2z2 z1z1 +#define z1z2 (scratch + 2*ecc->p.size) + +#define w (scratch + ecc->p.size) +#define i (scratch + 2*ecc->p.size) +#define j h +#define v i + +#define tp (scratch + 3*ecc->p.size) + + ecc_mod_sqr (&ecc->p, z2z2, z2, tp); /* z2z2 */ + /* Store u1 at x3 */ + ecc_mod_mul (&ecc->p, x3, x1, z2z2, tp); /* z2z2 */ + + ecc_mod_add (&ecc->p, z1z2, z1, z2); /* z2z2, z1z2 */ + ecc_mod_sqr (&ecc->p, z1z2, z1z2, tp); + ecc_mod_sub (&ecc->p, z1z2, z1z2, z2z2); /* z2z2, z1z2 */ + + /* Do s1 early, store at y3 */ + ecc_mod_mul (&ecc->p, z2z2, z2z2, z2, tp); /* z2z2, z1z2 */ + ecc_mod_mul (&ecc->p, y3, z2z2, y1, tp); /* z1z2 */ + + ecc_mod_sqr (&ecc->p, z1z1, z1, tp); /* z1z1, z1z2 */ + ecc_mod_sub (&ecc->p, z1z2, z1z2, z1z1); + ecc_mod_mul (&ecc->p, h, x2, z1z1, tp); /* z1z1, z1z2, h */ + ecc_mod_sub (&ecc->p, h, h, x3); + + /* z1^3 */ + ecc_mod_mul (&ecc->p, z1z1, z1z1, z1, tp); + + /* z3 <-- h z1 z2 delayed until now, since that may clobber z1. */ + ecc_mod_mul (&ecc->p, z3, z1z2, h, tp); /* z1z1, h */ + /* w = 2 (s2 - s1) */ + ecc_mod_mul (&ecc->p, w, z1z1, y2, tp); /* h, w */ + ecc_mod_sub (&ecc->p, w, w, y3); + + /* Note that use of ecc_mod_zero_p depends 0 <= h,w < 2p. */ + if (ecc_mod_zero_p (&ecc->p, h)) + { + /* X1 == X2 */ + if (ecc_mod_zero_p (&ecc->p, w)) { + /* Y1 == Y2. Do point duplication. Note that q input is + unclobbered, and that scratch need is smaller. Implies some + unnecessary recomputation, but performance it not so + important for this very unlikely corner case. */ + ecc_dup_jj (ecc, r, q, scratch); + return 1; + } + + /* We must have Y1 == -Y2, and then the result is the infinity + point, */ + mpn_zero (r, 3*ecc->p.size); + return 0; + } + ecc_mod_add (&ecc->p, w, w, w); + + /* i = (2h)^2 */ + ecc_mod_add (&ecc->p, i, h, h); /* h, w, i */ + ecc_mod_sqr (&ecc->p, i, i, tp); + + /* j and h can overlap */ + ecc_mod_mul (&ecc->p, j, h, i, tp); /* j, w, i */ + + /* v and i can overlap */ + ecc_mod_mul (&ecc->p, v, x3, i, tp); /* j, w, v */ + + /* x3 <-- w^2 - j - 2v */ + ecc_mod_sqr (&ecc->p, x3, w, tp); + ecc_mod_sub (&ecc->p, x3, x3, j); + ecc_mod_submul_1 (&ecc->p, x3, v, 2); + + /* y3 <-- w (v - x3) - 2 s1 j */ + ecc_mod_mul (&ecc->p, j, j, y3, tp); + ecc_mod_sub (&ecc->p, v, v, x3); + ecc_mod_mul (&ecc->p, y3, v, w, tp); + ecc_mod_submul_1 (&ecc->p, y3, j, 2); + + return 1; +} diff --git a/testsuite/ecc-add-test.c b/testsuite/ecc-add-test.c index 6f58a3bb..4793a4bf 100644 --- a/testsuite/ecc-add-test.c +++ b/testsuite/ecc-add-test.c @@ -19,6 +19,24 @@ test_main (void) test_ecc_get_g (i, g); + ecc->dup (ecc, g2, g, scratch); + test_ecc_mul_h (i, 2, g2); + + ecc->add_hhh (ecc, g3, g, g2, scratch); + test_ecc_mul_h (i, 3, g3); + + ecc->add_hhh (ecc, g3, g2, g, scratch); + test_ecc_mul_h (i, 3, g3); + + ecc->add_hhh (ecc, p, g, g3, scratch); + test_ecc_mul_h (i, 4, p); + + ecc->add_hhh (ecc, p, g3, g, scratch); + test_ecc_mul_h (i, 4, p); + + ecc->dup (ecc, p, g2, scratch); + test_ecc_mul_h (i, 4, p); + if (ecc->p.bit_size == 255 || ecc->p.bit_size == 448) { mp_limb_t *z = xalloc_limbs (ecc_size_j (ecc)); @@ -49,24 +67,20 @@ test_main (void) free (z); } + else + { + ASSERT (ecc_nonsec_add_jjj (ecc, g2, g, g, scratch)); + test_ecc_mul_h (i, 2, g2); - ecc->dup (ecc, g2, g, scratch); - test_ecc_mul_h (i, 2, g2); - - ecc->add_hhh (ecc, g3, g, g2, scratch); - test_ecc_mul_h (i, 3, g3); - - ecc->add_hhh (ecc, g3, g2, g, scratch); - test_ecc_mul_h (i, 3, g3); - - ecc->add_hhh (ecc, p, g, g3, scratch); - test_ecc_mul_h (i, 4, p); + ASSERT (ecc_nonsec_add_jjj (ecc, g3, g2, g, scratch)); + test_ecc_mul_h (i, 3, g3); - ecc->add_hhh (ecc, p, g3, g, scratch); - test_ecc_mul_h (i, 4, p); + ASSERT (ecc_nonsec_add_jjj (ecc, p, g, g3, scratch)); + test_ecc_mul_h (i, 4, p); - ecc->dup (ecc, p, g2, scratch); - test_ecc_mul_h (i, 4, p); + ASSERT (ecc_nonsec_add_jjj (ecc, p, g2, g2, scratch)); + test_ecc_mul_h (i, 4, p); + } free (g); free (g2); diff --git a/testsuite/ecdsa-sign-test.c b/testsuite/ecdsa-sign-test.c index c79493ae..b8a100b6 100644 --- a/testsuite/ecdsa-sign-test.c +++ b/testsuite/ecdsa-sign-test.c @@ -77,6 +77,18 @@ test_main (void) "3a41e1423b1853e8aa89747b1f987364" "44705d6d6d8371ea1f578f2e"); /* s */ + /* Produce a signature where verify operation results in a point duplication. */ + test_ecdsa (&_nettle_secp_256r1, + "1", /* Private key */ + "01010101010101010101010101010101" + "01010101010101010101010101010101", /* nonce */ + SHEX("6ff03b949241ce1dadd43519e6960e0a" + "85b41a69a05c328103aa2bce1594ca16"), /* hash */ + "6ff03b949241ce1dadd43519e6960e0a" + "85b41a69a05c328103aa2bce1594ca16", /* r */ + "53f097727a0e0dc284a0daa0da0ab77d" + "5792ae67ed075d1f8d5bda0f853fa093"); /* s */ + /* Test cases for the smaller groups, verified with a proof-of-concept implementation done for Yubico AB. */ test_ecdsa (&_nettle_secp_192r1, diff --git a/testsuite/ecdsa-verify-test.c b/testsuite/ecdsa-verify-test.c index 8110c64d..8d527000 100644 --- a/testsuite/ecdsa-verify-test.c +++ b/testsuite/ecdsa-verify-test.c @@ -109,6 +109,21 @@ test_main (void) "952800792ed19341fdeeec047f2514f3b0f150d6066151fb", /* r */ "ec5971222014878b50d7a19d8954bc871e7e65b00b860ffb"); /* s */ + /* Test case provided by Guido Vranken, from oss-fuzz. Triggers + point duplication in the verify operation by using private key = + 1 (public key = generator) and hash = r. */ + test_ecdsa (&_nettle_secp_256r1, + "6B17D1F2E12C4247F8BCE6E563A440F2" + "77037D812DEB33A0F4A13945D898C296", /* x */ + "4FE342E2FE1A7F9B8EE7EB4A7C0F9E16" + "2BCE33576B315ECECBB6406837BF51F5", /* y */ + SHEX("6ff03b949241ce1dadd43519e6960e0a" + "85b41a69a05c328103aa2bce1594ca16"), /* hash */ + "6ff03b949241ce1dadd43519e6960e0a" + "85b41a69a05c328103aa2bce1594ca16", /* r */ + "53f097727a0e0dc284a0daa0da0ab77d" + "5792ae67ed075d1f8d5bda0f853fa093"); /* s */ + /* From RFC 4754 */ test_ecdsa (&_nettle_secp_256r1, "2442A5CC 0ECD015F A3CA31DC 8E2BBC70" |