RSA Cryptography Today FAQ (3/3)
Archive-name: cryptography-faq/rsa/part3
Last-modified: 93/09/20
Version: 2.0
Distribution-agent: tmp@netcom.com
(This document has been brought to you in part by CRAM. See the
bottom for more information, including instructions on how to
obtain updates.)
===
Answers To
FREQUENTLY ASKED QUESTIONS
About Today's Cryptography
Paul Fahn
RSA Laboratories
100 Marine Parkway
Redwood City, CA 94065
Copyright (c) 1993 RSA Laboratories, a division of RSA Data Security,
Inc. All rights reserved.
Version 2.0, draft 2f
Last update: September 20, 1993
------------------------------------------------------------------------
Table of Contents
[part 3]
6 Capstone, Clipper, and DSS
6.1 What is Capstone?
6.2 What is Clipper?
6.3 How does the Clipper chip work?
6.4 Who are the escrow agencies?
6.5 What is Skipjack?
6.6 Why is Clipper controversial?
6.7 What is the current status of Clipper?
6.8 What is DSS?
6.9 Is DSS secure?
6.10 Is use of DSS covered by any patents?
6.11 What is the current status of DSS?
7 NIST and NSA
7.1 What is NIST?
7.2 What role does NIST play in cryptography?
7.3 What is the NSA?
7.4 What role does the NSA play in commercial cryptography?
8 Miscellaneous
8.1 What is the legal status of documents signed with digital
signatures?
8.2 What is a hash function? What is a message digest?
8.3 What are MD2, MD4 and MD5?
8.4 What is SHS?
8.5 What is Kerberos?
8.6 What are RC2 and RC4?
8.7 What is PEM?
8.8 What is RIPEM?
8.9 What is PKCS?
8.10 What is RSAREF?
--------------------------------------------------------------------
6 Capstone, Clipper, and DSS
6.1 What is Capstone?
Capstone is the U.S. government's long-term project to develop a set
of standards for publicly-available cryptography, as authorized by
the Computer Security Act of 1987. The primary agencies responsible
for Capstone are NIST and the NSA (see Section 7). The plan calls for
the elements of Capstone to become official U.S. government standards,
in which case both the government itself and all private companies doing
business with the government would be required to use Capstone.
There are four major components of Capstone: a bulk data encryption
algorithm, a digital signature algorithm, a key exchange protocol, and
a hash function. The data encryption algorithm is called Skipjack (see
Question 6.5), but is often referred to as Clipper, which is the
encryption chip that includes Skipjack (see Question 6.2). The digital
signature algorithm is DSS (see Question 6.8) and the hash function is
SHS (see Question 8.4 about SHS and Question 8.2 about hash functions).
The key exchange protocol has not yet been announced.
All the parts of Capstone have 80-bit security: all the keys involved
are 80 bits long and other aspects are also designed to withstand
anything less than an ``80-bit'' attack, that is, an effort of 2^{80}
operations. Eventually the government plans to place the entire Capstone
cryptographic system on a single chip.
6.2 What is Clipper?
Clipper is an encryption chip developed and sponsored by the U.S.
government as part of the Capstone project (see Question 6.1).
Announced by the White House in April, 1993 [65], Clipper was designed
to balance the competing concerns of federal law-enforcement agencies
with those of private citizens and industry. The law-enforcement
agencies wish to have access to the communications of suspected
criminals, for example by wire-tapping; these needs are threatened by
secure cryptography. Industry and individual citizens, however, want
secure communications, and look to cryptography to provide it.
Clipper technology attempts to balance these needs by using escrowed
keys. The idea is that communications would be encrypted with a
secure algorithm, but the keys would be kept by one or more third
parties (the ``escrow agencies''), and made available to law-enforcement
agencies when authorized by a court-issued warrant. Thus, for
example, personal communications would be impervious to recreational
eavesdroppers, and commercial communications would be impervious to
industrial espionage, and yet the FBI could listen in on suspected
terrorists or gangsters.
Clipper has been proposed as a U.S. government standard [62]; it would
then be used by anyone doing business with the federal government as well
as for communications within the government. For anyone else, use of
Clipper is strictly voluntary. AT&T has announced a secure telephone
that uses the Clipper chip.
6.3 How does the Clipper chip work?
The Clipper chip contains an encryption algorithm called Skipjack (see
Question 6.5}), whose details have not been made public. Each chip
also contains a unique 80-bit unit key U, which is escrowed in two parts
at two escrow agencies; both parts must be known in order to recover the
key. Also present is a serial number and an 80-bit ``family key'' F; the
latter is common to all Clipper chips. The chip is manufactured so that it
cannot be reverse engineered; this means that the Skipjack algorithm and
the keys cannot be read off the chip.
When two devices wish to communicate, they first agree on an 80-bit
``session key'' K. The method by which they choose this key is left
up to the implementer's discretion; a public-key method such as RSA or
Diffie-Hellman seems a likely choice. The message is encrypted with
the key K and sent; note that the key K is not escrowed. In addition
to the encrypted message, another piece of data, called the law-enforcement
access field (LEAF), is created and sent. It includes the session key K
encrypted with the unit key U, then concatenated with the serial number
of the sender and an authentication string, and then, finally, all encrypted
with the family key. The exact details of the law-enforcement field are
classified.
The receiver decrypts the law-enforcement field, checks the authentication
string, and decrypts the message with the key K.
Now suppose a law-enforcement agency wishes to tap the line. It uses the
family key to decrypt the law-enforcement field; the agency now knows the
serial number and has an encrypted version of the session key. It presents
an authorization warrant to the two escrow agencies along with the serial
number. The escrow agencies give the two parts of the unit key to the
law-enforcement agency, which then decrypts to obtain the session key K.
Now the agency can use K to decrypt the actual message.
Further details on the Clipper chip operation, such as the generation
of the unit key, are sketched by Denning [26].
6.4 Who are the escrow agencies?
It has not yet been decided which organizations will serve as the escrow
agencies, that is, keep the Clipper chip keys. No law-enforcement agency
will be an escrow agency, and it is possible that at least one of the
escrow agencies will be an organization outside the government.
It is essential that the escrow agencies keep the key databases
extremely secure, since unauthorized access to both escrow
databases could allow unauthorized eavesdropping on private
communications. In fact, the escrow agencies are likely to be one
of the major targets for anyone trying to compromise the Clipper
system; the Clipper chip factory is another likely target.
6.5 What is Skipjack?
Skipjack is the encryption algorithm contained in the Clipper chip; it was
designed by the NSA. It uses an 80-bit key to encrypt 64-bit blocks of data;
the same key is used for the decryption. Skipjack can be used in the same
modes as DES (see Question 5.3), and may be more secure than DES, since
it uses 80-bit keys and scrambles the data for 32 steps, or ``rounds''; by
contrast, DES uses 56-bit keys and scrambles the data for only 16 rounds.
The details of Skipjack are classified. The decision not to make the details
of the algorithm publicly available has been widely criticized. Many people
are suspicious that Skipjack is not secure, either due to oversight by its
designers, or by the deliberate introduction of a secret trapdoor. By contrast,
there have been many attempts to find weaknesses in DES over the years, since
its details are public. These numerous attempts (and the fact that they have
failed) have made people confident in the security of DES. Since Skipjack is
not public, the same scrutiny cannot be applied towards it, and thus a
corresponding level of confidence may not arise.
Aware of such criticism, the government invited a small group of independent
cryptographers to examine the Skipjack algorithm. They issued a report
[12] which stated that, although their study was too limited to reach a
definitive conclusion, they nevertheless believe that Skipjack is secure.
Another consequence of Skipjack's classified status is that it cannot
be implemented in software, but only in hardware by government-authorized
chip manufacturers.
6.6 Why is Clipper controversial?
The Clipper chip proposal has aroused much controversy and has been the
subject of much criticism. Unfortunately two distinct issues have become
confused in the large volume of public comment and discussion.
First there is controversy about the whole idea of escrowed keys.
Those in favor of escrowed keys see it as a way to provide secure
communications for the public at large while allowing law-enforcement
agencies to monitor the communications of suspected criminals. Those
opposed to escrowed keys see it as an unnecessary and ineffective
intrusion of the government into the private lives of citizens. They
argue that escrowed keys infringe their rights of privacy and free
speech. It will take a lot of time and much public discussion for society
to reach a consensus on what role, if any, escrowed keys should have.
The second area of controversy concerns various objections to the
specific Clipper proposal, that is, objections to this particular
implementation of escrowed keys, as opposed to the idea of escrowed
keys in general. Common objections include: the Skipjack algorithm
is not public (see Questions 6.5) and may not be secure; the key
escrow agencies will be vulnerable to attack; there are not enough
key escrow agencies; the keys on the Clipper chips are not generated
in a sufficiently secure fashion; there will not be sufficient
competition among implementers, resulting in expensive and slow chips;
software implementations are not possible; and the key size is fixed
and cannot be increased if necessary.
Micali [55] has recently proposed an alternative system that also
attempts to balance the privacy concerns of law-abiding citizens with
the investigative concerns of law-enforcement agencies. Called fair
public-key cryptography, it is similar in function and purpose to the
Clipper chip proposal but users can choose their own keys, which they
register with the escrow agencies. Also, the system does not require
secure hardware, and can be implemented completely in software.
6.7 What is the current status of Clipper?
Clipper is under review. Both the executive branch and Congress are
considering it, and an advisory panel recently recommended a full
year-long public discussion of cryptography policy. NIST has invited
the public to send comments, as part of its own review.
6.8 What is DSS?
DSS is the proposed Digital Signature Standard, which specifies a
Digital Signature Algorithm (DSA), and is a part of the U.S. government's
Capstone project (see Question 6.1). It was selected by NIST,
in cooperation with the NSA (see Section 7), to be the digital
authentication standard of the U.S. government; whether the government
should in fact adopt it as the official standard is still
under debate.
DSS is based on the discrete log problem (see Question 4.9) and derives
from cryptosystems proposed by Schnorr [75] and ElGamal [30]. It is for
authentication only. For a detailed description of DSS, see [63] or [57].
DSS has, for the most part, been looked upon unfavorably by the computer
industry, much of which had hoped the government would choose the RSA
algorithm as the official standard; RSA is the most widely used
authentication algorithm. Several articles in the press, such as [54],
discuss the industry dissatisfaction with DSS. Criticism of DSS has
focused on a few main issues: it lacks key exchange capability; the
underlying cryptosystem is too recent and has been subject to too little
scrutiny for users to be confident of its strength; verification of
signatures with DSS is too slow; the existence of a second authentication
standard will cause hardship to computer hardware and software vendors, who
have already standardized on RSA; and that the process by which NIST chose
DSS was too secretive and arbitrary, with too much influence wielded by NSA.
Other criticisms were addressed by NIST by modifying the original proposal.
A more detailed discussion of the various criticisms can be found in
[57], and a detailed response by NIST can be found in [78].
In the DSS system, signature generation is faster than signature
verification, whereas in the RSA system, signature verification is
faster than signature generation (if the public and private exponents
are chosen for this property, which is the usual case). NIST claims
that it is an advantage of DSS that signing is faster, but many people
in cryptography think that it is better for verification to be the
faster operation.
6.9 Is DSS secure?
The most serious criticisms of DSS involve its security. DSS was originally
proposed with a fixed 512-bit key size. After much criticism that this is
not secure enough, NIST revised DSS to allow key sizes up to 1024 bits. More
critical, however, is the fact that DSS has not been around long enough to
withstand repeated attempts to break it; although the discrete log problem
is old, the particular form of the problem used in DSS was first proposed
for cryptographic use in 1989 by Schnorr [75] and has not received much
public study. In general, any new cryptosystem could have serious flaws
that are only discovered after years of scrutiny by cryptographers. Indeed
this has happened many times in the past; see [13] for some detailed
examples. RSA has withstood over 15 years of vigorous examination for
weaknesses. In the absence of mathematical proofs of security, nothing
builds confidence in a cryptosystem like sustained attempts to crack it.
Although DSS may well turn out to be a strong cryptosystem, its relatively
short history will leave doubts for years to come.
Some researchers warned about the existence of ``trapdoor'' primes in
DSS, which could enable a key to be easily broken. These trapdoor primes
are relatively rare however, and are easily avoided if proper key
generation procedures are followed [78].
6.10 Is use of DSS covered by any patents?
NIST has filed a patent application for DSS and there have been claims that
DSS is covered by other public-key patents. NIST recently announced its
intention to grant exclusive sublicensing rights for the DSS patent to Public
Key Partners (PKP), which also holds the sublicensing rights to other patents
that may cover DSS (see Question 1.5). In the agreement between NIST and
PKP, PKP publicly stated uniform guidelines by which it will grant licenses
to practice DSS. PKP stated that DSS can be used on a royalty-free basis
in the case of personal, noncommercial, or U.S. government use. See [61]
for details on the agreement and the licensing policy.
6.11 What is the current status of DSS?
After NIST issued the DSS proposal in August 1991, there was a period
in which comments from the public were solicited; NIST then revised its
proposal in light of the comments. DSS may be issued as a FIPS and become
the official U.S. government standard, but it is not clear when this
might happen. DSS is currently in the process of becoming a standard,
along with RSA, for the financial services industry; a recent draft
standard [1] contains the revised version of DSS.
7 NIST and NSA
7.1 What is NIST?
NIST is an acronym for the National Institute of Standards and Technology,
a division of the U.S. Department of Commerce; it was formerly known as
the National Bureau of Standards (NBS). Through its Computer Systems
Laboratory it aims to promote open systems and interoperability that
will spur development of computer-based economic activity. NIST issues
standards and guidelines that it hopes will be adopted by all computer
systems in the U.S., and also sponsors workshops and seminars. Official
standards are published as FIPS (Federal Information Processing Standards)
publications.
In 1987 Congress passed the Computer Security Act, which authorized NIST
to develop standards for ensuring the security of sensitive but unclassified
information in government computer systems. It encouraged NIST to work with
other government agencies and private industry in evaluating proposed
computer security standards.
7.2 What role does NIST play in cryptography?
NIST issues standards for cryptographic routines; U.S. government agencies
are required to use them, and the private sector often adopts them as well.
In January 1977, NIST declared DES (see Question 5.1) the official U.S.
encryption standard and published it as FIPS Publication 46; DES soon
became a de facto standard throughout the U.S.
A few years ago, NIST was asked to choose a set of cryptographic standards
for the U.S.; this has become known as the Capstone project (see Section
6). After a few years of rather secretive deliberations, and in cooperation
with the NSA, NIST issued proposals for various standards in cryptography,
including digital signatures (DSS) and data encryption (the Clipper chip);
these are pieces of the overall Capstone project.
NIST has been criticized for allowing the NSA too much power in setting
cryptographic standards, since the interests of the NSA conflict with that
of the Commerce Department and NIST. Yet, the NSA has much more experience
with cryptography, and many more qualified cryptographers and cryptanalysts,
than does NIST; it would be unrealistic to expect NIST to forego such
available assistance.
7.3 What is the NSA?
The NSA is the National Security Agency, a highly secretive agency of the
U.S. government that was created by Harry Truman in 1952; its very existence
was kept secret for many years. For a history of the NSA, see Bamford [2].
The NSA has a mandate to listen to and decode all foreign communications of
interest to the security of the United States. It has also used its power
in various ways (see Question 7.4) to slow the spread of publicly available
cryptography, in order to prevent national enemies from employing encryption
methods too strong for the NSA to break.
As the premier cryptographic government agency, the NSA has huge financial
and computer resources and employs a host of cryptographers. Developments in
cryptography achieved at the NSA are not made public; this secrecy has led to
many rumors about the NSA's ability to break popular cryptosystems like DES
and also to rumors that the NSA has secretly placed weaknesses, called trap
doors, in government-endorsed cryptosystems, such as DES. These rumors have
never been proved or disproved, and the criteria used by the NSA in selecting
cryptography standards have never been made public.
Recent advances in the computer and telecommunications industries have
placed NSA actions under unprecedented scrutiny, and the agency has become
the target of heavy criticism for hindering U.S. industries that wish to use
or sell strong cryptographic tools. The two main reasons for this increased
criticism are the collapse of the Soviet Union and the development and
spread of commercially available public-key cryptographic tools. Under
pressure, the NSA may be forced to change its policies.
7.4 What role does the NSA play in commercial cryptography?
The NSA's charter limits its activities to foreign intelligence. However,
the NSA is concerned with the development of commercial cryptography
because the availability of strong encryption tools through commercial
channels could impede the NSA's mission of decoding international
communications; in other words, the NSA is worried lest strong commercial
cryptography fall into the wrong hands.
The NSA has stated that it has no objection to the use of secure cryptography
by U.S. industry. It also has no objection to cryptographic tools used for
authentication, as opposed to privacy. However, the NSA is widely viewed as
following policies that have the practical effect of limiting and/or weakening
the cryptographic tools used by law-abiding U.S. citizens and corporations;
see Barlow [3] for a discussion of NSA's effect on commercial
cryptography.
The NSA exerts influence over commercial cryptography in several ways.
First, it controls the export of cryptography from the U.S. (see Question
1.6); the NSA generally does not approve export of products used for
encryption unless the key size is strictly limited. It does, however,
approve for export any products used for authentication only, no matter
how large the key size, so long as the product cannot be converted to be
used for encryption. The NSA has also blocked encryption methods from being
published or patented, citing a national security threat; see Landau [46]
for a discussion of this practice. Additionally, the NSA serves an
``advisory'' role to NIST in the evaluation and selection of official U.S.
government computer security standards; in this capacity, it has played a
prominent, and controversial, role in the selection of DES and in the
development of the group of standards known as the Capstone project (see
Section 6), which includes DSS and the Clipper chip. The NSA can also
exert market pressure on U.S. companies to produce (or refrain from
producing) cryptographic goods, since the NSA itself is often a large
customer of these companies.
Cryptography is in the public eye as never before and has become the subject
of national public debate. The status of cryptography, and the NSA's role
in it, will probably change over the next few years.
8 Miscellaneous
8.1 What is the legal status of documents signed with digital signatures?
If digital signatures are to replace handwritten signatures they must have
the same legal status as handwritten signatures, i.e., documents signed
with digital signatures must be legally binding. NIST has stated that its
proposed Digital Signature Standard (see Question 6.8) should be capable
of ``proving to a third party that data was actually signed by the
generator of the signature.'' Furthermore, U.S. federal government
purchase orders will be signed by any such standard; this implies that
the government will support the legal authority of digital signatures
in the courts. Some preliminary legal research has also resulted in the
opinion that digital signatures would meet the requirements of legally
binding signatures for most purposes, including commercial use as defined
in the Uniform Commercial Code (UCC). A GAO (Government Accounting
Office) decision requested by NIST also opines that digital signatures
will meet the legal standards of handwritten signatures [20].
However, since the validity of documents with digital signatures has never
been challenged in court, their legal status is not yet well-defined.
Through such challenges, the courts will issue rulings that collectively
define which digital signature methods, key sizes, and security precautions
are acceptable for a digital signature to be legally binding.
Digital signatures have the potential to possess greater legal authority
than handwritten signatures. If a ten-page contract is signed by hand on
the tenth page, one cannot be sure that the first nine pages have not
been altered. If the contract was signed by digital signatures, however,
a third party can verify that not one byte of the contract has been altered.
Currently, if two people wish to digitally sign a series of contracts,
they may wish to first sign a paper contract in which they agree to be bound
in the future by any contracts digitally signed by them with a given
signature method and minimum key size.
8.2 What is a hash function? What is a message digest?
A hash function is a computation that takes a variable-size input and returns
a fixed-size string, which is called the hash value. If the hash function
is one-way, i.e., hard to invert, it is also called a message-digest function,
and the result is called a message digest. The idea is that a digest
represents concisely the longer message or document from which it was
computed; one can think of a message digest as a ``digital fingerprint'' of
the larger document. Examples of well-known hash functions are MD4, MD5,
and SHS (see Questions 8.3 and 8.4).
Although hash functions in general have many uses in computer programs, in
cryptography they are used to generate a small string (the message digest)
that can represent securely a much larger string, such as a file or message.
Since the hash functions are faster than the signing functions, it is much
more efficient to compute a digital signature using a document's message
digest, which is small, than using the arbitrarily large document itself.
Additionally, a digest can be made public without revealing the contents of
the document from which it derives. This is important in digital
time-stamping, where, using hash functions, one can get a document
time-stamped without revealing its contents to the time-stamping service
(see Question 3.18).
A hash function used for digital authentication must have certain
properties that make it secure enough for cryptographic use. Specifically,
it must be infeasible to find a message that hashes to a given value
and it must be infeasible to find two distinct messages that hash to
the same value. The ability to find a message hashing to a given value
would enable an attacker to substitute a fake message for a real message
that was signed. It would also enable someone to falsely disown a
message by claiming that he or she actually signed a different message
hashing to the same value, thus violating the non-repudiation property
of digital signatures. The ability to find two distinct messages hashing
to the same value could enable an attack whereby someone is tricked into
signing a message which hashes to the same value as another message with
a quite different meaning. The digest must therefore be long enough to
prevent an attacker from doing an exhaustive search for a collision. For
example, if a hash function produces 100-bit strings, exhaustive search
would take 2^{100} attempts on average to match a given value, and
approximately 2^{50} attempts on average to find two inputs producing
the same digest.
A digital signature system can be broken by attacking either the difficult
mathematical problem on which the signature method is based or the hash
function used to create the message digests. When choosing an authentication
system, it is generally a good idea to choose a signature method and a hash
function that require comparable efforts to break; any extra security in one
of the two components is wasted, since attacks will be directed at the weaker
component. Actually, attacking the hash function is harder in practice, since
it requires a large amount of memory and the ability to trick the victim into
signing a special message. With 2^{64} operations, an attacker can find two
messages that hash to the same digest under any of the MD hash functions;
this effort is comparable to that necessary to break 512-bit RSA; thus MD5 is
a good choice when using RSA with a 512-bit modulus. However, those with
greater security needs, such as certifying authorities, should use a longer
modulus and a hash function that produces a longer message digest; either SHS
(160-bit digest) or a modified version of MD4 that produces a 256-bit digest
[71] would suffice.
8.3 What are MD2, MD4 and MD5?
MD2, MD4 and MD5 (MD stands for Message Digest) are widely used hash
functions designed by Ron Rivest specifically for cryptographic use.
They produce 128-bit digests and there is no known attack faster than
exhaustive search.
MD2 is the slowest of the three; MD4 [71] is the fastest. MD5 [73]
has been dubbed ``MD4 with safety belts'' by Rivest, since it has a
more conservative design than MD4; the design gives it increased
security against attack, but at a cost of being approximately 33%
slower than MD4. MD5 is the most commonly used of the three algorithms.
MD4 and MD5 are publicly available for unrestricted use; MD2 is available
for use with PEM (see Question 8.7). Details of MD2, MD4, and MD5 with
sample C code are available in Internet RFCs (Requests For Comments)
1319, 1320, and 1321, respectively.
No feasible attacks on any of the MD algorithms have been discovered,
although some recent theoretical work has found some interesting
structural properties [24,25].
8.4 What is SHS?
The Secure Hash Standard (SHS) [58] is a hash function proposed by NIST
(see Question 7.1) and adopted as a U.S. government standard. It is
designed for use with the proposed Digital Signature Standard (see
Question 6.8) and is part of the government's Capstone project (see
Question 6.1}). SHS produces a 160-bit hash value from a variable-size
input. SHS is structurally similar to MD4 and MD5. It is roughly 25%
slower than MD5 but may be more secure, because it produces message
digests that are 25% longer than those produced by the MD functions.
SHS is currently the only part of Capstone that has been officially
adopted as a government standard.
8.5 What is Kerberos?
Kerberos is a secret-key network authentication system developed at MIT
[79]; it uses DES for encryption and authentication. Unlike a public-key
authentication system, it does not produce digital signatures: Kerberos
was designed to authenticate requests for network resources rather than
to authenticate authorship of documents. Kerberos provides real-time
authentication in a distributed environment, but does not provide for
future third-party verification of documents.
In a Kerberos system, there is a designated site on the network, called
the Kerberos server, which performs centralized key management and
administrative functions. The server maintains a database containing the
secret keys of all users, generates session keys whenever two users wish to
communicate securely, and authenticates the identity of a user who requests
certain network services.
Kerberos, like other secret-key systems, requires trust in a third party,
in this case the Kerberos server. If the server were compromised, the
integrity of the whole system would fall. Public-key cryptography was
designed precisely to avoid the necessity to trust third parties or
communication lines (see Question 1.4). Kerberos may be adequate
for those who do not need the more robust functions and properties of
public-key systems.
8.6 What are RC2 and RC4?
RC2 and RC4 are variable-key-size cipher functions designed by Ron Rivest
for fast bulk encryption. They are alternatives to DES (see Question
5.1) and are as fast or faster than DES. They can be more secure than
DES because of their ability to use long key sizes; they can also be less
secure than DES if short key sizes are used.
RC2 is a variable-key-size symmetric block cipher and can serve as a drop-in
replacement for DES, for example in export versions of products otherwise
using DES. RC2 can be used in the same modes as DES (see Question 5.3),
including triple encryption. RC2 is approximately twice as fast as DES,
at least in software. RC4 is a variable-key-size symmetric stream cipher
and is 10 or more times as fast as DES in software. Both RC2 and RC4 are
very compact in terms of code size.
An agreement between the Software Publishers Association (SPA) and the U.S.
government gives RC2 and RC4 special status by means of which the export
approval process is simpler and quicker than the usual cryptographic export
process. However, to qualify for quick export approval a product must limit
the RC2 and RC4 key sizes to 40 bits; 56 bits is allowed for foreign
subsidiaries and overseas offices of U.S. companies. An additional 40-bit
string, called a salt, can be used to thwart attackers who try to
precompute a large look-up table of possible encryptions. The salt is
appended to the encryption key, and this lengthened key is used to encrypt
the message; the salt is then sent, unencrypted, with the message. RC2 and
RC4 have been widely used by developers who want to export their products;
DES is almost never approved for export. RC2 and RC4 are proprietary
algorithms of RSA Data Security, Inc.; details have not been published.
8.7 What is PEM?
PEM is the Internet Privacy-Enhanced Mail standard, designed, proposed, but
not yet officially adopted, by the Internet Activities Board in order to
provide secure electronic mail over the Internet. Designed to work with
current Internet e-mail formats, PEM includes encryption, authentication,
and key management, and allows use of both public-key and secret-key
cryptosystems. Multiple cryptographic tools are supported: for each mail
message, the specific encryption algorithm, digital signature algorithm,
hash function, and so on are specified in the header. PEM explicitly
supports only a few cryptographic algorithms; others may be added later.
DES in CBC mode is currently the only message encryption algorithm supported,
and both RSA and DES are supported for the key management. PEM also supports
the use of certificates, endorsing the CCITT X.509 standard for certificate
structure.
The details of PEM can be found in Internet RFCs (Requests For Comments)
1421 through 1424. PEM is likely to be officially adopted by the Internet
Activities Board within one year. Trusted Information Systems has developed
a free non-commercial implementation of PEM, and other implementations should
soon be available as well.
8.8 What is RIPEM?
RIPEM is a program developed by Mark Riordan that enables secure Internet
e-mail; it provides both encryption and digital signatures, using RSA and
DES routines from RSAREF (see Question 8.10). RIPEM is not fully
PEM-compatible; for example, it does not currently support certificates.
However, future versions will include certificates and will be fully
compliant with the PEM standard. RIPEM is available free for non-commercial
use in the U.S. and Canada. To get RIPEM, obtain an ftp account at
ripem.msu.edu.
8.9 What is PKCS?
PKCS (Public-Key Cryptography Standards) is a set of standards for
implementation of public-key cryptography. It has been issued by RSA
Data Security, Inc. in cooperation with a computer industry consortium,
including Apple, Microsoft, DEC, Lotus, Sun and MIT. PKCS has been cited
by the OIW (OSI Implementors' Workshop) as a method for implementation of
OSI standards. PKCS is compatible with PEM (see Question 8.7) but extends
beyond PEM. For example, where PEM can only handle ASCII data, PKCS is
designed for binary data as well. PKCS is also compatible with the CCITT
X.509 standard.
PKCS includes both algorithm-specific and algorithm-independent
implementation standards. Specific algorithms supported include RSA, DES,
and Diffie-Hellman key exchange. It also defines algorithm-independent syntax
for digital signatures, digital envelopes (for encryption), and certificates;
this enables someone implementing any cryptographic algorithm whatsoever to
conform to a standard syntax and thus preserve interoperability. Documents
detailing the PKCS standards can be obtained by sending e-mail to
pkcs@rsa.com or by anonymous ftp to rsa.com.
8.10 What is RSAREF?
RSAREF is a collection of cryptographic routines in portable C source code,
available at no charge from RSA Laboratories, a division of RSA Data Security,
Inc. It includes RSA, MD2, MD5, and DES; Diffie-Hellman key exchange will
be included in a forthcoming version. It includes both low-level
subroutines, such as modular exponentiation, and high-level cryptographic
functions, such as verification of digital signatures. The arithmetic routines
can handle multiple-precision integers, and the RSA algorithm routines can
handle variable key sizes. RSAREF is fully compatible with the PEM and PKCS
standards.
RSAREF is available to citizens of the U.S. or Canada and to permanent
residents of the U.S. It can be used in personal, non-commercial applications
but cannot be used commercially or sent outside the U.S. and Canada. The
RSAREF license contains more details on the usage allowed and disallowed.
RSAREF is available on the Internet by sending e-mail to
rsaref@rsa.com or by ftp to rsa.com.
9 Acknowledgements
I would like to thank the following people, who have provided information
and helpful suggestions: Burt Kaliski, Jim Bidzos, Matt Robshaw, Steve Dusse,
Kurt Stammberger, George Parsons, John Gilmore, Stuart Haber, Dorothy
Denning, and Dennis Branstad.
BIBLIOGRAPHY
1. American National Standards Institute. Working Draft: American National
Standard X9.30-199X: Public Key Cryptography Using Irreversible
Algorithms for the Financial Services Industry: Part 1: The Digital
Signature Algorithm (DSA). American Bankers Association, Washington,
D.C., March 4, 1993.
2. J. Bamford. The Puzzle Palace. Houghton Mifflin, Boston, 1982.
3. J.P. Barlow. Decrypting the puzzle palace. Communications of the ACM,
35(7):25--31, July 1992.
4. D. Bayer, S. Haber, and W.S. Stornetta. Improving the efficiency and
reliablility of digital time-stamping. In R.M. Capocelli, editor,
Sequences '91: Methods in Communication, Security, and Computer Science,
Springer-Verlag, Berlin, 1992.
5. P. Beauchemin, G. Brassard, C. Crepeau, C. Goutier, and C. Pomerance. The
generation of random numbers that are probably prime. J. of Cryptology,
1:53--64, 1988.
6. E. Biham and A. Shamir. Differential Cryptanalysis of the Data Encryption
Standard. Springer-Verlag, New York, 1993.
7. E. Biham and A. Shamir. Differential cryptanalysis of the full 16-round
DES. In Advances in Cryptology --- Crypto '92, Springer-Verlag, New York,
1993.
8. M. Blum and S. Goldwasser. An efficient probabilistic public-key
encryption scheme which hides all partial information. In Advances in
Cryptology --- Crypto '84, pages 289--299, Springer-Verlag, New York,
1985.
9. J. Brandt and I. Damgard. On generation of probable primes by incremental
search. In Advances in Cryptology --- Crypto '92, Springer-Verlag, New
York, 1993.
10. G. Brassard. Modern Cryptology. Volume 325 of Lecture Notes in Computer
Science, Springer-Verlag, Berlin, 1988.
11. D.M. Bressoud. Factorization and Primality Testing. Undergraduate Texts
in Mathematics, Springer-Verlag, New York, 1989.
12. E.F. Brickell, D.E. Denning, S.T. Kent, D.P. Maher, and W. Tuchman.
Skipjack Review, Interim Report: The Skipjack Algorithm. July 28, 1993.
13. E.F. Brickell and A.M. Odlyzko. Cryptanalysis: A survey of recent
results. Proceedings of the IEEE, 76:578--593, 1988.
14. J. Brillhart, D.H. Lehmer, J.L. Selfridge, B. Tuckerman, and S.S.
Wagstaff Jr. Factorizations of b^n +/- 1, b=2,3,5,6,7,10,11,12 up to
High Powers. Volume 22 of Contemporary Mathematics, American
Mathematical Society, Providence, Rhode Island, 2nd edition, 1988.
15. J. Buchmann, J. Loho, and J. Zayer. An implementation of the general
number field sieve. In Advances, in Cryptology --- Crypto '93,
Springer-Verlag, New York, 1994. To appear.
16. J.P. Buhler, H.W. Lenstra, and C. Pomerance. Factoring integers with
the number field sieve. 1992. To appear.
17. M.V.D. Burmester, Y.G. Desmedt, and T. Beth. Efficient zero-knowledge
identification schemes for smart cards. Computer Journal, 35:21--29, 1992.
18. K.W. Campbell and M.J. Wiener. Proof that DES is not a group. In
Advances in Cryptology --- Crypto '92, Springer-Verlag, New York, 1993.
19. CCITT (Consultative Committee on International Telegraphy and
Telephony). Recommendation X.509: The Directory---Authentication
Framework. 1988.
20. Comptroller General of the United States. Matter of National Institute
of Standards and Technology --- Use of Electronic Data Interchange
Technology to Create Valid Obligations. December 13, 1991. File B-245714.
21. D. Coppersmith, A.M. Odlyzko, and R. Schroeppel. Discrete logarithms in
GF(p). Algorithmica, 1:1--15, 1986.
22. T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms.
MIT Press, Cambridge, Massachusetts, 1990.
23. G. Davida. Chosen signature cryptanalysis of the RSA public key
cryptosystem. Technical Report TR-CS-82-2, Dept of EECS, University of
Wisconsin, Milwaukee, 1982.
24. B. den Boer and A. Bosselaers. An attack on the last two rounds of MD4.
In Advances in Cryptology --- Crypto '91, pages 194--203, Springer-Verlag,
New York, 1992.
25. B. den Boer and A. Bosselaers. Collisions for the compression function
of MD5. In Advances in Cryptology --- Eurocrypt '93, 1993. Preprint.
26. Dorothy E. Denning. The Clipper encryption system. American Scientist,
81(4):319--323, July--August 1993.
27. W. Diffie. The first ten years of public-key cryptography. Proceedings
of the IEEE, 76:560--577, 1988.
28. W. Diffie and M.E. Hellman. Exhaustive cryptanalysis of the NBS Data
Encryption Standard. Computer, 10:74--84, 1977.
29. W. Diffie and M.E. Hellman. New directions in cryptography. IEEE
Transactions on Information Theory, IT-22:644--654, 1976.
30. T. ElGamal. A public-key cryptosystem and a signature scheme based on
discrete logarithms. IEEE Transactions on Information Theory,
IT-31:469--472, 1985.
31. A. Fiat and A. Shamir. How to prove yourself: Practical solutions to
identification and signature problems. In Advances in Cryptology ---
Crypto '86, pages 186--194, Springer-Verlag, New York, 1987.
32. S. Goldwasser and S. Micali. Probabilistic encryption. J. of Computer
and System Sciences, 28:270--299, 1984.
33. D.M. Gordon. Discrete logarithms using the number field sieve. March 28,
1991. To appear.
34. D.M. Gordon and K.S. McCurley. Massively parallel computation of discrete
logarithms. In Advances in Cryptology --- Crypto '92, Springer-Verlag,
New York, 1993.
35. J. Hastad. Solving simultaneous modular equations of low degree. SIAM J.
Computing, 17:336--241, 1988.
36. M.E. Hellman. A cryptanalytic time-memory trade off. IEEE Transactions
on Information Theory, IT-26:401--406, 1980.
37. D. Kahn. The Codebreakers. Macmillan Co., New York, 1967.
38. B.S. Kaliski. A survey of encryption standards. RSA Data Security, Inc.,
September 2, 1993.
39. B.S. Kaliski Jr., R.L. Rivest, and A.T. Sherman. Is the data encryption
standard a group? J. of Cryptology, 1:3--36, 1988.
40. S. Kent. RFC 1422: Privacy Enhancement for Internet Electronic Mail,
Part II: Certificate-Based Key Management. Internet Activities Board,
February 1993.
41. D.E. Knuth. The Art of Computer Programming. Volume 2, Addison-Wesley,
Reading, Mass., 2nd edition, 1981.
42. N. Koblitz. A Course in Number Theory and Cryptography. Springer-Verlag,
New York, 1987.
43. N. Koblitz. Elliptic curve cryptosystems. Mathematics of Computation,
48:203--209, 1987.
44. X. Lai and J.L. Massey. A proposal for a new block encryption standard.
In Advances in Cryptology --- Eurocrypt '90, pages 389--404,
Springer-Verlag, Berlin, 1991.
45. B.A. LaMacchia and A.M. Odlyzko. Computation of discrete logarithms
in prime fields. Designs, Codes and Cryptography, 1:47--62, 1991.
46. S. Landau. Zero knowledge and the Department of Defense. Notices of
the American Mathematical Society, 35:5--12, 1988.
47. A.K. Lenstra and H.W. Lenstra Jr. Algorithms in number theory. In J.
van Leeuwen, editor, Handbook of Theoretical Computer Science, MIT
Press/Elsevier, Amsterdam, 1990.
48. A.K. Lenstra, H.W. Lenstra Jr., M.S. Manasse, and J.M. Pollard. The
factorization of the ninth Fermat number. 1991. To appear.
49. A.K. Lenstra and M.S. Manasse. Factoring with two large primes. In
Advances in Cryptology --- Eurocrypt '90, pages 72--82, Springer-Verlag,
Berlin, 1991.
50. H.W. Lenstra Jr. Factoring integers with elliptic curves. Ann. of Math.,
126:649--673, 1987.
51. M. Matsui. Linear cryptanalysis method for DES cipher. In Advances in
Cryptology --- Eurocrypt '93, Springer-Verlag, Berlin, 1993. To appear.
52. R.C. Merkle and M.E. Hellman. Hiding information and signatures in
trapdoor knapsacks. IEEE Transactions on Information Theory,
IT-24:525--530, 1978.
53. R.C. Merkle and M.E. Hellman. On the security of multiple encryption.
Communications of the ACM, 24:465--467, July 1981.
54. E. Messmer. NIST stumbles on proposal for public-key encryption. Network
World, 9(30), July 27, 1992.
55. S. Micali. Fair public-key cryptosystems. In Advances in Cryptology ---
Crypto '92, Springer-Verlag, New York, 1993.
56. V.S. Miller. Use of elliptic curves in cryptography. In Advances in
Cryptology --- Crypto '85, pages 417--426, Springer-Verlag, New York,
1986.
57. National Institute of Standards and Technology (NIST). The Digital
Signature Standard, proposal and discussion. Communications of the ACM,
35(7):36--54, July 1992.
58. National Institute of Standards and Technology (NIST). FIPS Publication
180: Secure Hash Standard (SHS). May 11, 1993.
59. National Institute of Standards and Technology (NIST). FIPS Publication
46-1: Data Encryption Standard. January 22, 1988. Originally issued by
National Bureau of Standards.
60. National Institute of Standards and Technology (NIST). FIPS Publication
81: DES Modes of Operation. December 2, 1980. Originally issued by
National Bureau of Standards.
61. National Institute of Standards and Technology (NIST). Notice of
proposal for grant of exclusive patent license. Federal Register,
58(108), June 8, 1993.
62. National Institute of Standards and Technology (NIST). A proposed
Federal Information Processing Standard for an Escrowed Encryption
Standard (EES). Federal Register, 58(145), July 30, 1993.
63. National Institute of Standards and Technology (NIST). Publication XX:
Announcement and Specifications for a Digital Signature Standard (DSS).
August 19, 1992.
64. A.M. Odlyzko. Discrete logarithms in finite fields and their cryptographic
significance. In Advances in Cryptology --- Eurocrypt '84, pages 224--314,
Springer-Verlag, Berlin, 1984.
65. Office of the Press Secretary. Statement. The White House, April 16, 1993.
66. J. Pollard. Monte Carlo method for factorization. BIT, 15:331--334, 1975.
67. J. Pollard. Theorems of factorization and primality testing. Proc.
Cambridge Philos. Soc., 76:521--528, 1974.
68. M.O. Rabin. Digitalized signatures as intractable as factorization.
Technical Report MIT/LCS/TR-212, MIT, 1979.
69. R.L. Rivest. Cryptography. In J. van Leeuwen, editor, Handbook of
Theoretical Computer Science, MIT Press/Elsevier, Amsterdam, 1990.
70. R.L. Rivest. Finding four million random primes. In Advances in
Cryptology --- Crypto '90, pages 625--626, Springer-Verlag, New York,
1991.
71. R.L Rivest. The MD4 message digest algorithm. In Advances in Cryptology
--- Crypto '90, pages 303--311, Springer-Verlag, New York, 1991.
72. R.L. Rivest. Response to NIST's proposal. Communications of the ACM,
35:41--47, July 1992.
73. R.L. Rivest. RFC 1321: The MD5 Message-Digest Algorithm. Internet
Activities Board, April 1992.
74. R.L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital
signatures and public-key cryptosystems. Communications of the ACM,
21(2):120--126, February 1978.
75. C.P. Schnorr. Efficient identification and signatures for smart cards.
In Advances in Cryptology --- Crypto '89, pages 239--251,
Springer-Verlag, New York, 1990.
76. M. Shand and J. Vuillemin. Fast implementations of RSA cryptography. In
Proceedings of the 11th IEEE Symposium on Computer Arithmetic, pages
252--259, IEEE Computer Society Press, Los Alamitos, CA, 1993.
77. R.D. Silverman. The multiple polynomial quadratic sieve. Math. Comp.,
48:329--339, 1987.
78. M.E. Smid and D.K. Branstad. Response to comments on the NIST proposed
Digital Signature Standard. In Advances in Cryptology --- Crypto '92,
Springer-Verlag, New York, 1993.
79. J.G. Steiner, B.C. Neuman, and J.I. Schiller. Kerberos: an authentication
service for open network systems. In Usenix Conference Proceedings, pages
191--202, Dallas, Texas, February 1988.
80. M.J. Wiener. Efficient DES key search. August 20, 1993. Presented at
Crypto '93 rump session.
--------------------------------------------
RSA Laboratories is the research and consultation division of RSA Data
Security, Inc., the company founded by the inventors of the RSA
public-key cryptosystem. RSA Laboratories reviews, designs and
implements secure and efficient cryptosystems of all kinds. Its
clients include government agencies, telecommunications companies,
computer manufacturers, software developers, cable TV broadcasters,
interactive video manufacturers, and satellite broadcast companies,
among others.
For more information about RSA Laboratories, call or write to
RSA Laboratories
100 Marine Parkway
Redwood City, CA 94065
(415) 595-7703
(415) 595-4126 (fax)
PKCS, RSAREF and RSA Laboratories are trademarks of RSA Data
Security, Inc. All other trademarks belong to their respective
companies.
This document is available in ASCII, Postscript, and Latex formats
via anonymous FTP to rsa.com:/pub/faq.
Please send comments and corrections to faq-editor@rsa.com.
===
DISTRIBUTION: How to obtain this document
This document has been brought to you in part by CRAM, involved in the
redistribution of valuable information to a wider USENET audience (see
below). The most recent version of this document can be obtained via
the author's instructions above. The following directions apply to
retrieve the possibly less-current USENET FAQ version.
FTP
---
This FAQ is available from the standard FAQ server rtfm.mit.edu via
FTP in the directory /pub/usenet/news.answers/cryptography-faq/rsa/
Email
-----
Email requests for FAQs go to mail-server@rtfm.mit.edu with commands
on lines in the message body, e.g. `help' and `index'.
Usenet
------
This FAQ is posted every 21 days to the groups
sci.crypt
talk.politics.crypto
alt.security.ripem
sci.answers
talk.answers
alt.answers
news.answers
_ _, _ ___ _, __, _, _ _, ___ _ _, _, _ _ _, __, _, _ _ ___ __,
| |\ | |_ / \ |_) |\/| / \ | | / \ |\ | | (_ |_) / \ | | |_ | )
| | \| | \ / | \ | | |~| | | \ / | \| | , ) | \ / |/\| | |~\
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~~ ~ ~
===
CRAM: The Cyberspatial Reality Advancement Movement
In an effort to bring valuable information to the masses, and as a
service to motivated information compilers, a member of CRAM can help
others unfamiliar with Usenet `publish' their documents for
widespread dissemination via the FAQ structure, and act as a
`sponsor' knowledgable in the submissions process. This document is
being distributed under this arrangement.
We have found these compilations tend to appear on various mailing
lists and are valuable enough to deserve wider distribution. If you
know of an existing compilation of Internet information that is not
currently a FAQ, please contact us and we may `sponsor' it. The
benefits to the author include:
- use of the existing FAQ infrastructure for distribution:
- automated mail server service
- FTP archival
- automated posting
- a far wider audience that can improve the quality, accuracy, and
coverage of the document enormously through email feedback
- potential professional inquiries for the use of your document in
other settings, such as newsletters, books, etc.
- with us as your sponsor, we will also take care of the
technicalities in the proper format of the posted version and
updating procedures, leaving you free of the `overhead' to focus on
the basic updates alone
The choice of who we `sponsor' is entirely arbitrary. You always have
the option of handling the submission process yourself. See the FAQ
submission guidelines FAQ in news.answers.
For information, send mail to <tmp@netcom.com>.
\ \ \ \ \ \ \ \ \ | / / / / / / / / / /
_______ ________ _____ _____ _____
/// \\\ ||| \\\ /// \\\ |||\\\///|||
||| ~~ ||| /// ||| ||| ||| \\// |||
||| __ |||~~~\\\ |||~~~||| ||| ~~ |||
\\\ /// ||| \\\ ||| ||| ||| |||
~~~~~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~
/ / / / / / / / / | \ \ \ \ \ \ \ \ \ \
C y b e r s p a t i a l R e a l i t y A d v a n c e m e n t M o v e m e n t
* CIVILIZING CYBERSPACE: send `info cypherwonks' to majordomo@lists.eunet.fi *