RE: Remove SHOULD for elliptic curve groups in IKEv2

["Hallam-Baker, Phillip" <pbaker@verisign.com>]

Title: RE: Remove SHOULD for elliptic curve groups in IKEv2

It is impossible to find out whether anyone have filled a claim in this area.

 

What we can and must do if ECC is to be used is to send Certicom an official letter of enquiry. If Certicom responds that they have not or they will license the patent RF the spec can proceed.

 

 

I am still waiting for someone to provide a good reason for making ECC more than a MAY. The key length argument is fatuous. Concern about brute force attack is not a good reason to use the longer key lengths, the additional encryption rounds are.

 

 

    Phill

Phillip Hallam-Baker FBCS C.Eng.
Principal Scientist
VeriSign Inc.
pbaker@verisign.com
781 245 6996 x227

-----Original Message-----
From: Mark Winstead [mailto:Mark.Winstead@NetOctave.com]
Sent: Thursday, March 14, 2002 9:53 AM
To: 'Andrey Jivsov'; Chris Trobridge; ipsec@lists.tislabs.com
Subject: RE: Remove SHOULD for elliptic curve groups in IKEv2

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");
>  > [
> ...
>
>

Phillip Hallam-Baker (E-mail).vcf