Subject: Re: Reasons to include ECC to our charter

From: [email-masked] (Bodo Moeller)
Date: Sat, 1 Sep 2001 13:44:42 +0200 (CEST)

Peter Gutmann <[email-masked]>:
> Florian Weimer <[email-masked]>:

>> IIRC, not all ECC stuff is patented, only curves over GF(q), q even, which can
>> be implemented efficiently using two-valued logic.

> The rule of thumb for ECC is something like "ECC curves are divided into three
> groups, weak curves, inefficient curves, and curves patented by Certicom".

While Certicom certainly would like everybody to believe this, there
is few evidence that it is true.  Apart from patents on specific
cryptographic schemes, most patents relevant for ECC are on normal
bases for GF(2^m), which were originally thought to be useful because
they allow for very efficient implementation in custom-made hardware,
but turned out to be pretty irrelevant in practice.  (None of the
recommended curves in Certicom's recent SEC2 specification uses normal
bases.)

Curves over finite prime fields or curves over GF(2^m) when field
elements are represented using polynomial bases do not appear to have
such patent problems.  (Major manufacturers of cryptographic
coprocessors for smartcards implement these without worrying about
Certicom licences.)  For software implementations, they are not
automatically more time efficient than using conventional public key
cryptography in DSA-style groups, though.  The two important speed-up
techniques that can be used for the NIST recommended curves are due to
Jerry Solinas (NSA, not Certicom): All NIST recommended curves over
prime fields are based on specifically chosen primes (pseudo-Mersenne
primes) to allow for fast modular reduction; some of the NIST
recommended curves over GF(2^m) are Koblitz curves to allow for fast
point multiplication (see Jerry Solinas' CRYPTO '97 paper).
This makes ECC efficient in software without, as far as I am aware,
requiring any Certicom patent licences.

A caveat is that we do not know about additional pending patents that
Certicom may have.  Specifically, Certicom claims to have a patent
application covering point compression, and noone else really knows
what is in it.  So it may be prudent to avoid compressed point
representations.

---

From: Ben Laurie <[email-masked]>
Date: Mon, 03 Sep 2001 13:11:40 +0100

> what is in it.  So it may be prudent to avoid compressed point

It seems to me entirely unacceptable that we should even be discussing
I-Ds which relate to patents of unknown content. Certicom should either
reveal what they do or do not have pending, or go away.

Cheers,

Ben.

--
http://www.apache-ssl.org/ben.html

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: John W Noerenberg II <[email-masked]>
Date: Tue, 4 Sep 2001 08:49:04 -0700

>reveal what they do or do not have pending, or go away.

Clearly there is significant interest in ECC in this WG. 
Unfortunately, Ben is right, IPR issues are always troubling - there 
can be no mandatory requirements that have IPR restrictions.  Still, 
I have no desire to see this group ignore useful techniques, if it 
improves the utility of OpenPGP.   I'll contact some people at 
Certicom to see whether this can be definitively settled.  If there 
is no resolution soon, we'll have to drop discussion of it w/r/t to 
DRAFT status.

I may ultimately need some help from the IESG on this.  I'll keep you posted.
-- 

john noerenberg
[email-masked]
   --------------------------------------------------------------------------
   Peace of mind isn't at all superficial, really.  It's the whole thing.
   That which produces it is good maintenance; that which disturbs it
   is poor maintenance.
   -- Zen and the Art of Motorcycle Maintenance, Robert M. Pirsig, 1974
   --------------------------------------------------------------------------

---

From: Jon Callas <[email-masked]>
Date: Tue, 4 Sep 2001 14:06:05 -0700

I'm afraid that I don't see what the hand-wringing is over Certicom and
ECC. In the IETF, we forbid technologies with intellectual property
encumbrances from being *required*, but we don't forbid them from being
optional.

In the real world, any new public key system has an uphill battle to gain
any sort of acceptance. Look at the DSS/EG keys we have now. They were
invented for two reasons: (1) to address security problems in previous key
versions (2) to migrate from encumbered technologies to unencumbered ones.
Yet in some quarters of the user community, OpenPGP is looked on as if it
were fluoridation, for any number of reasons, none of which are really
relevant to this discussion. What *is* relevant is that if we put the ECC
parameters in OpenPGP, they probably won't be widely adopted, intellectual
property or not. So why not put them in, since they don't hurt anyone else?

Also as a real-world consideration, there's no need for any desktop or
laptop user to use ECC. Do I care if ECC means that a decrypt happens ten
times faster? Nope. The decrypt right now is happening in the blink of an
eye (like 50ms) or two. I'm not going to notice it taking place in a tenth
of an eye-blink. The delays I see in encrypted email are all related to UI
and layers and disk accesses and groveling through databases to *find* the
darned key. I might notice an improvement if I'm encrypting a message to a
dozen or more people, but maybe not. The size savings is utterly laughable.

