>> 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:sfluhrer@cisco.com]
Sent: Sunday, February 22, 2004 11:18 PM
To: ipsec@lists.tislabs.com
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: housley@vigilsec.com
>From: Ian McKinnon <IMcKinnon@certicom.com>
>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