My testimony at Wednesday's Senate hearing on encryption policy

[Matt Blaze <mab@crypto.com>]

WRITTEN TESTIMONY OF DR. MATTHEW BLAZE

BEFORE THE SENATE COMMITTEE ON COMMERCE, SCIENCE, AND TRANSPORTATION,
SUBCOMMITTEE ON SCIENCE, TECHNOLOGY, AND SPACE

JUNE 26, 1996


Thank you for the opportunity to speak with you about the technical
impact of encryption policy.  It is a privilege to be here, and I
hope my perspective will be useful to you.

Let me begin by describing my own background and biases.  I am a
Principal Research Scientist in the area of computer security and
cryptology at AT&T Research in Murray Hill, New Jersey.  I also
hold a number of ancillary appointments related to computer security;
among others, I teach an occasional graduate course in the subject
at Columbia University, and I serve as co-chair of the Federal
Networking Council Advisory Committee subcommittee on security and
privacy (which advises Federal agencies on computer networking
issues).  However, the views I am presenting here today are my own,
and should not be taken to represent those of any organization with
which I happen to be affiliated.

I am a computer scientist by training; my Ph.D. is from the Princeton
University Computer Science department, and my primary research
areas are cryptology, computer security, and large-scale distributed
systems.  Much of my research focuses on the management of encryption
keys in networked computing systems and understanding the risks of
using cryptographic techniques to accomplish security objectives.
Recent government initiatives in encryption, such as the "Clipper
Chip," have naturally been of great interest to me, in no small
part because of the policy impact they have on the field in which
I work, but also because they present a number of very interesting
technical and scientific challenges in their own right.

My testimony today focuses on three areas.  First, I will discuss
the role and risks of cryptographic techniques for securing the
current and future electronic world.  Next, I will examine in more
detail the security implications of the limitations imposed on
US-based cryptographic systems through the government's export
policies.  Finally, I will discuss the technical aspects of the
Administration's current approach to cryptography policy, which
promotes "key escrow" systems.


I  THE INCREASING IMPORTANCE OF ENCRYPTION

The importance of cryptographic techniques for securing modern
computer and communications systems is widely recognized today.
Evidence of the scope of  this recognition can be found in the
increasing number of hardware, software, and system vendors that
offer encryption in their products, the increasing demand for
high-quality encryption by users in a widening array of applications,
and the growing, thriving community of cryptologic researchers of
which I am a part.  It is vital that those who formulate our nation's
policies and official attitude toward encryption understand the
nature of the underlying technology and the reasons for its growing
importance to our society.

The basic function of cryptography is to separate the security of
a message's content from the security of the medium over which it
is carried.  For example, we might encrypt a cellular telephone
conversation to guard against eavesdroppers (allowing the call to
be transmitted safely over easily-intercepted radio frequencies),
or we might use encryption to verify that documents, such as
contracts, have not been tampered with (removing the need to
safeguard a copy of the original).  The idea that this might be
possible is not a new one; history suggests that the desire to
protect information is almost as old as the written word itself.
Perhaps as a consequence of the invention of the digital computer,
our understanding of the theory and practice of cryptography has
accelerated in recent years, with a number of new techniques
developed and many new applications emerging.  Among the most
important of the recent techniques is "public key cryptography."
It allows secure messages to be exchanged without the need

Modern cryptographic techniques are based on the application of
simple, if repetitive,  mathematical functions, and as such lend
themselves nicely to implementation by computer programs.  Any
information that can be represented digitally can be protected by
encryption, including computer files, electronic mail messages,
and even audio and video signals such as telephone calls, radio,
and television.  Encryption can be performed by means of software
on general-purpose computers, through special-purpose hardware, or
by special programming of microprocessor-based electronic products
such as the next generation of cellular telephones.  The basic cost
of encryption in terms of computational power required is quite
low, and the marginal cost of including encryption in a software-based
computer program or a programmable electronic product is essentially
zero.

Why, then, has encryption recently enjoyed so much attention?  The
reasons can be found from two perspectives: the technology of modern
communication systems, and the new purposes for which we are relying
on digital information.

