******************************************************************
////////////// ////////////// //////////////
/// /// ///
/////// /////// ///////
/// /// ///
////////////// /// ///
******************************************************************
EFFector Online Volume 5 No. 14 8/5/1993 editors@eff.org
A Publication of the Electronic Frontier Foundation ISSN 1062-9424
-==--==--==-<>-==--==--==-
In this issue:
Answers to Clipper Questions
SKIPJACK Review
Another Job Opening at EFF
-==--==--==-<>-==--==--==-
****************************
Answers to Clipper Questions
****************************
In a previous EFFector Online, we printed some of the 114 questions sent to
President Clinton by the Digital Privacy & Security Working Group on the
Clipper Chip. On July 29, we received a response to these questions from
John D. Podesta, Assistant to the President and Staff Secretary. Some
highlights of the response follow. The complete text of the response will
be posted to EFF's ftp site.
Why is key escrow being proposed?
The development of key escrow encryption technology was born out of a
recognition on the part of the U.S. Government of the public's growing
desire for high quality encryption capability for commercial and private
use. At the same time, the Government was concerned that the widespread
use of this technology could make lawfully authorized electronic
surveillance much more difficult. Historically, law enforcement
encountered very little encryption, owing largely to the expense and
difficulty in using such technology. With growing availability of lower
cost, commercial encryption technology for use by U.S. industry and private
citizens, it became clear that a strategy was needed that could accommodate
the needs of the private sector for top notch communications security; of
U.S. industry to remain competitive in the world's secure communications
market; and of U.S. law enforcement to conduct lawfully-authorized
electronic surveillance.
Enhancing the government's ability to decrypt non-key escrow encryption
used by the targets of authorized law enforcement wiretaps is another
possible strategy for coping with the effects of encryption on law
enforcement. However, since encryption appears in a number of forms and
applications, the costs are likely to be substantial and may not be either
affordable or practical given the requirement for "real time" decryption in
the course of wiretap operations.
Why is the algorithm classified?
A classified algorithm is essential to the effectiveness of the key escrow
solution. The use of a classified algorithm assures no one can use the
algorithm in non-escrowed systems. Also, disclosure of the algorithm
would, in effect, provide the world with an extremely secure encryption
capability that could be implemented and used in systems by those whose
interests are adverse to U.S. national security interests. Finally, NSA
classifies all of the algorithms used for defense systems as part of its
policy to take all reasonable steps to assure the security of systems it
develops. The algorithm was classified in accordance with Executive Order
12356 and its implementing regulations.
For all these reasons the encryption algorithm could not be chosen from
those already available to the public, such as the Data Encryption Standard
(DES). Similarly, the algorithm cannot be published for public review and
comment. Nonetheless, in keeping with the Presidential Decision Directive
of April to allow independent experts to review the integrity of the
classified algorithm, five such experts have already begun a study of the
algorithm. We expect their findings to be made public soon.
Is the key escrow initiative compatible with constitutional rights?
Questions have been raised whether the requirement of key disclosure
infringes upon one's right to free speech under the First Amendment, the
right against self incrimination contained in the Fifth Amendment, or the
right against improper search and seizure in the Fourth Amendment. The key
escrow scheme does not require the owner or user of a device equipped with
the key escrow encryption chip to say or produce anything. The key escrow
technique in no way addresses the issue of what people may choose to say,
and the individual user of key escrow products will not be required to
provide the government any information. Indeed, the individual will not
know the keys. Thus, this technology or technique in no way impacts the
rights available under the First or Fifth Amendments.
Law enforcement organizations will not be able to decrypt communications
without the device unique key and they can only obtain the key components
needed to determine a device unique key after making an appropriate
certification of their authority to conduct electronic surveillance to the
independent key escrow agents. Thus, this technology actually strengthens
the Fourth Amendment protections afforded individuals, since law
enforcement cannot obtain the contents of communications without first
obtaining the key component.
Will use of the key escrow technology be required?
One point clearly stated in the Presidential Decision Directive and
emphasized several times since April is that use of key escrow encryption
technology is voluntary. While the U.S. government encourages its use
because of the excellent security it provides, and will promulgate
standards permitting its use by government departments and agencies, there
is no requirement that the public use it. No doubt some, particularly
those intent on thwarting authorized wiretaps, will buy other forms of
encryption or could "double encrypt" their communications suing a key
escrow device in combination with a non-escrowed device. But we believe
the vast majority will buy this system because it is easy to use, provides
superb security, and likely will be readily available in commercial
products.
The Administration has chosen to encourage the widespread use of key escrow
devices rather than mandating or regulating its use. Though we recognize
the risks to law enforcement activities posed by the widespread use of
sophisticated encryption products, we also recognize that encryption is an
effective means to secure communications and computer systems. Thus far,
government purchases and standards have created secure products that sere
bought by private citizens "piggybacking" on the government's development
effort. It makes little sense for the government to promulgate standards
or to develop products that will defeat law enforcement interests if and
when they spread to the private sector. Because these measures may be
sufficient to make key escrow encryption the easiest and most available
privacy protection it would be imprudent to pursue the far more drastic
step of regulating private encryption. The Administration has progressed
far enough in its review to conclude it will not propose new legislation to
limit use of encryption technology.
***************
SKIPJACK Review
***************
The following interim report on the SKIPJACK, formerly Clipper, chip was
posted by Dorothy Denning to sci.crypt. It is reprinted here for
nonmembers of that list.
SKIPJACK Review
Interim Report
The SKIPJACK Algorithm
Ernest F. Brickell, Sandia National Laboratories
Dorothy E. Denning, Georgetown University
Stephen T. Kent, BBN Communications Corporation
David P. Maher, AT&T
Walter Tuchman, Amperif Corporation
July 28, 1993
(copyright 1993)
Executive Summary
The objective of the SKIPJACK review was to provide a mechanism whereby
persons outside the government could evaluate the strength of the
classified encryption algorithm used in the escrowed encryption devices
and publicly report their findings. Because SKIPJACK is but one
component of a large, complex system, and because the security of
communications encrypted with SKIPJACK depends on the security of the
system as a whole, the review was extended to encompass other
components of the system. The purpose of this Interim Report is to
report on our evaluation of the SKIPJACK algorithm. A later Final
Report will address the broader system issues.
The results of our evaluation of the SKIPJACK algorithm are as
follows:
1. Under an assumption that the cost of processing power is halved
every eighteen months, it will be 36 years before the cost of
breaking SKIPJACK by exhaustive search will be equal to the cost
of breaking DES today. Thus, there is no significant risk that
SKIPJACK will be broken by exhaustive search in the next 30-40
years.
2. There is no significant risk that SKIPJACK can be broken through a
shortcut method of attack.
3. While the internal structure of SKIPJACK must be classified in
order to protect law enforcement and national security objectives,
the strength of SKIPJACK against a cryptanalytic attack does not
depend on the secrecy of the algorithm.
1. Background
On April 16, the President announced a new technology initiative aimed
at providing a high level of security for sensitive, unclassified
communications, while enabling lawfully authorized intercepts of
telecommunications by law enforcement officials for criminal
investigations. The initiative includes several components:
A classified encryption/decryption algorithm called "SKIPJACK."
Tamper-resistant cryptographic devices (e.g., electronic chips),
each of which contains SKIPJACK, classified control software, a
device identification number, a family key used by law enforcement,
and a device unique key that unlocks the session key used to
encrypt a particular communication.
A secure facility for generating device unique keys and programming
the devices with the classified algorithms, identifiers, and keys.
Two escrow agents that each hold a component of every device unique
key. When combined, those two components form the device unique
key.
A law enforcement access field (LEAF), which enables an authorized
law enforcement official to recover the session key. The LEAF is
created by a device at the start of an encrypted communication and
contains the session key encrypted under the device unique key
together with the device identifier, all encrypted under the family
key.
LEAF decoders that allow an authorized law enforcement official to
extract the device identifier and encrypted session key from an
intercepted LEAF. The identifier is then sent to the escrow
agents, who return the components of the corresponding device
unique key. Once obtained, the components are used to reconstruct
the device unique key, which is then used to decrypt the session
key.
This report reviews the security provided by the first component,
namely the SKIPJACK algorithm. The review was performed pursuant to
the President's direction that "respected experts from outside the
government will be offered access to the confidential details of the
algorithm to assess its capabilities and publicly report their
finding." The Acting Director of the National Institute of Standards
and Technology (NIST) sent letters of invitation to potential
reviewers. The authors of this report accepted that invitation.
We attended an initial meeting at the Institute for Defense Analyses
Supercomputing Research Center (SRC) from June 21-23. At that meeting,
the designer of SKIPJACK provided a complete, detailed description of
the algorithm, the rationale for each feature, and the history of the
design. The head of the NSA evaluation team described the evaluation
process and its results. Other NSA staff briefed us on the LEAF
structure and protocols for use, generation of device keys, protection
of the devices against reverse engineering, and NSA's history in the
design and evaluation of encryption methods contained in SKIPJACK.
Additional NSA and NIST staff were present at the meeting to answer our
questions and provide assistance. All staff members were forthcoming
in providing us with requested information.
At the June meeting, we agreed to integrate our individual evaluations
into this joint report. We also agreed to reconvene at SRC from July
19-21 for further discussions and to complete a draft of the report.
In the interim, we undertook independent tasks according to our
individual interests and availability. Ernest Brickell specified a
suite of tests for evaluating SKIPJACK. Dorothy Denning worked at NSA
on the refinement and execution of these and other tests that took into
account suggestions solicited from Professor Martin Hellman at Stanford
University. NSA staff assisted with the programming and execution of
these tests. Denning also analyzed the structure of SKIPJACK and its
susceptibility to differential cryptanalysis. Stephen Kent visited NSA
to explore in more detail how SKIPJACK compared with NSA encryption
algorithms that he already knew and that were used to protect
classified data. David Maher developed a risk assessment approach
while continuing his ongoing work on the use of the encryption chip in
the AT&T Telephone Security Device. Walter Tuchman investigated the
anti-reverse engineering properties of the chips.
We investigated more than just SKIPJACK because the security of
communications encrypted with the escrowed encryption technology
depends on the security provided by all the components of the
initiative, including protection of the keys stored on the devices,
protection of the key components stored with the escrow agents, the
security provided by the LEAF and LEAF decoder, protection of keys
after they have been transmitted to law enforcement under court order,
and the resistance of the devices to reverse engineering. In addition,
the success of the technology initiative depends on factors besides
security, for example, performance of the chips. Because some
components of the escrowed encryption system, particularly the key
escrow system, are still under design, we decided to issue this Interim
Report on the security of the SKIPJACK algorithm and to defer our Final
Report until we could complete our evaluation of the system as a
whole.
2. Overview of the SKIPJACK Algorithm
SKIPJACK is a 64-bit "electronic codebook" algorithm that transforms a
64-bit input block into a 64-bit output block. The transformation is
parameterized by an 80-bit key, and involves performing 32 steps or
iterations of a complex, nonlinear function. The algorithm can be used
in any one of the four operating modes defined in FIPS 81 for use with
the Data Encryption Standard (DES).
The SKIPJACK algorithm was developed by NSA and is classified SECRET.
It is representative of a family of encryption algorithms developed in
1980 as part of the NSA suite of "Type I" algorithms, suitable for
protecting all levels of classified data. The specific algorithm,
SKIPJACK, is intended to be used with sensitive but unclassified
information.
The strength of any encryption algorithm depends on its ability to
withstand an attack aimed at determining either the key or the
unencrypted ("plaintext") communications. There are basically two
types of attack, brute-force and shortcut.
3. Susceptibility to Brute Force Attack by Exhaustive Search
In a brute-force attack (also called "exhaustive search"), the
adversary essentially tries all possible keys until one is found that
decrypts the intercepted communications into a known or meaningful
plaintext message. The resources required to perform an exhaustive
search depend on the length of the keys, since the number of possible
keys is directly related to key length. In particular, a key of length
N bits has 2^N possibilities. SKIPJACK uses 80-bit keys, which means
there are 2^80 (approximately 10^24) or more than 1 trillion
possible keys.
An implementation of SKIPJACK optimized for a single processor on the
8-processor Cray YMP performs about 89,000 encryptions per second. At
that rate, it would take more than 400 billion years to try all keys.
Assuming the use of all 8 processors and aggressive vectorization, the
time would be reduced to about a billion years.
A more speculative attack using a future, hypothetical, massively
parallel machine with 100,000 RISC processors, each of which was
capable of 100,000 encryptions per second, would still take about 4
million years. The cost of such a machine might be on the order of $50
million. In an even more speculative attack, a special purpose machine
might be built using 1.2 billion $1 chips with a 1 GHz clock. If the
algorithm could be pipelined so that one encryption step were performed
per clock cycle, then the $1.2 billion machine could exhaust the key
space in 1 year.
Another way of looking at the problem is by comparing a brute force
attack on SKIPJACK with one on DES, which uses 56-bit keys. Given that
no one has demonstrated a capability for breaking DES, DES offers a
reasonable benchmark. Since SKIPJACK keys are 24 bits longer than DES
keys, there are 2^24 times more possibilities. Assuming that the cost
of processing power is halved every eighteen months, then it will not
be for another 24 * 1.5 = 36 years before the cost of breaking
SKIPJACK is equal to the cost of breaking DES today. Given the lack of
demonstrated capability for breaking DES, and the expectation that the
situation will continue for at least several more years, one can
reasonably expect that SKIPJACK will not be broken within the next
30-40 years.
Conclusion 1: Under an assumption that the cost of processing power
is halved every eighteen months, it will be 36 years before the cost of
breaking SKIPJACK by exhaustive search will be equal to the cost of
breaking DES today. Thus, there is no significant risk that SKIPJACK
will be broken by exhaustive search in the next 30-40 years.
4. Susceptibility to Shortcut Attacks
In a shortcut attack, the adversary exploits some property of the
encryption algorithm that enables the key or plaintext to be determined
in much less time than by exhaustive search. For example, the RSA
public-key encryption method is attacked by factoring a public value
that is the product of two secret primes into its primes.
Most shortcut attacks use probabilistic or statistical methods that
exploit a structural weakness, unintentional or intentional (i.e., a
"trapdoor"), in the encryption algorithm. In order to determine
whether such attacks are possible, it is necessary to thoroughly
examine the structure of the algorithm and its statistical properties.
In the time available for this review, it was not feasible to conduct
an evaluation on the scale that NSA has conducted or that has been
conducted on the DES. Such review would require many man-years of
effort over a considerable time interval. Instead, we concentrated on
reviewing NSA's design and evaluation process. In addition, we
conducted several of our own tests.
4.1 NSA's Design and Evaluation Process
SKIPJACK was designed using building blocks and techniques that date
back more than forty years. Many of the techniques are related to work
that was evaluated by some of the world's most accomplished and famous
experts in combinatorics and abstract algebra. SKIPJACK's more
immediate heritage dates to around 1980, and its initial design to
1987.
SKIPJACK was designed to be evaluatable, and the design and evaluation
approach was the same used with algorithms that protect the country's
most sensitive classified information. The specific structures
included in SKIPJACK have a long evaluation history, and the
cryptographic properties of those structures had many prior years of
intense study before the formal process began in 1987. Thus, an
arsenal of tools and data was available. This arsenal was used by
dozens of adversarial evaluators whose job was to break SKIPJACK. Many
spent at least a full year working on the algorithm. Besides highly
experienced evaluators, SKIPJACK was subjected to cryptanalysis by less
experienced evaluators who were untainted by past approaches. All
known methods of attacks were explored, including differential
cryptanalysis. The goal was a design that did not allow a shortcut
attack.
The design underwent a sequence of iterations based on feedback from
the evaluation process. These iterations eliminated properties which,
even though they might not allow successful attack, were related to
properties that could be indicative of vulnerabilities. The head of
the NSA evaluation team confidently concluded "I believe that SKIPJACK
can only be broken by brute force there is no better way."
In summary, SKIPJACK is based on some of NSA's best technology.
Considerable care went into its design and evaluation in accordance
with the care given to algorithms that protect classified data.
4.2 Independent Analysis and Testing
Our own analysis and testing increased our confidence in the strength
of SKIPJACK and its resistance to attack.
4.2.1 Randomness and Correlation Tests
A strong encryption algorithm will behave like a random function of the
key and plaintext so that it is impossible to determine any of the key
bits or plaintext bits from the ciphertext bits (except by exhaustive
search). We ran two sets of tests aimed at determining whether
SKIPJACK is a good pseudo random number generator. These tests were
run on a Cray YMP at NSA. The results showed that SKIPJACK behaves
like a random function and that ciphertext bits are not correlated with
either key bits or plaintext bits. Appendix A gives more details.
4.2.2 Differential Cryptanalysis
Differential cryptanalysis is a powerful method of attack that exploits
structural properties in an encryption algorithm. The method involves
analyzing the structure of the algorithm in order to determine the
effect of particular differences in plaintext pairs on the differences
of their corresponding ciphertext pairs, where the differences are
represented by the exclusive-or of the pair. If it is possible to
exploit these differential effects in order to determine a key in less
time than with exhaustive search, an encryption algorithm is said to be
susceptible to differential cryptanalysis. However, an actual attack
using differential cryptanalysis may require substantially more chosen
plaintext than can be practically acquired.
We examined the internal structure of SKIPJACK to determine its
susceptibility to differential cryptanalysis. We concluded it was not
possible to perform an attack based on differential cryptanalysis in
less time than with exhaustive search.
4.2.3 Weak Key Test
Some algorithms have "weak keys" that might permit a shortcut
solution. DES has a few weak keys, which follow from a pattern of
symmetry in the algorithm. We saw no pattern of symmetry in the
SKIPJACK algorithm which could lead to weak keys. We also
experimentally tested the all "0" key (all 80 bits are "0") and the all
"1" key to see if they were weak and found they were not.
4.2.4 Symmetry Under Complementation Test
The DES satisfies the property that for a given plaintext-ciphertext
pair and associated key, encryption of the one's complement of the
plaintext with the one's complement of the key yields the one's
complement of the ciphertext. This "complementation property" shortens
an attack by exhaustive search by a factor of two since half the keys
can be tested by computing complements in lieu of performing a more
costly encryption. We tested SKIPJACK for this property and found that
it did not hold.
4.2.5 Comparison with Classified Algorithms
We compared the structure of SKIPJACK to that of NSA Type I algorithms
used in current and near-future devices designed to protect classified
data. This analysis was conducted with the close assistance of the
cryptographer who developed SKIPJACK and included an in-depth
discussion of design rationale for all of the algorithms involved.
Based on this comparative, structural analysis of SKIPJACK against
these other algorithms, and a detailed discussion of the similarities
and differences between these algorithms, our confidence in the basic
soundness of SKIPJACK was further increased.
Conclusion 2: There is no significant risk that SKIPJACK can be broken
through a shortcut method of attack.
5. Secrecy of the Algorithm
The SKIPJACK algorithm is sensitive for several reasons. Disclosure of
the algorithm would permit the construction of devices that fail to
properly implement the LEAF, while still interoperating with legitimate
SKIPJACK devices. Such devices would provide high quality
cryptographic security without preserving the law enforcement access
capability that distinguishes this cryptographic initiative.
Additionally, the SKIPJACK algorithm is classified SECRET NOT
RELEASABLE TO FOREIGN NATIONALS. This classification reflects the high
quality of the algorithm, i.e., it incorporates design techniques that
are representative of algorithms used to protect classified
information. Disclosure of the algorithm would permit analysis that
could result in discovery of these classified design techniques, and
this would be detrimental to national security.
However, while full exposure of the internal details of SKIPJACK would
jeopardize law enforcement and national security objectives, it would
not jeopardize the security of encrypted communications. This is
because a shortcut attack is not feasible even with full knowledge of
the algorithm. Indeed, our analysis of the susceptibility of SKIPJACK
to a brute force or shortcut attack was based on the assumption that
the algorithm was known.
Conclusion 3: While the internal structure of SKIPJACK must be
classified in order to protect law enforcement and national security
objectives, the strength of SKIPJACK against a cryptanalytic attack
does not depend on the secrecy of the algorithm.
**************************
Another Job Opening at EFF
**************************
ONLINE ACTIVIST
The Electronic Frontier Foundation (EFF), a nonprofit organization
dedicated to protecting civil liberties for users of newly emerging
technologies, is looking to hire an Online Activist.
The Online Activist will actively participate in and organize EFF's sites
on CompuServe, America Online, GEnie, Usenet and the WELL and will
distribute feedback from the various networks to EFF staff and board
through regular online summaries. This person will provide
leadership to groups of members and will possibly set up and maintain an
EFF BBS. The Online Activist will help to maintain EFF's ftp library.
This person will train new EFF staff members on online communications.
S/he will collect and solicit articles for, write articles for, edit and
assemble our biweekly electronic newsletter, EFFector Online. The Online
Activist will work with the System Administrator to distribute and post
EFFector Online and other EFF electronic publications and to maintain a
database of form answers for commonly asked questions, along with the
Membership Coordinator. This person must be willing to work out of EFF's
offices in Washington, DC.
The Electronic Frontier Foundation offers a competitive salary with
excellent benefits. For immediate consideration, please forward a resume,
along with a cover letter describing your online experience and reason for
applying for this job by August 23, 1993, to:
Online Activist Search
Electronic Frontier Foundation
1001 G Street, NW
Suite 950 East
Washington, DC 20001
fax (202) 393-5509
e-mail ssteele@eff.org (ASCII only, please)
EFF is an Equal Opportunity Employer.
=============================================================
EFFector Online is published biweekly by:
Electronic Frontier Foundation
1001 G Street, N.W., Suite 950 East
Washington, DC 20001 USA
Phone: +1 202 347 5400 FAX: +1 202 393 5509
Internet Address: eff@eff.org
Coordination, production and shipping by Shari Steele,
Director of Legal Services & Community Outreach (ssteele@eff.org)
Reproduction of this publication in electronic media is encouraged. Signed
articles do not necessarily represent the view of the EFF. To reproduce
signed articles individually, please contact the authors for their express
permission.
*This newsletter is printed on 100% recycled electrons.*
=============================================================
MEMBERSHIP IN THE ELECTRONIC FRONTIER FOUNDATION
In order to continue the work already begun and to expand our efforts and
activities into other realms of the electronic frontier, we need the
financial support of individuals and organizations.
If you support our goals and our work, you can show that support by
becoming a member now. Members receive our biweekly electronic newsletter,
EFFector Online (if you have an electronic address that can be reached
through the Net), and special releases and other notices on our activities.
But because we believe that support should be freely given, you can
receive these things even if you do not elect to become a member.
Your membership/donation is fully tax deductible.
Our memberships are $20.00 per year for students and $40.00 per year for
regular members. You may, of course, donate more if you wish.
=============================================================
Mail to:
Membership Coordinator
Electronic Frontier Foundation
1001 G Street, N.W.
Suite 950 East
Washington, DC 20001 USA
Membership rates:
$20.00 (student or low income membership)
$40.00 (regular membership)
[ ] I wish to become a member of the EFF. I enclose: $_______
[ ] I wish to renew my membership in the EFF. I enclose: $_______
[ ] I enclose an additional donation of $_______
Name:
Organization:
Address:
City or Town:
State: Zip: Phone: ( ) (optional)
FAX: ( ) (optional)
E-mail address:
I enclose a check [ ].
Please charge my membership in the amount of $
to my Mastercard [ ] Visa [ ] American Express [ ]
Number:
Expiration date:
Signature: ______________________________________________
Date:
I hereby grant permission to the EFF to share my name with
other nonprofit groups from time to time as it deems
appropriate. Initials:______________________
