21 May 1999. Thanks to VM.

To: coderpunks@toad.com
From: Vin McLellan <vin@shore.net>
Subject: <fyi> DSA (Digital Signature Standard)
Cc: Dave Farber <farber@cis.upenn.edu>,cryptography@C2.net

        On Coderpunks, Vin McLellan wrote:

>> Prof. Schnorr is an active defender of his patent claims   
>> with regard to the DSA, as indicated by his several posts  
>> to this List last year

         James A. Donald <jamesd@echeque.com> accurately noted:

>Posts that failed to impress some people on this list.

        While the estimable Ben Laurie <ben@algroup.co.uk>  growled:

/> i.e. if you believe that division is addition, 1 is 2 and black is
/> white, you'll have no problem with these claims.

        I hesitate to get into this, since I'm not qualified to judge the
viability of Prof. Schnorr's case, or even to effectively present his
technical arguments, but Schnorr's claims -- to judge from their impact on
DSA adoption, US crypto policy, and specifically the NSA's strategy for
managing the US standards process to ensure universal government access to
crypto keys (GAK) -- are neither trivial nor vacuous.   

        I think it is misleading to suggest that they are.  

        In 1992, the best patent lawyers the US government could hire were
far less certain than Ben and others here that Schnorr's US patent did not
impinge on the DSA design -- to say nothing of Schnorr's broader European
and Japanese patents on digital signature tech.    

        NIST's 1993 DSA patent (filed two months after Schnorr's US patent
was issued in 1991) is one of 51 US patents on cryptography, many of them
now classics, which explicitly refer to Schnorr's digital signature patent.
Among cryptographers, Whit Diffie has noted a "strong resemblence" between
DSA and the Schnorr design, and Bruce Schneier, who studied and wrote about
the DSS patent issues in Applied Cryptography, certainly didn't glibly dismiss
Schnorr's claims as some have here.  

        I don't have a formal cite or even a quote, but I've always
understood Prof. Schorr's digital signature algorithm to have been inspired
by El Gamal's work at Stanford in '89, and to have in turn inspired
Brickell and McCurley.  It is, I think, commonly believed among European
crypto scholars, at least, that the El Gamal and Schnorr designs were the
basis for David Kravitz's invention of the DSA.

        I do know that in 1991-'92 NIST hired two or three prominent US
patent firms to review the applicability of the Schnorr patents to the DSA.
The only consensus they got was: "Maybe, maybe not."  

        And this was after Kravitz, the NSA mathematician who developed
the DSA at Princeton for the NSA, was given the Schnorr patent and asked by
NIST to tweak his initial DSA design to minimize potential conflict with
Schnorr's US  patent. 

        Those who didn't see the Coderpunks posts in which Prof. Schnorr
responded to a thoughtful challenge from Anon on this List last year may
wish to read Schnorr's own informal pitch at:


But see Schnorr's submission to the IEEE PKC working group 1363:


And "A Study on the Coverage of the DSA by EP-Patent 0384475":


        Mr. Donald argued:
>If Schnorr's patent covers the DSA, then the patent office   
>has erred in giving a patent to the NSA for the claims that
>the NSA made, since the claims overlap.

        That may well be.  Anyone who recalls how the NSA had NIST doing
backflips to push the Key Escrow FIPS (FIPS 185) through in record time --
with an abbreviated period for public comment which garnered 322 responses;
only two pro-GAK -- would not be surprised to learn that the US Patent
Office was cowed by the NSA's expertise. 

        The DSS, of course, became FIPS 186 -- a federal purchasing
requirement which, with 185, effectively locked US government agencies out
of the commercial infosec market for years; probably cost hundreds of
millions in federal-only development costs; and contributed substantially to
the woeful state of computer security in federal US agencies even now.

        Patent-haters and nostalgic PGP adherents who today see DSA only as
a royalty-free alternative to RSA digitial sigs forget the context in which
the NSA initally sponsored the development of the DSA.

         The DSA was developed by the NSA explicitly to undermine the de
facto status of RSAPKC as an industry-supported standard.  Yes, it was
royalty-free -- but there were other "costs" presumed to be associated with
any widespread adoption of DSA in commercial compsec.  While there certainly
are apps which require only digital signatures, in many if not most
situations where a user needs a guarantee of authentication and integrity,
he will want at least the option of confidentiality as well.   The DSS was
not intended to serve alone.

        The DSS was a key element in a coordinated US government strategy
to block industry acceptance of any public key crypto in software in order
to force upon the market the NSA's version of fully-GAKed PKC in silicon.
This was the NSA's Capstone program -- strategic papa to CCEP,  Clipper,
GAKed Fortezza, key escrow/key recovery, et cetera.  

         At the time, as any industry veteran will tell you, the NSA had the
