tex version of USACM Crypto report. Note The IEEE US Activities committee also took a position. Sorr

[David Farber <>]

Confidentiality, the service most often associated with cryptography,
consists of transforming (encrypting) information so it is 
unintelligible to anyone except the intended recipient.  Because
cryptography for confidentiality purposes has the potential to interfere
with foreign intelligence gathering, it is often subject to stringent
export controls.  In the U.S., export control of cryptography used for
confidentiality is managed by the State Department, and products
incorporating ``strong''\footnotemark\  cryptographic algorithms for
confidentiality are generally not exportable.
 
Integrity is a security service that permits a user to detect whether
information has been tampered with during transmission or while in storage.
Closely related to integrity is authenticity, which provides a user with a
means of verifying the identity of the sender of a message.  Authentication
frequently involves associating a unique cryptographic key with a user.
 
Integrity and authenticity services are often implemented in tandem.  In
part, the motivation is that it generally is not useful to be able to
establish the authenticity of a message unless one can also establish the
integrity of the message (and vice versa).  However, information that is 
authenticated and integrity-checked is not necessarily confidential; that
is, confidentiality can be separated from integrity and authenticity.


Cryptography that provides integrity and authenticity only does not
interfere with many types of intelligence gathering.  In the U.S., export
control of  products offering only these services is generally managed
by the Commerce Department; export licenses are usually granted.
        
\begin{center}


Weak Links


\end{center}


\noindent Electronic communication networks are complex systems built out
of many components. An intruder wishing to access the communications in a
network will look for unprotected points or segments.  The weakest link is
where one might be able to bypass or avoid the security mechanisms
altogether.  Cryptography or other security measures in one part of a
system, or in one aspect of the transaction, could provide no protection at
all if weak links are not protected.  Because we want products to ship the
day before the last line of code is written, proper cryptography is often
never implemented.


However, even the most carefully designed system can have flaws (see
Chapter 2 for a more detailed discussion). The following are among the most
common weak links:


     * Modifications to software or hardware: An adversary modifies code or
some aspect of a product that controls the cryptography or access.  Such an
intruder could even make modifications to collect information, such as
cryptographic keys.


    * Access control: Someone masquerades as the user and thus has the
user's privileges and can alter or read information.  This may include 
control of the cryptography.


     * Cryptographic vulnerabilities: One can have sound cryptographic
algorithms properly implemented, but the associated initialization,
randomization, or key management may be sources of weakness.


     * Cryptographic algorithms: The fundamental mathematics of the
cryptography may have a subtle vulnerability that can be discovered
through clever analysis.


     * Cryptographic administration: Even the best cryptographic algorithms
can be subverted if their use is not properly administered.  Sloppy key
management can lead to exposures of the keys.  Operating system
vulnerabilities may lead to compromises of unencrypted text or of the
cryptography itself.


\begin{center}


Cryptographic Algorithms


\end{center}


\noindent In the last two decades the civilian sector has adopted certain
crytographic schemes for protecting electronic communications.  In 1975,
the United States proposed the Data Encryption Standard (DES) for the
protection of ``sensitive but unclassified information'' by government
agencies.  DES, designed by IBM, was vetted by the National Security Agency
(NSA), the U.S.  agency responsible for secure codes for military and
diplomatic communications.  It was adopted as a Federal Information
Processing Standard (FIPS) in 1977 (in the same series that now includes
the EES).  It is a classic private- or single-key system; the key used to
protect communications between two parties must be known to both parties
and kept secret from everyone else.  DES requires a secure method to
establish the key.


At the time DES was proposed, it enjoyed a period of controversy in which
its keys were characterized as too small and other weaknesses were
suspected.  Despite this, the algorithm has proven remarkably resistant to
public attacks.


DES was designed for use by Federal agencies for the protection of
sensitive but unclassified data.  Software versions of DES are quite common
outside the Federal government.  Although export of the algorithm for
confidentiality purposes is restricted, DES is believed to be the most
widely used cryptosystem in the world, except perhaps for scramblers used
for pay television.  In the United States, the American Bankers Association
recommends DES whenever encryption is needed to protect financial data
[ABA].\footnotemark\  DES is the cryptographic scheme most often used in
commercially available secure telephones [Bran]. A DES variant is used for
password encryption in almost all versions of Unix, a very popular
operating system for multitasking environments.


