From: [email-masked]
Date: Mon, 23 Feb 2004 12:25:14 -0500 (EST)

([email-masked] [192.94.214.100])
	by lists.tislabs.com (8.9.1/8.9.1) with ESMTP id LAA18216
	Mon, 23 Feb 2004 11:52:53 -0500 (EST)
Message-ID: <[email-masked]>
From: Michael Smith <[email-masked]>
To: "[email-masked]'" <[email-masked]>
Cc: "[email-masked]'" <[email-masked]>,
         Michael Smith
	 <[email-masked]>
Subject: Re: Fwd: Certicom IP Rights
Date: Mon, 23 Feb 2004 09:04:45 -0800
MIME-Version: 1.0
X-Mailer: Internet Mail Service (5.5.2655.55)
Content-Type: multipart/alternative;
	boundary="----_=_NextPart_001_01C3FA2E.E173E4D3"
Sender: [email-masked]
Precedence: bulk

This message is in MIME format. Since your mail reader does not understand
this format, some or all of this message may not be legible.

------_=_NextPart_001_01C3FA2E.E173E4D3
Content-Type: text/plain;
	charset="iso-8859-1"

>>  I have no idea how to find PCT Application #WO 00/01109, and so I did
not examine that.

See http://v3.espacenet.com/textdoc?DB=EPODOC&IDX=WO0001109

Mike Smith
iReady

-----Original Message-----
From: Scott Fluhrer [mailto:[email-masked]]
Sent: Sunday, February 22, 2004 11:18 PM
To: [email-masked]
Subject: Re: Fwd: Certicom IP Rights

I have examined the patents that Certicom has cited in their IP claim,
and list what I found below.  Now, of course, I am not a lawyer, and I
am not giving legal advice.

>To: [email-masked]
>From: Ian McKinnon <[email-masked]>
>Date: Fri, 31 Oct 2003 15:14:09 -0500
>
>
>Dear Mr. Housley:
>
>We wish to advise the IETF that Certicom believes it has rights under
>patents and/or pending applications that relate to RFC 3526 "More
Modular
>Exponential (MODP) Diffie-Hellman Groups for Internet Key Exchange
(IKE)",
>RFC 2409 "Internet Key Exchange",  Internet Draft
>(draft-ietf-ipsec-ikev2-11.txt) "Internet Key Exchange (IKEv2)
Protocol"
>and other IETF standards using MODP Groups.  The applicable patents
>include, but are not limited to, US Patents #5,933,504, #6,563,928,
>#6,078,667, #6,178,507, #6,195,433, US Patent Application Publications
>#2001/0014153, #2002/0090085, and PCT Application #WO 00/01109, and
>corresponding foreign applications.

Patent claims:
5,933,504:
6,563,928:
    (6,563,928 is an extended version of 5,933,504 with more claims and
so I address both together)
    Both patents are concerned with the Diffie-Hellman protocol and
detecting whether the public values received from the peer is within a
weak subgroup, that is, a value that would generate a relatively small
number of values for the shared secret.  The reasoning for this is that
an attacker may be able to introduce weak values for both exchanged
public values, and thus trick both sides into computing an easily
guessable shared secret.  Note that both IKEv1 and IKEv2 defend against
this attack in manners that differ from the method listed in the patent.
    That might sound reasonable, however, the MODP modulii that IKE uses
are all of the form (2*q+1) for q prime, and the generator used is a
quadratic residue to those modulii.  What this implies (in English) is
that these groups have only one small subgroup, namely the trivial
subgroup consisting of the single element {1}.  This means that the
patented operation is, in this case, comparing the public value you
received from the peer (KE payload) against the value 1, and rejecting
it if so.
    This brings up two obvious points:
- Is such an operation patentable?  Rejecting illegal values has been a
part of programming for quite a while.  Of course, I am not a lawyer.
(Also note that, if you are rejecting illegal values, you would also
want to reject the values 0, p-1, p, p+1, which do not appear to be a
part of the Certicom patents).
- None of the cited IETF documents (RFC3526, RFC2409, the draft IKEv2
document) mandates (or even mentions) such an operation.  It is thus
difficult to say why these documents, or an implementation based on
these documents, are in violation of either patent.

6,078,667:
    This patents a method of generating "unique and unpredictable values"
for use as a private key within a public key encryption system.
However, the cited IETF documents do not mandate a way for generating
the Diffie-Hellman exponents (and I cannot see any other way of applying
this patent).  As such, it is thus difficult to say why these documents
are in violation of this patent.