First, the technology and economics of modern communications and
computing systems strongly favors media that have little inherent
security.  For example, wireless telephones have great advantages
in convenience and functionality compared with their familiar wired
counterparts and are comprising an increasing proportion of the
telephone network.  This also makes eavesdropping much easier for
curious neighbors, burglars identifying potential targets, and
industrial spies seeking to misappropriate trade secrets.  Similarly,
decentralized computer networks such as the Internet have lower
barriers to entry, are much less expensive, are more robust and
can be used to accomplish a far greater variety of tasks than the
proprietary networks of the past, but, again, at the expense of
intrinsic security.  The Internet makes it virtually impossible to
restrict, or even predict, the path that a particular message will
traverse, and there is no way to be certain where a message really
originated or whether its content ha

Second, electronic communication is becoming increasingly critical
to the smooth functioning of our society and our economy and even
to protect the safety of human life.  Communication networks and
computer media are rapidly replacing less efficient, traditional
modes of interaction whose security properties are far better
understood.  As teleconferencing replaces face-to-face meetings,
electronic mail replaces letters, electronic payment systems replace
cash transactions, and on-line information services replace written
reference materials, we gain a great deal in efficiency, but our
assumptions about the reliability of very ordinary transactions
are often dangerously out-of-date.

Put another way, the trend in communication and computing networks
has been away from closed systems in favor of more open ones and
the trend in our society is to rely on these new systems for
increasingly serious purposes.  There is every reason to believe
that these trends will continue, and even accelerate, for the
foreseeable future.  Cryptography plays an important and clear role
in helping to provide security assurances that at least mirror what
we have come to expect from the older, more familiar communications
methods of the not-so-distant past.


II  KEY LENGTH AND SECURITY

The "strength" of an encryption system depends on a number of
variables, including the mathematical properties of the underlying
encryption function, the quality of the implementation, and the
number of different "keys" from which the user is able to choose.
It is very important that a cryptosystem and its implementation be
of high quality, since an error or bug in either can expose the
data it protects to unexpected vulnerabilities.  Although the
mathematics of cryptography is not completely understood and cipher
design is an exceptionally difficult discipline (there is as yet
no general "theory" for designing cipher functions), there are a
number of common cipher systems that have been extensively studied
and that are widely trusted as building blocks for secure systems.
The implementation of practical systems out of these building
blocks, too, is a subtle and difficult art, but commercial experience
in this area is beginning to lead to good practices for adding
high-quality encryption systems to software

The most easily quantified variable that contributes to the strength
of an encryption system is the size of the pool of potential values
from which the cryptographic keys are chosen.  Modern ciphers depend
on the secrecy of the users' keys, and a system is considered
well-designed only if the easiest "attack" involves trying every
possible key, one after the other, until the correct one is found.
The system is secure only if the number of keys is large enough to
make such an attack infeasible.  Keys are usually specified as a
string of "bits," and adding one bit to the key length doubles the
number of possible keys.  An important question, then, is the
minimum key length sufficient to resist a key search attack in
practice.

Last November, I participated in a study, organized by the Business
Software Alliance, aimed at examining the computer technology that
might be used by an "attacker" in order to determine the minimum
length keys that should be used in commercial applications.  We
followed an unusually conservative methodology in that we assumed
that the attacker would have only available standard "off-the-shelf"
technology and is constrained to purchase in single-unit quantities
with no economies of scale.  That is, our methodology would tend
to produce a recommendation for shorter keys than would an analysis
using the more conventional approach of giving the potential attacker
every benefit of the doubt in terms of technological advantages he
might enjoy.  Nonetheless, we concluded that the key lengths
recommended in existing U.S. government standards (e.g., the Data
Encryption Standard, with a 56-bit key) for domestic use are far
too short and will soon render data protected under them vulnerable
to attack with only modest

Attempting to design systems "at the margins" by using the minimum
key length needed is a dubious enterprise at best.  Because even
a slight miscalculation as to the technology and resources available
to the potential attacker can make the difference between a secure
system and an insecure one, prudent designers specify keys that
are longer than the minimum they estimate is needed to resist
attack, to provide a margin for error.

