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

Re: Remove SHOULD for elliptic curve groups in IKEv2



Through P1363, Certicom's intentions to patent point compression have
been public for some time.  The observation that point compression
is possible has been around for some years, there are several ways to
choose the meaning of the bit that encodes the second coordinate.
It's not at all clear that IKE's method infringes Certicom's, to my
actual knowledge.

I don't understand the claim about the co-factor.  How is it that
you claim the computation cannot be done with it?

Hilarie

Mark Winstead wrote:

> That patent statement of Certicom was written in may, 1999. There is one 
> patent granted to Certicom on a mathod to avoid the small subgroup 
> attack in August 1999, but no point compression method or other subgroup 
> attack related one listed on the U.S. government's database (supposedly 
> complete to March 12th 2002). What makes you think that the IKE 
> implementation is using one of Certicom's claimed patent applications?
> 
> I don't think that lowest order bit of x/y (y/x?) is patentable if it 
> isn't already patented. Hasn't that technique been around since the 80s?
> 
> 
> 
>  > -----Original Message-----
>  > From: Andrey Jivsov [mailto:andrey@brainhub.org]
>  > Sent: Wednesday, March 13, 2002 6:42 PM
>  > To: Chris Trobridge; ipsec@lists.tislabs.com
>  > Subject: Re: Remove SHOULD for elliptic curve groups in IKEv2
>  >
>  >
>  > After playing 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.
>  >
>  > The issue here is not a performance, but the fact that IKE
>  > implementation
>  > must use some of following techniques in order to interpret
>  > data in the KE
>  > payload or create the same g^xy:
>  >
>  >      1) point compression, such that only the lowest bit of polynomial
>  > representation of x/y is transmitted
>  >      2) g^xyc (or xyc * G in EC notation), where c is
>  > "cofactor", is used
>  > instead of g^xy
>  >
>  > 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 P1363 mailing list. Similar
>  > compression
>  > should be made mandatory.
>  > For 2) one will use DH without cofactor multiplication (i.e.,
>  > the shared
>  > secret will be exactly g^xy), but use other methods to verify
>  > g^x received
>  > from the peer.
>  >
>  > I believe that abovementioned draft should not assume
>  > patented formats on
>  > the wire and in g^xy, instead it should specify patent-free
>  > alternatives.
>  > ( This issue has nothing to do with internal representation
>  > of EC points or
>  > performance. )
>  >
>  > ----- 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.
>  >  >
>  >  > ]       ON HUMILITY: to err is human. To moo, bovine.           |
>  > firewalls
>  >  > [
>  >  > ]   Michael Richardson, Sandelman Software Works, Ottawa,
>  > ON    |net
>  >  > architect[
>  >  > ] mcr@sandelman.ottawa.on.ca
>  > http://www.sandelman.ottawa.on.ca/ |device
>  >  > driver[
>  >  > ] panic("Just another NetBSD/notebook using, kernel
>  > hacking, security
>  > guy");
>  >  > [
>  > ...
>  >
>  >
>