RE: Rivest Patent

Eric Cordian [mailto:emc@wire.insync.net] writes:
>> So we can't use the rotate instruction with a data-dependent shift 
>> count in a block encryption algorithm without a license from Ron?

"Harvey Rook (Exchange)" <hrook@exchange.microsoft.com> writes:
> It's a little bit more complicated than that. RC-6, which also uses data
> dependant rotations is patent free.

It's a little bit more complicated than that.  RC6 will be available
without licensing charges to anybody if it's tapped as the official
winner of the AES bakeoff.  If it's not selected, then it's my
understanding that RSADSI (Security Dynamics?) may choose to require
payment for licensing -- I assume based on the RC5 patent.  The current
understanding is that AES candidates sign over their rights only if they
are selected.  Several candidates have been explicitly put into the
public domain in advance of the selection process; RC6 is not one of these.

Please correct me if it's more complicated than <this>.
-- 
	Jim Gillogly
	Trewesday, 23 Blotmath S.R. 1998, 23:38
	12.19.5.12.6, 11 Cimi 19 Zac, Third Lord of Night

When the always well-informed John Young reported that the US Patent Office
had issued MIT Prof. Ron Rivest US Patent 5835600 for a "Block encryption
algorithm with data-dependent rotations," Eric Cordian
<emc@wire.insync.net> growled:

> So we can't use the rotate instruction with a data-dependent shift
> count in a block encryption algorithm without a license from Ron?
>
> Foo on that.

Really, Mr. Cordian, you should read a patent before you foo at it. See:
http://jya.com/rivest111098.htm

This particular patent is probably less than it first appears to be.

When a patent is marked as "divisional" of a specific application, it means
it has been broken off and separated from a prior patent application.

In this case, when Rivest sought a patent for RC5, a block cipher which is
notable for the elegant simplicity that has become Ron's trademark style,
the Patent Examiner suggested that he refile the application in two parts:
one on the encryption method, and a second on the key-schedule structure.

The patent on the RC5 encryption method, US5724428 -- which has generally
been referred to as the RC5 patent -- was issued March 3, 1998, with the
same title ("Block encryption algorithm with data-dependent rotations") and
an identical Abstract to this more recent patent, US5835600, which was
issued Nov. 10.  See:
http://www.patents.ibm.com/details?pn=US05724428__&language=en

This latest patent, US5835600, only covers the design of the key schedule
used in RC5 (and RC6). Period.  The data-dependent rotation claims were in
the earlier RC5 patent.

Even Ron's initial RC5 patent, however, referred to data-dependent
rotations only in the context that they are used in RC5. It surely is not
any universal IP claim.

Among the relevant prior work Rivest cited in his original application (and
US5724428) was Wolfram Becker's work for IBM in the 1970s -- patented in
US4157454 -- which seems to rely on data-dependent rotations too. Note that
the Patent Examiners determined that Becker's work did not impinge upon or
otherwise disqualify Rivest's specific RC5 claims.

(I wouldn't hazard a guess as to whether RSA's RC5 patent covers IBM's MARS
algorithm, as some have suggested, just because MARS also uses
data-dependent rotations. Some on this list may be competent to dice the
issues that fine but I am not.)

Mr. Cordian ventured an additional opinion or two:

|>As you may have guessed, I'm not a fan of permitting software to be
|>patented.  Particularly things like RSA for which obvious prior art
|>existed....

Eric Michael Cordian is a Persistant Network Nym which has been around for
quite a while. It recently caught to eye of some crypto mavens on these
lists when Cordian revealed himself as both a pseudonym and a collective
identity.

E.M. Cordian has been the net persona behind which a group of
self-described cryptographic professionals have raised $7,500 in donations
to underwrite the "DES Analytic Crack Project," an <ahem> ambitious effort
"to develop ANSI C code which will break DES in under one day on a $5k
workstation."

See: http://www.cyberspace.org/~enoch/crakfaq.html

Now, it seems to me reasonable, albiet academic, to argue whether or not
software should be patentable.  It is also certainly reasonable to argue
whether or not cryptographic algorithms should be patentable.

On the other hand, it seems to me unreasonable, willfully ill-informed,
and/or  malovelent to declare -- in the face of several judicial rulings
which have firmly ratified the RSA PKC patent -- that  "prior art" exists
which should have invalidated that patent.  Horseshit!

