September 20, 1991 Hon. Tim Valentine Chairman, subcommittee on Technology and Competitiveness House Committee on Space, Science, and Technology U.S. House of Representatives Dear Mr. Valentine: On August 30, 1991, nine years after their first attempt and over three years after being called upon by the Congress to do so under authority of the Computer Security Act of 1987 (the "Act"), the National Institute for Standards and Technology (NIST) has published a proposal for a public-key cryptographic standard. The proposal, developed with the National Security Agency (NSA), is called DSS, for "Digital Signature Standard."  While we recognize NIST's efforts in finally proposing such a standard, we have serious concerns about the proposal. We question NIST's justifications for their proposal and the manner in which it is being proposed. We are greatly concerned that NIST has not fulfilled its obligations under the Act. Since NIST provided some of these justifications in testimony to the Subcommittee on Technology and Competitiveness on June 27, 1991, you may be interested in our analyses. Before providing our analysis of the specific statements of justification in NIST's proposal, we would like to offer four criticisms of DSS and the manner in which it is being introduced. 1. NIST has offered only a 90 day comment period for their proposed standard. This time period is insufficient for analyzing DSS. Further, DSS will not be fully complete and presented within the 90 days, but will appear in pieces over a much longer period. DSS proposes a new, untested public-key cryptographic algorithm. The cryptosystems in use today became trusted over a period of more than ten years, during which much research was conducted and published. Since no one outside of NIST and NSA has seen the DSS algorithm until now, we feel that a much longer comment period----at least one year---is appropriate. Public-key technology has been ignored by NIST for fifteen years; it is inappropriate for NIST to foist a new scheme upon the country with such a short review period. NIST is admittedly submitting a proposal which is missing important components. It is therefore inappropriate for NIST to offer a comment period which expires prior to an opportunity to review a complete proposal. 2. NIST's proposal fails to address the use of public-key cryptography for privacy. It covers only authentication, and is incomplete even as an authentication proposal. Data privacy is an important requirement of the Act, and a large part of NIST's responsibility. While authentication is certainly important, neglecting to allow for the powerful privacy that public-key cryptography can provide denies U.S. industry important protection against industrial espionage. There is no discernible reason for this omission. Further, NIST's authentication proposal is incomplete --- it is missing important components such as a hashing algorithm and a structure for "certificates" and thus is not yet ready for any actual use. NIST gives no indication of its plans to complete the proposal, but it could easily be one to two years before their proposal is complete. This is a major reason why a 90 day comment period is inappropriate: there is not a complete proposal to comment on. 3. A system different from the one NIST proposes, known as RSA, has come into widespread use around the world as a de facto standard over the last ten years, but NIST, for reasons unknown, has ignored this development. A growing number of major computer industry companies have licensed and endorsed the patented RSA system. Many, including Motorola, Northern Telecom, Lotus Development and Novell, Inc., have already made RSA a standard part of their mainstream products and have shipped over half a million copies. Current plans of RSA licensees will put this number at several million within a year. (Recently, a Fortune 10 company purchased 15,000 copies of a product from a U.S. licensee of RSA which has privacy and authentication based on the RSA system embedded in it, for use in Europe.) The RSA system offers both authentication and privacy. Furthermore, there is a well developed, complete standard for its use, developed by a number of the most important companies in the U.S., including Microsoft, Sun Microsystems, Lotus, Digital Equipment, and many others. NIST has ignored these developments, not even acknowledging them. In response to criticism from the press that NIST has ignored developments in the private sector, NIST has stated that their standard is nominally "only for the government." However, it will be seen that NIST's behavior gives every indication that they are aggressively pursuing a U.S. commercial standard based on their system, attempting to supplant existing de facto standards, and employing every means available to accomplish these objectives. 4. The proposed NIST standard as presented thus far appears inflexible, and cannot support or adapt to new technologies or new technological developments. In a security standard, such inflexibility amounts to gross negligence. Any cryptographic standard should be structured to support multiple algorithms. (With the exception of the NIST proposal, all such efforts have this flexibility.) Such a facility would provide a means to "switch" algorithms in the event one algorithm becomes "broken," or unsuitable. Support for multiple algorithms is normal practice in cryptography standards, and does not affect interoperability. Such a facility, in this case, would also protect a major investment by U.S. industry, made during government inaction over the last ten years. NIST's approach gives the appearance of trying to reverse a major worldwide trend in industry and standards making. In the same direction, the NIST proposal does not allow for a gradual increase in key size as technological improvements give greater strength to potential adversaries. With computer performance steadily increasing at approximately 40% per year, any reasonable security standard must plan to compensate with a gradual increase in key size. Any proposal, such as NIST's, that contains unnecessary restrictions on allowable key sizes (NIST's proposal only allows 512-bit keys) contains the cause of its own eventual demise. There is no reason for the NIST proposal to restrict users from choosing arbitrarily large key sizes, and thus protecting themselves from technological advances. We will formally submit these observations to NIST during the comment period for DSS, and request explanation and justification from NIST, consistent with their obligations. NIST'S JUSTIFICATIONS FOR DSS It is interesting to review NIST's justifications for DSS. The proposal states: "Among the factors that were considered during this process were the level of security provided, the ease of implementation in both hardware and software, the ease of export from the U.S.; the applicability of patents, impact on national security and law enforcement and the level of efficiency in both the signing and verification functions." We shall examine each of these justifications separately. SECURITY LEVEL The security level of DSS is clearly an important consideration. The most serious technical flaw in DSS is that it provides insufficient security. The security of the system depends on the size of certain numbers. Based on the most thorough and recent work on the subject, numbers (such as the DSS numbers at the proposed length of 512 bits) "should definitely be avoided" because they offer only "marginal security" . Such numbers are vulnerable to catastrophic failure, compromising the security of every single user of the system. An attacker could surreptitiously have the "run of the system." The threat this poses to the security of sensitive U.S. government, commercial, and financial data cannot possibly be justified. The referenced research  on the security of the discrete logarithm problem, on which the DSS system is based, is well known worldwide, ensuring that the NIST system would never be used by any company not forced to do so, and would never be purchased from U.S. suppliers by companies outside of the U.S. In addition, every single use of the NIST proposal to create a "digital signature" requires a new, truly random value. Although the NIST proposal does not warn users of this, an attacker who could obtain the random value used in any one signature could easily derive that user's private key. Given the user's private key, the attacker could forge the user's digital signature on any document. Obtaining cryptographic quality random values is non-trivial, and may not be possible in some computing environments, making DSS unusable in many applications. We note that the RSA system does not suffer from this weakness. EASE OF IMPLEMENTATION In addition to the security risk it poses, the added burden of providing the "randomizing" apparatus in a secure manner makes the NIST proposal a cumbersome and costly scheme to implement. Other, more popular schemes do not share this burden; they either require no randomization whatsoever or do not require that the randomization apparatus be kept secret. Furthermore, the inefficiency of the DSS proposal --- see the following section on efficiency --- makes it difficult to implement if specific performance goals must be met. EASE OF EXPORT We note that as a signature system, the NIST proposal is no more or less exportable than any system employing cryptography (of any type) for authentication, as opposed to data privacy. All systems that employ cryptography for authentication only fall under Commerce Department jurisdiction, whereas systems applying cryptography to data privacy are controlled by the State Department. APPLICABILITY OF PATENTS NIST cites, as a major justification for this decision, economic factors related to patent applicability. (see "U.S. Plan Is Seen Hurting Electronic Data Standard," the Wall Street Journal, July 2, 1991.) NIST feels the government should not pay royalties for the use of technology. (see "NIST Proposes Standard for Electronic Signatures - Move Criticized by Some as Ignoring Tried and True," Network World, July 1, 1991.) It is a simple fact that the U.S. government does not need to pay royalties or any fees for the use of any public-key cryptography developed in the U.S. since the known public-key schemes were all developed with at least partial federal funding, thereby giving the government royalty-free use. Further, the government has the right to solicit the private sector to build products, royalty-free, for government use. This justification by NIST could not be more wrong. NIST further claims it wants to offer a royalty-free system for industry as well. Most licensees of the patented RSA system do not pay royalties but have already absorbed the cost through single payments so that high-grade security can be made available at no extra cost to users as a standard part of high-volume products. Again, since NIST has not consulted industry, it is fair to ask how NIST has determined that this should be the most important criteria. Much of industry has already spoken; a well-studied and well-respected public-key system is worth paying a reasonable royalty for. A significant part of the U.S. computer industry clearly felt the RSA system offered sufficient value to invest in. Whether one feels RSA is worth paying for or not, NIST's proposal attempts to take this option away from U.S. industry and from the U.S. government. There are currently well over 100,000 documented users of products containing RSA-based security in the federal government and defense industry alone. In April of 1990, the patent holders for the RSA system offered to cooperate with NIST in a well publicized letter to the agency. Unfortunately, NIST chose not to respond to this offer to work with industry. NIST's decision to work with NSA instead of industry has the unfortunate effect of "punishing" those companies that haven't waited for DSS. If the NIST standard should prevail as proposed, then those who decided not to wait for NIST lose their investment, and, further, may be put at a disadvantage as they must "retool." How the Commerce Department, after four years of work, could develop a standards proposal that would result in a setback for U.S. companies whose collective annual revenues exceed $30 billion, demands more explanation than NIST has provided. By punishing our industry leaders who have adopted RSA, NIST's proposal also has the undesirable effect of discouraging the adoption of innovative technology, something U.S. industry must do to be competitive in a global marketplace. We note that if the NIST proposal becomes the government standard to the exclusion of all others, as currently proposed, then the government itself is deprived of the economic benefit of the investment industry has made in the RSA system. NIST is the only organization to propose a non-RSA scheme as a public key standard. Those who have proposed RSA standards include the British, French and Swiss banking communities; the International Organization for Standardization; CCITT; and the Internet, among others. Of course, no one can expect that U.S. industry will ignore these developments in favor of the NIST proposal; so in order to remain competitive internationally, U.S. companies will be forced to bear the economic burden of supporting two different systems. We also note that it has been administration doctrine for over a decade that the government should support, rather than compete, with private industry. NIST's actions are in direct conflict with this policy. EFFICIENCY OF SIGNATURE COMPUTATION VS. SIGNATURE VERIFICATION NIST has stated that performance in signature creation is more important than in signature verification, and offered this as part of its justification for DSS. We believe, however, that it can be shown without doubt that NIST's claim about the relative importance of these functions is absolutely false, and we invite NIST to justify their claim publicly. We note that special purpose hardware provides identical performance regardless of the algorithm used. NIST's claim makes no sense. We note that it is true that the NIST proposal features an algorithm with the property that "signing" is faster than "verifying." However, we also note that the RSA system "signs" 35% faster than the NIST proposal, and that RSA operates 40 to several hundred times faster in the critical "signature verification" function. (This can be demonstrated mathematically.) It's poor performance makes DSS useless in interactive applications. DSS will be unusable by a large segment of U.S. industry without the added expense of special purpose hardware, and entirely unusable in most software applications. NATIONAL SECURITY AND LAW ENFORCEMENT CONSIDERATIONS We are left to speculate as to what the concerns of national security and law enforcement NIST refers to may be. We are deeply concerned that it is likely NIST and NSA intend to restrict use of DSS to specific conditions facilitating their own ability to "break the system." Law enforcement organizations are concerned that the plaintext version of encrypted information be obtainable by subpoena. This was established during the debate over Senate Bill 266 (see "Move on Unscrambling of Messages is Assailed," the New York Times, April 17, 1991). One may justly ask whether a future privacy standard based on DSS is in fact not NIST's intended concession to national security and law enforcement. The known concerns over obtaining plaintext, NIST's potential use of patents , and the weaknesses in DSS make this possibility difficult to ignore. Using a short comment period to avoid future scrutiny and offering only an incomplete signature proposal increases suspicions. Therefore, we must view DSS as the underlying technology for providing a standard for data privacy in the future, and ask if it is appropriate for this use. Of course, NIST could reveal its plans for a privacy feature to calm these fears. Instead, NIST states that a privacy mechanism is "years away," and will not give any indication as to its plans. If such a system becomes the de facto U.S. commercial standard, then it may indeed benefit law enforcement, albeit at the expense of the privacy of everyone. In this case, a "breakable" system is effected by forcing the use of a single number or small group of numbers that the government can "break," but that they believe no one else can. A number of the size proposed by NIST seems just about right for this scenario. As a standard for U.S. private sector, such a system gives the government unwarranted, unnecessary, and undesirable powers to violate personal privacy. Further, there is no assurance that a foreign government cannot also "break" the system, running the risk of a "digital Pearl Harbor" --- a devastating loss of the security of the entire national financial and business transaction systems. The possibility that DSS is intended to be used in this manner alone justifies congressional investigation. OTHER CONCERNS The DSS proposal states, "This proposed FIPS is the result of evaluating a number of alternative digital signature techniques. In making the selection, the NIST has followed the mandate contained in section 2 of the Computer Security Act of 1987 that NIST develop guidelines and standards to '...assure the cost-effective security and privacy of sensitive information in Federal Systems.'" We note that NIST has so far declined to identify alternative techniques it evaluated. A Freedom of Information Act request was filed in August of this year by CPSR (Computer Professionals for Social Responsibility) with NIST seeking documents related to NIST's evaluation, but NIST claims to be exempt in this case, claiming in their response that such information is "advisory and pre-decisional" as well as "related to pending patent applications." We note that NIST has made and publicized its decision and that it has also published the scheme it hopes to patent. NIST's denial of information with no apparent justification does not inspire confidence in DSS, but intensifies concern that there is a hidden agenda, such as laying the groundwork for a national public-key cryptosystem that is in fact vulnerable to being broken by NIST and/or NSA. Statements made by NIST officials in defense of DSS do not offer any clarity. According to Lynn McNulty, associate director of the National Computer Systems Laboratory at NIST, "Even if someone breaks the DSS, it is only a signature standard." ("NIST Signature Standard Whips Up Storm of Controversy from Industry," Federal Computer Week, Sep. 2, 1991.) Aside from the insight this comment may provide about the security of DSS, this statement may be misleading if NIST in fact plans to base a data privacy standard around DSS. CONCLUSIONS It is well known that the larger part of NSA's mission is to gather electronic intelligence. It is also well known that strong data encryption technology (already well known and coming into use around the world) may interfere with that mission. But electronic eavesdropping by others and industrial espionage through electronic means are also realities. The U.S., with the largest computer market in the world, is at greatest risk, and therefore has the most to gain from high quality encryption technology. Through its active promotion to industry of less than fully open programs such as CCEP (NSA's Commercial Comsec Endorsement Program), NSA has lost any credibility it may have had with the private sector. (see "A Supersecret Agency Finds Selling Secrecy to Others Isn't Easy," page 1, column 1, the Wall Street Journal, March 28, 1988.) Sadly, NIST seems to be headed down the same path. The government should be playing a leading role in advancing the U.S. information industry into the next century. The NIST proposal, with its unanswered questions, NSA origins, and questionable justification, looks backward. We would hope that with the stakes involved in the country's first government standard for public-key cryptography, NIST would "go the extra mile" to ensure the integrity of the process. Instead, NIST shuns industry cooperation and offers flawed proposals developed secretly with NSA. NIST's proposal gives industry no privacy mechanism, and has a long way to go before being usable for authentication. It is a great disappointment that a multi-year effort involving the Commerce and Defense Departments has yielded such an incomplete, flawed product. U.S. industry and the taxpayers of this country deserve better from our government. NIST is either unable or unwilling to justify its actions. Only Congress has the power to force NIST and NSA to answer critical questions about the proposed DSS. Even the most remote possibility that there is a hidden agenda behind DSS justifies congressional action. We urge you and your committee to have NIST, and, if necessary, NSA, answer important questions about their proposal or have it withdrawn. We are at the disposal of the Committee if we can be of any assistance. Respectfully, RSA Data Security, Inc. (signed) D. James Bidzos President cc: Members, Subcommittee on Technology and Competitiveness Hon. Jack Brooks, Chairman, House Committee on the Judiciary Hon. Robert Mosbacher, U.S. Secretary of Commerce Dr. Willis H. Ware, RAND Corporation  NIST's proposal is Docket No. 910807-1207, RIN 0693-AA86, "A Proposed Federal Information Processing Standard for Digital Signature Standard (DSS)." A digital signature is an electronic analogue to a handwritten signature that demonstrates the authenticity of an electronic document or message. A user "signs" a document by applying a cryptographic function to the contents of the document using a quantity known only to that user called a a "private key." Anyone can "verify" a user's digital signature on a document by applying another cryptographic function to the contents of the signed document employing the user's corresponding "public key," a quantity published and known to everyone. Digital signatures are essential for the transition of commerce from a paper-based system to electronic media.  "Furthermore, since many discrete log cryptographic schemes have the feature that they use a fixed prime which cannot easily be changed, one has to allow for attacks that consume not just a couple of months, but even a couple of years of computing time. Therefore, even 512-bit primes appear to offer only marginal security..." from "Computation of Discrete Logarithms in Prime Fields" by B. A. LaMacchia and A. M. Odlyzko, published in "Designs, Codes, and Cryptography 1" (Kluwer, 1991, pp47-62) DSS specifies a 512-bit prime modulus, and states that such a modulus can be shared by groups. This is important as the discrete log problem is known to be "brittle," meaning a table of discrete logarithms could be built, allowing an attacker to simply "look up," rather than have to "break," a user key.  NIST has stated clearly in its proposal that worldwide patents have been filed for DSS. It is not clear how NIST can justify spending tax dollars to file for worldwide patents on DSS if, as NIST claims, the goal is to grant royalty-free use of DSS. NIST need simply publish the scheme without patenting it, and save the expense. One likely reason to patent DSS is to control its use. NIST could then offer "royalty-free patent licenses to anyone who practices the standard." This would insure that no one could use DSS except as specified by NIST. Interestingly, there is precedent for precisely this approach to licensing standards.
Please report problems with the web pages to the maintainer