Subject: Elliptic-Curve Diffie-Hellman Key Exchange draft

From: Douglas Stebila <[email-masked]>
Date: Tue, 11 May 2004 23:12:54 +0100

I recently posted a draft to add support for the use of elliptic curve
cryptography in the form of Elliptic Curve Diffie-Hellman (ECDH) key
agreement to the exchange portion of the SSH Transport Layer protocol.

I would appreciate any feedback on the draft, which can be found at:

http://www.ietf.org/internet-drafts/draft-stebila-secsh-ecdh-01.txt

-- 

Douglas Stebila
Sun Microsystems Laboratories
Email: [email-masked]

---

From: [email-masked] (Niels Möller)
Date: 12 May 2004 08:40:06 +0200

> agreement to the exchange portion of the SSH Transport Layer protocol.

What's the current patent status on that area? Is it possible to
implement any cryptography on elliptic curves without getting a patent
license from the patent holders (certicom? Others?).

If not, I don't think there's much point in standardizing it, and I'm
not going to spend any time reading drafts about it. You could of
course still do it as a [email-masked] thing.

/Niels

---

From: der Mouse <[email-masked]>
Date: Wed, 12 May 2004 02:50:02 -0400 (EDT)

>> [...] Elliptic Curve Diffie-Hellman (ECDH) key agreement [...]
> implement any cryptography on elliptic curves without getting a
> patent license from the patent holders (certicom? Others?).

I haven't looked into it, but I'd guess there's a decent chance that
the patent in question is a USA patent only, in which case certainly
most of the world can benefit and I think standardizing it would be a
Good Thing.  (Aren't there jurisdictions that forbid algorithm patents
in practice as well as theory?)

Even if patents are held in many jurisdictions, the patent holder may
be willing to grant an irrevocable sublicensable license for use with
ssh; such things have happened before, and in the presence of such a
thing I see no reason not to standardize such a key-exchange method.

/~\ The ASCII				der Mouse
\ / Ribbon Campaign
 X  Against HTML	       [email-masked]
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

---

From: Douglas Stebila <[email-masked]>
Date: Thu, 13 May 2004 09:04:50 +0100

> license from the patent holders (certicom? Others?).

Yes, it is possible and it can be easily done.

ECC as an algorithm was introduced in 1985 by Neal Koblitz and Victor 
Miller with no patents over the algorithm.  Certicom does not hold an 
umbrella patent right over the algorithm. It only holds patents on some 
peripheral implementation or optimization techniques.

RSA has a FAQ about patents related to elliptic curve cryptography at
http://www.rsasecurity.com/rsalabs/faq/6-3-4.html.  Highlights include:

"Elliptic curve cryptosystems, as introduced in 1985 by Neal Koblitz
and Victor Miller, have no general patents, though some newer elliptic
curve algorithms and certain efficient implementation techniques may
be covered by patents. ..."
and
"... In all of these cases, it is the implementation technique that is
patented, not the prime or representation, and there are alternative,
compatible implementation techniques that are not covered by the
patents."

Elliptic curve crypto can be implemented using basic school book 
techniques which have no patent infringement concern. Simple standard 
techniques such as "window table lookup", "projective coordinate space", 
and "non-adjacent form wNAF" can be used for performance optimization 
with no patent concern. These techniques are school book techniques 
commonly used for RSA optimization and other multi-precision integer 
arithmetic computation.

Sun has contributed an ECC implementation to the OpenSSL project,
and has filed some patent applications related to elliptic curve
cryptography, but has explicitly indicated in the ECC code it
contributed to the OpenSSL project that "Sun does not intend to assert
its patent rights associated with the code that was delivered to the
OpenSSL project."  (See
http://research.sun.com/projects/crypto/FrequenlyAskedQuestions.html
for more information.)

It should be noted that elliptic curve cryptography implementations
can now be found in a number of open source projects (OpenSSL,
Mozilla's Netscape Security Services, Victor Shoup's NTL, Wei Dai's
Crypto++) and there are any number of standards on ECC.  In fact, at
present an ECC in TLS draft is going through IETF's TLS working group
and to my knowledge there are no concerns on patent issues.

I hope this helps dispel some of your concerns about the patent issues 
concerning ECC.

Regards,

Douglas Stebila

---

From: der Mouse <[email-masked]>
Date: Thu, 13 May 2004 04:47:33 -0400 (EDT)

> Sun has contributed an ECC implementation to the OpenSSL project, and
> has filed some patent applications related to elliptic curve
> contributed to the OpenSSL project that "Sun does not intend to
> assert its patent rights associated with the code that was delivered
> to the OpenSSL project."

