Merge branch 'ecdsa-duplication-fix'

9 files changed, 255 insertions, 36 deletions

diff --git a/ChangeLog b/ChangeLog
index 93da4856..6f6bd841 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -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"