ftp.ee.pdx.edu/2014.02.ftp.ee.pdx.edu.tar/ftp.ee.pdx.edu/pub/lpf/bidzos.letter

Internet Message Format | 1992-11-02 | 24KB

Date: Sat, 21 Sep 91 23:04:37 -0700
From: [e-mail] (Dennis Gentry)
Return-Path: <[e-mail]>
To: [e-mail]
Subject: Letter from RSA to the chair of the House subcommitte on Technology and Competitiveness.

I thought you might be interested in this letter.  It appeared
in the risks digest recently and was forwarded to me by a friend.

Dennis

---------Begin Forwarded Message
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." [1]

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" [2].  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 [2] 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 [3],
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

[1] 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.

[2] "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.

[3] 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.


---------End Forwarded Message