Ernest F. Brickell, Sandia National
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)
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:
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.
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.
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.
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.
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.
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.
Conclusion 2: There is no significant risk that SKIPJACK can be broken through a shortcut method of attack.
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.
Copyright © 1994-1996 Quadralay Corporation. All rights reserved.