RE: Rivest Patent

[Vin McLellan <vin@shore.net>]

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
                         -- <@><@> --