ECC will matter only on constrained devices. If you want to make a OpenPGP
secured pager or SMS cell phone, then we're starting to see a reason for
ECC. Why not let these people do it interoperably?

I can understand some people's concern that the ECC proponents aren't
pushing things. But they did. About three years ago, some Certicom guys
made a presentation at an IETF meeting (Chicago?) and were basically pelted
with tomatoes and hooted out of the room. It was pretty embarrassing. If I
worked for Certicom, my reaction to this working group would be, "When you
want to talk rationally, email me."

We aren't going to make ECC a MUST or even a SHOULD. We will try very hard
to make the formats for ECC not favor anyone's implementation. We all know
that. So why don't we encourage some ECC experts to write an informational
RFC, do some interoperability testing, and make sure that it doesn't assume
a patented technology? And then if we like it, we can put it in a future
draft, or a follow-on document? We already have reserved PK algorithm
numbers for ECC and ECDSA.

	Jon

---

From: Ben Laurie <[email-masked]>
Date: Tue, 04 Sep 2001 22:49:54 +0100

Jon Callas wrote:
> a patented technology?

That's precisely the issue - how do we make sure it doesn't assume a
patented technology if we don't know what the patents are?

Why should this WG spend its time on stuff that may end up patented? By
all means, once its clear what we can and can't use, then let's proceed.
Until then, what's the point?

Cheers,

Ben.

---

From: "vedaal" <[email-masked]>
Date: Tue, 4 Sep 2001 17:56:55 -0400

- ----- Original Message ----- 
From: "Jon Callas" <[email-masked]>
To: <[email-masked]>
Sent: Tuesday, September 04, 2001 5:06 PM
Subject: Re: Reasons to include ECC to our charter

> eye (like 50ms) or two. I'm not going to notice it taking place in a
> tenth of an eye-blink. 

but that would be a very noticeable increase in speed  of encryption of
very large files,
or pgp disk encryption at the gb level of pgp disk size

agree fully with the principle of including it as an option even though it
is patented.

once the advantages become clear enough, someone will hopefully find a way
to produce a funtionally similar patentless alternative

vedaal

---

From: Jon Callas <[email-masked]>
Date: Tue, 4 Sep 2001 15:40:51 -0700

>to produce a funtionally similar patentless alternative

ECC does *not* affect the speed of large file encryption. Actually, it's
the opposite; it matters most for *small* files.

Remember, the bulk encryption is done with a block cipher. If you want it
to be fast, you use CAST, Twofish, or Rijndael. All of them are very fast.
You might spend 50ms with the public key packet, and then 1 or 2 ms with
the data.

The symmetric key is then wrapped in the public key encryption. For a small
file, you spend a lot of time with the wrapper and then pop open the data
packet. With a big file, the heavy cost of the public key operation is a
smaller fraction of the total cost, and ECC matters less. ECC is a win when
you have teeny processors sending small messages.

	Jon

---

From: Ben Laurie <[email-masked]>
Date: Tue, 04 Sep 2001 23:43:20 +0100

Jon Callas wrote:
> 
> At 10:49 PM +0100 9/4/01, Ben Laurie wrote:
> 
> If someone comes up with a layout that supports ECC generically, I'd say go
> with it.
> 
> I have no idea how to do that, myself. But if someone else does the work
> and convinces us that it's generic, I say go for it. That's also why I said
> to do an informational RFC, make a sample implementation, let someone hack
> up GPG to work with it, and we'll see.

What will we see? Clearly its possible to do - so what's interesting
about doing it before we can be sure we can use it?

Cheers,

Ben.

---

From: Jon Callas <[email-masked]>
Date: Tue, 4 Sep 2001 15:34:57 -0700

But all of this has a lot of ifs wrapped around it.

	Jon

---

From: John W Noerenberg II <[email-masked]>
Date: Wed, 5 Sep 2001 13:46:56 -0700

W/r/t Certicom's patents, I'm waiting to hear from a Simon 
Blake-Wilson at Certicom.  I don't know if he's a crypto guy, a 
patent guy,or something else entirely.  If someone knows him and has 
an email address, I'll pester him directly.

>up GPG to work with it, and we'll see.

Dominikus'  draft has proposals for changes.  Is the proposal 
generic?  Do the proposals conflict with 2440bis in any way?  Are 
there implementations (and do they interoperate)?  These are the 
issues, *if* we clear the IPR hurdle.
-- 

john noerenberg
[email-masked]

---

From: [email-masked] (Bodo Moeller)
Date: Mon, 10 Sep 2001 21:21:50 +0200 (CEST)

Jon Callas <[email-masked]>:

[...]
> the opposite; it matters most for *small* files.

You cannot expect elliptic curve based encryption to be faster than
RSA encryption.  Signing and decryption may be faster than for RSA or
DSA/ElGamal (but not necessarily when the platform is a PC or
workstations and if the modular exponentiation implementation is
reasonably well optimized), but it is hard to beat RSA public key
operations with small exponents.