This is notable more for what it does not say than for what it does
say.

In particular, it does not say that Sun will not use its patents, if
any, against similar code written by others (which locks everyone into
Sun's code's license) or against modified versions of Sun's code.

In fact, it does not say that Sun will not use its patents against
users of its own contributions in the future, only that it currently
does not intend to do so: it is not a commitment to anything.

If Sun really does want to DTRT with their patent, let them give a
royalty-free, sublicenseable license in perpetuity to, oh, say, Eric
Raymond, maybe, or Alan Cox, or someone else suitably trusted by the
open-source world.  Heck, let it give out half a dozen such licenses.

That is, let them _commit_ themselves.  Unless and until they do
something legally binding, I believe that statements of intent and so
forth are all very pretty-sounding, but cannot be trusted: normal
behaviour for corporations is what would be considered psychopathic for
an individual, and in particular, corporations' promises cannot be
trusted unless they are legally binding - and not always even then, but
that's about as strong as we'll get.

/~\ The ASCII				der Mouse
\ / Ribbon Campaign

---

From: [email-masked] (Niels Möller)
Date: 13 May 2004 10:57:49 +0200

> Yes, it is possible and it can be easily done.

[...]

> compatible implementation techniques that are not covered by the

Ok, that's good news.

> OpenSSL project."

I'm always uneasy about such promises. Ok, Sun may have the best
intentions now. But even if Sun's intentions don't change over time,
the patents could be sold off to other companies with different plans.

For example, in RFC 1170, Public Key Partners, owners of RSA and
Diffie-Hellman patents at the time, promised that "licenses to
practice RSA signatures will be available under reasonable terms and
conditions on a non- discriminatory basis". A few years later, the
company I worked for tried to actually buy RSA licenses from the
patent owner, the RSA company. They were unwilling to even negotiate
the price for such a license, they could sell us their software
toolkit BSAFE, but patent licenses were out of the question.

What patents do Sun have in this area? Searching for "Sun" and
"Elliptic" I find US patent 6721771,

: Method for efficient modular polynomial division in finite fields f(2 m)
: 
: Abstract
: 
: The present invention provides a method for performing an inversion
: and multiply in a single operation as a polynomial divide operation.
: As a result, the invention reduces the number of mathematical
: operations needed to perform point doubling and point addition
: operations. An elliptic curve cryptosystem using the present invention
: can be made to operate more efficiently using the present invention.
: An elliptic curve crypto-accelerator can be implemented using the
: present invention to dramatically enhance the performance of the
: elliptic curve cryptosystem. The invention uses five registers A, B,
: U, V, and M, to accomplish a polynomial divide operation. Four
: registers A, B, U, and V are initialized with values so that the
: registers maintain a number of invariant relationships. The registers
: store initial values a(t)=x(t), u(t)=y(t), b(t)=prime(t), and v(t)=0.
: Here the polynomials in registers A, U, B, and V are denoted as a(t),
: u(t), b(t), and v(t), respectively. Register M stores the irreducible
: polynomial prime(t). By applying a series of invariant operations to
: the registers, the register values are systematically reduced until
: registers A and B have a value of one. At that point, register U
: stores a value which represents y(t)/x(t) mod prime(t), solving the
: polynomial division.

and four published applications,

: 20030212729 Modular multiplier
: 
: 20030208518 Generic implementations of ellipitic [sic] curve
:             cryptography using partial reduction
: 
: 20030206629 Hardware accelerator for elliptic curve cryptography
: 
: 20030206628 Generic modular multiplier using partial reduction

Are these the relevant patents, or am I missing something? (There are
3811 patents assigned to "Sun Microsystems" in the uspto database, and
795 published patent applications, so I really can't make an exhaustive
search).

> I hope this helps dispel some of your concerns about the patent issues

Thanks for the information. I think I'd have to talk to a lawyer
before implementing any elliptic curve cryptography.

Regards,
/Niels

---

From: Douglas Stebila <[email-masked]>
Date: Thu, 13 May 2004 10:41:46 +0100

> the patents could be sold off to other companies with different plans.