At about the same time as DES was introduced, academic researchers
developed a family of cryptographic techniques that became known as
public-key or two-key cryptography.  One approach, proposed by Ralph Merkle
at Berkeley and refined by Whitfield Diffie and Martin Hellman at Stanford,
allowed two parties to negotiate a common secret piece of information over
an insecure channel.  Another, proposed by Diffie and Hellman and realized
by Ronald Rivest, Adi Shamir, and Leonard Adleman of MIT, made it possible
to use a key that was not secret (a public key) to encrypt a message that
could  be decrypted only by a particular secret key.  Conversely, a message
transformed by a secret key could be verified as coming from the sender by
applying the sender's public key.  This second use of public-key technology
came to be called a digital signature.


Products containing RSA (as the Rivest-Shamir-Adleman algorithm came
to be known) are available commercially.  It is used as the basis for
Privacy Enhanced Mail (PEM) and Pretty Good Privacy (PGP), widely available
systems for protecting electronic mail.  It is also used in some commercial
secure telephones.


There are many applications for which DES and RSA are combined, including
PEM [Kent], and telecommunications equipment by Motorola and Northern
Telecom [DOW].  For comparable levels of security, the fastest
implementations of DES are about a thousand times faster than the fastest
RSA implementions;\footnotemark\ RSA is used for key exchange when two
parties wish to establish private communications, and their only link is
over an insecure channel. Having established a private key, DES is used to
encrypt the information.


These algorithms provide the U.S. commercial sector with techniques for
achieving confidentiality, integrity, and authenticity.  However, with the
exception of exporting DES for use by financial institutions or foreign
offices of U.S.-controlled companies, the State Department typically
refuses export license for confidentiality systems employing strong
cryptography.  This presents a serious problem to U.S. industry, all the
more so because DES is widely available outside the United States.  A March
1994 study by the Software Publishers Association lists 152 products being
developed and distributed in 33 countries, all using DES
[SPA-94].


\begin{center}
                 The Emerging Problem -- and a Possible Solution
\end{center}


\noindent DES is coming to the end of its useful life with its key size and
complexity being overtaken by improvements in speed and cost of computers
[Wie].  Yet the U.S. private sector, from bankers to the future users of
the NII, need strong cryptography. Strong cryptography can impede law
enforcement and the collection of foreign intelligence by national security
organizations.  A repeat of a publicly disclosed, government-certified,
strong cryptosystem for confidentiality purposes seems unlikely.


On April 16, 1993, the White House proposed the Escrowed Encryption
Standard (EES) as a solution that attempts to balance the privacy and
security needs of American citizens and business with the needs of U.S. law
enforcement and national security.  It has been controversial from the day
it was proposed.  There are various competing viewpoints.  Civil
libertarians view privacy protection as fundamental while law enforcement
officers are concerned over criminal use of encryption. National security
needs are for continued excellence in communications intelligence, and for
effective protection of the civilian information infrastructure. U.S.
undustry wants to be allowed to energetically compete in the world
marketplace.  In the next chapters of this report, we present these
views.




\newpage
\begin{center}


Notes


\end{center}
{\small
\begin{enumerate}
\item Private communication with Lewis Branscomb on March 22,
1994.  Branscomb was IBM's liason with U.S. government intelligence
agencies from 1972 -1986.


\item Strong cryptographic algorithms are ones that are
exceedingly difficult to break by all attacks, including exhaustive search
over the entire key space.


\item The Treasury Directive on
Electronic Funds and Securities Transfer Policy -- Message Authentication
(TD81-80) makes it Department of Treasury policy that all Federal EFT
transactions be ``properly authenticated.''  The authentication measures
adopted in TD81-80 are those recommended by the American National Standards
Institute (ANSI) in Standard X9.9.  In addition, authentication equipment
must comply with FIPS 140-1 regarding minimum general security requirements
for implementing the Data Encryption Standard (DES) algorithm.  Key
management standards are based on ANSI X9.17 [USDoT, pg II-1].


\item A typical commercial RSA chip, the Cylink CY1024, can
encrypt a thousand-bit number in about one tenth of a second --- a
throughput rate of ten kilobits.  By comparison, the AMD9518 DES chip can
encrypt data at approximately fifteen megabits.
\end{enumerate}}




\clearpage
\newpage
\begin{center}


{\Large{\bf                Diffie-Hellman Key Exchange}}


\end{center}


\medskip