6,178,507:
    This patents a method of authentication involving elliptic curves.
As the claims are limited systems involving ECC, this is inapplicable to
the MODP-based protocols in question.

6,195,433:
    This patents the idea of using statistical tests (or 'predetermined
set of criteria') when generating private keys.  As the cited IETF
documents do not mandate any such tests, it is thus difficult to say why
these documents are in violation of this patent.

US Patent Application Publications
2001/0014153:
    This patents the idea of checking a generated public/private key pair
for validity.  As the cited IETF documents do not mandate any such
checks, it is difficult to say why these documents are in violation.

2002/0090085:
    This patents a method of generating a random number between 0 and q
(the order of a group).  The cited IETF documents do not mandate any
such method for generating the Diffie-Hellman exponents (and for MODP
groups, you generally don't generate exponents as large as the group
order), and thus it is difficult to say why these documents are in
violation.

I have no idea how to find PCT Application #WO 00/01109, and so I did
not examine that.

It is possible that WO 00/01109 or some of the uncited patents or non-US
patent applications may be applicable.  However, in every case I did
examine, I could not see how any of the IETF documents in question, or
an implementation based on such documents, would necessarily be in
violation.  I would encourage other people to scan through these
patents, and see if my assessments are accurate.  And again, for the
third time, I am not a lawyer, and please do not use my opinions as
legal advise.

-- 
scott

------_=_NextPart_001_01C3FA2E.E173E4D3
Content-Type: text/html;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV=3D"Content-Type" CONTENT=3D"text/html; =
charset=3Diso-8859-1">
<META NAME=3D"Generator" CONTENT=3D"MS Exchange Server version =
5.5.2656.60">
<TITLE>Re: Fwd: Certicom IP Rights</TITLE>
</HEAD>
<BODY>

<P><FONT SIZE=3D2>&gt;&gt; I have no idea how to find PCT Application =
#WO 00/01109, and so I did</FONT>
<BR><FONT SIZE=3D2>not examine that.</FONT>
</P>

<P><FONT SIZE=3D2>See <A =
HREF=3D"http://v3.espacenet.com/textdoc?DB=3DEPODOC&IDX=3DWO0001109" =
TARGET=3D"_blank">http://v3.espacenet.com/textdoc?DB=3DEPODOC&IDX=3DWO00=
01109</A></FONT>
</P>

<P><FONT SIZE=3D2>Mike Smith</FONT>
<BR><FONT SIZE=3D2>iReady</FONT>
</P>

<P><FONT SIZE=3D2>-----Original Message-----</FONT>
<BR><FONT SIZE=3D2>From: Scott Fluhrer [<A =
HREF=3D"mailto:[email-masked]">mailto:[email-masked]</A>]</FONT>=

<BR><FONT SIZE=3D2>Sent: Sunday, February 22, 2004 11:18 PM</FONT>
<BR><FONT SIZE=3D2>To: [email-masked]</FONT>
<BR><FONT SIZE=3D2>Subject: Re: Fwd: Certicom IP Rights</FONT>
</P>
<BR>

<P><FONT SIZE=3D2>I have examined the patents that Certicom has cited =
in their IP claim,</FONT>
<BR><FONT SIZE=3D2>and list what I found below.&nbsp; Now, of course, I =
am not a lawyer, and I</FONT>
<BR><FONT SIZE=3D2>am not giving legal advice.</FONT>
</P>

<P><FONT SIZE=3D2>&gt;To: [email-masked]</FONT>
<BR><FONT SIZE=3D2>&gt;From: Ian McKinnon =
&lt;[email-masked]&gt;</FONT>
<BR><FONT SIZE=3D2>&gt;Date: Fri, 31 Oct 2003 15:14:09 -0500</FONT>
<BR><FONT SIZE=3D2>&gt;</FONT>
<BR><FONT SIZE=3D2>&gt;</FONT>
<BR><FONT SIZE=3D2>&gt;Dear Mr. Housley:</FONT>
<BR><FONT SIZE=3D2>&gt;</FONT>
<BR><FONT SIZE=3D2>&gt;We wish to advise the IETF that Certicom =
believes it has rights under </FONT>
<BR><FONT SIZE=3D2>&gt;patents and/or pending applications that relate =
to RFC 3526 &quot;More</FONT>
<BR><FONT SIZE=3D2>Modular </FONT>
<BR><FONT SIZE=3D2>&gt;Exponential (MODP) Diffie-Hellman Groups for =
Internet Key Exchange</FONT>
<BR><FONT SIZE=3D2>(IKE)&quot;, </FONT>
<BR><FONT SIZE=3D2>&gt;RFC 2409 &quot;Internet Key =
Exchange&quot;,&nbsp; Internet Draft </FONT>
<BR><FONT SIZE=3D2>&gt;(draft-ietf-ipsec-ikev2-11.txt) &quot;Internet =
Key Exchange (IKEv2)</FONT>
<BR><FONT SIZE=3D2>Protocol&quot; </FONT>
<BR><FONT SIZE=3D2>&gt;and other IETF standards using MODP =
Groups.&nbsp; The applicable patents </FONT>
<BR><FONT SIZE=3D2>&gt;include, but are not limited to, US Patents =
#5,933,504, #6,563,928, </FONT>
<BR><FONT SIZE=3D2>&gt;#6,078,667, #6,178,507, #6,195,433, US Patent =
Application Publications </FONT>
<BR><FONT SIZE=3D2>&gt;#2001/0014153, #2002/0090085, and PCT =
Application #WO 00/01109, and </FONT>
<BR><FONT SIZE=3D2>&gt;corresponding foreign applications.</FONT>
</P>

<P><FONT SIZE=3D2>Patent claims:</FONT>
<BR><FONT SIZE=3D2>5,933,504:</FONT>
<BR><FONT SIZE=3D2>6,563,928:</FONT>
<BR><FONT SIZE=3D2>&nbsp;&nbsp; (6,563,928 is an extended version of =
5,933,504 with more claims and</FONT>
<BR><FONT SIZE=3D2>so I address both together)</FONT>
<BR><FONT SIZE=3D2>&nbsp;&nbsp; Both patents are concerned with the =
Diffie-Hellman protocol and</FONT>
<BR><FONT SIZE=3D2>detecting whether the public values received from =
the peer is within a</FONT>
<BR><FONT SIZE=3D2>weak subgroup, that is, a value that would generate =
a relatively small</FONT>
<BR><FONT SIZE=3D2>number of values for the shared secret.&nbsp; The =
reasoning for this is that</FONT>
<BR><FONT SIZE=3D2>an attacker may be able to introduce weak values for =
both exchanged</FONT>
<BR><FONT SIZE=3D2>public values, and thus trick both sides into =
computing an easily</FONT>
<BR><FONT SIZE=3D2>guessable shared secret.&nbsp; Note that both IKEv1 =
and IKEv2 defend against</FONT>
<BR><FONT SIZE=3D2>this attack in manners that differ from the method =
listed in the patent.</FONT>
<BR><FONT SIZE=3D2>&nbsp;&nbsp; That might sound reasonable, however, =
the MODP modulii that IKE uses</FONT>
<BR><FONT SIZE=3D2>are all of the form (2*q+1) for q prime, and the =
generator used is a</FONT>
<BR><FONT SIZE=3D2>quadratic residue to those modulii.&nbsp; What this =
implies (in English) is</FONT>
<BR><FONT SIZE=3D2>that these groups have only one small subgroup, =
namely the trivial</FONT>
<BR><FONT SIZE=3D2>subgroup consisting of the single element {1}.&nbsp; =
This means that the</FONT>
<BR><FONT SIZE=3D2>patented operation is, in this case, comparing the =
public value you</FONT>
<BR><FONT SIZE=3D2>received from the peer (KE payload) against the =
value 1, and rejecting</FONT>
<BR><FONT SIZE=3D2>it if so.</FONT>
<BR><FONT SIZE=3D2>&nbsp;&nbsp; This brings up two obvious =
points:</FONT>
<BR><FONT SIZE=3D2>- Is such an operation patentable?&nbsp; Rejecting =
illegal values has been a</FONT>
<BR><FONT SIZE=3D2>part of programming for quite a while.&nbsp; Of =
course, I am not a lawyer.</FONT>
<BR><FONT SIZE=3D2>(Also note that, if you are rejecting illegal =
values, you would also</FONT>
<BR><FONT SIZE=3D2>want to reject the values 0, p-1, p, p+1, which do =
not appear to be a</FONT>
<BR><FONT SIZE=3D2>part of the Certicom patents).</FONT>
<BR><FONT SIZE=3D2>- None of the cited IETF documents (RFC3526, =
RFC2409, the draft IKEv2</FONT>
<BR><FONT SIZE=3D2>document) mandates (or even mentions) such an =
operation.&nbsp; It is thus</FONT>
<BR><FONT SIZE=3D2>difficult to say why these documents, or an =
implementation based on</FONT>
<BR><FONT SIZE=3D2>these documents, are in violation of either =
patent.</FONT>
</P>

<P><FONT SIZE=3D2>6,078,667:</FONT>
<BR><FONT SIZE=3D2>&nbsp;&nbsp; This patents a method of generating =
&quot;unique and unpredictable values&quot;</FONT>
<BR><FONT SIZE=3D2>for use as a private key within a public key =
encryption system.</FONT>
<BR><FONT SIZE=3D2>However, the cited IETF documents do not mandate a =
way for generating</FONT>
<BR><FONT SIZE=3D2>the Diffie-Hellman exponents (and I cannot see any =
other way of applying</FONT>
<BR><FONT SIZE=3D2>this patent).&nbsp; As such, it is thus difficult to =
say why these documents</FONT>
<BR><FONT SIZE=3D2>are in violation of this patent.</FONT>
</P>

<P><FONT SIZE=3D2>6,178,507:</FONT>
<BR><FONT SIZE=3D2>&nbsp;&nbsp; This patents a method of authentication =
involving elliptic curves.</FONT>
<BR><FONT SIZE=3D2>As the claims are limited systems involving ECC, =
this is inapplicable to</FONT>
<BR><FONT SIZE=3D2>the MODP-based protocols in question.</FONT>
</P>

<P><FONT SIZE=3D2>6,195,433:</FONT>
<BR><FONT SIZE=3D2>&nbsp;&nbsp; This patents the idea of using =
statistical tests (or 'predetermined</FONT>
<BR><FONT SIZE=3D2>set of criteria') when generating private =
keys.&nbsp; As the cited IETF</FONT>
<BR><FONT SIZE=3D2>documents do not mandate any such tests, it is thus =
difficult to say why</FONT>
<BR><FONT SIZE=3D2>these documents are in violation of this =
patent.</FONT>
</P>

<P><FONT SIZE=3D2>US Patent Application Publications</FONT>
<BR><FONT SIZE=3D2>2001/0014153:</FONT>
<BR><FONT SIZE=3D2>&nbsp;&nbsp; This patents the idea of checking a =
generated public/private key pair</FONT>
<BR><FONT SIZE=3D2>for validity.&nbsp; As the cited IETF documents do =
not mandate any such</FONT>
<BR><FONT SIZE=3D2>checks, it is difficult to say why these documents =
are in violation.</FONT>
</P>

<P><FONT SIZE=3D2>2002/0090085:</FONT>
<BR><FONT SIZE=3D2>&nbsp;&nbsp; This patents a method of generating a =
random number between 0 and q</FONT>
<BR><FONT SIZE=3D2>(the order of a group).&nbsp; The cited IETF =
documents do not mandate any</FONT>
<BR><FONT SIZE=3D2>such method for generating the Diffie-Hellman =
exponents (and for MODP</FONT>
<BR><FONT SIZE=3D2>groups, you generally don't generate exponents as =
large as the group</FONT>
<BR><FONT SIZE=3D2>order), and thus it is difficult to say why these =
documents are in</FONT>
<BR><FONT SIZE=3D2>violation.</FONT>
</P>
<BR>

<P><FONT SIZE=3D2>I have no idea how to find PCT Application #WO =
00/01109, and so I did</FONT>
<BR><FONT SIZE=3D2>not examine that.</FONT>
</P>

<P><FONT SIZE=3D2>It is possible that WO 00/01109 or some of the =
uncited patents or non-US</FONT>
<BR><FONT SIZE=3D2>patent applications may be applicable.&nbsp; =
However, in every case I did</FONT>
<BR><FONT SIZE=3D2>examine, I could not see how any of the IETF =
documents in question, or</FONT>
<BR><FONT SIZE=3D2>an implementation based on such documents, would =
necessarily be in</FONT>
<BR><FONT SIZE=3D2>violation.&nbsp; I would encourage other people to =
scan through these</FONT>
<BR><FONT SIZE=3D2>patents, and see if my assessments are =
accurate.&nbsp; And again, for the</FONT>
<BR><FONT SIZE=3D2>third time, I am not a lawyer, and please do not use =
my opinions as</FONT>
<BR><FONT SIZE=3D2>legal advise.</FONT>
</P>
<BR>

<P><FONT SIZE=3D2>-- </FONT>
<BR><FONT SIZE=3D2>scott</FONT>
</P>

</BODY>
</HTML>
------_=_NextPart_001_01C3FA2E.E173E4D3--