Stanford and Cylink couldn't find it, despite a highly motivated and
well-funded search. They doubtless would have paid you handsomely for your
evidence and definitive testimony, but you missed your chance.

Now you'll -- collectively, Sirs? -- just have to settle for being another
cadre in the crowd that hoots and sneers at Ron Rivest whenever he comes up
with something new which significantly enhances our cryptographic arsenal
(and has the gall to patent it or otherwise claim IP ownership.)

Seems like a demeaning role for a group of professionals which claim to
collectively have "decades of practical experience in successfully
implementing the most complex computer algorithms."

	Suerte,

		_Vin

PS. Regarding the debate about whether RC6 will be freely available, my
understanding (as a consulant to RSA) is that Jim Gillogly has it right.

If RC6 is selected as the American AES, RSA (now a subsidary of Security
Dynamics) will relinquish all patent rights and royalty expectations.  If
RC6 is not selected as the AES -- and given the decades of conflict,
antagonism, and competition between the spooks of the NSA and RSA, RC6 is
surely a remote long shot -- RSA will offer it as a commercial product.

The two RC5 patents appear to cover RC6. The AES evaluation process will
provide an invaluable high-stress testbed for Rivest's innovative use of
data-dependent rotations.  When the AES is chosen by the NSA -- whichever
algorithm is finally chosen -- the cryptographic community will know a lot
more about the security and viability of this particular Rivest design.
Then we can start wondering what Rivest will come up with for Ron's Code
(RC) 7.

-----
      Vin McLellan + The Privacy Guild + <vin@shore.net>
  53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548
                         -- <@><@> --

Vin writes:

> On the other hand, it seems to me unreasonable, willfully ill-informed,
> and/or  malovelent to declare -- in the face of several judicial rulings
> which have firmly ratified the RSA PKC patent -- that  "prior art" exists
> which should have invalidated that patent.  Horseshit!

Judicial rulings notwithstanding, a description of that which is now known
as RSA Public Key Cryptography was published in a book of algorithms which
pre-dated by quite a few years its patenting and commercial promotion by
the current patent holders.  That exponentiation modulo the product of two
distinct odd primes was not easily reversable given knowlege of the
modulus and the exponent was hardly a closely guarded mathematical secret,
even decades before this fact was employed by cryptographers. 

All of this was extensively discussed here on Cypherpunks back when
disputes over the RSA patent were newsworthy, and I suggest you grep the
archives for more specifics. 

My point was that the US is one of the few countries to permit the
patenting of abstract mathematics, albeit it under the guise of some
practical "method and apparatus" jargon.  The fact that the patent
couldn't be successfully challenged even though its mathematical
underpinnings were well known years prior reflects badly only upon the
notion of mathematical patents, and hardly refutes the facts in evidence. 

> Stanford and Cylink couldn't find it, despite a highly motivated and
> well-funded search. They doubtless would have paid you handsomely for
> your evidence and definitive testimony, but you missed your chance. 

Again, (patent not invalidated) != (no prior art)

But then, I'm sure you knew that. 

> Now you'll -- collectively, Sirs? -- just have to settle for being
> another cadre in the crowd that hoots and sneers at Ron Rivest whenever
> he comes up with something new which significantly enhances our
> cryptographic arsenal (and has the gall to patent it or otherwise claim
> IP ownership.) 

One "foo on that" at the notion of patenting mathematics in general, and
of patenting ciphers employing data dependent rotates in particular,
hardly constitutes hooting and sneering directed at Ron Rivest, whose work
is greatly respected in the cryptographic community.

But then, I'm sure you knew that too. 

I'm also pleased to report that the DES Analytic Crack Project is plodding
along towards its goal of an algebraic inverse to DES. 

While the project will generate $10k in sponsorship money when fully
subscribed, we have started it off with a much smaller number of sponsors,
as quite a few potential sponsors have indicated an interest in seeing
some preliminary research results prior to remitting funds. 

Since we are not hurting for funds at the moment, we have decided to
devote 100% of our effort to the project at this time, and will probably
not have a further "pledge break" until 8-round DES bites the dust. Then
we will try to get the project fully subscribed, do the 16-round crack,
and write up the final report. 

