Path: gmdzi!unido!mcsun!uunet!hoptoad!gnu
From: gnu@hoptoad.uucp (John Gilmore)
Newsgroups: sci.crypt,alt.privacy
Subject: NIST announces public-key signature standard
Message-ID: <18960@hoptoad.uucp>
Date: 27 Jun 91 18:35:14 GMT
Organization: Cygnus Support, Palo Alto
Lines: 97
Xref: gmdzi sci.crypt:54396 alt.privacy:917
Statement of Raymond G. Kammer, Deputy Director
National Institute of Standards and Technology
Before the Subcommittee on Technology and Competitiveness
of the Committee on Science, Space, and Technology
On Computer Security Implementation
House of Representatives
June 27, 1991
Digital Signature Standard
I know that you are interested in our progress in developing a federal
digital signature standard based upon the principles of public-key
cryptography. I am pleased to tell you that we are working out the
final arrangements on the planned standard, and hope to announce later
this summer our selection of a digital signature standard based on a
variant of the ElGamal signature technique.
Our efforts in this area have been slow, difficult, and complex.
We evaluated a number of alternative digital signature techniques, and
considered a variety of factors in this review: the level of security
provided, the ease of implementation in both hardware and software, the
ease of export from the U.S., the applicatility of patents and the level
of efficiency in both the signature and verification functions that the
technique performs.
In selecting digital signature technique method [sic], we followed the mandate
contained in section 2 of the Computer Security Act of 1987 to develop
standards and guidelines that ". . . assure the cost-effective security
and privacy of sensisive information in Federal systems." We placed
primary emphasis on selecting the technology that best assures the
appropriate security of Federal information. We were also concerned
with selecting the technique with the most desirable operating and use
characteristics.
In terms of operating characteristics, the digital signature technique
provides for a less computational-intensive signing function than
verification function. This matches up well with anticipated Federal
uses of the standard. The signing function is expected to be performed
in a relatively computationally modest environment such as with smart
cards. The verification process, however, is expected to be implemented
in a computationally rich environmnet such as on mainframe systems or
super-minicomputers.
With respect to use characteristics, the digital signature technique is
expected to be available on a royalty-free basis in the public interest
world-wide. This should result in broader use by both government and
the private sector, and bring economic benefits to both sectors.
A few details related to the selection of this technique remain to be
worked out. The government is applying to the U.S. Patent Office for a
patent, and will also seek foreign protection as appropriate. As I
stated, we intend to make the technique available world-wide on a
royalty-free basis in the public interest.
A hashing function has not been specified by NIST for use with the
digital signature standard. NIST has been reviewing various candidate
hashing functions; however, we are not satisfied with any of the
functions we have studied thus far. We will provide a hashing function
that is complementary to the standard.
I want to speak to two issues that have been raised in the public debate
over digital signature techniques. One is the allegation that a "trap
door", a method for the surreptitious defeat of the security of this
system, has been built into the technique that we are selecting. I
state categorically that no trap door has been designed into this
standard nor does the U.S. Government know of any which is inherent in
the ElGamal signature method that is the foundation of our technique.
Another issue raised is the lack of public key exchange capabilities. I
believe that, to avoid capricious activity, Public Key Exchange under
control of a certifying authority is required for government
applications. The details of such a process will be developed for
government/industry use.
NIST/NSA Technical Working Group
Aspects of digital signature standard were discussed by the NIST/NSA
Technical Working Group, established under the NIST/NSA Memorandum of
Understanding. The Working Group also discussed issues involving the
applicability of the digital signature algorithm to the classified
community, cryptographic key management techniques, and the hashing
function to be used in conjunction with the digital signature standard.
Progress on these items has taken place; however, as with the digital
signature standard, non-technical issues such as patents and
exportability require examination, and this can be a lengthy process. We
have found that working with NSA is productive. The Technical Working
Group provides an essential mechanism by which NIST and NSA can conduct
the technical discussions and exchange contemplated by the Computer
Security Act and also allows us to address important issues drawing upon
NSA's expertise.
--
John Gilmore {sun,uunet,pyramid}!hoptoad!gnu g...@toad.com g...@cygnus.com
"The Soviets believe that nothing -- like constitutional protection of
citizens' right to privacy -- must interfere with the security of the
state. ...We clearly do not want to change our societal standards to
theirs..." -- Adm. Stansfield Turner, ex-dir. CIA, _Secrecy and Democracy_
Path: gmdzi!unido!mcsun!uunet!elroy.jpl.nasa.gov!sdd.hp.com!think.com!
snorkelwacker.mit.edu!bloom-picayune.mit.edu!athena.mit.edu!jim
From: j...@chirality.rsa.com (Jim Bidzos)
Newsgroups: sci.crypt,alt.privacy
Subject: Re: NIST announces public-key signature standard
Message-ID: <JIM.91Jun27234652@chirality.rsa.com>
Date: 27 Jun 91 21:46:52 GMT
References: <18960@hoptoad.uucp>
Sender: ne...@athena.mit.edu (News system)
Organization: RSA Data Security, Inc.
Lines: 148
Xref: gmdzi sci.crypt:54402 alt.privacy:919
In-Reply-To: gnu@hoptoad.uucp's message of 27 Jun 91 18:35:14 GMT
RSA DATA SECURITY, INC. RESPONSE TO STATEMENT BY RAYMOND G. KAMMER,
DEPUTY DIRECTOR, NIST, BEFORE THE SUBCOMMITTEE ON TECHNOLOGY AND
COMPETITIVENESS ON JUNE 27, 1991
Today NIST/NSA formally presented information that is apparently the
result of the NIST and NSA collaboration on a proposal for digital
signature standard based on cryptographic techniques. Based on
activities in this area around the world, a US standard based on
public-key cryptography will have a profound effect on US industry and
will also bear directly on such issues as personal privacy and the
role of government in the affairs of individuals. Based on RSA Data
Security's expertise in cryptography and its long experience in the
application of digital signatures, we provide the following
preliminary response to Mr. Kammer's statement. A copy, in letter
form, will be mailed to all US representatives of the House Committee
on Science, Space, and Technology.
First, a correction: The technology described by Kammer has been
erroneously called a "digital signature standard" by members of the
press. Kammer's statement only offers a peek at NIST and NSA's intent
to develop a proposal for a standard, which must undergo a public
comment period, and ultimately may become a FIPS (Federal Information
Processing Standard). Since the details of the proposal are
incomplete and entire technology components are unidentified, this
statement falls far short of describing a "standard" or even a
proposal for a standard.
The first claim in Kammer's statement is that NIST/NSA "...followed
the mandate contained in section 2 of the Computer Security Act of
1987 to develop standards and guidelines that '...assure the
cost-effective security and privacy of sensitive information contained
in the Federal systems.'" The proposed algorithm fails to fully meet
the requirements Kammer himself quotes. There is NO provision for
privacy. Kammer's comments only address authentication.
Kammer's claim for the desirability of the "less
computational-intensive signing function than verification function"
of the algorithm is incredible. We have not met anyone in industry or
in government outside of NIST and NSA who agree with this. There are
no circumstances, that a long list of experts can envision, under
which they would agree with Kammer. The very use of a certificate
based key distribution system, such as the one proposed in the
Internet, guarantees that signatures will be verified more than made.
Better proof: Consider virus detection, a classic use of digital
signatures, where every computer user can apply the technology and
benefit from it. The millions of copies of Lotus 1-2-3, Microsoft
Word, and other programs that are distributed will be signature
verified by every user, perhaps daily or weekly, to detect viruses.
Yet, the master copy will be signed only once by the manufacturer! (Or
the government agency that certifies them "clean.") That's a ratio of
many millions to one (verification to actual signature) that
demonstrates the absurdity of NIST's and NSA's position. To further
demonstrate how far off base NIST/NSA are, the verification will take
place on PC's, including the hundreds of thousands of XT class
machines the US Government owns. So NIST/NSA have it backwards when
they claim signature verification will occur in a "computationally
rich environment." Certainly users will verify signatures on email at
their desktop machines.
NIST and NSA have selected a digital signature algorithm with a very
slow signature verification time, making their algorithm unsuitable
for almost all commercial applications.
NIST claims that the proposed technique is expected to be available on
a royalty-free basis. There are over one hundred patents that discuss
digital signatures, and at least two that bear directly on the
NIST/NSA algorithm. It is irresponsible and misleading for NIST to
unilaterally claim no patents apply.
No hashing function has been specified, according to NIST/NSA. We
observe that any proposed standard is literally worthless without one.
Kammer claims that no "trap door" that would allow surreptitious
defeat of the security of the system has been built in, and he states
categorically that "...no trap door has been designed into this
standard nor does the US Government know of any which is inherent in
the Elgamal signature method..."
We observe that this statement may be technically correct, but
misleading. It does not exclude the possibility of a trap door.
First, even without a specific "trap door," the possibility for
surreptitious defeat of the overall system security is in fact
inherent in the Elgamal technique. The system is typically used with
a single large prime number (the "modulus") shared by every user.
Applying large amounts of computational power to attacking this number
allows the attacker to them defeat the security of any user system
wide, at will. Note that NSA is rumored to have more computational
power than any organization in the world. It is worth noting that any
organization, not just the US Government, capable of "breaking" this
single number can surreptitiously break any part of the system. This
potential for "catastrophic failure" is perhaps the main reason
Elgamal is virtually nonexistent in systems. We note that the RSA
algorithm does not suffer from these weaknesses, where the keys of
every individual user must be attacked separately.
The common number, or modulus, may be composite, in which case
supplying that number after carefully "constructing" it eliminates the
need to even attack it. This can be easily confirmed by any
cryptographer familiar with the literature. Thus the "trap door" is
not part of the standard itself, but built into the common number.
Perhaps NIST/NSA can assure us that such a shared number will not be
used, and each user will generate their own, in which case the system
becomes more secure.
Although Kammer mentions the relevance of exportability, he does not
discuss this issue further, except to say he expects the system to be
used world-wide. This clearly implies that the government expects to
derive every users' secret keys from their public keys; otherwise
these keys could be used as a basis for an encryption scheme that
exceeds normal export restrictions.
It is ironic that Kammer's statement was made to the Subcommittee on
Technology and Competitiveness. Standards for digital signatures have
been proposed or developed by SWIFT, DARPA's Internet, the French
Banks, ISO, Standards Australia, and a significant part of the US
computer industry, including Microsoft, Lotus, and Novell. Every one
of them either specify the RSA algorithm or have requirements that RSA
meets but the NIST/NSA algorithm does not. Over 70 companies in the US
alone have made considerable investments of time and money
implementing the RSA cryptosystem in their products, including
Motorola, the US arm of Northern Telecom, Digital Equipment
Corporation, and three of four largest software companies in the
world. Of course, their foreign competitors have as well. No one has
proposed or is using the NIST/NSA algorithm. Whose competitiveness
are NIST and NSA concerned about? Expect a strong response to the
Subcommittee from industry.
In fact, ISO is voting on their digital signature standard (for which
the NIST/NSA algorithm would not qualify, on technical merits) on June
30th, in two days. This timing makes the NIST/NSA action particularly
interesting. It would be informative if the press were able to report
on who represents the US and how they vote.
RSA Data Security will soon be making a white paper available which
compares the Elgamal scheme with other available schemes, and will
give a preliminary analysis as to why the Elgamal scheme is unsuitable
for a federal or industry standard. A thorough analysis will, of
course, have to wait until NIST/NSA make public the details of their
proposal.
Based on what is known at present, however, we expect that NIST and
NSA are likely to propose a scheme that is an engineering albatross,
covered by prior patents, containing a common-modulus trap door, that
fails to recognize current widespread industry practices.
RSA Data Security, Inc.
Path: gmdzi!unido!mcsun!uunet!cis.ohio-state.edu!ucbvax!ulysses!
ulysses.att.com!smb
From: s...@ulysses.att.com (Steven Bellovin)
Newsgroups: sci.crypt,alt.privacy
Subject: Re: NIST announces public-key signature standard
Message-ID: <15065@ulysses.att.com>
Date: 28 Jun 91 16:46:33 GMT
References: <18960@hoptoad.uucp> <JIM.91Jun27235056@chirality.rsa.com>
Sender: net...@ulysses.att.com
Lines: 16
Xref: gmdzi sci.crypt:54409 alt.privacy:928
In article <JIM.91Ju...@chirality.rsa.com>,
j...@chirality.rsa.com (Jim Bidzos) writes:
> RSA DATA SECURITY, INC. RESPONSE TO STATEMENT BY RAYMOND G. KAMMER,
> DEPUTY DIRECTOR, NIST, BEFORE THE SUBCOMMITTEE ON TECHNOLOGY AND
> COMPETITIVENESS ON JUNE 27, 1991
....
> The common number, or modulus, may be composite, in which case
> supplying that number after carefully "constructing" it eliminates the
> need to even attack it.
Is this really a feasible trapdoor? Given the number of primality-testing
algorithms available, I would think that someone would be able to learn
that soon enough. I suppose it's conceivable that NSA has found a
large pseudo-prime that isn't caught by any of the currently-known good
algorithms, but it's still a hell of risk for them to take.
Path: gmdzi!unido!mcsun!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!
think.com!snorkelwacker.mit.edu!bloom-picayune.mit.edu!athena.mit.edu!jim
From: j...@chirality.rsa.com (Jim Bidzos)
Newsgroups: sci.crypt,alt.privacy
Subject: Re: NIST announces public-key signature standard
Message-ID: <JIM.91Jun28112107@chirality.rsa.com>
Date: 28 Jun 91 09:21:07 GMT
References: <18960@hoptoad.uucp> <JIM.91Jun27235056@chirality.rsa.com>
<15065@ulysses.att.com>
Sender: ne...@athena.mit.edu (News system)
Organization: RSA Data Security, Inc.
Lines: 4
Xref: gmdzi sci.crypt:54410 alt.privacy:930
In-Reply-To: smb@ulysses.att.com's message of 28 Jun 91 16:46:33 GMT
The composite could be large enough to make factorization infeasible,
and consist of just the right number of primes, each just the right
size. Unless you can factor it, you can't prove anything.
Path: gmdzi!unido!mcsun!uunet!spool.mu.edu!sdd.hp.com!think.com!paperboy!
hsdndev!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brn...@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: sci.crypt,alt.privacy
Subject: Re: NIST announces public-key signature standard
Message-ID: <25630.Jun2821.25.5591@kramden.acf.nyu.edu>
Date: 28 Jun 91 21:25:55 GMT
References: <JIM.91Jun27235056@chirality.rsa.com> <15065@ulysses.att.com>
<JIM.91Jun28112107@chirality.rsa.com>
Organization: IR
Lines: 27
Xref: gmdzi sci.crypt:54414 alt.privacy:933
In article <JIM.91Ju...@chirality.rsa.com>
j...@chirality.rsa.com (Jim Bidzos) writes:
> The composite could be large enough to make factorization infeasible,
> and consist of just the right number of primes, each just the right
> size. Unless you can factor it, you can't prove anything.
You don't understand what Steve said.
Nobody has to factor the number. All it takes is a few random tries of
some primality test, say the Miller test. No matter what composite the
NSA chooses, there is a chance larger than 0.999 that someone applying
ten random Miller rounds will conclusively prove the number composite.
To avoid detection they'd have to know what random numbers people were
going to choose for the test, and that's simply impossible.
So everyone will end up screaming at the NSA, asking why they didn't use
a prime number and demanding to know how they chose the factors of the
composite. Everyone will assume that a trap door is built in.
In other words, this isn't a practical scheme for the NSA. The system
simply does not lend itself to trap doors, at least not in the way you
claimed.
Of course, you're probably going to say it does in your ``analysis'' of
public-key systems, because you'll do anything to make RSA look better
than it really is. Have fun making a fool of yourself.
---Dan
Path: gmdzi!unido!mcsun!uunet!zaphod.mps.ohio-state.edu!think.com!
snorkelwacker.mit.edu!bloom-picayune.mit.edu!athena.mit.edu!jim
From: j...@chirality.rsa.com (Jim Bidzos)
Newsgroups: sci.crypt,alt.privacy
Subject: Re: NIST announces public-key signature standard
Message-ID: <JIM.91Jun30232518@chirality.rsa.com>
Date: 30 Jun 91 21:25:18 GMT
References: <18960@hoptoad.uucp> <JIM.91Jun27235056@chirality.rsa.com>
<15065@ulysses.att.com>
Sender: ne...@athena.mit.edu (News system)
Organization: RSA Data Security, Inc.
Lines: 54
Xref: gmdzi sci.crypt:54430 alt.privacy:941
In-Reply-To: smb@ulysses.att.com's message of 28 Jun 91 16:46:33 GMT
Bernstein writes:
> You don't understand what Steve said.
You don't understand what I said. Given a composite modulus, you
can't "prove" that there is a trapdoor, you can only suspect and
accuse. This assumes that NSA would not explain why and how they
chose a composite modulus; I don't claim they will try to hide whether
it's prime or composite. Let Steven ask his own questions.
> In other words, this isn't a practical scheme for the NSA. The
> system simply does not lend itself to trap doors, at least not in
> way you claimed.
If a composite modulus n is the product of 3 primes around 80 or 90
digits each, then one could use CRT to reduce taking discrete logs mod
n to the task of computing discrete logs separately mod p1, mod p2,
and mod p3, which is feasible for an organization with the suspected
computing power of NSA. The primes are big enough that no one should
find them using ECM factorization. Unless you can factor n, you're
left to compute discrete logs mod the much larger n, which should be
infeasible. Then the "supplier" of n simply refuse to answer questions
about it. Sounds pretty practical to me.
This behaviour is consistent with their position on DES, making it
politically practical as well, from their point of view. They
declined to discuss their rationale for the structure of the S-Boxes,
the choice of key size, and they simply didn't respond to Diffie and
Hellman's proposed DES breaking machine. People suspected DES had a
trap door but that hasn't stopped a lot of people from using it, nor
did it prevent it becoming a national standard. Based on experience,
they have every reason to believe the approach described above will
succeed.
A soon-to-be-published paper (weeks) will show how it may be possible
to choose a prime modulus p such that p-1 has no small prime factors
but does have a nonobvious structure (which would be computationally
infeasible to discover) that makes taking discrete logs mod p easy for
the one who chooses p.
So if there is a common modulus, prime or composite, and it is
"supplied" as part of the standard, one could suspect a trap door
exists, but not be able to prove it.
> ...you'll do anything to make RSA look better than it really is.
If the issue is whether a national cryptographic standard should have
a government trap door, then RSA is a better choice than the NIST
proposal for those who don't want a trap door (and a better choice for
reasons of performance and versatility) regardless of what I say or
do.
Perhaps you can prove otherwise.