Diffie-Hellman key exchange is a public-key technique that takes advantage of
the fact that it is easy to compute powers in modular arithmetic, but very
difficult to extract logarithms.  If $y$ is the $x$th power of $b$, modulo
$p$: $$ y = b^x \pmod{ p} $$ where $b$ is a suitable base number, then, as
in ordinary arithmetic, $x$ is the logarithm of $y$ to the base $b$, modulo
$p$: 


$$ 
x = \log_by  \pmod{ p} 
$$


Calculation of $y$ from $x$ is easy, but computing $x$ from $y$ is
difficult.  In the following illustration using exponential key exchange to
establish session keys, the equipment being used to carry out the key
distribution is personified as Alice and Bob, just as if the users were
doing the computing in their heads.


The base $b$ is known to both users.  To initiate communication, Alice
chooses a random number: $A$. She keeps $A$ secret, but sends: 
$$
b^A\pmod {p}
$$


\noindent to Bob. Bob in turn chooses a random number, $B$, and sends the 
corresponding $b^B$ to Alice. Both Alice and Bob can now compute
$$
         b^{AB} \pmod{ p }
$$


\noindent and use this as their key. Bob computes $b^{AB}$ by raising the
$b^A$ he obtained from Alice to his secret power $B$:


$$
         (b^A)^B \pmod {p} =b^{AB}\pmod {p}.
$$


Similarly, Alice obtains $(b^B)^A = b^{AB}$. Only Alice and Bob know the
secret value $b^{AB}$. There is no known way for anyone who does not
know either $A$ or $B$ to compute $b^{AB}$ without first attacking the
difficult problem of taking the logarithm of $b^A$ or $b^B$.


If $p$ is a prime about 1,000 bits in length, only about 2,000
multiplications of 1000-bit numbers are required to compute the
exponentiations. By contrast, the fastest techniques for taking logarithms
in arithmetic modulo $p$ currently demand more than $2^{100}$ (or
approximately $10^{30}$) operations. Even with today's supercomputers, it
would take a billion billion years to perform this many operations.




\addtocontents{toc}{Diffie-Hellman Key Exchange}{}
\newpage
\chapter{                        Integrating Cryptography}


\framebox[5.25in][c]{
\begin{minipage}{5.0in}
\noindent Vocabulary words:\\


\smallskip


\noindent  Distributed system:  A system in which there may be multiple
processors, possibly geographically dispersed.  Control is typically
decentralized, and is coordinated among the various processors.


\smallskip


\noindent STU-III: Third generation of U.S. government secure telephones.


\end{minipage}}


\medskip


\noindent Why is cryptography important?  The unique virtue of cryptography
is that it provides security that does not depend on the characteristics of
the channel through which the text passes.  This makes it the only way of
protecting communications over channels that are not under the user's
control. Often it is the most economical way of protecting communications
over channels that are.


\begin{center}


Secure Telephony


\end{center}


\noindent Secure telephony gives an excellent example of cryptography's
utility.  No telephone user, even the government, can afford to secure the
entire telephone system.  The only way to provide a secure voice path
between two telephones at arbitrary locations is to encrypt the words
spoken into one and decrypt them as they come out of the other.  Public key
cryptography makes it possible for the two phones to agree on a common key
known only to them without consulting any other party.  The users simply
establish the call, push a button, and wait a few seconds for the phones to
make the arrangements.


Encryption assures the confidentiality of the phone call, but what assures
its authenticity?  In the simplest systems, the users must rely on voice
recognition, just as with unsecured phone calls.\footnotemark\ If the
system must provide authentication to users who do not know one another,
some central administration is required to issue cryptographic credentials
by which each phone can recognize the other.  Although such systems have
been designed and built, lack of standards has limited purchasers of
commercial systems to the products of a single manufacturer.  Only the
government's STU-III secure telephone system, which is inaccessible to the
general public, offers such services on a large scale.\footnotemark


The shortcoming of secure telephones is that they are expensive.  In
addition to the cryptographic devices, a secure phone must include a voice
digitizer to convert speech to a form in which it can be encrypted and a
modem to encode the digitized signal for transmission over the phone line.
Currently, the least expensive secure phones cost over a thousand dollars
apiece.


\begin{center}


Secure Computer Communications:  the Problems


\end{center}


