Commercial Key Escrow: part 1 of 2

[David Farber <farber () central cis upenn edu>]

Posted-Date: Wed, 4 Jan 1995 10:49:27 -0500
To: farber () central cis upenn edu


This paper describes the ideas  mentioned a few weeks
ago. Comments are welcome. Feel free to distribute widely.
A paper copy with the 2 figures is in the mail to you.  It is also
available from ftp.tis.com directory /pub/crypto/cke.


Happy New Year.


Steve




                   Commercial Key Escrow:


                   Something for Everyone
                   Now and for the Future


                      Stephen T. Walker
                      Steven B. Lipner
                       Carl M. Ellison
                     Dennis K. Branstad
                      David M. Balenson


                Trusted Information Systems, Inc.


                       January 3, 1995




Summary


A tension has been growing for the past twenty years between the
interests of the public to protect its sensitive information and
the interests of governments to access the information of their
adversaries. The Clipper Key Escrow program, introduced by the
U.S. Government in 1993, was an attempt to overcome this tension
by giving the public good cryptography while retaining for law
enforcement the ability to decrypt communications when
authorized.  But Clipper has many problems that make it
unattractive to the public.


The basic concepts of key escrow are very attractive to
individuals and organizations who fear the consequences of losing
their encryption keys.  A key escrow system that satisfies the
concerns of individuals and corporations and also meets
governments  interests could help resolve this growing national
tension.


This paper reviews the reasons for this tension and the evolution
of software key escrow systems.  It then examines the variety of
alternative key escrow systems and describes why the government
must take urgent steps to promote commercial key escrow before
serious and permanent harm is done to government s law
enforcement and national security interests.


A Fundamental Tension


Secret writing has existed since the beginning of recorded
history.  During this century, encryption has been largely the
domain of governments.  The history of World War II shows how
important the secret wars over secret communications have been
and still are to the conduct of modern government. During most of
this time, the general public had little knowledge of or interest
in encryption.


Twenty years ago, with the introduction by the U.S. Government of
the Data Encryption Standard (DES), encryption was made easily
accessible to the public for protecting sensitive, non government
information.  DES awakened public interest in encryption that led
to, among other things, the development of public key
cryptography by non-government scientists.  The public s desire
to be able to protect its sensitive information quickly led to a
fundamental tension between governments and their people over the
"right" of individuals to protect important information versus
the "right" of governments to listen to the communications of
their adversaries.


Governments have always used export controls1 on cryptography to
attempt to control its proliferation and use against their
interests.  Even though the use of encryption is not controlled
in most countries, U.S. Government export controls have seriously
impeded the use of encryption in commercially available software
products and thus its use by individuals and organizations within
as well as outside the U.S. This de facto internal use control
has served to increase the tension between the public and its
government.


With the explosion of personal computers and global information
infrastructures, this tension has increased further, as more
citizens have realized that their sensitive information is openly
vulnerable, and, some argue, the national economic interest is at
stake.


Congressional hearings [Brooks] warned of serious consequences of
foreign and domestic industrial and government espionage.
National Research Council reports [NRC] repeatedly called for a
careful examination of these issues.


A National Cryptography Policy?


During this period, a proposal was put forth for a national
cryptography policy, which was intended to forge an acceptable
balance between both sides:


       Good Cryptography shall be available to the public without
       government restriction, where


              "Good cryptography" is defined as DES (with 56-bit
              keys) and RSA with a modulus less than 1024 bits, and


              "without government restriction" means without export
              control or other mandatory government restriction.


It was noted that the present de facto national cryptography
policy in effect defines "good cryptography" as symmetric key
algorithms restricted to 40 bits and asymmetric keys limited to
512 bits.


Even though this proposed policy highlighted that the gap between
the public's and the government's interests may be only the
difference between 56 bits and 40 bits, that gap appeared
effectively insurmountable.


The tension rose to the point where those who spoke in favor of
the national economic interests and of the reality of worldwide
availability of cryptography, even in the face of government
export controls, were accused of acting against the interests of
national security. Clearly something was needed to relieve this
fundamental tension.


Enter Clipper - a Tension Reliever?


In April 1993, the U.S. Government introduced Clipper2, and with
it a new concept, key escrow, which was intended to relieve some
of the tension.  The idea was to give the public good encryption,
better than was generally available before, but retain the
ability for law enforcement, when authorized, to access encrypted
communications or files.  It was hoped that this would satisfy
the interests of both sides and relieve the growing tension.


