From: Mark Wooding <mdw@distorted.org.uk>
Date: Thu, 18 Jan 2007 16:51:18 +0000 (+0000)
Subject: ec-info: Overhaul elliptic curve domain parameter checking.
X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/30ac115b90b0ed66eed17b722a76d3e7e6e4531c

ec-info: Overhaul elliptic curve domain parameter checking.

  * Separate out the common parts of prime and binary curve checking into
    its own function.

  * Replace the cofactor checking with a new, rather more complicated,
    algorithm which verifies that it has the correct value without
    needing an explicit square-root.  Also allow larger cofactors; it's
    not our responsibility to avoid small-subgroup attacks.

  * Replace the embedding-degree check with one that's rather more
    enlightened.  Unfortunately, it has to intuit the desired security
    level, and that's not going to work well.

Also check for memory leaks in the test harness (one snuck in during
development and was caught by another test).
---

diff --git a/ec-info.c b/ec-info.c
index 474691b..0e225a7 100644
--- a/ec-info.c
+++ b/ec-info.c
@@ -328,46 +328,17 @@ void ec_freeinfo(ec_info *ei)
  * Use:		Checks an elliptic curve according to the rules in SEC1.
  */
 
-static int primeeltp(mp *x, field *f)
-{
-  return (!MP_NEGP(x) && MP_CMP(x, <, f->m));
-}
-
-static const char *primecheck(const ec_info *ei, grand *gr)
+static const char *gencheck(const ec_info *ei, grand *gr, mp *q)
 {
   ec_curve *c = ei->c;
   field *f = c->f;
-  int i;
+  int i, j, n;
+  mp *qq;
+  mp *nn;
   mp *x, *y;
   ec p;
   int rc;
 
-  /* --- Check %$p$% is an odd prime --- */
-
-  if (!pgen_primep(f->m, gr)) return ("p not prime");
-
-  /* --- Check %$a$%, %$b$%, %$G_x$% and %$G_y$% are in %$[0, p)$% --- */
-
-  if (!primeeltp(c->a, f)) return ("a out of range");
-  if (!primeeltp(c->b, f)) return ("b out of range");
-  if (!primeeltp(ei->g.x, f)) return ("G_x out of range");
-  if (!primeeltp(ei->g.x, f)) return ("G_y out of range");
-
-  /* --- Check %$4 a^3 + 27 b^2 \not\equiv 0 \pmod{p}$% --- */
-
-  x = F_SQR(f, MP_NEW, c->a);
-  x = F_MUL(f, x, x, c->a);
-  x = F_QDL(f, x, x);
-  y = F_SQR(f, MP_NEW, c->b);
-  y = F_TPL(f, y, y);
-  y = F_TPL(f, y, y);
-  y = F_TPL(f, y, y);
-  x = F_ADD(f, x, x, y);
-  rc = F_ZEROP(f, x);
-  MP_DROP(x);
-  MP_DROP(y);
-  if (rc) return ("not an elliptic curve");
-
   /* --- Check %$G \in E$% --- */
 
   if (EC_ATINF(&ei->g)) return ("generator at infinity");
@@ -377,24 +348,54 @@ static const char *primecheck(const ec_info *ei, grand *gr)
 
   if (!pgen_primep(ei->r, gr)) return ("generator order not prime");
 
-  /* --- Check %$h = \lfloor (\sqrt{p} + 1)^2/r \rlfoor$% --- *
+  /* --- Check that the cofactor is correct --- *
+   *
+   * Let %$q$% be the size of the field, and let %$n = h r = \#E(\gf{q})$% be
+   * the number of %$\gf{q}$%-rational points on our curve.  Hasse's theorem
+   * tells us that
+   *
+   *   %$|q + 1 - n| \le 2\sqrt{q}$%
+   *
+   * or, if we square both sides,
+   *
+   *   %$(q + 1 - n)^2 \le 4 q$%.
+   *
+   * We'd like the cofactor to be uniquely determined by this equation, which
+   * is possible as long as it's not too big.  (If it is, we have to mess
+   * about with Weil pairings, which is no fun.)  For this, we need the
+   * following inequalities:
+   *
+   *   * %$A = (q + 1 - n)^2 \le 4 q$% (both lower and upper bounds from
+   *	 Hasse's theorem);
    *
-   * This seems to work with the approximate-sqrt in the library, but might
-   * not be so good in some cases.  Throw in some extra significate figures
-   * for good measure.
+   *   * %$B = (q + 1 - n - r)^2 > 4 q$% (check %$h - 1$% isn't possible);
+   *	 and
+   *
+   *   * %$C = (q + 1 - n + r)^2 > 4 q$% (check %$h + 1$% isn't possible).
    */
 
-  x = mp_lsl(MP_NEW, f->m, 128);
-  x = mp_sqrt(x, x);
-  y = mp_lsl(MP_NEW, MP_ONE, 64);
-  x = mp_add(x, x, y);
-  x = mp_sqr(x, x);
-  mp_div(&x, 0, x, ei->r);
-  x = mp_lsr(x, x, 128);
-  rc = MP_EQ(x, ei->h);
+  rc = 1;
+  qq = mp_add(MP_NEW, q, MP_ONE);
+  nn = mp_mul(MP_NEW, ei->r, ei->h);
+  nn = mp_sub(nn, qq, nn);
+  qq = mp_lsl(qq, q, 2);
+
+  y = mp_sqr(MP_NEW, nn);
+  if (MP_CMP(y, >, qq)) rc = 0;
+
+  x = mp_sub(MP_NEW, nn, ei->r);
+  y = mp_sqr(y, x);
+  if (MP_CMP(y, <=, qq)) rc = 0;
+
+  x = mp_add(x, nn, ei->r);
+  y = mp_sqr(y, x);
+  if (MP_CMP(y, <=, qq)) rc = 0;
+
   MP_DROP(x);
   MP_DROP(y);
-  if (!rc) return ("incorrect cofactor");
+  MP_DROP(nn);
+  MP_DROP(qq);
+  if (!rc) return ("incorrect or ambiguous cofactor");
 
   /* --- Check %$n G = O$% --- */
 
@@ -404,41 +405,82 @@ static const char *primecheck(const ec_info *ei, grand *gr)
   EC_DESTROY(&p);
   if (!rc) return ("incorrect group order");
 
-  /* --- Check that %$p^B \not\equiv 1 \pmod{r}$% for %$1 \le B < 20$% --- *
+  /* --- Check %$q^B \not\equiv 1 \pmod{r}$% for %$1 \le B < 20$% --- *
    *
-   * The spec says %$q$%, not %$p$%, but I think that's a misprint.
+   * Actually, give up if %$q^B \ge 2^{2000}$% because that's probably
+   * good enough for jazz.
    */
 
   x = MP_NEW;
-  mp_div(0, &x, f->m, ei->r);
-  i = 20;
-  while (i) {
-    if (MP_EQ(x, MP_ONE)) break;
+  mp_div(0, &x, q, ei->r);
+  n = mp_bits(ei->r) - 1;
+  for (i = 0, j = n; i < 20; i++, j += n) {
+    if (j >= 2000)
+      break;
+    if (MP_EQ(x, MP_ONE)) {
+      MP_DROP(x);
+      return("curve embedding degree too low");
+    }
     x = mp_mul(x, x, f->m);
     mp_div(0, &x, x, ei->r);
-    i--;
   }
   MP_DROP(x);
-  if (i) return ("curve is weak");
-
-  /* --- Check %$0 < h \le 4$% --- */
-
-  if (MP_CMP(ei->h, <, MP_ONE) || MP_CMP(ei->h, >, MP_FOUR))
-    return ("cofactor out of range");
 
   /* --- Done --- */
 
   return (0);
 }
 
-static const char *bincheck(const ec_info *ei, grand *gr)
+static int primeeltp(mp *x, field *f)
+  { return (!MP_NEGP(x) && MP_CMP(x, <, f->m)); }
+
+static const char *primecheck(const ec_info *ei, grand *gr)
 {
   ec_curve *c = ei->c;
   field *f = c->f;
-  int i;
   mp *x, *y;
-  ec p;
   int rc;
+  const char *err;
+
+  /* --- Check %$p$% is an odd prime --- */
+
+  if (!pgen_primep(f->m, gr)) return ("p not prime");
+
+  /* --- Check %$a$%, %$b$%, %$G_x$% and %$G_y$% are in %$[0, p)$% --- */
+
+  if (!primeeltp(c->a, f)) return ("a out of range");
+  if (!primeeltp(c->b, f)) return ("b out of range");
+  if (!primeeltp(ei->g.x, f)) return ("G_x out of range");
+  if (!primeeltp(ei->g.x, f)) return ("G_y out of range");
+
+  /* --- Check %$4 a^3 + 27 b^2 \not\equiv 0 \pmod{p}$% --- */
+
+  x = F_SQR(f, MP_NEW, c->a);
+  x = F_MUL(f, x, x, c->a);
+  x = F_QDL(f, x, x);
+  y = F_SQR(f, MP_NEW, c->b);
+  y = F_TPL(f, y, y);
+  y = F_TPL(f, y, y);
+  y = F_TPL(f, y, y);
+  x = F_ADD(f, x, x, y);
+  rc = F_ZEROP(f, x);
+  MP_DROP(x);
+  MP_DROP(y);
+  if (rc) return ("not an elliptic curve");
+
+  /* --- Now do the general checks --- */
+
+  err = gencheck(ei, gr, f->m);
+  return (err);
+}
+
+static const char *bincheck(const ec_info *ei, grand *gr)
+{
+  ec_curve *c = ei->c;
+  field *f = c->f;
+  mp *x;
+  int rc;
+  const char *err;
 
   /* --- Check that %$m$% is prime --- */
 
@@ -462,64 +504,12 @@ static const char *bincheck(const ec_info *ei, grand *gr)
 
   if (F_ZEROP(f, c->b)) return ("b is zero");
 
-  /* --- Check that %$G \in E$% --- */
-
-  if (EC_ATINF(&ei->g)) return ("generator at infinity");
-  if (ec_check(c, &ei->g)) return ("generator not on curve");
-
-  /* --- Check %$r$% is prime --- */
-
-  if (!pgen_primep(ei->r, gr)) return ("generator order not prime");
-
-  /* --- Check %$h = \lfloor (\sqrt{2^m} + 1)^2/r \rlfoor$% --- *
-   *
-   * This seems to work with the approximate-sqrt in the library, but might
-   * not be so good in some cases.  Throw in some extra significate figures
-   * for good measure.
-   */     
-
-  x = mp_lsl(MP_NEW, MP_ONE, f->nbits + 128);
-  x = mp_sqrt(x, x);
-  y = mp_lsl(MP_NEW, MP_ONE, 64);
-  x = mp_add(x, x, y);
-  x = mp_sqr(x, x);
-  mp_div(&x, 0, x, ei->r);
-  x = mp_lsr(x, x, 128);
-  rc = MP_EQ(x, ei->h);
-  MP_DROP(x);
-  MP_DROP(y);
-  if (!rc) return ("incorrect cofactor");
-
-  /* --- Check %$n G = O$% --- */
-
-  EC_CREATE(&p);
-  ec_mul(c, &p, &ei->g, ei->r);
-  rc = EC_ATINF(&p);
-  EC_DESTROY(&p);
-  if (!rc) return ("incorrect group order");
-
-  /* --- Check %$2^{m B} \not\equiv 1 \pmod{r}$% for %$1 \le B < 20$% --- */
+  /* --- Now do the general checks --- */
 
   x = mp_lsl(MP_NEW, MP_ONE, f->nbits);
-  mp_div(0, &x, x, ei->r);
-  i = 20;
-  while (i) {
-    if (MP_EQ(x, MP_ONE)) break;
-    x = mp_mul(x, x, f->m);
-    mp_div(0, &x, x, ei->r);
-    i--;
-  }
-  MP_DROP(x);
-  if (i) return ("curve is weak");
-
-  /* --- Check %$0 < h \le 4$% --- */
-
-  if (MP_CMP(ei->h, <, MP_ONE) || MP_CMP(ei->h, >, MP_FOUR))
-    return ("cofactor out of range");
-
-  /* --- Done --- */
-
-  return (0);
+  err = gencheck(ei, gr, x);
+  mp_drop(x);
+  return (err);
 }
 
 const char *ec_checkinfo(const ec_info *ei, grand *gr)
@@ -561,6 +551,7 @@ int main(int argc, char *argv[])
 	  ok = 0;
 	}
       }
+      assert(mparena_count(MPARENA_GLOBAL) == 0);
     }
   } else {
     fputs("checking standard curves:", stdout);
@@ -576,6 +567,7 @@ int main(int argc, char *argv[])
       } else
 	printf(" %s", ee->name);
       fflush(stdout);
+      assert(mparena_count(MPARENA_GLOBAL) == 0);
     }
     fputs(ok ? " ok\n" : " failed\n", stdout);
   }
diff --git a/tests/group b/tests/group
index bc954d0..dd09060 100644
--- a/tests/group
+++ b/tests/group
@@ -28,7 +28,7 @@ check {
        0xdb7c2abf62e35e668076bead2088, 0x659ef8ba043916eede8911702b22
        0x09487239995a5ee76b55f9c2f098, 0xa89ce5af8724c0a23e0e0ff77500
        0xdb7c2abf62e35e7628dfac6561c5 * 2
-  }" "incorrect cofactor";
+  }" "incorrect or ambiguous cofactor";
 
   # --- This one's oakley-155 ---