[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Fwd: Re: P1363: prudent fields]
We recommend to either drop or replace Group 3 (ECC) and Group 4 (ECC).
I asked Alfred to comment on the Weil Descent attack.
His reply is below.
Thanks,
Yuri Poeluev
====================================================================
Some further words on the message below which was originally
posted to the IEEE P1363 working group.
The paper "Solving Elliptic Curve Discrete Logarithm Problems
Using Weil Descent" shows that a special class of elliptic curves
over the finite field GF(2^155) that was previously considered
to be secure is in fact *not* secure. This special class of
elliptic curves is a small fraction of the set of all elliptic
curves over GF(2^155). In particular, the IPSEC Oakley curve
over GF(2^155) is *not* included in this special class, and so
is still considered to be secure against the Weil Descent attack.
However, it is our opinion that this provides strong evidence
for the weakness of *all* elliptic curves over GF(2^155), and
that it would be prudent to avoid such curves all together. It is
perfectly reasonably to expect that the Weil Descent attack could
be extended to succeed against a larger class of elliptic curves
over GF(2^155). More generally, we recommend that elliptic curves
over GF(2^n) where be n is composite be avoided, including elliptic
curves over GF(2^185).
Please note that the Weil descent attack fails against all
elliptic curves over GF(2^n) where n is a prime number in the
interval [160,600]. For example, the Weil descent attack fails
against elliptic curves over GF(2^163) and GF(2^283). For further
details about why the attack fails in these cases, see the paper
"Analysis of the Weil descent attack of Gaudry, Hess and Smart"
by Menezes and Qu in the Proceedings of the RSA 2001 conference.
Thus, our recommendation, is to:
1) Remove the IPSEC Oakley elliptic curves over GF(2^155) and
GF(2^185). These are also called Groups 3 and 4.
2) Retain the IPSEC Oakley elliptic curves over GF(2^163), GF(2^283),
GF(2^409) and GF(2^571). The are also called Groups 6, 7, 8, 9,
10, 11, 12 and 13.
We would like to emphasize that our recommendations are based
purely on security arguments.
Regards,
Alfred
Sandy Harris wrote:
>
> Forwarding this because it seems to raise some concerns for at least one of
> the IKE DH groups.
>
> Is this a serious worry? Should the IKE ECC groups be dropped or replaced?
>
> -------- Original Message --------
> Subject: Re: P1363: prudent fields
> Date: Sat, 23 Jun 2001 07:55:50 -0400 (EDT)
> From: Alfred John Menezes <ajmeneze@cacr.math.uwaterloo.ca>
> To: Richard Schroeppel <rcs@cs.arizona.edu>
> CC: Don Johnson <djohnson@certicom.com>,
> stds-p1363-discuss@majordomo.ieee.org,himanee <arjunkar@vsnl.net>
>
> ---------------------------------------------------------------------
> This is a stds-p1363-discuss broadcast. See the IEEE P1363 web page
> (http://grouper.ieee.org/groups/1363/) for more information. For list
> info, see http://grouper.ieee.org/groups/1363/WorkingGroup/maillist.html
> ---------------------------------------------------------------------
>
> On Fri, 22 Jun 2001, Richard Schroeppel wrote:
>
> > Take a look at Nigel Smart's recent talk at Eurocrypt 2001,
> > where he takes on the IPSEC Oakley curve over GF[2^155].
> > The attack reduces the estimated work for breaking the
> > curve from "10^11 years" to "over 10^10 years".
> >
> > [deleted]
> >
> >
> > Rich Schroeppel rcs@cs.arizona.edu
>
> You may be interested in the preprint" "Solving Elliptic Curve Discrete
> Logarithm Problems Using Weil Descent" by M. Jacobson, A. Menezes and
> A. Stein available from eprint.iacr.org (Report #2001/041). In this
> paper, we solve an instance of the ECDLP over the field GF(2^124)
> by using the Gaudry-Hess-Smart (GHS) Weil descent method to reduce
> the ECDLP to an instance of the HCDLP (hyperelliptic curve discrete
> logarithm problem) in a genus 31 hyperelliptic curve over GF(2^4),
> and then solving the latter problem using the Enge-Gaudry method.
> The elliptic curve chosen has order twice a prime, and so resists
> all other known attacks, including Pollard rho which would take about
> 2^62 steps. Our implementation of Enge-Gaudry solved the HCDLP instance
> in less time than it took to solve the 108-bit ECC2-108K Certicom
> challenge.
>
> We have also identified a class of elliptic curves over GF(2^155)
> for which the ECDLP can be efficiently reduced to the HCDLP in a genus
> 31 hyperelliptic curve over GF(2^5). These HCDLP instances can be solved
> in about 27,000 days on a single 1GHz Pentium III machine, or in 30
> days on a network of 1000 such machines. This is less time than it takes
> to perform exhaustive search for a 56-bit DES key. Note that Pollard
> rho on an elliptic curve over GF(2^155) whose order is twice a prime would
> take 2^77 steps which is considered infeasible.
>
> We did not actually solve an instance of the ECDLP for an elliptic curve
> over GF(2^155). Note however that the expected time of 27,000 days
> mentioned above is *exact* (see the paper for details). That is, we
> did not make wild estimates based on asymptotic running times which
> include O() or o(1) expressions as is done, for example, in estimating
> the running time of the Number Field Sieve for factoring large integers.
>
> We carefully point out that the above attack only applies to 2^32 of the
> 2^156 isomorphism classes of elliptic curves over GF(2^155). Thus, the
> GHS attack is virtually certain to fail against a randomly chosen curve
> over GF(2^155). However, given that there is much more work that remains
> to be done understanding Weil descent, and that there are many possible
> ways in which to extend the attack, my opinion is that elliptic curves
> over GF(2^155) should be altogether avoided.
>
> If you wish to learn more about Weil descent, see Nigel Smart's collection
> of papers at www.cs.bris.ac.uk/~nigel/weil_descent.html
>
> - Alfred