Current U.S. policy encourages the designers of encryption systems
to take exactly the opposite approach.  Encryption systems designed
for export from the United States at present generally must use
keys no more than 40 bits long.  Such systems provide essentially
no cryptographic security, except against the most casual "hacker."
Examples of 40 bit systems being "broken" through the use of spare
computer time on university computer networks are commonplace.
Unfortunately, it is not only users outside the U.S. who must make
do with the inferior security provided by such short keys.  Because
of the difficulty of maintaining  multiple versions of software,
one for domestic sale and one for export, and the need for common
interoperability standards, many US-based products are available
only with export-length keys.

There is no technical, performance, or economic benefit to employing
keys shorter than needed.  Unlike, for example, the locks used to
protect our homes, very secure cryptographic systems with long keys
are no more expensive to produce or any harder to design or use
than weaker systems with shorter keys.  The only reason vendors
design systems with short keys is to comply with export requirements.

The key length figures and analysis in this section are based on
so-called "secret key" cryptosystems.  For technical reasons,
current public key cryptosystems employ much longer keys than secret
key systems to achieve equivalent security (public keys are measured
in hundreds or thousands of bits).  However, virtually all systems
that use public key cryptography also rely on secret key cryptography,
and so the overall strength of any system is limited by the weakest
encryption function and key length in it.


III  THE RISKS OF KEY ESCROW

A number of recent Administration initiatives have proposed that
future cryptosystems include special "key escrow" provisions to
facilitate access to encrypted data by law enforcement and intelligence
agencies.  In a such systems, copies of keys are automatically
deposited, in advance, with third parties who can use them to
arrange for law enforcement access if required in the future.
Several key escrow systems have been proposed by the Administration,
differing in the details of how keys are escrowed, and who the
third party key holders are.  In the first proposal, called the
"Clipper chip," the system is embedded in a special tamper-resistant
hardware-based cryptosystem and copies of keys are held by federal
agencies.  In the more recent "public key infrastructure" proposal,
keys are escrowed at the time a new public key is generated and
are held by the organization (public or private) responsible for
certification of the public key.

Although the various key escrow proposals differ in the details of
how they accomplish their objective, there are a number of very
serious fundamental problems and risks associated with all of them.

There are some appropriate commercial applications of key escrow
techniques.  A properly designed cryptosystem makes it essentially
impossible to recover encrypted data without the correct key.  This
can be a double-edge sword; the cost of keeping unauthorized parties
out is that if keys are lost or unavailable at the time they are
needed, the owner of encrypted data will be unable to make use of
his own information.  This problem, of balancing  secrecy with
assurances of continued availability, remains an area of active
research, and commercial solutions are starting to emerge.  The
Administration's initiatives do not address this problem especially
well, however.

The first problem with key escrow is the great increase in engineering
complexity that such systems entail.  The design and implementation
of even the simplest encryption systems is an extraordinarily
difficult and delicate process.  Very small changes can introduce
fatal security flaws that often can be exploited by an attacker.
Ordinary (non-escrowed) encryption systems have conceptually rather
simple requirements (for example, the secure transmission of data
between two parties) and yet, because there is no general theory
for designing them, we still often discover exploitable flaws in
fielded systems.  Key escrow renders even the specification of the
problem itself far more complex, making it virtually impossible to
assure that such systems work as they are intended to.  It is
possible, even likely, that lurking in any key escrow system are
one or more design weaknesses that allow recovery of data by
unauthorized parties. The commercial and academic world simply does
not have the tools to analyze or des

Key escrow is so difficult that even systems designed by the
classified world can have subtle problems that are only discovered
later.  In 1994 I discovered a new type of "protocol failure" in
the Escrowed Encryption Standard, the system on which the Clipper
chip is based.  The failure allows, contrary to the design objectives
of the system, a rogue user to circumvent the escrow system in a
way that makes the data unrecoverable by the government.  Others
weaknesses have been discovered since then that make it possible,
for example, to create incriminating messages that appear to have
originated from a particular user.

