Re: Remove SHOULD for elliptic curve groups in IKEv2

["Andrey Jivsov" <andrey@brainhub.org>]

After experiments with one of IKE gateways which implements ECC groups from
draft-ietf-ipsec-ike-ecc-groups-03.txt I found that there appear to be no
way to interoperate with this box without violating some of patents.

In order to interoperate with that vendor IKE implementation must use some
of following techniques in order to process data in the KE payload or
generate the same g^xy:

     1) point compression, such that only the lowest bit of polynomial
representation of x/y is transmitted
     2) xyc * G is used in place of of g^xy, where c is "cofactor"

These techniques are likely to be patented in applications #2 and #5
respectively, listed on the last page of
     http://www.secg.org/collateral/certicom_secg_patent.pdf:

     > 2.  Methods for point compression.
     ...
     > 5.  Methods to avoid the small subgroup attack.

It is possible to avoid patented methods.

For 1) there exist more efficient techniques, such as the one proposed by
Roger Schlafly on Nov 12 2001 to the P1363 mailing list. Similar compression
method should be made mandatory.
For 2) one will use DH without cofactor multiplication (i.e., the shared
secret will be exactly g^xy) and use other methods to verify g^x received
from the peer.

It would be beneficial if abovementioned draft had clearly specified
patent-free point compression and g^xy.

----- Original Message -----
From: "Chris Trobridge" <CTrobridge@baltimore.com>
To: <ipsec@lists.tislabs.com>
Sent: Wednesday, March 13, 2002 4:27 AM
Subject: RE: Remove SHOULD for elliptic curve groups in IKEv2


 > Certicom have been very active in this area.
 >
 > They have a document stating their patents/applications:
 >
 > http://www.secg.org/collateral/certicom_secg_patent.pdf
 >
 > This is better than what they used to say which was along the lines of "we
 > have patents in this area that you might infringe but if you buy a licence
 > from us you'll be ok".
 >
 > Their earliest patent listed above was in 1988 and covers multiplication
 > using base-normal form.  There are other patents (by others) covering
 > multiplication with normal basis representation.
 >
 > I did a (general) patent search on "Elliptic Curve" and "Cryptography" and
 > that came up with 114 patents in the last 6 years.  Quite apart from
various
 > acceleration patents, a number of signature methods are also covered.
 >
 > Again, I am not experienced in interpreting patents either.
 >
 > Chris
 >
 > -----Original Message-----
 > From: Michael Richardson [mailto:mcr@sandelman.ottawa.on.ca]
 > Sent: 12 March 2002 20:16
 > To: ipsec@lists.tislabs.com
 > Cc: Mark.Winstead@NetOctave.com; Paul Koning
 > Subject: Re: Remove SHOULD for elliptic curve groups in IKEv2
 >
 >
 >
 > >>>>> "Paul" == Paul Koning <pkoning@equallogic.com> writes:
 >     Paul> One data point:
 >
 >     Paul> Even before AES was nailed down, there were chip vendors
 > announcing
 >     Paul> hardware acceleration support for AES.
 >
 >     Paul> On the other hand, years after EC came out, hardware accelerator
 >     Paul> support for it is still somewhere between very rare and
 > nonexistent.
 >
 >     Paul> I'm inclined to view these data as an indication of the interest
 > level
 >     Paul> in EC; it supports Paul Hoffman's suggestion.
 >
 >   My understanding is that there are specific patents (less than a decade
 > old) on hardware accelerated EC. I do not recall who owed them, wasn't
HiFn
 > or RSA/Verisign though.
 >
...