In my previous email I should have included the actual legal covenant 
Sun made in contributing its code to the OpenSSL project:

  * The Elliptic Curve Public-Key Crypto Library (ECC Code) included
  * herein is developed by SUN MICROSYSTEMS, INC., and is contributed
  * to the OpenSSL project.
  *
  * The ECC Code is licensed pursuant to the OpenSSL open source
  * license provided below.
  *
  * In addition, Sun covenants to all licensees who provide a reciprocal
  * covenant with respect to their own patents if any, not to sue under
  * current and future patent claims necessarily infringed by the making,
  * using, practicing, selling, offering for sale and/or otherwise
  * disposing of the ECC Code as delivered hereunder (or portions 
thereof),
  * provided that such covenant shall not apply:
  *  1) for code that a licensee deletes from the ECC Code;
  *  2) separates from the ECC Code; or
  *  3) for infringements caused by:
  *       i) the modification of the ECC Code or
  *      ii) the combination of the ECC Code with other software or
  *          devices where such combination causes the infringement.

This license only appears in one file in OpenSSL, crypto/bn/bn_gf2m.c, 
which is the only file Sun contributed that contains technology covered 
under Sun patents (patent 6721771 as listed below).  Moreover, this 
code is #ifdef'ed out by default and replaced by a text-book 
implementation.  So it is certainly possible to have no Sun-patented 
technology in an ECC implementation (and default configurations of 
OpenSSL would have that status).  Other open-source ECC 
implementations, like that in NSS, have no Sun-patented technology in 
them.

[...]
> 795 published patent applications, so I really can't make an 
> exhaustive search).

To my knowledge, those are the relevant patents and applications, 
although there may be others filed in the future.  Note that Sun's 
covenant as listed above covers all "current and future patent claims" 
concerning the contributed code.

Douglas

---

From: Bill Sommerfeld <[email-masked]>
Date: Thu, 13 May 2004 09:49:35 -0400

[wearing my WG chair hat.]
Doug:

There is an old story about how penguins decide it's safe to go
swimming.  A large crowd of them mill about near the edge of the ice,
jostling each other until finally one of them falls in.  The remaining
ones then see if the first bird gets eaten by a shark -- if not, the
rest jump in..

With ECC, we're in the milling-about stage.  Sharks have been sighted,
though not very recently.  But the penguins are still nervous and
really would prefer that someone else go first....

This WG has limited time and energy.  For this to be adopted as a WG
item I'll need to hear from a community of implementors interested in
adopting it.

When possible, this WG (like much of the IETF as a whole) has
traditionally preferred functionaly equivalent unencumbered technology
even when it has lower performance (see DSS vs RSA).

The message I'm getting from WG members who have spoken up thus far is
that the uncertainties regarding the ECC IPR situation make it
uninteresting to them.

As others have suggested, the name@domain syntax for negotiable
parameters within ssh allows ample room for interoperable
experimentation.  If folks are interested in pursuing the use of ECC
within the ssh protocol, I suggest that they get together off-list
with Doug and figure out what they want to do, and report back to me
and/or the WG.

						- Bill

---

From: Damien Miller <[email-masked]>
Date: Fri, 14 May 2004 08:17:20 +1000

> that the uncertainties regarding the ECC IPR situation make it

OpenSSH has no desire to implement anything tainted by patents and we
strongly oppose any efforts to standardise encumbered methods in
IETF-published standards.

That goes for "free to use with strings attached" patent licenses too,
such as the code that Sun contributed to OpenSSL.

-d

---

From: Joseph Galbraith <[email-masked]>
Date: Thu, 13 May 2004 16:56:42 -0600

> commonly used for RSA optimization and other multi-precision integer 

Perhaps I'm missing something here?

Doesn't the above state that ECC is _not_ patent encumbered?
In other words, doesn't the above state that is possible
to create an ECC implementation that does not infringe on
any patents?

Or is it that people are concerned that the information provided
from RSA's faq may not be accurate?

I'm interested in seeing this work go forward.

Thanks,

- Joseph

---

From: Nils Larsch <[email-masked]>
Date: Wed, 19 May 2004 15:41:39 +0200

Hi Damien,

Damien Miller wrote:
...
> OpenSSH has no desire to implement anything tainted by patents and we

Does this mean that you don't like/want ecc, because there are various
patents in this area, although the basic cryptographic methods (in this
case) could be implemented without using patented algs ?

> IETF-published standards.

agree

Cheers,
Nils

---

From: Damien Miller <[email-masked]>
Date: Thu, 20 May 2004 07:52:49 +1000

> case) could be implemented without using patented algs ?

It means that we will avoid any area fraught with patents - the risk
that we will inadvertently stumble into a patented method is too great.
Especially given the fact that we do not have the time, resources or
desire to perform and tediously intepret patent searches before we
implement anything.

Right now, ECC is one of these areas.

-d

PS. Please direct followups off-list, this isn't on-topic.