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:

       http://privacy.nb.ca/cryptography/archives/coderpunks/new/1998-08/0006.html

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

       http://grouper.ieee.org/groups/1363/letters/SchnorrMar98.html

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

       http://grouper.ieee.org/groups/1363/letters/SchnorrMar98Study.ps

            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.

            Suerte,
                            _Vin

            (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