-- 
Sponsor the DES Analytic Crack Project
http://www.cyberspace.org/~enoch/crakfaq.html

Vin McLellan <vin@shore.net> wrote:

>> Now, it seems to me reasonable, albiet academic, to argue whether or not
>>software
>> should be patentable.  It is also certainly reasonable to argue whether
>>or not
>> cryptographic algorithms should be patentable.
>>
>> On the other hand, it seems to me unreasonable, willfully ill-informed,
>> and/or  malovelent to declare -- in the face of several judicial rulings
>> which have firmly ratified the RSA PKC patent -- that  "prior art" exists
>> which should have invalidated that patent.

	Eric Michael Cordian <emc@wire.insync.net> -- the "Nym" or
pseudonym for someone who says he is a group of people, and who has been
collecting  $500 donations from folks willing to help the Cordian Group
sponsor an algebraic attack on the DES (See the "DES Analytic Crack
Project" at http://www.cyberspace.org/~enoch/crakfaq.html) -- spun off an
individual voice to respond:

>Judicial rulings notwithstanding, a description of that which is now known
>as RSA Public Key Cryptography was published in a book of algorithms which
>pre-dated by quite a few years its patenting and commercial promotion by
>the current patent holders.

	When I read Cordian's claim, I asked Ron Rivest if he had ever
heard of such a thing.  Prof. Rivest was curious, but said was all news to
him. To the best of his knowledge, he said, there had never been anything
like a description of the RSA public key cryptosystem published prior to
the paper he, Adi Shamir and Len Adelman, published in April, 1977: "On
Digital Signatures and Public Key Cryptosystems."

	Last year, former Cylink attorney Pat Flinn suggested that one
possible  challenge to the RSA patent might be to highlight the similarity
between the RSA PKC and the Pohlig-Hellman crypto system, invented at
Stanford University in 1975. For an invention to be patentable, of course,
it must be useful, novel, and non-obvious. Flinn argued that the
reformulation of the Pohlig-Hellman algorithm with a modulus that was the
product of two prime numbers was a potentially "obvious" enhancement.

	But not even Pat Flinn claimed to know anything about a
"description of that which is now known as RSA Public Key Cryptography"
being published somewhere -- anywhere -- years before the RSA cryptosystem
was invented and named at MIT.

	As Matt Blaze pointed out, there have also been recent reports
about secret research into public-key cryptosystems by cryptographers
within the British cryptographic service, GCHQ, in the early 1970s.
According to former NSA Director Bobby Ray Inman, the NSA was working on
PKC even earlier. Until last December, when the Brits released a GCHQ
historical paper written by John Ellis in 1987, there had been little or no
unclassified information available about this pioneering research. See:
http://www.nytimes.com/library/cyber/week/122497encrypt.html   We still
don't know what was done at the NSA, by whom, and when. Secret government
R&D, however, is not really relevant to intellectual property claims on
public key crypto. Full publication of the details of an invention -- in
exchange for a limited-duration property right -- is really at the heart of
the patent process.  Except in extraordinary circumstances, the NSA doesn't
play in this league.

	In the commecial world, on the other hand, it's hard to think of
priceless information being kept secret (particularly when it is only worth
something if it is on a bargaining table.) In the lawsuits between
Stanford/Cylink and RSA Data Security over the scope and validity of the
Stanford and RSA patents, "obvious prior art" -- certainly evidence that
the RSA cryptosystem had been published by someone other than the MIT
inventors before 1977 -- would have been worth tens of millions of dollars.
It might have been potentially worth that much to Pat Flinn himself.

	Since I knew that no mention of such a document or book had ever
emerged in Cylink's multi-year campaign to invalidate the RSA patent, it
seemed a safe bet to challenge Mr. Cordian directly.

	"There was no such book. Cordian's statement is just not true," I
declared.

	Mr. Cordian replied with dry scorn:

>>> Only a complete moron would place himself in the position of trying to
>>> prove such an all-encompassing negative.

	(Not light of hand, our Mr. Cordian.  Yet not all negative
propositions are impossible to prove.  For the rest, I'll leave it to the
List and other readers to decide which of us deserves a Dunce Cap for
placing himself in an untenable position.)

	Mr. Cordian didn't press his initial argument that a cryptographic
algorithm, even if embodied in a pseudo-mechanical device or process,
doesn't deserve patent protection. Since 1981, the US Courts have allowed a
process which includes a mathematical algorithm to be patented  -- if the
algorithm is merely part of an otherwise patentable process. For the RSA
cryptosystem, this seems reasonably straightforward to those without a
religious bias.

	To quote the Federal Court in the Schlafly Case, affirmed by the
Circuit Court:

"Taken as a whole, the RSA patent is entitled to patent protection. The
claims of the patent make use of known structures, a communications
channel, an encoding device and a decoding device, to produce a practical
invention, i.e. a means for securely transmitting messages across an
insecure line. The messages are comprised of word signals that are
transformed from one state, plaintext, to another state, ciphertext, by the
patented invention. The word signals are then transmitted across an
insecure line and transformed by the decoding device from ciphertext into
plaintext. As such, the claimed invention is not merely a disembodied
mathematical concept but rather a specific machine designed to transform
and transmit word signals."

	(I was never impressed by the absolutist argument against patents
on math-based processes. Mr. Cordian summarized this POV: "The fact that
the [RSA] patent couldn't be successfully challenged even though its
mathematical underpinnings were well known years prior reflects badly only
upon the notion of mathematical patents, and hardly refutes the facts in
evidence." By that logic, it seems to me, a basic knowledge of physics
could invalidate almost all patents for mechanical inventions.)

	The second traditional attack upon the RSA public key cryptosystem,
noted above, is the charge that it was "obvious" or insufficiently novel.
Section 103 of the US Patent Act provides that a patent is invalid "if the
differences between the subject matter sought to be patented and the prior
art are such that the subject matter as a whole would have been obvious at
the time the invention was made to a person having ordinary skill in the
art...."

	If, as Mr. Cordian claimed, there was "a description of that which
is now known as RSA Public Key Cryptography" published in some book years
before the 1976 (re)discovery of the RSA cryptosystem by Rivest, Shamir,
and Adleman, it would have -- and clearly should have -- invalidated the
RSA patent under that rule.

	So what do we get when Mr. Cordian finally chooses to reveal to a
curious List the source of his amazing report that the RSA public key
cryptosystem was actually published in the _19th_ Century?

	Patrick J. Flinn!  Hey, what a surprise!

	As his hallowed source, Mr. Cordian cites a footnote from Flinn's
impassioned 1997 denunciation of the RSA patent in the Cyberlaw journal.

	Read one-time Cylink attorney Flinn at
http://www.cyberlaw.com/rsa.html (and a brisk bare-knuckle retort from Bob
Haslam, RSADSI's attorney, at http://www.cyberlaw.com/rthrsa.html.)

	Flinn led the team of patent and litigation lawyers that
represented Cylink Corporation in its suit against RSA Data Security Inc.
to determine the validity and scope of the RSA PKC patent after the breakup
of an early RSA/Cylink licensing partnership. In a separate case, Flinn's
team also represented Cylink and Stanford University against RSADSI in a
suit which sought to define the validity and scope of the so-called
Stanford patents: the Hellman-Merkle Patent and the Diffie-Hellman Patent.

	Critics of Flinn's Cyberlaw article characterized him as a one-time
Cylink gunslinger who had already failed in several attempts to invalidate
the RSA patent -- and who was finally bounced from the case in 1996 when
Cylink decided that further litigation was futile and potentially
disasterous. Cylink subsequently negotiated the purchase of a license for
the RSA public key cryptosystem from RSADSI.

	RSA's attorneys, as you might expect, rudely dismissed Flinn's
list of potential vulnerabilities in the RSA patent in Cyberlaw. They
pointed out that Flinn's arguments were being published, rather than heard
in a courtroom, because those same arguments had failed to impress several
judges and hearing officers.  "As a matter of fact," declared RSA attorney
Bob Haslam, "none of Mr. Flinn's three arguments about the supposed
invalidity of the RSA Patent have ever been remotely successful in actual
litigation."

	To its credit, Flinn's Cyberlaw article doesn't really try to be
anything but a determined advocate's last-ditch list of legal attacks that
might -- with a good tailwind behind them -- potentially chip, limit, or
even invalidate RSA's teflon-coated PKC patent.  Flinn's Cyberlaw
presentation drew notably unsympathetic responses from the law profs and IP
experts on the Cyberia mailing list -- although they seemed to admire his
style and gall in publishing a case he wasn't going to be allowed try
before a judge or jury.

	For all that, the pretentions of Flinn's Cyberlaw footnote on 19th
Century Mathematics turned out to be _far, far_ less than what Mr. Cordian
had claimed.

	Mr. Cordian must have discovered this when he went back and pulled
up his source data. Then -- to put it diplomatically -- Mr. Cordian seems
to have decided to flim-flam the List a little. Rather than admit an error,
a little over-enthusiasm in his recollection of the facts, Cordian decided
bluff it out.

	He quoted for us only the beginning of Flinn's footnote, and he
ignored the rest of the footnoted text -- which, quite inconveniently for
him, seemed to directly refute his initial claim.

	(A nymed net-gent like Mr. Cordian -- who hides his real identity
behind the Cordian pseudonym -- can perhaps risk his reputation a little
more carelessly than the rest of us. If he soils this one, after all, he
can just pony up for a new identity.)

	Wrote Mr. Cordian:

>Quoting "Cyberlaw":
>
>    "There are a number of references in the prior art, moreover,
>     to using the problem of factoring composite numbers in
>     cryptography, dating back to the 19th century.
>
>    "In 1870, a book by William S. Jevons described the
>     relationship of one-way functions to cryptography and went
>     on to discuss specifically the factorization problem used
>     to create the "trap-door" in the RSA system."

	Actually, the first line of Cordian's quote is from the main text
of Flinn's article: http://www.cyberlaw.com/rsa.html. The second line is
from Flinn's Footnote # 64.

	The _full_ text of Footnote # 64 reads as follows:

[64] In 1870, a book by William S. Jevons described the relationship of
one-way functions to cryptography and went on to discuss specifically the
factorization problem used to create the "trap-door" in the RSA system. In
July, 1996, one observer commented on the Jevons book in this way:

In his book The Principles of Science: A Treatise on Logic and Scientific
Method, written and published in the 1890's, William S. Jevons observed
that there are many situations where the 'direct' operation is relatively
easy, but the 'inverse' operation is significantly more difficult, One
example mentioned briefly is that enciphering (encryption) is easy while
deciphering (decryption) is not. In the same section of Chapter 7:
Introduction titled 'Induction an Inverse Operation', much more attention
is devoted to the principle that multiplication of integers is easy, but
finding the (prime) factors of the product is much harder. Thus, Jevons
anticipated a key feature of the RSA Algorithm for public key cryptography,
though he certainly did not invent the concept of public key cryptography.

Solomon W. Golomb, On Factoring Jevons' Number, CRYPTOLOGIA 243 (July 1996)
(emphasis added).

	<End of quoted text.>

	(The conflict between the 1870 and 1890 dates cited in different
paragraphs for the pub date of Jevon's "The Principles of Science" is as
published in the original Cyberlaw article. I have no explanation, but the
1870 date seems most likely.  William Stanley Jevons, an astonishingly
prolific American economist, philosopher, and logician, was born 1835 and
died in 1882. He is probably the W.S. Jevons cited here, but I can't be
sure since I can find this title among the list of Jevon books in the
Library of Congress.)

	The Cryptologia journal, unfortunately, is not yet available
on-line, and the Golomb article doesn't seems available elsewhere.  Might
be worth digging that up. I'd love to read more of what Shannon Award
winner Sol Golomb had to say about the relationship between Jevon's 19th
Century mathematical research and public key cryptography.

	I think it is appropriate to note, however, that Prof. Golomb did
_not_ conclude that the functionality of the RSA public key cryptosystem
was "obvious" to anyone familiar with Jevons' work.

	Suerte,
		_Vin


-----
"Cryptography is like literacy in the Dark Ages. Infinitely potent, for
good and ill... yet basically an intellectual construct, an idea, which by
its nature will resist efforts to restrict it to bureaucrats and others who
deem only themselves worthy of such Privilege."
_ A Thinking Man's Creed for Crypto  _vbm.

 *     Vin McLellan + The Privacy Guild + <vin@shore.net>    *
      53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548