From: "L. Detweiler" <ld231782@longs.lance.colostate.edu>
Date: Thu, 29 Jul 93 18:23:53 PDT
To: cypherpunks@toad.com
Subject: S. Walker review of NIST-PKP-DSS options
Message-ID: <9307300121.AA13277@longs.lance.colostate.edu>
MIME-Version: 1.0
Content-Type: text/plain


DIGITAL SIGNATURE STANDARDS

OK cypherpunks, if my rantings on this subject were too obscure and
made no sense (as one respondent told me), then read this excellent
review of the past and present NIST-DSS-PKP situation. I recommend it
go on the soda.berkeley archive. Most importantly, it gives a small
glimmer of the sheer future economic impact of the signature standard
decision (it is far more vast than he suggests). It is the very basis
of a vast future `EC' economy, Electronic Commerce.

- RSA vs. DSA, duality of encryption & authentication
- free use of DSS: a promise broken
- Schnorr Patent: a wrench in the works
- Content and expiration dates of various PKP patents
- burdensome economic/social cost of DSS under current NIST proposed scenario
- available alternatives: other algorithms & expirations

Quotes:

>Reflecting on this range of alternatives, it quickly becomes
>apparent that the June 8 approach advocated by the Government is
>just about the worst approach one could devise. 

>this analysis
>shows that everyone, including the Government, will be better off
>if NIST just dropped DSS, including the plan announced on June 8,
>1993, and did nothing else.

Interesting tidbits: refers to the CSSPAB DSA announcement snub,
`government scientists' at NIST (where are they?), three other
algorithms considered but under wraps by the NSA, `highly censored
minutes' by NSA on them.

Corrections: 

- he says that no public key algorithm has been proposed by NIST/NSA.
But that is precisely the point of Clipper and Capstone. Denning made
this clear once (RISKS). A public key system with the most important
black ingredient: wiretappability!

- he assumes near the end that as soon as RSA patent expires, industry
will leap to it irrespective of any current standards, even suggesting
that commercial implementations of other algorithms would dry up and
become unavailable (if I read him right). I'd like to see that, but
it's a bit of a leap of faith because it completely ignores the inertia
of entrenched standards. In fact, this seems to be one of the weakest,
least supported, and least explained paragraphs.

Holes:

- doesn't cover the hoopla about the supposed insecurity of DSA (and
associated key length changes) that characterized a lot of the early bickering.

- doesn't cover the angle that the government gets unlimited use of
patented public-key authentication schemes (RSA, Diffie-Hellman) for
use in Capstone-Clipper combination based on the PKP DSS agreement.
This is a *major* ulterior motive & motivation for the agreement on the NSA side.

- doesn't look at the NSA as defiant, conspirational or subversive esp.
in regard to the DSA scheme & DSS hearings--almost no mention at all.

- doesn't look much at PKP as a company attempting to maximize its
profit to the point of backroom collusion, patent mongering, and vast
monopolizing, although hints at it.

===cut=here===

Date: Wed, 28 Jul 1993 18:41:43 -0500
From: farber@central.cis.upenn.edu (David Farber)
Subject:  DIGITAL SIGNATURE STANDARD We can do better! by  Stephen T. Walker




                        DIGITAL SIGNATURE STANDARD

                             We can do better!


                            Stephen T. Walker
                                President
                    Trusted Information Systems, Inc.

                               July 28, 1993


The National Institute of Standards and Technology (NIST)
recently announced its intention to grant Public Key Partners
(PKP) an exclusive license to NIST's pending patent for the
Digital Signature Algorithm (DSA), stating that this action "will
best serve the interests of the Federal Government and the
public."  While this may be a "good" deal for the Government's
own use of the Digital Signature Standard (DSS)[1], it leaves the
public in much worse shape for a much longer time than if NIST
did nothing.  History is full of examples where, if what is
thought to be best for the Government is not also clearly best
for the public, the Government also loses.  This will be yet
another example if something is not done very soon.  But there
are alternatives that open a wide range of possibilities, some
not very far from where we wanted to be in the first place with
DSS.

- - ----------
FOOTNOTE [1]: The Digital Signature Algorithm is the algorithm
that NIST has chosen to be the Digital Signature Standard.  For clarity
throughout this document, the term DSS will be used to refer to both the
standard and the algorithm.
- - ----------

This paper explores the background of the present NIST proposal
and how we got here.  It then analyzes the public key patent
situation and provides a high level economic analysis of the
impact that the NIST decision will have, followed by a discussion
of several alternatives.  Finally, it recommends a course of
action which seems to serve the interests of the Federal
Government and the public much better than the present proposal.

These comments are my own personal opinions and should not be
construed as necessarily representing the views of any
organization with which I am affiliated.

Background

In August 1991, after years of urging by Congress and industry,
NIST, with the behind-the-scenes help of the National Security
Agency (NSA), announced the Digital Signature Standard, which
adopts the Digital Signature Algorithm as a proposed Federal
Information Processing Standard (FIPS).  Most advocates actually
wanted a Federal standard for public key encryption that would
include both signature and confidentiality capabilities.  The
Rivest/Shamir/Adleman (RSA) algorithm is the obvious choice and
is already widely used in the U.S. and around the world. 
Nonetheless, the Government chose an algorithm which is useful
only for signatures and appears to have no plans to choose a
public key algorithm for encryption.

DSS is based on a variant of the ElGamal signature algorithm. 
The Government filed a patent application for DSS in July 1991. 
Dr. Ray Kammer, then Deputy Director of NIST, testified on June
27, 1991, to the House Subcommittee on Technology and
Competitiveness that "the digital signature technique is expected
to be available on a royalty-free basis in the public interest
world-wide."  Several months prior to this, Prof. Dr. C. P.
Schnorr of Germany obtained a U.S. patent for his digital
signature algorithm.  In October 1991,  Dr. Schnorr notified NIST
of his belief that DSS infringed his patent rights.

The ability to digitally sign information in electronic form is a
fundamental capability of great importance to the future of all
forms of Electronic Commerce (EC).  Some means of verifying the
identity of the sender and integrity of the message is essential
for the widespread success of EC.  Since EC will soon encompass
all forms of communications devices including telephones,
personal computers, and televisions, a universal, freely
available means for digitally signing electronic messages is
essential for U.S. industry.

If DSS could provide a royalty free signing capability, many
people would view this as an advantage which might outweigh the
serious disadvantage of its being incompatible with the widely
available, proprietary RSA algorithm which is subject to royalty
payments for the next seven (7) years in the U.S.

After the August 1991 announcement, much debate over the
technical strengths and weaknesses of DSS ensued, and the
Government initiated efforts to resolve the potential patent
issues that had arisen over the relationship of DSS to the
Schnorr patent and others held by PKP (see The Patent Situation
section below).  Minor changes to the key length resulted from
the first comment period on the proposed standard, and then a
long period of silence set in.  During 1992, both the Government
and PKP pursued the rights to the Schnorr patent and eventually
PKP succeeded in licensing those rights.

Then in the June 8, 1993 Federal Register[2], NIST announced its
intention to grant an exclusive license to PKP for the NIST DSS
patent.  In an Appendix to this notice, PKP stated "It is PKP's
intent to make practice of the DSA royalty free for personal,
non-commercial, and U.S. Federal, state and local government
use."  Commercial use of DSS would be subject to royalty payments
to PKP throughout the life of the Government DSS patent, a period
of seventeen (17) years after the patent is awarded (as of this
writing, the DSS patent has yet to be awarded).

- - ----------
FOOTNOTE [2]:  The announcement was signed by the Acting Director of
NIST on June 2, 1993, the first of three days of public hearings
on the Government's policies on cryptography by the Computer
System Security and Privacy Advisory Board (CSSPAB), a
Congressionally chartered Board charged with advising the
Executive and Legislative Branches on technical matters relating
to computer security.  Had the Government thought to have this
major development in the long struggle to get a digital signature
FIPS revealed to the public for criticism or endorsement, they
would have had the perfect audience and opportunity. 
Unfortunately, those in charge decided to keep the announcement
under wraps until four days after the meeting, missing an
excellent opportunity to explain the circumstances behind their
decision.
- - ----------

The Government has not publicly stated all of the reasons why it
believes granting PKP this exclusive license is in its and the
public's best interests.  It is not a far-reaching speculation
that this action was viewed by the Government's lawyers as
necessary to prevent PKP from charging the Government a royalty
for use of DSS based on its infringement of the PKP-owned Schnorr
patent.  Despite the fact that the Government has royalty free
rights to the PKP patents, it does not have rights to the Schnorr
patent.

All of this seems most unfortunate for the commercial development
of EC.  Suddenly the only significant argument for many in the
private sector in favor of DSS, the fact that it was to be free
for all uses to all users, is gone.  Without that positive
benefit, there no longer appears to be any advantage to DSS, and
the negative factor, its incompatibility with RSA (now even more
widely used), looms all the more heavily.  Much of industry will
continue to use RSA irrespective of the Government's position on
DSS, so those who must interact with both industry and the
Government will be forced to use both algorithms, each with its
own royalty payment.  The difficulties of validating digital
signatures based on two incompatible algorithms have been
described in detail at the February 1993 NIST-sponsored Federal
Digital Signature Applications Symposium.

The Government has always maintained that DSS is not covered by
earlier patents.  However,  to avoid lengthy patent disputes and
to get its proposed algorithm approved quickly, the Government
has, unfortunately, lost sight of one of its original objectives. 
The Government has protected its own direct interests by getting
royalty free use of its own algorithm, but at an enormous price
to the American public.  Does the Government have the right to
propose a Federal standard that goes directly against a well
established industry trend (the use of RSA) and that will result
in U.S. commercial interests having to pay substantially greater
royalty fees?  Can a FIPS be promulgated without an analysis of
the impact it will have on the public?  The answers appear to be
yes, but there are alternatives that should be considered first.

The Patent Situation

To understand these alternatives, we must first understand some
basic facts about the public key patent situation.

In the early 1980s, four patents covering various forms of public
key cryptography were granted.  They are, in order of date of
patent award:


     (1)  Patent #: 4,200,770 Issued on:     April 29, 1980
                              Expires on:    April 29, 1997

          Diffie/Hellman - Cryptographic Apparatus and Method
          (the "Diffie-Hellman" key exchange, covering both the
          secure generation and the secure exchange of the key)


     (2)  Patent #: 4,218,582 Issued on:     August 19, 1980
                              Expires on:    August 19, 1997
 
          Hellman/Merkle - Public Key Cryptographic Apparatus 
          (general concepts of secure communications using public
          key cryptography and general concepts of digital
          signature; specific public key "knapsack" systems for
          secure communications)


     (3) Patent #: 4,405,829  Issued on:     September 20, 1983
                              Expires on:    September 20, 2000

          Rivest/Shamir/Adleman - Cryptographic Communications
          System and Method
          (cryptographic communications systems employing the
          "RSA" algorithm)


     (4)  Patent #: 4,424,414 Issued on:     January 3, 1984
                              Expires on:    January 3,  2001

          Hellman/Pohlig - Exponentiation Cryptographic Apparatus 
          and Method
          (variant of Diffie-Hellman for secure exchange of
          messages)

In the late 1980s, the owners/licensees of these patents banded
together to form Public Key Partners.

Because the research that developed these algorithms was
sponsored by the U.S. Government, the Government has royalty free
access to these technologies.
 
In 1985, ElGamal published a paper on a digital signature
technique but did not seek a patent.  In August 1989, Schnorr
published a paper on this subject and in 1991 received a U.S.
patent:

     Patent #: 4,995,082 Issued on:     February 19, 1991
                         Expires on:    February 19, 2008

     Schnorr - Method for Identifying Subscribers and for
     Generating and Verifying Electronic Signatures in Data
     Exchange Systems
     (data exchange system working with processor chip cards to
     perform identification and electronic signature
     generation/verification procedures)

The U.S. Government does not have royalty free access to the
Schnorr patent.

After NIST announced the proposed DSS in August 1991, Schnorr
informed NIST of his belief that DSS infringed on his patent. 
Sometime later, PKP obtained a license for the Schnorr patent,
giving them a virtual monopoly in public key technology patents
in the U.S.

Economic Impact of NIST's June 8 Announcement

I recently asked NIST if the Government had analyzed the economic
impact on the Government or the public of granting an exclusive
license to PKP for DSS.  I was told that no such analysis had
been done.

The following high level analysis offers some very approximate
estimates of what it might cost if DSS, licensed as proposed by
NIST, were fully accepted by industry and became widely used.  We
acknowledge that these estimates could be off by as much as a
factor of five (5) or more either way, nonetheless they tell a
compelling story.

In its July 26, 1993 issue, Business Week discussed home shopping
networks which will involve the use of televisions, telephones,
and personal computers.  The article describes recent
conglomerates that will reach "more than 60 million viewers, or
two thirds of all television households." 

If digital signature standards were routinely available today,
they would be highly useful in confirming the identity of the
purchaser and the authenticity of the purchase request.


The cost of a DSS royalty per the NIST announcement "will be no
more then 2 1/2% for hardware products and 5% for software, with
the royalty rate further reduced to 1% on any portion of the
product price exceeding $1000."

The analysis below focuses on the potential home shopping market
for the Digital Signature Standard involving televisions,
telephones, and personal computers.  It assumes conservative
numbers of devices, periods of use, and royalties to derive
potential royalty figures.

     Assuming: 60 million televisions used in home retail
                    that need to be replaced every five (5) years
                    and
                    a  royalty of $2.50 per television
                    (5% of the $50 price for the signature
                    software),

               during the seventeen (17) years that the public
               will have to pay royalties to PKP for DSS, the
               cost will be approximately $500 million.
                    (60 million * 17 years/5 years * $2.50)


     Assuming: 150 million telephones, only 20% involved in home
               retailing
                    that need to be replaced every five (5) years
                    and
                    a royalty of $2.50 per telephone,

               the royalty cost will be approximately $250
               million.
                    (150 million * 20% * 17 years/5 years *
                    $2.50)
               If one includes growth from new phone markets,
               this number could easily grow to $750 million.


     Assuming: 40 million personal computers and workstations
                    that need to be replaced every five (5) years
                    and
                    a royalty of $5.00 per computer,

               the royalty cost will be approximately $680
               million
                    (40 million * 17 years/5 years * $5.00)

     Approximate total royalty payment over seventeen (17) years
     is $2 billion.

These are rough estimates for one business segment.  They do not
take into account business use for banking, financial, or dozens
of other commercial uses.  If one chooses to scale these down by
five (5) to be even more conservative, the $2 billion royalty
bill drops just below $400 million.  Others may want to raise the
estimate by five (5) because of growth in a rapidly emerging
industry, raising it to over $10 billion.


These are of course hypothetical scenarios that assume DSS is
widely endorsed by industry and becomes a commercial standard.

No matter how one looks at this deal, it's a very good thing the
Government got use of the 
DSS for free, because the public certainly will pay a fortune for
it.

Alternatives?

The Government appears to have been operating under the premise
that DSS, as currently defined, is its only possible way to
proceed.  The close relationship of DSS to the Schnorr patent
makes it subject to infringement charges from PKP.  This
unfortunate relationship seems to have forced the Government to
their June 8 "give away" of DSS as "best serving the Federal
Government and the public."

However, we should recognize that within four (4) years, the
Hellman/Merkle patent, which is the principal broadly based
public key signature patent, expires.  At that time, one could
implement an ElGamal-based algorithm which did not use the
techniques of the Schnorr patent and is therefore royalty free
from then on.  The Schnorr techniques involve efficiency
enhancements for ElGamal, but even if this new approach were not
as efficient as the present DSS, the removal of patent issues and
royalty payments would make up for a lot of inefficiency.

The above alternative suggests doing nothing for four (4) years
except defining a new signature algorithm (which may take that
long anyway).  Of course, we could take this path immediately and
agree to pay PKP royalties for the new algorithm until the
Hellman/Merkle patent expires.  The Government would not be
subject to these royalties since it has a free license to the
technology anyway.  Commercial users and developers would be much
less  unhappy to pay royalties for a few years rather than for
seventeen (17).  NIST scientists could start immediately to
identify an ElGamal-based algorithm that is not subject to
Schnorr patent restrictions.  There are indications in the highly
censored minutes to the NIST-NSA Technical Working Group that
there were at least three (3) other algorithms being considered
before the present DSS candidate was chosen, so perhaps we
already have a head start on this process.

Realizing that this alternative algorithm approach could reduce
PKP's potential royalty period for DSS from seventeen (17) years
to four (4) years opens other alternatives that include paying
PKP a reasonable sum based on estimates of DSS royalties for this
limited period, to allow royalty free use of the present DSS for
all users forever.  Faced with the alternative of the extremely
high royalty payments discussed above, it is likely that a
Government/industry consortium could be formed to raise the funds
to eliminate the four (4) year wait and the need to switch to a
new algorithm.

Of course, such a Government/industry consortium could also
decide to apply pressure on PKP to grant, as IBM did with the
Data Encryption Standard algorithm, royalty free use for the
public for all time.  PKP could continue to collect royalties on
all its other algorithms but, in return for the Government's
(and, therefore, the public's) having paid for the research that
led to those patents in the first place, PKP should make DSS
available for all royalty free.

There are those who claim the whole DSS exercise has been forced
upon us because some in Government do not want to see RSA become
a widely used "standard."  Those individuals must recognize that
the present plan is working directly against their desires.  The
RSA patents expire in seven (7) years, while the NIST plan forces
a seventeen year (17) royalty period.  Industry will choose the
shorter period, and DSS will be relegated to Government special
purchase efforts.  Indeed, after the RSA patent expires, it will
be impossible for the Government to get DSS from any commercial
source.  Thus, by the very terms of the June 8 announcement, RSA
will become the de facto standard for digital signature that
these individuals want to prevent.

Reflecting on this range of alternatives, it quickly becomes
apparent that the June 8 approach advocated by the Government is
just about the worst approach one could devise.  (Please do not
try to find a worse one!)

A Suggested Plan of Action

We strongly suggest that the Government back up from its headlong
plunge toward indenturing the U.S. public for a much needed
Digital Signature Standard.  There are alternatives, if we are
willing to wait a few years, that will reduce a high royalty
payment bill to zero.  There are approaches to analyzing this
situation that allow continuing with DSS at a greatly reduced
cost to the American public, perhaps even reducing it to zero. 
Any of these approaches will yield a more economically viable and
more generally available solution which serves the interests of
the Federal Government and the public far better than the present
plan.

Even if none of these alternatives are pursued, this analysis
shows that everyone, including the Government, will be better off
if NIST just dropped DSS, including the plan announced on June 8,
1993, and did nothing else.

Please, NIST, reconsider your options before it's too late!