[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Fwd: Re: P1363: prudent fields]
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