|
ICSA Guide to Cryptography Randall Nichols $69.95 0-07-913759-8 |
|
| Chapter: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 10 |
| Reserve your copy at a Beta Bookstore near you! |
Contact Bet@books © 1998 The McGraw-Hill Companies, Inc. All rights reserved. Any use of this Beta Book is subject to the rules stated in the Terms of Use. |
In 1997, NIST requested public comment on an Advanced Encryption Standard (AES) to replace their old workhorse DES. It is amazing (and a testament to its founders) that DES in its various forms has lasted for so many years as a viable cryptographic package. The new AES will be secure with 256 bit keys.
DES represents the turning point from classical cryptography into modern cryptography. DES is nothing more than a complex combination of the substitution and transposition systems. We need to define some new information concepts to understand why the DES combination of simpler systems makes for such a strong in situ cryptosystem.
Invertible Transformations
Encryption is the key operation at the disposal of cryptography. It is a special computation that operates on messages, converting them into representation that is meaningless for all parties other than the intended receiver. Transformations effected on messages are so intricate that it is beyond the means of the interloper to undo the process. Modern cryptosystems rely upon the difficulty of reversing the encryption transformation as a basis for a secure communication.
The encryption algorithm is chosen from a family of invertible transformations known as the general system, or cryptosystem. The parameter that selects the particular transformation from the family is called the enciphering key. The cryptosystem may take any of several forms, a set of instructions, a piece of hardware or a program, one of which is selected by the enciphering key.
Public key schemes are based on a class of functions known as one-way trapdoor functions; derived from a class of computationally difficult problems termed NP (non-deterministic polynomial) problems. Private secret key schemes, in contrast, rely on a series of complex substitution and transposition operations, called involution, which are very difficult to analyze mathematically.
Formally, a cryptosystem is a single parameter family of invertible transformations,
Ek; K Î K Eq. 6-1
where K is the keyspace, which is of finite length, with elements k1, k2...kn. If M is the message space and C is the cryptogram or cipher text space, then the system must have the following properties:
Ek: M -> C Eq. 6-2
for any fixed encryption key k Î K, Ek is an invertible transformation of the message space into the cryptogram space, i.e. Ek(M) = C, where M Î M and C Î C;
there is an inverse algorithm Ek -1 = Dk called the decryption algorithm
Dk: C -> M, such that Dk(C) = Dk[Ek(M)] = M ; Eq. 6-3
Ek1(M) ¹ Ek2(M) if k1 ¹ k2 Eq. 6-4
Modern cryptography deals with the design and analysis of systems that provide secure communications or resist cryptanalysis. A system is said to be compromised (or "cracked" or "exploited" in the lingo) via cryptanalysis if it is possible to recover the original message, plain text, from the cipher text, without knowledge of the key used in the encryption algorithm.
Cryptanalysis draws from such disciplines as probability theory, number theory, statistics and algebra, topology, chaos theory, matrix theory, non linear calculus, and communication language. The redundant properties of language, which often give a valuable point of entry to the solution, are usually well masked in modern cryptography.
Cryptanalysis is a system identification problem and the goal of cryptography is to build systems that are hard to identify. An ideal system is one that has a flat distribution for all statistical properties of the cipher, implying that the redundant qualities of the natural language have been obscured.
In 1948, research performed by Shannon characterized the two main methods of uniformly distributing the redundant characteristics of a natural language. First through diffusion, which spreads the correlation’s and dependencies of the messages over substrings as long as feasible so as to maximize the unicity distance. The unicity distance indicates the number of characters needed to determine the key. The second approach is confusion, where the functional dependencies of the related variables are made as complex as possible so as to increase the time needed to analyze the system. DES takes maximum advantage of both of these approaches.
The "noisy channel" problem is analogous to the problem of secure communication in cryptography - the noise corresponding to the enciphering transformation and the received message as the cipher text. The role of the sender, though, is to make the recovery of the original message as difficult as possible, if not impossible. Cryptographers seek to devise encryption techniques that produce cipher text that cannot be distinguished from purely random bit strings by the opponent.
The statistical communication channel of the coding/decoding model has been replaced by a game theoretic channel; nature has been replaced by an intelligent opponent. Game theory is a mathematical theory that deals with the general features of competitive situations, placing particular emphasis on the decision-making process of adversaries.
It is not sufficient that a cryptosystem be able to thwart cryptanalysis alone. It should frustrate any aims of unauthorized parties attempting to subvert the integrity of a supposedly secure channel.
FIGURE 6-1
NOISY CHANNEL
Noise
|
|
M ----------+------------> M'
Sender Receiver
Opponent Attacks Against A Cryptosystem
The typical aims of an opponent are:
a. To determine the content of the message M;
b. To alter message M to M' and have M' accepted by the receiver as a message from transmitter of M;
c. To initiate communications to a receiver and have the interloper posing as an authorized transmitter. This is also called "spoofing".
Traditionally (a), known as the privacy problem, has been the focus of much research. Electronic communications has acquired a ubiquitous presence in public and private spheres. The latter two aims (b) and (c) have become more important in systems design. Foiling these aims, known as authentication and repudiation are equally important.
Denning Model
A cipher is considered breakable if it is possible to determine the plain text or key from
the cipher text, or to determine the key from plain text-cipher text pairs.
Dr. Dorothy Denning of Georgetown University defined four basic methods of attack to determine the adequacy of a prospective cryptosystem: cipher text-only, known-plain text, chosen-plain text, and chosen-cipher text.
Under a cipher text-only attack, a cryptanalyst must determine the key solely from the intercepted cipher text, through the method of encryption, the plain text language, the subject matter of the cipher text, and certain probable words may be known.
Under a known plain text attack, a cryptanalyst knows some plain text-cipher text pairs. Knowledge of probable words allows a close approximation to the known plain text attack. Encrypted programs are particularly vulnerable because of the appearance of keywords - e.g. begin, end, var, procedure, if, then. Even if the positions of these words are not known, reasonable guesses may be made.
Under a chosen plain text attack, a cryptanalyst is able to acquire the cipher text corresponding to selected plain text. This is the most favorable condition for the cryptanalyst. A database system may be particularly vulnerable to this type of attack if users can insert elements into the database, and then observe the changes in the stored cipher text. This is called the planted record problem.
Public-key systems have introduced a fourth kind of attack: a chosen-cipher text attack. Although the plain text is not likely intelligible, the key may be deduced.
A cipher is unconditionally secure if, no matter how much cipher text is available or intercepted, there is not enough information in the cipher text to determine the plain text uniquely. With one exception, the one-time pad, all ciphers are breakable given unlimited resources, so we are more interested in ciphers that are computationally infeasible to break. A cipher is computationally secure or strong if it cannot be broken by systematic analysis with available computing resources or time.
Threats To Data Stored In Computer Systems
Information transmitted over electronic lines is vulnerable to passive wiretapping, which threatens secrecy, and to active wiretapping, which threatens authenticity. Passive wiretapping (eavesdropping) refers to the interception of messages, usually without detection. Active wiretapping (tampering) refers to deliberate modifications made to the message stream. Encryption protects against message modification and injection of false messages by making it infeasible for the opponent to create cipher text that deciphers into meaningful plain text. Note that whereas it can be used to detect message modification it can not prevent it. Encryption does not necessarily, ipso facto, protect against replay, because an opponent could simply replay the previous cipher text. Protocols requiring acknowledgments normally prevent against intentional message deletion.
Data in computer systems is subject to similar threats. Threats to secrecy include: browsing, leakage, and inference. Browsing refers to searching through main memory or storage for information and confidential programs. If access controls are not employed, cipher text searching for identical information pairs may be effective. Leakage refers to the transmission of data to unauthorized persons by computer processes with legitimate access to the data. Inference refers to the deduction of confidential data about a particular subject from known or published information.
Threats to authenticity include tampering and accidental destruction. Tampering with data in computer systems is analogous to active wiretapping on communication channels. Accidental destruction refers to the unintentional overwriting or deletion of data. Computer programs like Norton Utilities© and Nuts and Bolts© have been a great help in this area.
Computer systems are also vulnerable to another problem: masquerading or spoofing. If an intruder can gain access to a system under another user’s account, he has access to all the information within that user’s domain. Digital signatures provide a means to authenticate users and processes.
Information Theory – Shannon’s Concepts
Security is directly related to the difficulty associated with the inverting encryption transformation(s) of a cryptosystem. The protection afforded by the encryption procedure can be evaluated by the uncertainty facing an opponent in determining the permissible keys used. Shannon characterized a system that has perfect security with the following property: if an opponent knows E (the encryption transformation see equations 6-1 through 6-4) and has an arbitrary amount of cipher, he/she is still left with a choice between all messages from the message space when attempting to recover the corresponding plain text for some cipher text.
Let Pc(M) be the probability that a message M was sent given that C was received,
with C = E(M).
Perfect security is defined as:
Pc(M) = P(M) Eq. 6-5
where P(M) is the probability that message M will occur. Let Pm(C) be the probability of receiving cipher text C given that M was sent. Then Pm(C) is the sum of the probabilities P(K) of the keys that encipher M as C:
K
Pm(C) = å P(K) Eq. 6-6
K,Ek(M) = C Eq. 6-7
where the bold K means across the space of keyspace K. Usually there will only be one key k that satisfies
Ek(M) = C Eq. 6-8
A necessary and sufficient condition for perfect secrecy is that for every C,
Pm(C) = P(C) Eq. 6-9
This means that the probability of receiving cipher text C is independent of encrypting it with plain text M. Perfect secrecy can only be assured if the length of the key is as long as the message sent, and the cardinality of the key space is the same as that of the message space. These conditions ensure that the uncertainty of the key and cipher are maintained and maximized.
Ciphers that could not be shown to have perfect secrecy but did not disclose sufficient information to allow the key to be determined, Shannon called ideally secret. By not revealing more information than the unicity distance, these systems were effectively unbreakable.
The opponent is faced with at least as much uncertainty with respect to the message as he is with the key. The only system that fits this definition is the one time pad. The key used is a non-repeating stream of random bits, and is discarded after each transmission. A separate key is used for each transmission as two cipher texts encrypted with the same key could be correlated. Being in possession of C adds no information to the task of recovering M = Dk(C). Systems based on Shannon's equivocation are unconditionally secure, meaning the system will resist cryptanalysis even in the presence of infinite computing power. The security of the system is derived from statistical uncertainty.
If Hc(K), the entropy of the key, never approaches zero for any message length, then the cipher is considered unconditionally secure.
Shannon assumed, in devising his perfect ciphers, that opponents have access to unlimited computing power. It is far from unreasonable though, to believe that any single opponent, or cartel of opponents, except NSA, is in possession of inexhaustible computing resources. Such security measures as warranted by Shannon would appear excessive, for what they are guarding against is not a tangible threat. Modern cryptosystems look beyond uncertainty and unicity distances to establish a basis of security and, in particular, the work factor, the ratio of the complexity (Appendix C) of cryptanalyzing a system to decryption, is taken as a strong indication of a system's security. Security can be cited in terms of the number of person/computer years needed to break the system. The subtle distinction can be drawn between perfect secrecy and cryptosecrecy, the first being asymptotically defined while the latter appeals to the concept of intractability. There does not really exist a completely general method to prove a cryptosystem is cryptosecure.
Designers have come to rely upon certification by cryptanalysts, who with considerable zest attempt to compromise the system using ad hoc and heuristic measures, as an indication of a system's security. History has repeatedly shown that systems purported to be unbreakable by their inventors were demonstrated to be far less secure than thought after being scrutinized by cryptanalysts.
We have described the four basic attacks on a cryptosystem. The systems security does not depend on the concealment of its encryption transformation or algorithm.
Kerckhoffs’ principle provides that the algorithm is available for all to examine and study. When E is revealed, a very difficult or inefficient method is also revealed to compute the inverse of E. Given the cipher text C, the cryptanalyst can examine the message space exhaustively until M is found such that E(M) = C. This method is also called brute force. Whenever a key of finite length is employed, it can always be compromised by direct search methods. The success of such an attack depends upon the work factor associated with the cipher, i.e. the minimal number of computations needed to invert the system. It should be noted that the unicity distance indicates the number of characters needed to determine the key, but it makes no comment on the complexity of this task. A system can disclose more cipher text than its unicity distance considers safe but still may remain cryptosecure.
A system is considered computationally secure if the task of inverting E is computationally infeasible or intractable. You might recognize this as similar to the properties of NP (non deterministic polynomial) problems (Appendix C gives an additional tutorial on this subject.)
Entropy and Equivocation
Information theory measures the amount of information in a message by the average number of bits needed to encode all possible messages in an optimal encoding. For example, the Sex field in a personnel database, contains only one bit of information because a 0 can represent a Male and a 1 can represent a Female. We could spell the words out, take up more space, but not yield more information. In computer systems, programs and text files are usually encoded in 8-bit ASCII codes, regardless of the amount of information in them. Furthermore, text files can be compressed by about 40% without losing any information.
The amount of information in a message is formally measured by the entropy of the message. The entropy is a function of the probability distribution over the set of all possible messages.
Let X1, ..., Xn be n possible messages occurring with probabilities of p(X1),......p(Xn), where:
n
å p(Xi) = 1 Eq. 6-10
i=1
The entropy of a given message is defined by the weighted average:
n
H(x) = - å p(Xi) log2 p(Xi) Eq. 6-11
i=1
If we write this sum over all messages X:
1
H(x) = - å p(X) log2 [------] Eq. 6-12
X P(x)
In the example above, with the p(male) = p(female) = 1/2
H(X) = 1/2 log2 (2) + 1/2 log2 (2) = 1/2 + 1/2 =1 Eq. 6-13
which confirms our observation that only 1 bit of information is required in the sex field of the database.
Intuitively, each term log2 (1/p(X)) represents the number of bits needed to encode message X in an optimal encoding - that is it minimizes the expected number of bits transmitted over a channel. The weighted average H(X) gives the expected number of bits in the optimally encoded message.
Because 1/p(X) decreases as p(X) increases, an optimal encoding uses short codes for frequently occurring messages at the expense of using longer ones for infrequent messages. Morse code applies this principle. The most frequent letters use the shortest codes.
The entropy of a message H(M), also measures its uncertainty, in that it indicates the number of bits of information that must be required to recover a message distorted by a noisy channel or concealed through ciphers. The uncertainty of a message cannot exceed log2n bits, where n is the possible number of messages.
The rate of language r for messages of length k is defined as:
r = H(X)/k Eq. 6-14
which denotes the average number of bits of information in each character. For English, when k is large, r has been estimated to lie between 1.0 bits/letter and 1.5 bits/letter. The absolute rate of a language is the maximum number of bits of information that could be encoded in each character assuming all combinations of characters are equally likely. If there are K letters in the language, then the absolute rate is given by
R = log2K Eq. 6-15
which is the maximum entropy of the individual characters. For English, this is 4.7 bits/letter. The actual rate of English (3.2 bits/letter) is much less as it is highly redundant, like all natural languages. Redundancy stems from the underlying structure of a language, in particular certain letter and combinations of letters occur frequently, while others have a negligible likelihood of occurring (e.g. the letters E, T, A, I, N and O occur very frequently, as do digrams TH and EN, while Z and X are infrequent). The redundancy of a language with rate r is defined as D = R - r. When r =1 and R = 4.7, the ratio D/R shows that English is about 79% redundant!
We note that the more redundant a language is, the stronger the statistical relations between the letters in a sequence. On the other hand, if a language has no redundancy then occurrences of subsequent letters are statistically independent.
We can easily calculate the entropy of a single letter H1(M). Also, the entropy H2(M) of two-letter words can be found relatively easily. Unfortunately, the amount of calculation for Hn(M) grows exponentially as a function of n. The practical redundancy of a language is expressed as:
r¥ = limit Hn(M)/n Eq. 6-16
n ->¥
¥ = infinity
Equivocation, defined as the conditional entropy of message M given that cipher text C has occurred, is:
1
Hc(M) = å P(C) å Pc (M) log2 ---- Eq. 6-17
C M Pc(M)
where Pc(M) is the conditional probability of message M given cipher text C has occurred. Shannon measured the secrecy of a cipher with respect to its key equivocation, Hc(K); for cipher text C and key K, it may be interpreted as the degree of uncertainty in K given C, and expressed as;
1
Hc(K) = å P(C) å Pc (K) log2 ---- Eq. 6-18
C K Pc(K)
where Pc(K) is the probability of K given C. If Hc(K) is zero then there is no uncertainty in the cipher, making it unbreakable.
The unicity distance of a cipher is defined as the minimum message length that forces Hc(K) to approximate zero. So, the unicity distance of a cipher is the amount of cipher text needed to uniquely determine the key. Intuitively, as the length of the cipher text increases, the equivocation of the cipher decreases.
The equivocation of a simple cryptographic system becomes more complex as the number of messages and keys grow. The unicity distance of a cipher may be calculated or estimated, but, unfortunately, we may not be able to use this knowledge to break the cipher. Based on unicity, all ciphers can be divided into two classes:
Shannon defined the unicity distance of a cipher in order to be able to get some quantitative measure of:
It is given by:
H(K)
N @ ------ Eq. 6-19
D
where D is the redundancy of the language (3.2 bits per letter for English) and H(K) is the information content of the key.
Symmetric Algorithms - Product Cipher
A product cipher E is the composition of t functions (ciphers) Fi,...,Ft where each Fi may be a substitution or a transposition. Rotor machines are product ciphers, where Fi is implemented by rotor Ri, 1 < i < t. The famous ENIGMA machine used by Germany, Japan, and their allies were of the multiple rotor type. A variation, the Hagelin machine was used extensively by diplomatic posts for many years. These machines used symmetric algorithms. Both the sender and receiver knew the same secret key.
Mixing Transformations
Shannon proposed composing different kinds of functions to create "mixing transformations", which randomly distribute the meaningful messages uniformly over the set of all possible cipher text messages.
Mixing transformations could be created, for example, by applying a transposition followed by an alternating sequence of substitutions and simple linear operations. An algorithm embodying this approach was known as LUCIFER and was designed by IBM in the early '70's. LUCIFER used a transformation that alternately applied substitutions and transpositions. Table 6-1 shows how the principle works with some small blocks (in practice much longer blocks are used.) Table 6-1 gives a minute illustration of how substitutions and then permutation may be used to encipher using involutions only. The first three letters are substituted by removing one to the right in the alphabet and the second three letters are moved two to the right.
This can be deciphered by reversing the order of the operations and applying the inverse of each substitution and permutation.
Table 6-1
Involution Example
A B C D E F
S1 B C D F G H
P1 H F G C D B
S2 I G H E F D
P2 G I E H D F
Iterated Cryptosystems
We define an iterated cryptosystem as part of a family of cryptographically strong functions based on iterating a weaker function n times. Each iteration is called a round and the cryptosystem is called an n-round cryptosystem. The round-function is a function of output of the previous round and a sub-key, which is a key dependent value calculated via a key-scheduling algorithm. The round-function is usually based on lookup tables (also known as S Boxes), bit permutations, arithmetic operations and the exclusive-or operation denoted as Å .
In the late 1960’s IBM set up a research project in computer cryptography led by Horst Feistal. The project concluded in 1971 with the development of an algorithm known as LUCIFER. LUCIFER was sold to Lloyd’s of London for use in cash dispensing systems, also designed by IBM. LUCIFER was a block cipher that operated on 128 bit blocks, using a key size of 128 bits. Carl Meyer and Walter Tuchman headed up an effort to make LUCIFER a commercial product that could be implemented on a single chip. They gained advice from outside consultants and NSA. The outcome of this effort was a more resistant algorithm with a shorter key size of 56 bits. It was this version that was submitted to the National Bureau of Standards (NBS) in response to a RFP (Request for Proposal) for a national cipher standard. IBM submitted the results of the Tuchman- Meyer project. It was by far the best algorithm proposed and was adopted in 1977 as the Data Encryption Standard (DES).
DES was not adopted without intense criticism. The reduced key size of 56 bits rather than the original 128 bits and the design of the S boxes (per help of NSA) were both questioned as possible political weakpoints. The debate has been healthy. DES has enjoyed many years of commercial service - especially in the financial community.
Data Encryption Standard (DES)
The Data Encryption Standard (DES) is an improved version of LUCIFER. DES is not, as my HAZMAT friend suggests "a synthetic estrogen, diethylstilbestrol, used as a growth stimulant in food animals. Residues in meat are thought to be carcinogenic."
The round-function of LUCIFER had a combination of non-linear substitution (S boxes) and a bit permutation. The input bits are divided into groups of four consecutive bits. Each group is translated by a reversible S box giving a four-bit result. The output bits of all the S boxes are permuted in order to mix them when they become input to the following round. In LUCIFER only two fixed S boxes (S0 and S1) were chosen. Each S box can be used at any S box location and the choice is key dependent. For a block size of 128 bits and a 16 round cryptosystem there are 512 S box entries for which 512 key bits are needed (for the eight round variants 256 key bits are needed). A key expansion algorithm that repeats each key bit four times reduces the key size to 128 bits. Decryption is accomplished by running the data backwards using the inverse of each S box.
The Data Encryption Standard (DES) is a mathematical algorithm used for the cryptographic protection of computer data. The algorithm is designed for use with binary-coded data and uses a 64-bit key to encipher 64 bits of information. The 64-bit key is of prime importance since a unique key results in the cryptographic generation of a unique set of 64-bits of cipher text from 64 bits of plain text. Since the general public knows the algorithm, the cryptographic security of the DES is dependent on the security used to protect the key. Encrypted information can be transformed into the original plain text through a reversal of the algorithm process using the same key that was employed for encryption.
The Data Encryption Algorithm (DEA) was designed so that 56 bits of the 64 bit key are used for the encryption process and the remaining 8 bits are used only for parity error-detecting bits. The key is divided into eight 8-bit bytes (8 bits = 1 byte). In an 8-bit byte, 7 bits are used by the algorithm and the eighth bit can be used to maintain odd parity to form a complete 64-bit block of plain text enciphered with a 56-bit key.
Overview of DEA
DEA incorporates the following steps to encipher a 64- bit message (block of data) using a 64-bit key:
1. A transposition operation, referred to as the initial permutation (IP). This transposition does not use the 64-bit key and operates solely on the 64 data bits.
2. A complex key-dependent product transformation that uses block ciphering to increase the number of substitution and reordering patterns.
The three major steps for DEA are shown in Figure 6-2:
FIGURE 6-2
OVERVIEW OF ENCIPHERING PROCESS FOR
THE STANDARD DATA ENCRYPTION ALGORITHM
The IP and IP-1 , are simple bit transpositions; the product transformation is fairly complex. Product transformations are successive applications of substitution and transposition ciphers. Large blocks of data are transformed as a unit, providing the advantage of increasing the number of substitutions and reordering patterns. This is also called block ciphering.
In the product ciphering step of DEA, the block cipher substitutions are under the control of a cipher key while transpositions are performed according to a fixed sequence. Figure 6-3 depicts one iteration of the product transformation, which includes the following operations:
1. The 64-bit block of plain text is divided into two 32- bit blocks, denoted by Li and Ri for the left and right halves, respectively.
2. The rightmost 32 bits of the input block become the leftmost 32 bits of the output block.
3. The rightmost 32 bits of the input block, Ri-1, goes through a selection process yielding 48-bit data block. This is a fixed selection and it is not key dependent (called an expansion permutation).
4. The 64-bit key is used to generate a 48-bit subkey Kn, where 1 < n < 16. Each Ki is unique and corresponds to the iteration of the product transformation.
5. The 48-bit subkey is added (modulo 2) to the output of step 3 yielding a 48-bit result (called XORed Å ).
6. The 48-bit output of step 5 is divided into eight 6- bit groups, that are each subjected to a unique substitution cipher that yields eight 4-bit groups, that are concatenated to form a 32-bit output.
7. The 32-bit output of step 6 is permuted by simple transposition to produce a 32-bit block.
8. The 32-bit output of step 7 is added modulo 2 to the left-most 32 bits of the input block, denoted Li-1, yielding Ri, which is the rightmost 32 bits of the 64-bit output block.
Steps 1 - 8 are repeated 16 times; this constitutes the major part of the product transformation. The last step is a block transformation (i.e. exchange) of the left and right halves of the output of the last iteration.
The deciphering process is the exact reversal of the encipherment process, in reverse order, K16 to K1.
FIGURE 6-3
OVERVIEW OF ONE ITERATION OF THE COMPUTATIONS IN THE PRODUCT TRANSFORMATION OF THE STANDARD DATA ENCRYPTION ALGORITHM
Components Of The Decryption Algorithm
There are 6 components that make up the DEA:
1. The key schedule calculations, which generate 16 subkeys,
2. The XOR or modulo-2 addition Å ,
3. The cipher function, which comprises the main operations in the product transformation,
4. The block transposition that yields the "preoutput block" which serves as input to the inverse initial permutation,
5. The initial permutation described as a selection table,
6. The inverse initial permutation described as a selection table.
Key Schedule Calculations
The key schedule calculations generate 16 subkeys, referred to as Kn, required for enciphering and deciphering processes. Each Kn is 48 bits long and is derived through the use of permutation, selection, and shifting operations. The bits are numbered 1 - 64, going from left to right. Parity bits are numbered 8,16,24,32,40,48,56, and 64 leaving the following bits for key schedule computations:
The key schedule calculations are executed as follows:
1. The non-parity bits in the key go through a permutation operation yielding two 28 bit blocks denoted by C0 and D0. This is the starting point for computing the subkeys.
2. C0 and D0 are circularly left shifted one place yielding C1 and D1
3. Selected bits from C1 and D1 are tapped off yielding subkey K1.
4. C1 and D1 are circularly left shifted one place yielding C2 and D2
5. Selected bits from C2 and D2 are tapped off yielding subkey K2.
6. The process continues for subkeys K3 through K16. Each Ci and Di is obtained from the preceding value after a prescribed number of circular left shifts.
The key schedule calculations are summarized in Figures 6-4 a,b,c. Each subkey, denoted by Ki, is obtained through a selection operation from Ci and Di. Ci and Di are obtained from Ci-1 and Di-1, respectively, through prescribed shift operations.
Figures 6-4 a,b,c
SUMMARY OF THE KEY SCHEDULE CALCULATIONS
Initially C0 and D0 are obtained from the 64-bit key with permuted choice 1, which is summarized in Table 6-2 and Figure 6-5.
Figure 6-5
PERMUTED CHOICE 1, USED IN THE CALCULATION OF C0 AND D0
The cipher key active bits used to determine C0 are 57,49...36, etc. Similarly, the bits of D0 are respectively bits 63,55...4 of the cipher key.
Permuted choice 2 is used to select a particular key Kn from the concatenation of Cn and Dn. Cn and Dn are 28 bits long so that CnDn combined has bits that run from 1-56 (Figure 6-6).
Figure 6-6
PERMUTED CHOICE, 2, USED IN THE CALCULATION OF SUBKEY Kj
The number of circular left shifts for each iteration in the key schedule calculation are:
Table 6-2
Iteration # of circular left shifts
1 1
2 1
3 2
4 2
5 2
6 2
7 2
8 2
9 1
10 2
11 2
12 2
13 2
14 2
15 2
16 1
Cipher Function
The cipher function (Figure 6-7) comprises the main operations in the product transformation, f(A, Kn) where A is a string of 32 data bits representing Ri for encryption
or Li for decryption, and Kn, is a 48 bit subkey determined by the key schedule.
FIGURE 6-7
OVERVIEW OF CIPHER FUNCTION
The cipher function combines the following operations:
1. A selection operation E that operates on the argument A of 32 bits and produces a 48 bit result.
2. A XOR addition which adds the result of the selection operation E and the 48 bit key Kn on a bit by bit basis yielding a 48 bit result.
3. A unique set of selection functions, Si, that converts the 48 bit result of step 2 to a set of 32 bits.
4. A permutation operation P that operates on the result of step 3 and produces a 32 bit result.
The selection operation function ,E, shown in Figure 6-8 yields a 48-bit result wherein the bits of the result are respectively 32,1,2,...1,.etc. of the symbolic argument ,A, which may represent Ri or Li depending on the function.
FIGURE 6-8
THE SELECTION OPERATION OF THE CIPHER FUNCTION
S Boxes
The unique set of selection functions Si take a 6-bit block as input and yield a 4 bit result. A selection function represented by a 4 X 16 matrix of numbers used in a prescribed manner (see Figure 6-9).
Input to the unique S Boxes 1-8 (selection functions Si) is a 48-bit block, denoted symbolically as B1B2B3B4B5B6B7B8. Each Bi contains 8 bits. S1 is used for B1, etc.
The result of the selection of Si with Bi as an argument Si(Bi) is computed:
1. The first and last bits of Bi represent a binary number in the range of 0 - 3 denoted m.
2. The middle four bits of Bi represent a binary number in the range of 0 - 15 denoted n.
3. Using zero-origin indexing, the number located in the mth row and nth column of the Si's matrix is selected as a four bit binary block.
4. The result of step 3 is the output of the selection function Si.
The output of a complete set of selection functions, is a bit string is:
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8)
each of the Si's are 4 bit outputs.
FIGURE 6-9
EXAMPLE OF THE USE OF SELECTION FUNCTION S1
INPUT IS THE 6-BIT STRING 101100.
OUTPUT IS THE 4-BIT STRING 0010.
Table 6-3 gives the matrices corresponding to the selection function S1 through S8.
Table 6-3
Matrices for the selection functions S1 through S8
Matrices for the Selection functions S1 through S8.
S1
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S2
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S3
10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
S4
7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S5
2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
S6
12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
S7
4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
S8
13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
The output of the set of eight selection functions, S1 through S8 is a string of 32 bits. This 32-bit output goes through a permutation operation P that yields a 32-bit result and completes the cipher function. P does not complete the algorithm, but only the cipher function denoted by f(A, Kn). This final permutation in the cipher function is given in Figure 6-10. The permutation operation P yields a 32-bit result wherein the bits of the result are 16, 7, etc. of the 32-bit result of the set of selection functions.
FIGURE 6-10
PERMUTATION OPERATION P OF THE CIPHER FUNCTION
Preoutput Block
The output of the last iteration in the product transformation goes through a block transformation yielding a 64-bit result called the preoutput block (Figure 6-11). It is a simple exchange of R16 and L16. The bits of R16 are followed by the bits of L16 and constitutes a 64-bit block, with bits numbered from 1 - 64 from left to right.
FIGURE 6-11
BLOCK TRANSFORMATION YEILDING THE PREOUTPUT BLOCK
IP
The initial permutation (IP) is the first step in the standard data encryption algorithm and is a key-independent permutation as shown in Figure 6-12. The output of the IP are respectively, bits 58, 50,...2 etc. of the plain text input to the block. The result of the IP is a 64-bit block. The leftmost 32 bits constitute L0 and the rightmost 32 bits constitute R0. L0 and R0 are the initial input blocks to the product transformation.
FIGURE 6-12
THE INITIAL PERMUTATION (IP)
IP-1 Inverse Initial Permutation
The output of the product transformation is the preoutput block, which is subjected to a permutation, which is the inverse of the IP. The IP-1 is shown in Figure 6-13. The output of IP-1, which is synonymously, the cipher text output of the algorithm, is bits 40, 8...to 25 of the preoutput block.
The 64-bit cipher text output of the DEA can be used as a string of data bits for transmission or storage, or may be converted back into BCD characters for further processing.
FIGURE 6-13
THE INVERSE INITIAL PERMUTATION (IP-1)
The Enciphering Process
The enciphering process can be summarized symbolically. Given two blocks L and R and using the convention that LR denotes the block consisting of bits of L followed by bits of R, the initial permutation (IP) is specified as:
L0R0 <--- IP (<64-bit input block>) Eq. 6-20
Let KS denote the key schedule calculations, where the function KS yields a 48-bit subkey Kn for arguments n and KEY, where Key is a 64-bit cipher key, it follows that:
Kn <-- KS(n, KEY) Eq. 6-21
denotes the calculation of subkey Kn.
The 16 iterations in the product transformation that use the cipher function are then represented symbolically as:
Ln <-- Rn-1 Eq. 6-22
Rn <-- Ln-1 Å f(Rn-1, Kn) Eq. 6-23
and f is the cipher function. Ln and Rn are computed as n goes from 1 - 16. The preoutput block is R16L16 and the result of the DEA is specified as:
<64-bit cipher text> <-- IP-1 (R16L16) Eq. 6-24
Table 6-4
Summarization of the Enciphering and Deciphering Equations
L0R0 ß IP (á 64-bit input blockñ ) Eq. 6-25
Ln ß Rn-1 Eq. 6-26
Rn ß Ln-1 Å f(Rn-1, Kn) Eq. 6-27
á 64-bit cipher textñ ß IP-1 (R16L16) Eq. 6-28
Enciphering Equations
R16L16 ß IP (á 64-bit cipher textñ ) Eq. 6-29
Rn ß Ln Eq. 6-30
Ln-1 ß Rn Å f(Ln, Kn) Eq. 6-31
á 64-bit plain textñ ß IP-1 (L1R1) Eq. 6-32
Deciphering Equations
function KS yields a 48-bit subkey Kn for input arguments n and KEY, where KEY is the 64-bit cipher key, it follows that
Kn ß KS (n, KEY) Eq. 6-33
denotes the calculation of subkey Kn.
The 16 iterations in the product transformation that utilize the cipher function are then represented symbolically as:
Ln ß Rn-1 Eq. 6-34
Rn ß Ln-1 Å f(Rn-1, Kn) Eq. 6-35
where f is the cipher function and Å denotes bit-by-bit modulo-2 addition. Ln and Rn are computed as n goes from 1 to 16. The preoutput block is R16L16 and the result of the algorithm is specified as:
á 64-bit cipher textñ ß IP-1 (R16L16) Eq. 6-36
The enciphering equations are summarized in Table 6-4.
THE DECIPHERING PROCESS
The process of deciphering a 64-bit cipher text message block involves the same algorithm as encipherment, as stated in FIPS publication 46 (Data Encryption Standard, U.S. Department of Commerce, National Bureau of Standards, FIPS publication 46, 1977 January 15, p.10):
.....to decipher it is only necessary to apply the very same algorithm to an enciphered message block, taking care that at each iteration of the computation the same block of key bits K is used during decipherment as was used during the encipherment of the block.
This is precisely the case because the IP and IP-1 are by definition inverses of each other.
Applying the notation given above, the result of the initial permutation (IP) is:
R16L16 <-- IP(<64-bit cipher text>) Eq. 6-37
where the expression takes the final block transformation into consideration. The 16 iterations in the product transformation are represented:
Rn-1 <-- Ln Eq. 6-38
Ln-1 <-- Rn Å f(Ln,Kn) Eq. 6-39
The XOR has the following properties:
[A Å B] Å C = A Å [B Å C], Eq. 6-40
D Å D = 0 Eq. 6-41
E Å 0 = E Eq. 6-42
where the Ln and Rn are computed as n goes from 16 - 1. The result of the decipherment is then specified:
<64-bit plain text> <-- IP-1 (L0R0) Eq. 6-43
Avalanche Effect
The key effect of the DEA is the avalanche effect. A desirable property of any encryption algorithm is that a small change in the plain text should produce a large effect in the cipher text. A change in one bit of the plain text or one bit of the key should produce a change in many bits of the cipher text. DES exhibits a strong avalanche effect. We have seen that in the E operation (expansion permutation) the right half of the data Ri is expanded from 32 bits to 48 bits. Because this operation changes the order of the bits as well as repeating certain bits, it is a true expansion permutation. This operation has two purposes: it makes the result the same size as the key for the XOR operation, and it provides a longer result that can be compressed during the substitution operation.
Neither of these is its main cryptographic purpose, though. By allowing one bit to affect two substitutions, the dependency of the output bits on the input bits spreads faster. This is called the avalanche criteria. Much of DES's design revolves around reaching as quickly as possible the condition of having every bit of the cipher text depend on every bit of the plain text and every bit of the key. Meyer notes that statistical output dependency is reached after just five rounds of DES. Konheim (see Table 6-5) suggests eight rounds are required to reach full output dependency of the data.
Table 6-5
Avalanche Effect in DES
(a) Change in Plain text (b) Change in Key
Round No. of Bits No. of Bits
That Differ That Differ
________________________________________________________
0 1 0
1 6 2
2 21 14
3 35 28
4 39 32
5 34 30
6 32 32
7 31 35
8 29 34
9 42 40
10 44 38
11 32 31
12 30 33
13 30 28
14 26 26
15 29 34
16 34 35
Weak Keys
Because of the way the initial key is modified to get a subkey for each round of the algorithm, certain keys are weak keys (Table 6-6). Since the original DES key is split in half and each half is shifted independently, if all the bits are 0's or 1's, then the key used for any cycle is the same for all cycles: K1 = K2 = K2 =Ki =Kn. Additionally, some pairs of keys encrypt plain text to the identical cipher text. This is due to the key generation mechanism in DES. Instead of generating 16 different subkeys, these keys generate only two different subkeys. Each of these subkeys is used eight times in the algorithm. We label these semi-weak keys. A similar problem occurs when some keys only produce four subkeys and are used only four times in the algorithm. The total number of possibly weak keys is 64 out of 72,057,594,037,927,936 possible keys. Selecting a random key, the odds of picking one out of the 64 are worse than winning the Texas lottery twice in a month.
Table 6-6
DES Weak Keys in Hex
Weak Key Value Actual Key
(with parity bits)
0101 0101 0101 0101 0000000 0000000
1F1F 1F1F 0E0E 0E0E 0000000 FFFFFFF
E0E0 E0E0 F1F1 F1F1 FFFFFFF 0000000
FEFE FEFE FEFE FEFE FFFFFFF FFFFFFF
DES Semiweak Key Pairs
01FE 01FE 01FE 01FE and FE01 FE01 FE01 FE01
1FE0 1FE0 0EF1 0EF1 and E01F E01F F10E F10E
01E0 01E0 01F1 01F1 and E001 E001 F101 F101
1FFE 1FFE 0EFE 0EFE and FE1F FE1F FE0E FE0E
011F 011F 010E 010E and 1F01 1F01 0E01 0E01
E0FE E0FE F1FE F1FE and FEE0 FEE0 FEF1 FEF1
Modes of DES
FIPS PUB 74,81 defines four modes of operation that cover virtually all the possible applications of encryption for which DES could be used. Table 6-7 summarizes them.
TABLE 6-7
DES Modes of Operation
|
Mode |
Description |
Typical Application |
|
Electronic Codebook (EBC) |
Each block of 64 plain text bits is encoded independently using the same key. |
Secure transmission of single values (e.g., an encryption key) |
|
Cipher Block Chaining (CBC) |
The input to the encryption algorithm is the XOR of the next 64 bits of plain text and the preceding 64 bits of cipher text. |
General-purpose block-oriented transmission |
|
Cipher Feedback (CFB) |
Input is processed J bits at a time. Preceding cipher text is used as input to the encryption algorithm to product pseudoandom output, which is XORed with plain text to produce next unit of cipher text. |
Authentication |
|
Output Feedback (OFB) |
Similar to CFB, except that the input to the encryption algorithm is the preceding DES output. |
Stream-oriented transmission over noisy channel (e.g., satellite communication) |
ECB Mode
The Electronic Codebook (ECB) Mode is relatively uncomplicated. The plain text is handled 64 bits at a time and each block is encrypted using the same key (Figure 6-14). The term codebook may be used because there is a unique cipher text for each 64-bit of plain text. Messages rarely fit into 64 bits. Longer messages are simply broken into 64 bit blocks, padding the last block if necessary. ECB has an exploitable flaw. Plain text repeats always are reproduced in the cipher text form for the same 64 bit blocks. This particular flaw can be exploited using cryptanalysis. This author does not recommend using ECB because of this flaw.
FIGURE 6-14
ELECTRONIC CODEBOOK (ECB) MODE
CBC Mode
The Cipher Block Chaining (CBC) Mode (Figure 6-15) improves on the ECB mode by ensuring that same plain text blocks produce different cipher text blocks, enciphered by the same key. The input to the encryption algorithm is XOR’d with the preceding cipher text block, the same key is used for each block. We effectively chain together the processing of the plain text blocks. Repeating 64-bit patterns are not exposed. Decryption is simply the reverse of encryption. To produce the first cipher text, an initialization vector (IV) is XOR’d with the first block of plain text. Both sender and receiver must know the IV. The IV may be the weak point in the CBC mode of operation. Stallings discusses spoof and inversion attacks on the IV. Lastly, CBC mode may be used for authentication.
FIGURE 6-15
CIPHER BLOCK CHAINING (CBC) MODE
CBC Descriptive Equations
Cn = EK[Cn-1 Å Pn] Eq. 6-44
DK[Cn]= DK[EK(Cn-1 Å Pn)] Eq. 6-45
DK[Cn] = Cn-1 Å Pn Eq. 6-46
Cn-1 Å DK[Cn] = Cn-1 Å Cn-1 Å Pn = Pn Eq. 6-47
CFB Mode
The DES scheme is essentially a block cipher technique that uses 64-bit blocks. However, it is possible to convert DES into a stream cipher, using either the cipher feedback or the output feedback mode. A stream cipher eliminates the need to pad a message to be an integral number of blocks. It also can operate in real time. Thus, if a character stream is being transmitted, each character can be encrypted and transmitted immediately using a character-oriented stream cipher.
One desirable property of a stream cipher is that the cipher text be of the same length as the plain text. Thus, if 8-bit characters are being transmitted, each character should be encrypted using 8 bits. If more than 8 bits are used, transmission capacity is wasted.
Figure 6-16 depicts the CFB scheme. In the figure, it is assumed that the unit of transmission is j bits; a common value is j = 8. As with CBC, the units of plain text are chained together, so that the cipher text of any plain text unit is a function of all the preceding plain text.
First, consider encryption. The input to the encryption function is a 64-bit shift register that is initially set to some initialization vector (IV). The leftmost (most significant) j bits of the output of the encryption function are XORed with the first unit of plain text P1 to produce the first unit of cipher text C1, which is then transmitted. In addition, the contents of the shift register are shifted left by j bits, and C1 is placed in the rightmost (least significant) j bits of the shift register. This process continues until all plain text units have been encrypted.
FIGURE 6-16
J-BIT CIPHER FEEDBACK (CFB) MODE
OFB Mode
The output feedback mode (OFB) is similar in structure to that of CFB, as illustrated in Figure 6-17. As can be seen, it is the output of the encryption function that is fed back to the shift register in OFB, whereas in CFB the cipher text unit is fed back to the shift register.
One advantage of the OFB method is that bit errors in transmission do not propagate. For example, if a bit error occurs in C1, only the recovered value of P1 is affected; subsequent plain text units are not corrupted. With CFB, C1 also serves as input to the shift register and therefore causes additional corruption downstream.
The disadvantage of OFB is that it is more vulnerable to a message-stream modification attack than is CFB. Consider that complementing a bit in the cipher text complements the corresponding bit in the recovered plain text. Thus, controlled changes to plain text can be made. However, most error correction codes will pick up on such modifications.
FIGURE 6-17
J-BIT OUTPUT FEEDBACK (OFB) MODE
Over the years, DES has been a very practical cryptosystem. Its 56 bit key potential vulnerability to brute force attack has forced many to look at multiple encryption schemes using DES to increase its cryptographic strength. Figure 6-18 shows multiple encryption schemes for DES.
FIGURE 6-18
MULTIPLE ENCRYPTION
Double DES
Double DES has two encryption stages and uses two keys. Given a plain text P and Keys K1 and K2, cipher text C is generated in this fashion:
C = Ek2 [ Ek1(P)] Eq. 6-48
Decryption is performed in reverse order:
P = Dk1 [ Dk2(P) ] Eq. 6-49
Double DES is vulnerable to the famous man-in-the middle (MIM) attack described by Winfield Diffie in 1977. His attack will work on almost any block cipher and is not dependent on any property of DES.
The MIM was described as:
C = Ek2[ Ek1(P)] Eq. 6-50
and
X = Ek1(P) = Dk2( C) Eq. 6-51
The MIM attack is a known plain text attack. Given a known plain/cipher pair (P,C), P is enciphered for all 256 possible values of K1. The results are sorted and stored by values of X. Next C is decrypted using all 256 possible values of K2. As each decryption is produced, the results are checked against the first table for a match. If there is a match, a test is made against a new known plain/cipher text pair. If the two keys produce the correct cipher text than accept the keys as the correct keys. Double DES in effect uses a 112-bit key and for any given plain text there are 264 possible cipher text values that can be produced via Double DES. Stallings shows that the probability that the correct keys are determined is 1 - 2 -16. He feels that the MIM would succeed against double DES with an effort of the order of 256.
Triple DES
An obvious approach to defeat the MIM attack is to make it too costly to perform efficiently. Triple DES with three keys with the effective key size at 56 x 3 = 168 bits and the cost of the plain text attack at about 2112 is one option. Tuchman described a better alternative and just as effective - triple DES with two keys.
Triple DES with Two Keys (3DES)
The sequence of 3DES is EDE or encrypt - decrypt - encrypt:
C = Ek1[ Dk2 [ Ek1 (P )] Eq. 6-52
3DES is very popular and has been adopted for use in the key management standards ANS x9.17 and ISO 8732, and for Privacy Enhanced Mail (PEM). 3DES is very strong and has survived the theoretical attacks designed by such researchers as Merkle and Oorshot. Both theoretical attacks set up plain text pairs that reduce to either a zero alternative or the double DES problem.
Set of DES
DES is a secret-key, symmetric cryptosystem: when used for communication, both sender and receiver must know the same secret key, which is used both to encrypt and decrypt the message. DES can also be used for single-user encryption such as to store files on a hard disk in encrypted form. In a multi-user environment, secure key distribution may be difficult; public-key cryptography was invented to solve this problem. DES operates on 64-bit blocks with a 56-bit key. It works well for bulk encryption, that is, for encrypting a large set of data.
NIST has recertified DES as an official U.S. government encryption standard every five years; DES was last recertified in 1993, by default. NIST has indicated, however, that it will not recertify DES after 1997. NIST has asked for public submissions/comment on development of the Advanced Encryption Standard (AEC). Submissions may be studied at: www.nist.aes.gov.
In April 1998, Ron Rivest on behalf of RSA Laboratories submitted an advanced encryption system to NIST for evaluation. The future should be very interesting.
DES has never officially been cracked, despite the efforts of many researchers over many years. The obvious method of attack is brute-force exhaustive search of the key space; this takes 255 steps on average. Early on it was suggested that some country could build a special-purpose computer capable of breaking DES by exhaustive search in a reasonable amount of time. Later, Hellman demonstrated a time-memory trade-off that allowed improvement over exhaustive search if memory space was plentiful, after an exhaustive precomputation. These ideas fostered doubts about the security of DES. There were accusations that the NSA had intentionally weakened DES. Despite these suspicions, no feasible way to break DES faster than exhaustive search was discovered.
In 1991, the cost of a specialized computer to perform exhaustive search was estimated by Michael Wiener at one million dollars and could find a DES key in, on average, about 3.5 hours. Michael Wiener updated his study in 1998 and published his results in RSA’s Cryptobytes publication. In 1998 dollars and technology, today’s version of Wiener’s million dollar machine could find a 56 bit DES key in about 35 minutes. It would use 57600 specialized key search chips, each chip capable of testing 50 million keys per second.
The first attack on DES that was better than exhaustive search was announced by Eli Biham and Adi Shamir using a technique known as differential cryptanalysis. This attack required encryption of 247 chosen plain texts, i.e., plain texts chosen by the attacker. Although a theoretical breakthrough, this attack is not practical under normal circumstances because it requires the attacker to have easy access to the DES device in order to encrypt the chosen plain texts. Another attack, known as linear cryptanalysis, does not require chosen plain texts.
Differential Cryptanalysis and Linear Cryptanalysis
Both Linear and Differential analysis require obtaining enormous numbers of known-plain text pairs to be feasible. This is not practical in most environments. Linear cryptanalysis is possible in a cipher text only environment if some of the underlying plain text redundancy is known such as the parity or higher order 0 bits in ASCII.
Differential cryptanalysis is, in this authors opinion, one of the most general cryptanalytic tools to date against modern iterated block ciphers such as DES or FEAL. However it is a chosen plain text attack. Menezes (Table 6-8) showed how DES strength fared against various attacks.
Table 6-8
DES Strength Against Various Attacks
|
Attack Method |
Data Complexity |
Storage |
Processing |
|
Known Chosen |
Complexity |
Complexity |
|
|
Exhaustive precomputation |
--- 1 |
256 |
1 (table lookup) |
|
Exhaustive search |
1 --- |
negligible |
255 |
|
Linear cryptanalysis |
243 (85%) --- |
for texts |
243 |
|
243 (10%) --- |
for texts |
250 |
|
|
Differential cryptanalysis |
--- 247 |
for texts |
247 |
|
255 --- |
for texts |
255 |
To be meaningful, attack comparisons based on different models (e.g., Table 6-8) must appropriately weigh the feasibility of extracting (acquiring) enormous amounts of chosen (known) plain texts, which is considerably more difficult to arrange than a comparable number of computing cycles on an adversary’s own machine. Exhaustive search with one known plain text-cipher text pair and 255 DES operations is significantly more feasible in practice (e.g., using highly parallelized custom hardware) than linear cryptanalysis (LC) requiring 243 known pairs.
Menezes suggests that while exhaustive search, linear, and differential cryptanalysis allow recovery of a DES key and, therefore, the entire plain text, the attacks which become feasible once in about 232 cipher texts, may be more efficient if the goal is to recover only part of the text.
The consensus is that DES, when used properly, is moderately secure against all but the most powerful players. In fact, triple encryption DES with three keys may be secure against anyone at all. DES is used extensively in a wide variety of cryptographic systems, and in fact, most vendor implementations of public-key cryptography include DES or 3DES at some product level.
How secure is DES today? Two commonly suggested ways to thwart key search attacks and enhance DES security are 1) avoiding known plaintext and 2) making frequent key changes. The first may be difficult to achieve. At least three vendor products tested by ICSA leave fixed-byte known file headers. As little as 2 bits of redundancy can be used to reduce the number of overall key searches.
A commonly suggested way to avoid key search attacks is to change the DES key frequently. The assumption is that the encrypted information is stale after the key is changed. If it takes 35 minutes to find a DES key, why not change the keys every 5 minutes. The logic fallacy that exists is that it does not take 35 minutes to find a key. The actual time is distributed between 0 and 70 minutes. The 5 minute window represents a 5/70 = 1/14 probability of success. This turns out to be a factor of two in run time and a poor substitute for a strong algorithm with longer keys.
Winn Schwartau writes that the NSA built a massively parallel DES-cracking machine as early as the mid-1980's. Both contextual and statistical attacks might reduce the DES effective key size. NSA has giant databanks of plain and cipher text to pre-perform the statistical calculations on and then go out to an array of optical disks and retrieve the key. If you believe the popular fictions of Chris Davis in Death by Fire, NSA’s ‘Allo" group has been cracking 56-bit DES by brute force for some time.
Diffie pointed out that many systems in use today have either 40-bit keys (which can be searched easily) or 56-bit keys (which can be searched with difficulty). Dragging key (looking through all possible keys) thus has a role to play in contemporary cryptanalysis. A far more subtle, but also universal, cryptanalytic method is the Berlekamp-Massey algorithm (Berlekamp 1968; Massey 1969). It is a fact that any sequence of bits (keystream) whatsoever can be generated by a linear shift register of sufficient length. The Berlekamp-Massey algorithm automatically produces the right register. A major design criterion in modern cryptography is that the "right register" be too long for this approach to be practical. Diffie also feels that NSA’s intercept equipment is quite effective. Under a deal between NSA and the Software Publisher’s Association, some cryptographic systems with 40-bit keys can be rather freely exported when embodied in "mass market software." Since modern computer workstations can execute 240 instructions in an hour, 40-bit keys do not represent very much security from a commercial viewpoint. On the other hand, it is unlikely that intercept devices, which are comparable in price to high-end workstations, can do any better. Since decisions about intercept must be made not in hours, but in fractions of a second, it is prudent to presume that NSA knows how to break the ciphers in question with a workfactor substantially less than 240.
As a final thought, Dan Ryan at SAIC provided some interesting data (Table 6-9). Incorporating specialized hardware, field programmable gate arrays (FPGA) and application specific integrated circuits (ASIC), we can estimate that the effort to crack a 56 bit DES key by a government entity is measured in seconds.
Table 6-9
Key Strength
Time to Break
Threat Budget Technology 40 Bits 56 Bits
Hacker Tiny Scavenged time 1 week infeasible
Small $10K FPGA 12 min. 556 days
Business
Corporation $300K FPGA or ASIC 24 sec. 19 days
Big Corp. $10M FPGA or ASIC .7 sec. 13 hours
Governement $300M ASIC .0002 sec. 12 sec.
FPGA = Field Programmable Gate Array
ASIC = Application Specific Integrated Circuits
Wrap-Up
DES represents the turning point from classical to modern cryptographic systems. DES has its foundations in information theory and represents a complex combination of the mathematical operations available up to the 1950’s. DES has survived for a long time but the fat lady is warming up her vocal chords. Modern attacks on single DES have invalidated its use for commercial purposes. Triple DES represents a more secure approach for commercial puposes.
DES is a natural randomizer. The avalanche criteria is perhaps the most important cryptographic effect of DES. DES modes of operation set the stage for all modern cipher operations and variants. The 56-bit key size is the DES weak link and multiple encryption methodologies have been suggested to improve the security of the DES cryptosystem. Modern day attacks have invalidated the 56 bit key length for DES but DES is still offered in most cryptographic products. The call for an AES by NIST is a flag that can not be ignored. We should strive to use the best encryption available to us with the longest key.
Chapter: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 10 |
| Reserve your copy at a Beta Bookstore near you! |
Contact Bet@books © 1998 The McGraw-Hill Companies, Inc. All rights reserved. Any use of this Beta Book is subject to the rules stated in the Terms of Use. |