\noindent Securing communications in a distributed computer system presents
somewhat different problems.  In data communication, there is no analogue
of the voice recognition that plays such a valuable role in the telephone
case.  If authentication is to be available at all, it must be done by
formal cryptographic procedures.  This requires the computers to identify
people or machines through long-term keys.  The relationship between
telephones, even secure telephones, is conceptually simple: they set up
calls and transmit sound.  The relationship between computers in a
distributed system is considerably more complex: they permit their users to
login remotely, and to share files. The networked machines routinely
execute programs for each other.  These wedded interactions complicate the
process of protection and make computer break-ins difficult to prevent.


Systems owners are typically unwilling to make substantial investments in
hardware or software for security purposes, although they may be willing to
pay some premium for products that contain integrated security
features.\footnotemark\ Many vendors see software as the least expensive
means of adding cryptographic security features to their products.


A secure mail system like Privacy Enhanced Mail (PEM) is the workstation
analogue of a secure telephone; it encrypts and decrypts mail so the user
can correspond privately.  Unfortunately, a software implementation of PEM
is vulnerable to penetration of the program including the compromise of its
long-term keys.  One of the ways in which penetrations occur is through the
implanting of modified programs or other data into the user's working
environment.\footnotemark


An essential element in many distributed systems is the Remote Procedure
Call, wherein one computer asks another to perform a task on its behalf.
This primitive underlies the Network File System,\footnotemark\ which
permits computers to access files on remote disks as though they were
locally available.  One computer, the client, asks another, the server, to
send it information, print a file, or perform a computation.  Without
authentication of the request, the server has no way of knowing that the
client is entitled to the service requested.  Without authentication of the
response, the client has no way of knowing that the information returned is
genuine.


\begin{center}


Cryptography as Part of a Solution


\end{center}


\noindent Continuing our example, let us reexamine the secure mail program.
The user at his workstation requests the PEM program from a server.  If the
network file system is not secure, an intruder can send a program that has
all the functionality of PEM, and an additional dangerous one: when the
user types in the password that decrypts his private key, the bogus PEM
sends this key to the intruder.


If the communications between the workstation and the file server provide
authentication, the copy of PEM received by the workstation is verified as
being valid.  This serves to protect the user against the broad class of
attacks that involve substituting one file for another.  


To provide this broad basis for protection, cryptography must be
incorporated in the basic interactions of workstations and servers so that
its capabilities are available when establishing communications between
machines.  It must be done in such a way that the cryptography cannot be
easily compromised. Without trustworthiness in the operating system,
cryptography embedded in an application is no panacea.


In a large company system, security facilitates moving sensitive
applications from mainframes to more economical networked machines.  Adding
such sensitive applications as personnel, purchasing, or travel agency
services to the system involves ensuring that the applications interoperate
correctly with the system standards.  If the underlying distributed system
is not sufficiently secure, each of the sensitive applications must provide
its own security, a more cumbersome and risky way to solve the problem.
Nonetheless, some applications, such as E-mail, will require specific
security measures in addition to underlying system security facilities.




\begin{center}


The Cryptography Market


\end{center}


\noindent The cryptographic market is paradoxical.  It is easy to build a
case for buying cryptography futures.  The number of tasks that can be done
by computer is growing by leaps and bounds. Many of these either involve
substantial sums of money or confidential information about individuals,
business plans, etc.  Cryptography's supporters have been predicting an
explosion in the market for more than twenty years.\footnotemark\
Nonetheless, cryptography remains a niche market in which (with the
exception of several hundred million dollars a year in government sales by
a few major corporations) a handful of companies gross only a few tens of
millions of dollars annually.


The arguments for the importance of cryptography and the brightness of its
future remain as strong as ever: the cost of cryptography is declining,
information products have become a major industry, and the popularity of
(vulnerable) wireless communications is increasing.  Attempts to explain
the apparent discrepancy point to the government's failure to carry through
on the standards thrust begun in the mid-seventies and the effect of the
export-control regulations.  Selling cryptography, however, is selling
insurance against a loss (being spied on) that is hard to detect.  It may
be that users find the inconvenience of add-on products, complexities of
key management, and complications of competing standards unacceptable, and
are waiting for seamlessly integrated cryptographic capabilities.  It may
simply be that although the price is dropping, it has not yet dropped far
enough. Or it might be that the need for such insurance has not yet become
manifest.


\newpage
\begin{center}
Notes
\end{center}
{\small
\begin{enumerate}


\item A technical trick is used to guarantee that an intruder
has not snuck in by participating in the key setup process.  The phones