From 61a0271a91d0019def76775ed5d1285cfd3a2fe5 Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Tue, 20 Feb 2007 17:32:07 +0000 Subject: [PATCH] ec-info: Better checking of embedding degrees. Replace the rather cheap embedding degree check with a more sophisticated analysis. * Use the new key-size conversions from keysz-conv.c to determine a suitable embedding degree. * Following L. Hitt's paper, we ensure that no field with the same characteristic as the curve field is sufficiently small to cause concern; the old algorithm just checked extensions of the curve field, which can miss the smallest possible target field. * This involves a rather fancy algorithm which partially factors the curve order r - 1, making use of the new prime iteration code. Still to do on this: * Work out how to identify curves where pairings will help an attacker solve the DDH problem. * Provide a mechanism for passing parameters to checking functions. --- ec-info.c | 253 +++++++++++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 227 insertions(+), 26 deletions(-) diff --git a/ec-info.c b/ec-info.c index ebc05dc..6fcef88 100644 --- a/ec-info.c +++ b/ec-info.c @@ -29,14 +29,224 @@ /*----- Header files ------------------------------------------------------*/ +#include + #include "ec.h" #include "ectab.h" #include "gf.h" +#include "keysz.h" +#include "mpbarrett.h" #include "pgen.h" +#include "primeiter.h" #include "mprand.h" #include "mpint.h" #include "rabin.h" +/*----- Embedding degree checking -----------------------------------------* + * + * Let %$q = p^m$% be a prime power, and let %$E$% be an elliptic curve over + * %$\gf{q}$% with %$n = \#E(\gf{q}) = r h$% where %$r$% is prime. Then the + * Weil and Tate pairings can be used to map %$r$%-torsion points on + * %$E(\gf{q})$% onto the %$r$%-th roots of unity (i.e., the order-%$r$% + * subgroup) in an extension field %$\gf{p^k}$% of %$\gf{p}$% (%%\emph{not}%% + * of %$\gf{q}$% -- see [Hitt]). We call the smallest such %$k$% the + * %%\emph{embedding degree}%% of the curve %$E$%. The + * Menezes-Okamoto-Vanstone (MOV) attack solves the discrete log problem in + * %$E(\gf{q})$% by using the pairing and then applying index calculus to + * extract a discrete log in %$\gf{p^k}$%; obviously this only works if %$k$% + * is small enough. + * + * The usual check, suggested in, e.g., [P1363] or [SEC1], only covers + * extension fields %$\gf{q^\ell}$% of %$\gf{q}$%, which is fine when %$q$% + * is prime, but when we're dealing with binary fields it works less well. + * Indeed, as [Hitt] demonstrates, the embedding field can actually be + * %%\emph{smaller}%% than %$\gf{q}$%, and choosing %$m$% prime doesn't help + * (even though I previously thought it did). + * + * Define the %%\emph{embedding degree bound}%% %$B$% to be the smallest + * %$i$% such that discrete logs in %$\gf{p^i}$% are about as hard as in + * %$E(\gf{q})$%. + * + * The embedding group is a subgroup of the multiplicative group + * %$\gf{p^k}^*$% which contains %$p^k - 1$% elements; therefore we must have + * %$r \mid p^k - 1$%, or, equivalently, %$p^k \equiv 1 \pmod{r}$%. + * + * The recommended checking procedure, e.g., in [P1363], is just to check + * %$q^i \not\equiv 1 \pmod{r}$% for each %$0 < i < B$%. This is fast when + * you only consider extension fields of %$\gf{q}$%, since %$B$% is at most + * about 27. However, as noted above, this is inadequate when %$q$% is a + * prime power, and we must check all the extension fields of %$p$%. Now + * %$B$% can be about 15000, which is rather scarier -- we need a better + * algorithm. + * + * As noted, we must have %$p^k \equiv 1 \pmod{r}$%; but by minimality of + * %$k$%, we must have %$p^i \not\equiv 1 \pmod{r}$% for %$0 < i < k$%. + * Therefore %$p$% generates an order-%$k$% subgroup in %$\gf{r}^*$%, so we + * must have %$k \mid r - 1$%. + * + * Of course, factoring %$r - 1$% is a mug's game; but we're not interested + * in the complete factorization -- just the %$B$%-smooth portion. An + * algorithm suggests itself: + * + * 1. Extract the factors of %$r - 1$% which are less than %$B$%. + * + * 2. For each divisor %$d$% of %$r - 1$% less than %$B$% (which we can + * construct using this factorization), make sure that + * %$p^d \not\equiv 1 \pmod{r}$%. + * + * This takes a little while but not ever-so long. + * + * This is enough for cryptosystems based on the computational Diffie- + * Hellman problem to be secure. However, it's %%\emph{not}%% enough for the + * %%\emph{decisional}%% Diffie-Hellman problem to be hard; it appears we + * also need to hope that there aren't any suitable distortion maps with + * which one can solve the DDH problem. I don't know how to check for those + * at the moment. + * + * We'll take the subgroup order as indicative of the security level actually + * wanted. Then, to ensure security against the MOV attack, we must ensure + * that the embedding degree is sufficiently large that discrete logs in + * %$\gf{q^m}$% are at least as hard as discrete logs over the curve. + * + * We actually allow a small amount of slop in the conversions, in order to + * let people pick nice round numbers for their key lengths. + * + * References: + * + * [Hitt] L. Hitt, On an improved definition of embedding degree; + * http://eprint.iacr.org/2006/415 + * + * [P1363] IEEE 1363-2000: Standard Specifications for Public Key + * Cryptography; http://grouper.ieee.org/groups/1363/P1363/index.html + * + * [SEC1] SEC 1: Elliptic Curve Cryptography; + * http://www.secg.org/download/aid-385/sec1_final.pdf + */ + +/* --- @movcheck@ --- * + * + * Arguments: @mp *r@ = curve subgroup order + * @mp *p@ = field characteristic + * @unsigned long B@ = embedding degree bound + * + * Returns: Zero if OK, nonzero if an embedding was found. + * + * Use: Checks a curve for embeddings with degree less than the + * stated bound %$B$%. See above for explanation and a + * description of the algorithm. + */ + +static int movcheck(mp *r, mp *p, unsigned long B) +{ + mpmont mm; + mp *r1, *pp = MP_NEW, *t = MP_NEW, *u = MP_NEW, *v = MP_NEW, *tt; + struct factor { + unsigned long f; + unsigned c, e; + }; + DA_DECL(factor_v, struct factor); + factor_v fv = DA_INIT; + size_t nf; + struct factor *ff; + primeiter pi; + mp *BB; + unsigned long d, f; + unsigned i, j; + int rc = 0; + + /* --- Special case --- * + * + * If %$r = 2$% then (a) Montgomery reduction won't work, and (b) we have + * no security worth checking anyway. Otherwise we're guaranteed that + * %$r$% is a prime, so it must be odd. + */ + + if (MP_EQ(r, MP_TWO)) + return (0); + + /* --- First factor the %$B%-smooth portion of %$r - 1$% --- * + * + * We can generate prime numbers up to %$B$% efficiently, so trial division + * it is. + */ + + BB = mp_fromulong(MP_NEW, B); + r1 = mp_sub(MP_NEW, r, MP_ONE); + primeiter_create(&pi, 0); + for (;;) { + pp = primeiter_next(&pi, pp); + if (MP_CMP(pp, >, BB)) + break; + mp_div(&u, &v, r1, pp); + if (!MP_ZEROP(v)) + continue; + i = 0; + do { + tt = r1; r1 = u; u = tt; i++; + mp_div(&u, &v, r1, pp); + } while (MP_ZEROP(v)); + DA_ENSURE(&fv, 1); + DA_UNSAFE_EXTEND(&fv, 1); + DA_LAST(&fv).f = mp_toulong(pp); + DA_LAST(&fv).e = i; + DA_LAST(&fv).c = 0; + } + MP_DROP(BB); MP_DROP(pp); primeiter_destroy(&pi); + nf = DA_LEN(&fv); ff = DA(&fv); + + /* --- Now generate divisors of %$r - 1$% less than %$B$% --- * + * + * For each divisor %$d$%, check whether %$p^d \equiv 1 \pmod{r}$%. + */ + + mpmont_create(&mm, r); + u = mpmont_mul(&mm, u, p, mm.r2); + for (;;) { + + /* --- Construct the divisor --- */ + + d = 1; + for (i = 0; i < nf; i++) { + f = ff[i].f; j = ff[i].c; if (!j) continue; + for (;;) { + if (f >= (B + d - 1)/d) goto toobig; + if (j & 1) d *= f; + j >>= 1; if (!j) break; + f *= f; + } + } + v = mp_fromulong(v, d); + + /* --- Compute %$p^k \bmod r$% and check --- */ + + t = mpmont_expr(&mm, t, u, v); + if (MP_EQ(t, mm.r)) { + rc = -1; + break; + } + + /* --- Step the divisors along --- */ + + toobig: + for (i = 0; i < nf; i++) { + if (ff[i].c < ff[i].e) { + ff[i].c++; + goto more; + } + ff[i].c = 0; + } + break; + more:; + } + + /* --- Clear away the debris --- */ + + mpmont_destroy(&mm); + MP_DROP(t); MP_DROP(u); MP_DROP(v); MP_DROP(r1); + DA_DESTROY(&fv); + return (rc); +} + /*----- Main code ---------------------------------------------------------*/ /* --- @ec_curveparse@ --- * @@ -328,18 +538,21 @@ void ec_freeinfo(ec_info *ei) * Use: Checks an elliptic curve according to the rules in SEC1. */ -static const char *gencheck(const ec_info *ei, grand *gr, mp *q) +static const char *gencheck(const ec_info *ei, grand *gr, mp *q, mp *ch) { ec_curve *c = ei->c; - field *f = c->f; - int i, j, n; + unsigned long qmbits, rbits, cbits, B; mp *qq; mp *nn; mp *x, *y; ec p; int rc; - /* --- Check %$G \in E$% --- */ + /* --- Check curve isn't anomalous --- */ + + if (MP_EQ(ei->r, q)) return ("curve is anomalous"); + + /* --- Check %$G \in E \setminus \{ 0 \}$% --- */ if (EC_ATINF(&ei->g)) return ("generator at infinity"); if (ec_check(c, &ei->g)) return ("generator not on curve"); @@ -397,7 +610,7 @@ static const char *gencheck(const ec_info *ei, grand *gr, mp *q) MP_DROP(qq); if (!rc) return ("incorrect or ambiguous cofactor"); - /* --- Check %$n G = O$% --- */ + /* --- Check %$n G = 0$% --- */ EC_CREATE(&p); ec_mul(c, &p, &ei->g, ei->r); @@ -405,26 +618,14 @@ static const char *gencheck(const ec_info *ei, grand *gr, mp *q) EC_DESTROY(&p); if (!rc) return ("incorrect group order"); - /* --- Check %$q^B \not\equiv 1 \pmod{r}$% for %$1 \le B < 20$% --- * - * - * Actually, give up if %$q^B \ge 2^{2000}$% because that's probably - * good enough for jazz. - */ + /* --- Check the embedding degree --- */ - x = MP_NEW; - 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); - } - MP_DROP(x); + rbits = mp_bits(ei->r); + cbits = mp_bits(ch); + qmbits = keysz_todl(keysz_fromec(rbits * 7/8)); + B = (qmbits + cbits - 1)/cbits; + if (movcheck(ei->r, ch, B)) + return("curve embedding degree too low"); /* --- Done --- */ @@ -470,7 +671,7 @@ static const char *primecheck(const ec_info *ei, grand *gr) /* --- Now do the general checks --- */ - err = gencheck(ei, gr, f->m); + err = gencheck(ei, gr, f->m, f->m); return (err); } @@ -507,7 +708,7 @@ static const char *bincheck(const ec_info *ei, grand *gr) /* --- Now do the general checks --- */ x = mp_lsl(MP_NEW, MP_ONE, f->nbits); - err = gencheck(ei, gr, x); + err = gencheck(ei, gr, x, MP_TWO); mp_drop(x); return (err); } -- 2.11.0