[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Elliptic curves in IPSec [revisited]

Hello,

A few people have asked us to reiterate our concerns over the default
elliptic curves defined in IPSec.

Our concerns are basically about the security of the curves. So I asked
Simon Blake-Wilson for technical comments from our researchers on
the security aspect. Unfortunately not many of the references are
available in soft copy but I did hand out hard copies to interested
parties
at the Chicago IETF meeting.

We are also concerned that the default curves are not aligned with all
the other standards efforts in elliptic curve cryptography. The point
representation and point order used is not compliant with ANSI X9.62
and X9.63, IEEE P1363, ISO 15849, WAP and the like. It's a serious
mistake to
ignore the work of these other standards to align all elliptic curve
implementations. Our primary fear is that the implementation of
non-standard
techniques like those in IPSec will hinder the deployment of elliptic
curve
cryptography - much as the variety of different techniques used in RSA
standards like ISO 9796, PKCS 1, ANSI X9.31, etc seems to have caused
RSA problems. The non-standard techniques used in IPSec also mean
that the default curves cannot be used by ECDSA if it is later
integrated
into IPSec.

We have an implementation of IPSec with some alternative curves and
plan to propose them shortly.

Best regards,
Yuri Poeluev

-------------------------------------------------------------------------------------------------------

Default IPSec elliptic curves

IPSec defines two default elliptic curves. One over F2^155, and one over

F2^185. We are worried because these curves are defined over F2^m
with m composite. The security of curves over F2^m with m composite has
been questioned by many leading researchers. Our concerns have recently
been echoed by the US government: Miles Smid of NIST announced at the
ANSI X9F1 meeting in Ottawa in October that these curves will not be
supported in the upcoming FIPS elliptic curve standards because of
security concerns.

Concerns about the security of the curves stem from the same property
which
is exploited in implementations: the existence of non-trivial subfields
of F2^m
when m is composite. It is often claimed that these subfields do not
endow
elliptic curves with any additional structure that could be exploited,
but this is
untrue: for example the subfields endow the Weil descent of the curve
with rich
additional structure. In layman's terms the Weil descent looks at
algebraic
structures related to the elliptic curve by considering F2^m with m=nn'
as a
vector space of dimension n' over F2^n. From this angle the elliptic
curve
corresponds to an algebraic curve of dimension (at most) n' over F2^n.
For
example if the algebraic curve happens to be a hyperelliptic curve then
the
elliptic curve can now be broken using the Adleman-Huang algorithm.

Leading experts who have expressed concern about these curves include
Gerhard Frey [2], Alfred Menezes, and Scott Vanstone [6]. We take their
fears
particularly seriously since they have already broken other special
cases of
the elliptic curve logarithm problem...see [3] and [5]. Other experts
who have
publicly raised their concerns about these curves include Erik De Win,
Serge
Mister, Bart Preneel, and Mike Wiener [1],  Volker Mueller and Sachar
Paulus [7], and Claus Schnorr [8].

(The only concrete results on these curves so far are minor improvements
due
to Rob Gallant, Rob Lambert, and Scott Vanstone [4] and Mike Wiener and
Robert Zuccherato [9]. These results apply to elliptic curves over
F2^nn' which
are defined over F2^n.)

1. E. De Win, S. Mister, B. Preneel, and M. Wiener. On the performance
    of signature schemes based on elliptic curves. Proceedings of ANTS
'98.
    Springer-Verlag.
2. G. Frey. Invited presentation at Eurocrypt '97.
    (Copies of his slides were available at the conference.)
3. G. Frey and H.-G. Ruck. A remark concerning m-divisibility and the
    discrete logarithm problem in the divisor class group of curves.
Mathematics
    of Computation, number 62, volume 206, pages 865-874. 1994.
4. R. Gallant, R. Lambert, and S. Vanstone. Improving the parallelized
    Pollard lambda search on binary anomalous curves. To appear in
    Mathematics of Computation. Earlier version available from:
    http://cacr.math.uwaterloo.ca/
5. A. Menezes, T. Okamoto, and S. Vanstone. Reducing elliptic curve
    logarithms to logarithms in a finite field. IEEE Transactions on
Information
    Theory, number 39, pages 1639-1646, 1993.
6. A. Menezes and S. Vanstone. Comments at the IEEE P1363 meeting after
    Crypto '98.
7. V. Mueller and S. Paulus. On the generation of cryptographically
strong
    elliptic curves. Available from:
    http://www.informatik.th-darmstadt.de/TI/Mitarbeiter/vmueller.html
8. C. Schnorr. Rump session talk on breaking the Chor-Rivest knapsack
    system. Crypto '97.
9. M. Wiener and R. Zuccherato. Fast attacks on elliptic curve
cryptosystems.
    Proceedings of SAC '98. Springer-Verlag.