But Clipper has problems.  In order to provide
better-than-commonly-available encryption, a classified
encryption algorithm is used that must be embedded in hardware to
be protected from disclosure.  Software vendors want a software
solution.  The classified algorithm stirs suspicion: Is it really
as good as claimed, or does it have special trap doors?  Despite
the early years of controversy, much of the public has come to
trust DES to an extent that any other algorithm that has not
undergone many years of public scrutiny will not be acceptable.


And the Clipper form of key escrow, which we will henceforth
refer to as government key escrow, has problems of its own.  It
requires extensive government-controlled data bases of escrowed
keys.  Once the key for a hardware chip is revealed, that chip
could be compromised forever.  The government established a wide
variety of procedures to safeguard against abuse: two key escrow
centers so neither had the whole key, controls on who could
access the escrowed keys, and more, but concerns remained.


The biggest problem with government key escrow is that it does
nothing for the user or his or her employer.  While it ensures
that the government can always have access to a key to decrypt
communications or files, if a user loses his or her key,
government key escrow will not help. Any Marketing 101 class will
convince us that a product that does little or nothing for its
purchaser will not fare well in the marketplace.  Without a solid
market incentive, Clipper will likely be restricted to a segment
of the market driven mostly by mandatory government requirements.




Following Clipper s introduction last year, opposition by the
software vendors, civil liberties groups, and users in general
grew very rapidly.  In hearings on Clipper by the Computer System
Security and Privacy Advisory Board (CSSPAB) during the summer of
1993, speaker after speaker arose in opposition to any form of
government key escrow.


Congressional hearings were called in October 1993 and again in
May 1994.  Congress called for another National Research Council
study, this time focused on what our national cryptography policy
should be.  This study finally began in October 1994 with an
eighteen to twenty-four month duration.


During this same period, the most significant challenge to the
continued export control of encryption as a munition was mounted
by Congresswoman Cantwell [Cantwell] and others.  National
security and law enforcement authorities mounted a strong
counterattack that eventually resulted in 1) a letter from the
Vice President to Congresswoman Cantwell, professing the
Administration's interest in alternatives to Clipper [Gore] and
2) withdrawal of the Cantwell amendment.


Meanwhile, sales of Clipper devices have languished.  It appears
highly unlikely that government key escrow will provide that
critical element that will relieve the tension between the
government's and the public's interests in encryption.  If
anything, Clipper seems to have raised the level of public
awareness of this tension to new heights [Time].  What used to be
primarily a debate among technical people has reached the general
public.  The tension has risen in ways never before seen.


Can a Generally Useful Key Escrow System Be Built?


The concept of key escrow in its most general sense is much
broader than the government key escrow envisioned in Clipper.3
The idea of an encryption system in which the user or his or her
employer can recover a lost key and thus "lost" encrypted
information is a very important and attractive concept.  Many
organizations have refrained from using encryption, even though
they know they may lose vital sensitive information to
adversaries, because they fear their own loss of that information
if the encryption key is lost or the person who encrypted the
data is unavailable for whatever reason.


A commercial key escrow system that serves the needs of the user,
his or her employer, the software publishing industry as well as
the government's interests would exert a major influence in
relaxing the tension that has been holding the government and
much of the public at odds.  Can such a system be built?


First Step: A Clipper Software Key Escrow Design


In the spring of 1994, we developed a software key escrow system
that we believe provides law enforcement capabilities equivalent
to those of Clipper [TIS].  Designed to parallel government key
escrow as closely as possible, our Clipper Software Key Escrow
design (See Figure 1) has several advantages over the hardware
Clipper system.


It can be implemented entirely in software (firmware or hardware
implementations are also possible but not necessary).  It can use
any encryption algorithm for the basic encryption functions.  Our
design could be used with classified algorithms such as Skipjack,
but software- only solutions will not protect the secrecy of the
algorithm.


Our design uses public key cryptography, with the government
controlling the private keys of the public / private key pairs
associated with each software product.  All of the information in
the user's software packages is publicly available.  This gives
our approach a unique advantage in detecting spoofing of the Law
Enforcement Access Field (LEAF).  The receiving or decrypting
program has available to it all of the information to completely
reconstruct the LEAF and compare it with the received LEAF.  In
this way, our design can detect even single bit errors in the
session key used in constructing the LEAF.  Our design is not
subject to the attacks on the Clipper design proposed by Matt
Blaze [Blaze].


