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