US standards-development groups almost completely in its thrall. As a
reporter covering compsec and federal info security policy at the time, I
came to the conclusion that -- PGP and Phil Z. as Jonny Appleseed
notwithstanding -- it was only because PKC was patented, privately owned,
and defended by Jedi Knights with a knack for dirty street-fighting was
there any future for strong crypto in the US.  (I still think historians
will agree with me, although I realize that it is an opinion shared by few
on the Net's crypto forums today.)

        Ten years ago, the idea of mass market products which packaged DES
and a software version of public key crypto -- either RSA or D-H, both then
managed by the PKP partnership -- for key exchange was a vivid NSA
nightmare.  The NSA's strategy for blocking this was to use the NSA's
control over the US standards orgs to block any American or international
effort to standardization around either RSA or D-H  -- until the market
accepted Capstone and GAKed key-exchange in silicon. 

        To meet the acknowledged market needs for a digital signature
utility -- and to prep the market for Capstone key management -- the NSA
came up with DSA (ignoring industry howls that DSA was 10-40  times slower
than RSAPKC for verification -- then, as now, the crucial functionality in
digital signature apps.)

        Watching  NIST abjure its obligations under Brooks' Computer
Security Act of '87 to foster strong computer security for industry and
government and become a mere cat's paw for the NSA's eavesdroppers  in
offering the DSA --  in what was clearly a strategic ploy to undermine the
acceptance and slow the adoption of public key crypto with un-GAKed
confidentiality -- was a turning point in my view of the Clinton
Administration and the prospects for  privacy and e-commerce in the US.  

        Democrats proved no more resistant than Republicans to the
blandishments of whispers from Fort Meade.  (The lure of the Dark Side of
the Force is strong, my fellow geeks.)

        Twenty year earlier I had provided Sam Ervin and the US Senate's
Constitutional Rights Subcommittee with the internal US Army plans  which
described the full extent of how Army intelligence agencies were misused to
illegally surveil US citizens during the Vietnam era.  GIs were assigned to
track elected labor union officers, under some 1930s presumption that unions
were radical hotbeds. Honest!)  Then I had watched Congress heroicly
struggle to force the revocation of Reagan's NSDD 145, which had temporarily
established the NSA as the US Infosec Czar.   

        ( The idea that the Pentagon and the NSA were again presuming to
claim hegemony in civil society irked me greatly. People forget that with
Clipper and Capstone, the NSA was not only trying to GAK all commercial and
personal communications, but that the spooks of the NSA were also claiming
the right to determine which vendors would be allowed the privilege of
integrating GAKed PKI chips into their products.  This was like giving the
NSA a veto over which entrepreneurs could get venture capital.)

        I think the historic importance of the Schnorr patents (at least in
the US) was that, in '92, when Claus Schnorr chose to align himself with
RSA rather than sell out to NIST and the NSA, he gave RSA's Jim Bidzos a
powerful weapon, at a crucial time, to counter the DSS FIPS.  Neither Prof.
Schnorr nor RSA has suggested that any challenge to DSS is pending, although
the Schnorr patents are valid until 2008, so at one level this discussion is
a mere intellectual exercise.  

        Five years ago, when the DSS was issued,  the Schnorr patents posed
the threat of an embarassing checkmate.

        The existance of the Schnorr patents made the adoption of the
royalty-free DSA -- authentication and integrity, stripped of both
key-managment and confidentiality -- and the Capstone/Fortezza scheme
inextricably linked to it, much less  attractive for US computer vendors.  

        When RSA got control of the Schnorr patents, the NSA and NIST pulled
the plug on their campaign to foster commercial acceptance of DSA.   Balked
-- NIST was forced to announce that they would assist anyone RSA sued, if
that firm was using DSS persuant to a government contract, but everyone else
was on their own --  the strategists at the NSA  turned instead to pushing
the main event: Capstone, Fortezza, and the Escrowed Encryption Standard (ESS).

        With the threat of a patent suit -- and marvellous theater, like
when Bidzos got 20 major RSA licensees  to purchase rights to the Schnorr
patents so that they could "legally" use DSA -- RSA managed to stall
widespread acceptance of the DSA just long enough for it to be seen as what
it was: part and parcel of the Fort Meade's overall strategy to deny US
citizens (as well as overseas customers of US vendors) access to un-GAKed
interoperable public key crypto.  

       The NSA's imprematur on DES gave it credibility and allowed its
widespread adoption with minimal liability within the private sector.  The
DSA, just because it came from the NSA, never escaped the taint of Capstone
and Clipper, despite the fact that it was royalty-free.  Free code is a
relative value.  Context is all.  


        (It is, I presume, clear that this is a personal statement and none
of my clients are responsible for these meandering recollections.  I have
been a consultant to SDTI, RSA's parent firm, for many years, which may have
warped my judgement.)


  "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