We have implemented our design in a prototype demonstration that
has been shown widely to the government and industry.  This
demonstration has led to extensive discussions within government
and between government and industry concerning the government's
interest in software key escrow systems, as expressed in the Vice
President's letter to Congresswoman Cantwell [Gore].


       A Word on Software Binding


It is essential for any software key escrow system to be closely
bound to the application that it is protecting.4  Concerns for a
user disabling the key escrow process or for pirated copies of an
escrow-enabled software product being sold with the key escrow
process disabled have been the major impediments to consideration
of software solutions in the past.


In order to make progress, we must understand what we are trying
to prevent with either a hardware or software solution.  In
either case, we cannot prevent someone from writing software that
employs encryption without key escrow.  We also cannot prevent a
pair of sophisticated software hackers from modifying their own
copies of a program that uses either hardware or software key
escrow since we know the dual-rogue issue cannot be stopped with
either hardware or software.


The threat we must try to prevent in the case of software key
escrow is the widespread deployment of a pirated copy of an
escrow-enabled commercial product wherein the key escrow has been
defeated.  We believe that, against this type of threat, we can
make software binding arbitrarily difficult and thus deter
attempts to reverse engineer the original product. Such binding
techniques will more likely force the pirate back to writing his
or her own incompatible version from scratch.  As with all such
techniques, however, the more difficult one makes reverse
engineering, the harder it may become to maintain the product.
Such tradeoffs are part of the process we must all understand to
build a system that satisfies all interested parties.


Second Step: A Commercial Key Escrow System


A software-based Clipper design is still a Clipper design, and we
have already established that Clipper is not the tension reliever
that we have been seeking. So in August 1994, we set about to
devise a commercial key escrow system that would address the
objections to Clipper without sacrificing the government's law
enforcement interests.


Our commercial key escrow design (see figure 2) employs a Data
Recovery Center (DRC) established by a commercial entity (a
corporation might establish one for its own use or a bonded
service organization might offer the service for the public at
large).  A corporate DRC will be a central point within the
organization with which all corporate "escrow-enabled (EE)"
software programs are registered.  We envision the general
process as follows:


       Initialization:  Registration takes place when the user
       installs the EE program on his or  her workstation or
       laptop. Registration consists of the user providing the DRC
       with the information needed to authenticate himself or
       herself if it should be necessary to recover a lost
       encryption key.  During registration, the DRC will return to
       the user's program an identifier for the user, the DRC's
       public key (its private key is held in secret by the DRC),
       and the identity of the DRC itself.


       Key Escrow:  Every time an EE program encrypts a file or
       message, it will add a Data Recovery Field (DRF) that
       contains the session key and user's identity encrypted in
       the DRC's public key and the DRC's public identifier.  This
       information is stored within the file   or message and is
       the only place that the encrypted session key is kept. There
       is no data base of escrowed keys at the DRC or any where
       else.


       Recovery:  If the user ever finds he or she is unable to
       decrypt a message, the user need only send the DRF along
       with proper authentication to the DRC.  The DRC will use its
       private key to decrypt the session key and return it to the
       user using a protected protocol exchange.  If corporate
       management should ever need to decrypt a file or message
       from an employee who is unavailable, they can obtain the
       session key from the DRC by a similar means.


       Liability:  The question of liability for loss of the
       information by improper disclosure is eliminated in the
       corporate case, since all of the information is already the
       property of the corporation.  Liability in the case of a
       bonded public service DRC is no different from that faced by
       other bonded services.


       Law Enforcement:  If law enforcement authorities ever need
       to decrypt a file or message of an employee of a company,
       they need only approach management with appropriate legal
       authority, and they, too, can obtain the session key in
       question.  The issue of law enforcement access is thus
       reduced to an already well-understood legal procedure. If
       law enforcement anticipates that it may encounter many such
       files or messages, it may be able to establish a means to
       obtain rapid access once initial authority has been
       obtained.


       If an individual needs to encrypt information of a personal
       nature, he or she may decide to subscribe to one of many
       bonded commercial key escrow services that are expected to
       become available.  In this case, only the user will normally
       be able to access the escrowed session key.  But law
       enforcement, given the appropriate legal authorization, will