Fenced DES

Ritter Software Engineering 2609 Choctaw Trail Austin, Texas 78745 (512) 892-0494, ritter@io.com Fenced DES Terry Ritter April 17, 1994 Introduction This article is one in a series which document my attempts to find a fast, strong, acceptable extension to the U.S. Data Encryption Standard (DES), which I believe is now dangerously insecure. The intent is to find a relatively-simple and believable construct which uses DES as a building block, thus avoiding the need to certify a complete new cipher. I note that currently there is no institution which could and also would provide such certification. In this article I propose a new "fenced" ciphering construct which may be a solution. The experimental 256-bit-block implementation takes about 1.2 times the computation (per byte) of DES alone, and may have the strength of four DES keys. In this design, some important block-cipher properties seem to follow logically from the widely-accepted existence of those properties in DES itself. Wide Blocks All practical block ciphers attempt to emulate a large substitution table algorithmically; DES employs substantial computation simply to behave like a substitution table of 2**64 elements. Accepting DES as a reasonable design means that we have implicitly accepted the argument that a fast 8-bit-wide substitution is not secure (by itself). Certainly, if a small-block substitution were secure, we would all use that simple and fast alternative instead of DES. Since we do not, we must have accepted the fact that block size is a significant factor in block cipher strength. DES is often used to encipher language text, which contains a surprisingly small amount of information. Since data-compression programs routinely compress language text by 60%, we can expect that a 64-bit block of language text may contain perhaps 26 bits of information. While it is not currently known how this could be exploited, a 256-bit-wide block should contain four times that much information, which should solve any related problem. A large block size also addresses some aspects of cryptoanalytic weakness: Some attacks on block ciphers make use of the "birthday paradox" to find a matching pair from a large number of ciphertexts. With a 64-bit block about 2**32 ciphertext blocks would be expected to be needed; a large number, admittedly, but still possible. But the same attack on a 256-bit block would require about 2**128 ciphertext blocks, which is completely out of the question. Thus, a large block size eliminates one type of attack on the cipher. A large-block 4x-wide cipher need not expand ciphertext beyond the normal expansion for DES (CBC initialization vector and key-length aside), provided that one trailing 2x and one trailing 1x block can be used if needed. All the preceding blocks would be 4x blocks. The Two Problems This project has had to address two major problems: 1. Weaknesses of Multi-Layer Constructs: Many simple multi- level ciphering structures based on DES can be attacked by working simultaneously on both the input and output layers, given "known plaintext" or "defined plaintext." In general, this means that two-level constructs are much weaker than one might expect. This leads to three-level construct like "triple-DES" which tend to be very slow. 2) Weakness in Multi-Block Constructs: Similarly, simple large-block structures based on DES can be attacked by defining or "fixing" the input values of all but one DES block, using "defined plaintext." Apparently, any composite structure which does not have each bit affect the every DES ciphering will have this weakness. To expand the effective block size while using DES itself, Fenced- DES uses the "block mixing transform" construct which I described in the previous article. In this article I want to clarify how those transforms can be used to create a cipher with a large block size out of smaller blocks, despite the mixing having no strength of its own. The Block Mixing Transform In a previous article I introduced the concept of a "block mixing transform" (extended from work by Eli Biham) as a tool to mix the information in two data blocks, and then recover that information. This concept could be expressed as two pairs of expressions: X := f1( A, B ); Y := f2( A, B ); A := f3( X, Y ); B := f4( X, B ); The term "transform" is taken from the ability to change the data into a different data-space, and then recover the original values, and also the similarity to the "fast Fourier transform" "butterfly" operation. This "block mixing transform" should be distinguished from the "mixing transformation" described by Shannon [10: 711]. The particular form I suggested was: X := 2A + 3B; Y := 3A + 2B; A := 2X + 3Y; B := 3X + 2Y; with operations mod-2 and mod-p, where p is some primitive mod-2 polynomial of appropriate degree for the data blocks X, Y, A and B. (Later work shows that p need not be primitive, but p must be irreducible in cryptographic service.) This transform is a self- inverse, has good mixing correlation properties, is statistically balanced, and has a processing cost which is linear with block size. Efficient implementation suggests a re-labeling as follows: X := 3A + 2B; Y := 2A + 3B; A := 3X + 2Y; B := 2X + 3Y; Comments on the original "block mixing transform" article have uncovered a few other references to fixed-size math transforms, including Agarwal and Burrus [1], Pollard [6], and Rader [7], but none related to cryptography. I would be glad to hear of any other references of any sort. The mixing transform need not be a cipher by itself. Indeed, it need have no "strength" at all, but must provide at least a minimal level of mixing and be cryptographically-balanced; it should also be expandable and fast. Although speed is not an issue in most individual ciphering, speed is a major issue for industrial applications, including centralized network servers. The application in this article mixes blocks of substantial size, making many other forms of mixing completely impractical. 4x Fenced-DES Consider the following construct: S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S --------------mix-------------- --------------mix-------------- ------------------------------mix------------------------------ ------DES------ ------DES------ ------DES------ ------DES------ ------------------------------mix------------------------------ --------------mix-------------- --------------mix-------------- S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S Here each "S" represents an 8-bit substitution table. Thus, we have 32 input substitutions and 32 output substitutions, each a separately-shuffled and independent table, and an overall block size of 256 bits. We also have four DES operations, plus two levels of input mixing and two levels of output mixing. Note that the innermost mixing levels combine two 128-bit blocks, a substantial operation which is nevertheless practical using the selected block mixing transform. The idea is to spread the effect of each input bit to each of the four DES operations, and to produce a particular output bit from a combination of all four DES results. If this works, The Opponent would be forced to search all four DES keyspaces simultaneously to match a particular known-plaintext pair. An experimental implementation of the above construct performs all 64 substitutions and all 6 mixings in less time than a single DES computation. Currently, it ciphers 4 times the data with about 4.8 times the computation, and has, perhaps, a keyspace of 224 bits or so. (A much faster hybrid implementation might do the DES computations in hardware.) In the experimental implementation, table and key initialization take about 200 times the computation of a single 256-bit-block ciphering. (This is mainly a consequence of shuffling 64 small substitution tables.) Even so, it is probably faster to compute the 16K initial state than to decipher 16K of saved state with software DES or Fenced-DES: Construction is faster than ciphering. The keyed construction of the substitution tables implies the presence of a specific cryptographic RNG. This means that any overall Fenced-DES specification will pin-down the key processing which varies so widely in current DES applications. The current implementation uses a fast 992-bit Additive RNG and the nonlinear "jitterizer" [8] which I have discussed many times with respect to my Penknife cipher and my other Dynamic Substitution [9] ciphers. In the experimental implementation, a User Key of arbitrary length and content is hashed (CRC'd) by 32 separate degree-31 primitive mod-2 polynomials (11- through 19-nomials), producing the 992-bit RNG state, which also eventually generates the DES keys. Note that this approach eliminates the need for keys to have a specific format unique to this particular cipher. This enables the selection of an arbitrary cipher from among many different ciphers, all of which can use the exact same key. Deciphering simply uses inverse substitutions (the inverse of each encipher output substitution is used for decipher input) and DES in decipher mode. The selected block mixing transform is a self- inverse and needs no changes. Mixing Levels The arrangement of the mixing levels deserves some comment. First, note that a change in any one input data bit produces a distribution of changes out of the associated input substitution, depending on the particular substitution, original input value, and change. Any possible byte input has a 50 percent probability of affecting each of the eight output bits from that substitution. A substitution table S is an indexable n-element vector of output codes. An invertible substitution table S with inverse table inv(S) has the property that for any input code i in n, inv(S)[ S[i] ] = i. This implies that S contains n different output codes. An invertible substitution table S contains each output code value exactly once. Since each possible index selects a different element, any index change will select a different output code. Since different code values must differ in at least one bit, any input change must produce a change in at least one output bit. Given invertible substitution table S with shuffled contents, define the output distribution for any input code change to be an arbitrary selection from the output codes which differ from the current output code. If the output codes are a complete set of 2**m values (0..(2**m-1)) for some m, counting arguments show that it is likely that about half of the output bits will change for any input code change of any nature whatsoever. Conversely, since each output bit is produced by an output code, and the selected output code is completely dependent upon every bit in the input code, each output bit is dependent on every bit of the input. A network with this property is normally called "complete" [5], and localized completeness is also the basis for "avalanche" [3: 22] in an iterated block cipher. Next, note that we first mix two 64-bit blocks (twice), then two 128-bit blocks. Suppose we have a change in any one input data bit: this produces an 8-bit substituted result which would normally affect just a single DES block. But the 64-bit mixing extends those changes to two DES blocks, and the 128-bit mixing extends the changes to all four DES blocks. Thus, any change of even a single input bit will affect all four DES operations. Using the transformation X := 3A + 2B; Y := 2A + 3B; any value change to A or B must be reflected in both X and Y: Suppose some change C is added to A: X := 3A + 2B (mod 2, mod p) X' := 3(A+C) + 2B X' := 3A + 3C + 2B dX := X' - X = 3C but 3C is non-zero (thus affecting the output) for any C which is not zero, and if C is zero, there has been no change to A. Suppose some change C added to B: X := 3A + 2B (mod 2, mod p) X' := 3A + 2(B+C) X' := 3A + 2B + 2C dX := X' - X = 2C Similarly, 2C is also non-zero for any C which is not zero. Suppose we try to make C half the value of p plus the highest bit (2**(deg(p)-1)) so that p will be activated and 2C will cancel the lower bits of p: Alas, p is irreducible so there is no q S.T. 2q = p. Similar arguments apply for Y := 2A + 3B. The experimental implementation uses the degree-128 irreducible 0100004000000400200002000004000001 (hex), and the degree-64 irreducible 010002000000800201 as block mixing polynomials. The output from each DES operation is, of course, random-like, so one might think it could be used directly. However, a three- level structure is still necessary to prevent, for example, "fix- in-the-middle" attacks, so the output substitutions are important. We also need the output mixing so that the result from a single DES block cannot be isolated and worked on independently. The guaranteed performance of the input substitution and the block mixing transform imply that each DES input block collectively depends upon each and every input bit. The expected performance of the DES algorithm extends this, making every DES output bit depend upon each and every input bit in the entire large input block, thus making all DES outputs "complete" over the large input block. Cryptographic Strength First let's review where modern cryptographic science stands with respect to "strength": 1. There is no algorithmic test to "certify" or evaluate the "strength" of a cipher. 2. Despite a half-century of intensive mathematical work, we still have exactly one cipher which is commonly accepted as having been proven "unbreakable," and that cipher is normally impractical. Despite this immense effort, and the fact that a "proof" of cipher strength is unfulfilled for any practical cipher whatsoever, there are still calls for "proofs" of new cipher designs. 3. While various cryptanalytic attack strategies are known, each such attack is necessarily specific to the particular cipher being attacked. Attack names represent strategies, rather than generally-applicable algorithms. Simply knowing the history of previous attacks does not necessarily provide insight into applying those attacks to a new cipher. 4. Ordinarily we speak of the "strength" of a cipher as the minimum effort needed to "break" the cipher. Unfortunately, we are necessarily limited to discussing what we know now, and not what can be known in the future. Any current minimum may not last, and we may not be able to know whether it will last or not. With those points in mind, the current "strength" for 4x Fenced-DES is ((2**56)**4)(256!**64) keys, a very big number. I would be delighted to learn of a simpler attack. It would of course be ridiculous to accept this sort of number as a true indication of strength. Personally, I would be happy with anything over 112 bits, since this should be sufficient for the next couple of decades and then we may have a stronger basis for cryptographic design. Design Strength Note that we need assume no "strength" for the mixing layers, but simply mixing: Each mixed output block must be a function of each and every bit in both input blocks. In this particular design we need only two levels of mixing to make sure that every input bit has propagated to all four DES blocks. And then we need two more to make sure that all four DES blocks participate in every output bit. The purpose of the small substitutions is to prevent the (weak and known) mixing functions from being exploited to divide-and-conquer the DES operations. Small substitutions appear to be sufficient to isolate the mixing functions, because "known plaintext" is only available across the entire cipher, and not across the internal layers of the cipher. When known-plaintext is not available, and substitutions cannot be separated for divide-and-conquer, little substitutions can be surprisingly strong. In the 4x construct, we might lay all the strength on the four DES keys, which would imply a 224-bit value. On the other hand, an attack which is able to isolate one of the DES keys (perhaps as a consequence of 1x operation using the same state), would reduce this to 168 bits. Note that the substitutions must be keyed even if we discount their "strength." Strength Arguments by Attack Exhaustive Search: Try each key until the correct one is found. Preventing this now requires a keyspace substantially larger than 56 bits (or, with a computationally-expensive setup phase, perhaps a few bits less). It seems reasonable to claim that Fenced-DES has at least a 224-bit keyspace. Note that this is not four times the DES keyspace, but four times the key size, which is 2**168 times the conventional DES keyspace. Known-Plaintext/Defined Plaintext: Somehow "obtain" both the plaintext and the corresponding ciphertext for some large number of encipherings (under one key). This has many flavors: Codebook: Try to obtain all possible ciphertexts and associated plaintext; then, when a ciphertext occurs, look it up. This is normally prevented by having a large number of transformations, which implies both a large block size and a large keyspace. Fenced-DES has both. Codebook approaches can be combined with "divide-and-conquer" to isolate and define parts of some ciphers. Fenced-DES tries to avoid these attacks by not allowing the parts to be isolated and worked on separately. Meet-in-the-Middle: With a multi-layered structure, given known- or defined-plaintext, search the top keyspace to find every possible result, and search the bottom keyspace to find every possible value. With a two-level construct, matches can be verified with some subsequent known-plaintext/ciphertext pairs. Fenced-DES avoids this by using a three-level construction, and by using outer layers which have a huge "keyspace." Differential Cryptanalysis: Given a S-P iteration cipher with known tables, use any statistical unbalance in the tables to peer back into previous steps. Fenced-DES avoids this by having no fixed tables, by using only balanced full-substitution tables, and by using a fully-balanced block mixing transform to avoid "divide-and-conquer." Important Aspects of the Design First, the Fenced-DES construct is more like a Kam-Davida substitution-permutation (S-P) design [5] than the common iterated Feistel design [3] represented by DES itself. The block mixing transform is specifically intended to avoid the sort of weakness exploited by the recent Heys-Tavares attack [4] on S-P designs. Next, it seems that there is a fundamental weakness in any two- layer construct for some form of "meet in the middle" attack when we assume "defined-plaintext" capabilities. Fenced-DES has three independent layers to avoid such attacks. Conventional block-cipher designs generally use unkeyed static substitution tables which are selected for "optimum" performance. In contrast, Fenced-DES uses only key-generated tables, in which any table permutation is as good as any other, making selection unnecessary. (A shuffled substitution is very unlikely to be linear [2], but linearity is itself unimportant when it cannot be detected externally. The mid-level substitution--here DES--acts to hide any S-box linearity.) Conventional block-cipher designs are also very economical with state, using either small tables (e.g., the 256 bytes in eight 6-bit to 4-bit tables in DES), or no tables at all (e.g., IDEA). But 4x Fenced-DES uses 16K (bytes) of tables, all keyed. More conventional S-P designs tend to use the same block size at each substitution level, thus becoming vulnerable to Heys-Tavares attacks [4]. Fenced-DES differs from this approach by having a middle layer with a block size which is much larger than the outer layers (this is similar to a Kam-Davida "partition" [5: 749] but differs in that it is a single block). This should prevent those small substitutions associated with a single internal block from being separated and attacked individually. Other contemporary block-cipher designs generally use a 64-bit block size. This is much weaker than it was 20 years ago, when that size was selected for DES. To avoid birthday attacks on ciphertext, as well as unknown information-based attacks, 4x Fenced-DES has a nominal block size of 256 bits, although 8x or even 16x versions are both possible and practical. 2x and 1x versions can be used to cipher the last part of a message, thus reducing data expansion to that expected with DES alone. A fundamental difference is that conventional S-P designs perform only a bit-permutation (or "transposition") between substitution layers; this is a weakness in that an input bit to one layer is exactly the same as some output bit in the previous layer. Fenced-DES differs from other block-cipher designs in the use of a block mixing transform to make the input code to a middle-layer substitution (in this case, DES) a function of every substitution in the previous layer. This allows the external block size to be expanded while preventing substitutions in the middle layer from being separated and attacked individually. An interesting aspect of the Fenced-DES design is the possibility that assumed properties of DES--a cipher which has been studied and evaluated for almost 20 years--can be provably expanded into properties of the larger cipher. Summary A new type of cryptographic ciphering construct has been introduced which uses DES as a building block. The result seems to provide a larger block size and more strength than triple-DES (the leading alternative), while operating almost three times as fast. References [1] Agarwal, R. and C. Burrus. 1974. Fast Convolution Using Fermat Number Transforms with Applications to Digital Filtering. IEEE Transactions on Acoustics, Speech, and Signal Processing. ASSP-22(2): 87-97. [2] Ayob, F. 1982. Probabilistic completeness of substitution- permutation encryption. IEE Proceedings, Pt. E. 129(5): 195-199. [3] Feistel, H. 1973. Cryptography and Computer Privacy. Scientific American. 228(5): 15-23. [4] Heys, H. and S. Tavares. 1993. Cryptanalysis of Tree- Structured Substitution-Permutation Networks. Electronics Letters. 29(1): 40-41. [5] Kam, J. and G. Davida. 1979. Structured Design of Substitution-Permutation Encryption Networks. IEEE Transactions on Computers. C-28(10): 747-753. [6] Pollard, J. 1971. The Fast Fourier Transform in a Finite Field. Mathematics of Computation. 25(114): 365-374. [7] Rader, C. 1972. Discrete Convolutions via Mersenne Transforms. IEEE Transactions on Computers. C-21(12): 1269-1273. [8] Ritter, T. 1991. The Efficient Generation of Cryptographic Confusion Sequences. Cryptologia. 15(2): 81-139. [9] Ritter, T. 1990. Substitution Cipher with Pseudo-Random Shuffling: The Dynamic Substitution Combiner. Cryptologia. 14(4): 289-303. [10] Shannon, C. 1949. Communication Theory of Secrecy Systems. Bell System Technical Journal. 28: 656-715. --- Terry Ritter ritter@io.com