It should be noted that these weaknesses have been discovered in
spite of the fact that most of the details of the standard are
classified and were not included in the analysis that led to the
discovery of the flaws.  But these problems did not come about
because of incompetence on the part of the system's designers.
Indeed, the U.S. National Security Agency is likely the most advanced
cryptographic enterprise in the world, and is justifiably entrusted
with developing the cryptographic systems that safeguard the
government's most important military and state secrets.  The reason
the Escrowed Encryption Standard has flaws that are still being
discovered is that key escrow is an extremely difficult technical
problem, with requirements unlike anything previously encountered.

A second problem with key escrow arises from the difficulty of
operating a key escrow center in a secure manner.   According to
the Administration (for example, see the May 20, 1996 White House
draft report "Enabling Privacy, Commerce, Security and Public Safety
in the Global Information Infrastructure"), key escrow centers must
be prepared to respond to law enforcement requests for escrowed
data 24 hours a day, completing transactions within two hours of
receiving each request.  There are thousands of law enforcement
agencies in the United States authorized to perform electronic
surveillance, and the escrow center must be prepared to identify
and respond to any of them within this time frame.  If the escrow
center is also a commercial operation providing data recovery
services, it may also have tens of thousands of additional private
sector customers that it must be prepared to serve and respond to.
There are few, if any, secure systems that operate effectively on
such a scale and under such tightly-constr

A third problem with the Administration's key escrow proposals is
that they fail to distinguish between cryptographic keys for which
recovery might be required and those for which recoverability is
never needed.  There are many different kinds of encryption keys,
but for the purposes of discussing key escrow it is sufficient to
divide keys into three categories.  The first includes keys used
to encrypt stored information, which must be available throughout
the lifetime of the data.  The owner of the data has an obvious
interest in ensuring the continued availability of such keys, and
might choose to rely on a commercial service to store "backup"
copies of such keys.  A second category of key includes those used
to encrypt real-time communications such as telephone calls.  Here,
the key has no value to its owner once the transaction for which
it was used has completed.  If a key is lost or destroyed in the
middle of a conversation, a new one can be established in its place
without permanent loss of informatio

Unfortunately, however, the current Administration proposal exposes
all three types of keys equally to the risks introduced by the
escrow system, even though recoverability is not required for all
of them.  Partly this is because there is no intrinsic difference
in the structure of the different types of keys; they are usually
indistinguishable from one another outside of the application in
which they are used.

Finally, there is the problem that criminals can circumvent almost
any escrow system to avoid exposure to law enforcement monitoring.
All key escrow systems are vulnerable to so-called "superencryption,"
in which a user first encrypts data with an unescrowed key prior
to processing it with the escrowed system.  Most escrow systems
are also vulnerable to still other techniques that make it especially
easy to render escrowed keys useless to law enforcement.  The ease
of avoiding law enforcement when convenient raises an obvious
question as to whether the reduced security and high cost of setting
up an escrow system will yield any appreciable public safety benefit
in practice.


IV  CONCLUSIONS AND RECOMMENDATIONS

The wide availability of encryption is vitally important to the
future growth of our global information infrastructure.  In many
cases, encryption offers the only viable option for securing the
rapidly increasing range of human, economic and social activities
taking place over emerging communication networks.  It is no
exaggeration to say that the availability of encryption in the
commercial marketplace is and will continue to be necessary to
protect national security.  Unfortunately, current policy, through
export controls and ambiguous standards, discourages, rather than
promotes, the use of encryption.

Current encryption policy is enormously frustrating to almost
everyone working in the field.  Export controls make it difficult
to deploy effective cryptography even domestically, and we can do
little more than watch as our foreign colleagues and competitors,
not constrained by these rules, are matching our expertise and
obtaining an ever-increasing share of the market.  A large part of
the problem is that the current regulations were written as if to
cover hardware but are applied to software, including software in
the public domain or aimed at the mass market.  The PRO-CODE bill
goes a long way toward moving the regulations in line with the
realities of the technology.