In the recent past, the U.S. Data Encryption Standard (DES) has been the single widely-accepted cryptographic standard. However, continued advances in computation speed have now placed DES in range of attack. For the future we need a stronger cipher, hopefully one which takes much less computation than Triple-DES. One approach is to perform four cipherings of DES over a large 4x block width, and mix these cipherings, and hide the mixing, so that each ciphering contributes to each bit of the block. This approach uses the well-known strength of DES to produce a much stronger "4x Fenced DES" cipher, which is nearly as fast as DES itself. Using the 4x version with smaller 2x and 1x versions means that data will not expand any more than DES itself, thus generally providing a DES replacement based on DES.
The U.S. Data Encryption Standard (DES) was defined almost two decades ago. During this period, unprecedented advances in computational machinery have improved the ability to attack the cipher. While the same advances can be applied to implement the cipher as well as attack it, DES has a keyspace which is fixed and limited. Even though DES can be made to operate faster, it cannot be any stronger than it was designed to be almost 20 years ago. Relative to available attack technology, the cipher is far weaker than it was, and continues to weaken.
DES has become vulnerable to modern technical attack. It now appears that a substantial capital investment in engineering development and equipment could construct a "DES breaking" machine. Such a machine could search the entire DES keyspace in a few hours.
Would all users need to abandon DES if it could be penetrated at will by governments, corporations and organized crime? One can certainly argue that most data do not need ultimate protection. But when a DES-cracking machine finally is built, the economics of that expense argue that the machine will be kept busy if at all possible. Thus, DES attacks could become relatively fast and cheap. Businesses which currently protect very expensive and marketable secrets with DES should take immediate notice.
To maintain earlier levels of security, DES must be replaced with a stronger cipher. The one obvious alternative to DES is a simple construct built from DES called Triple-DES. Triple-DES, while generally being thought of as "strong enough," also unfortunately requires three times the computation of normal DES.
Because every security system is required to provide more benefit than its cost, raising costs by a factor of three (compared to normal DES) is a significant issue. Such costs could dangerously delay the necessary retirement of ordinary DES.
New ciphering algorithms are often challenged to "prove" they are stronger than DES. Since it is impossible to measure the "strength" of a cipher (and there is no absolute proof of strength for any practical cipher), new cipher algorithms are often considered curiosities. On the other hand, DES itself is well-known and accepted (despite having no proof of strength), so there seems to be some advantage in using DES as a component in a stronger cipher.
It is unfortunately impossible to measure the strength of a cipher, but we can measure related quantities. Perhaps the most useful quantity in a block cipher is overall diffusion or "avalanche." For example, suppose we encipher some arbitrary input block to an output block: Now, if we change the input block by even a single bit, each bit in the output block should change with probability 0.5. If we change different input bits, we will get different results, but still, about half of the output bits should change. If we perform this experiment for many different input values, we can measure the ability of the cipher mechanism to diffuse changes across the entire block.
The essence of building a wide block cipher from smaller components is mixing between the components. It turns out that we can develop a Balanced Block Mixing component which, when used with a substitution table or block cipher, provably assures such mixing. With this new component we can connect multiple DES cipherings together into a larger block. And, based on universally accepted assumptions about DES, we can prove that the resulting structure must have overall diffusion. While this is not "strength," it is related to strength, and having clear proof of a major ciphering property is very unusual. DES itself may have no such proofs.
S S S S S S S S
------DES------
S S S S S S S S
Each of the "S" characters represents an "eight-bit-wide" (256-byte) substitution table shuffled by a Random Number Generator (RNG) initialized from some key. The tables will be initialized before ciphering, and will not change during ciphering.
First note that all of the message information flows through DES itself. This means that the overall cipher cannot possibly be weaker than DES. This is a particularly important point for any new cipher design.
Moreover, the 1x Fenced DES structure is clearly stronger than DES, because a "known plaintext" attack requires knowing the actual input and output values at the DES cipher itself, and these values are hidden by the input and output substitution layers. If even a single input bit to DES is wrong (that is, if even one value in one input substitution is off by even one bit), DES will "avalanche" and about half of the output bits from DES will be wrong. Thus, a single wrong bit has the same statistical effect as a mostly-wrong value; this means that it is not possible to know when the input value is "close," so it does not appear possible to solve the substitutions in an advantageous way.
But 1x Fenced DES still has the same block-width as DES, and this is a problem. A block size which appeared substantial in the mid-70's is rapidly becoming a manipulable quantity.
| | | | | | | | | | | | | | | |
-------S------- -------S------- ...
| | | | | | | | | | | | | | | |
| | | | | | | | ...
| | | | | | | |________________________
| | | | | | |________________________ |
| | | | | |________________________ | |
| | | | |________________________ | | |
| | | | | | | |
--------------------DES--... -------------------DES--...
| | | | ________________________| | | |
| | | | | ________________________| | |
| | | | | | ________________________| |
| | | | | | | ________________________|
| | | | | | | | ...
| | | | | | | | | | | | | | | |
-------S------- -------S------- ...
| | | | | | | | | | | | | | | |
Here we show 2 of 16 input substitutions, and 2 of 16 output substitutions for a 128-bit block cipher. Each of the lines represents a single bit: Each input "S" contributes 4 bits to each of the two DES operations, and each output "S" takes 4 bits from each DES operation.
But with this design, unless we specially arrange the tables, we can only guarantee that a single-bit input change will avalanche one of the DES operations. This could be a problem, because when it is possible to externally isolate the internal components, they can be worked on separately. Requiring special table arrangements is also a problem.
S S S S S S S S S S S S S S S S
--------------mix--------------
------DES------ ------DES------
--------------mix--------------
S S S S S S S S S S S S S S S S
If we can assume that any input change to a Block Mixing Transform will propagate to both outputs, then we can guarantee that any one-bit change to the overall input block will avalanche both DES operations.
Note that we do not care how the DES operations are affected. If the DES input is affected at all, the cipher must construct another output code ("at random"); and, thus, "avalanche." It is not necessary that a Balanced Block Mixer itself "avalanche," DES will do that. It is not necessary that a Balanced Block Mixer have "strength," DES and the fencing substitutions will do that. It is only necessary that the Balanced Block Mixer guarantee that any input change whatsoever get propagated to each DES operation.
Another Balanced Block Mixer combines the randomized outputs from the DES operations, producing output blocks which are, therefore, also randomized. These randomized blocks are then substituted to produce the final output, which, of course, is also "random-like."
A Balanced Block Mixer takes multiple input blocks and generates the same number (and width) of output blocks, such that:
The advantage is to be able to mix blocks of substantial size very efficiently; 4x Fenced DES mixes 128-bit blocks.
The Fenced DES Block Mixing Transform uses the equations:
X = 3A + 2Bmod 2 and mod p, where p is a mod 2 irreducible polynomial of appropriate degree. This transform is a self-inverse.
Y = 2A + 3B
A consequence of this particularly efficient construction is that this Balanced Block Mixer has essentially no "strength" of its own. But suppose we consider DES with a known key: This is also a "weak" operation, but would nevertheless provide strong, invertible mixing for two 32-bit blocks. Strength is not necessarily related to mixing.
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
This 4x construct handles a 256-bit block. Similar 2x and 1x constructs could be used at the end of a message to reduce total data expansion to only that of DES itself.
Each "S" represents a separately-shuffled and independent 8-bit substitution table. This implies the presence of a particular keyed cryptographic RNG to shuffle the tables. The tables are set up and shuffled before ciphering, and then remain static during ciphering.
Each "---DES---" represents an ordinary 64-bit-block DES operation.
Each "---mix---" represents the mixing of the covered data blocks using Balanced Block Mixing technology. There are two levels of mixing on each side of the DES operations: The innermost levels each have two mixings which combine two 64-bit blocks; the outermost levels each have a single mixing which combines two 128-bit blocks.
An experimental implementation of this construct requires about 4.8 times the computation of DES to cipher 4 times the data. In contrast, Triple-DES would of course need 12 times the computation of DES to cipher the same amount of data. Thus, 4x Fenced DES is about 2.5 times as fast as Triple-DES.
In the experimental version, the keyed initialization of the 16K of state present in 64 small substitution tables (plus four DES keys) takes about 200 times the computation of a single 256-bit ciphering. However, several alternatives are available to provide dynamic block-by-block keying with minimal overhead, after a single major initialization. A major initialization might occur once a day.
The sequential combination of any number of invertible functions will itself constitute an invertible function.
In the 4x Fenced DES construction, we have five functional layers: The input substitutions, the input mixing transforms, the DES operations, the output mixing transforms, and the output substitutions. Because each layer is separately invertible, their sequential combination must also be invertible, so the cipher as a whole is invertible.
Now we ask whether the Fenced DES construct will have the overall diffusion property. There are five levels: Input and Output Substitution, Input and Output Block Mixing, and DES.
Since the Input Substitutions are invertible by construction, any change whatsoever in their input value will produce some change in their output value.
The Input Block Mixing is designed so that a single-bit change to one of the two input ports will produce some change to all four of the output ports. Since each of the output ports feeds a DES operation, this is sufficient to avalanche all four DES operations.
(Of course, for substantial input changes, it is possible to generate values which will leave one or more of the DES operations unaffected, although this is quite unlikely to happen by chance. In the mixing transform, such a circumstance requires specific related 128-bit values on each of the two input ports, and these values are hidden behind the input substitutions. We could manage to keep a DES operation unaffected if we knew the arrangement of the values in all the input substitutions, but that uncertainty is part of the strength of the cipher. And it seems unlikely that we could tell from the outside that we were successful -- that fewer than four DES operations have avalanched -- because any avalanche will enter the output block mixing and so be reflected over the whole width of the large block, with the specific resulting values hidden by the output substitutions.)
Thus, any single-bit change into the large input block will avalanche all four DES operations, producing a 256-bit avalanche overall.
When presented with four randomized values from the DES operations, the Output Block Mixing Transform will have no choice but to also output random-like values.
The Output Substitutions hide and protect the random-like values from the Output Mixing Transform. And, since their inputs are random-like, their outputs will also be random-like.
Rather than attempt to analyze the whole design at once, it seems worthwhile to reason about the design with various features disabled. In this way we have a better chance of seeing the overall strength when we use a combination of those features.
Here we try to understand the strength of the fencing layer: If we assume that the DES key is known, DES cannot provide strength. The only remaining "strength" is in the fencing layer. Thus, here we examine the ability of the input substitutions to hide the value going into the DES ciphering.
The attack consists of trying all possible plaintext values until the known ciphertext value appears on the output. This will identify a single element in each input substitution, which will also uniquely determine an element in each output substitution. We could instead work on the output substitutions, but the effort would be the same.
Note that if even one bit to the DES ciphering is wrong, DES will avalanche, so it will be impossible to tell how many bits are right until the correct input transformation is found. DES with a known key thus provides an example of "bit mixing" without "strength," which nevertheless contributes "strength" to the overall cipher.
For a given 64-bit input value, there are eight 8-bit values which select some value in eight different keyed input substitutions. There are 256 possible values for each of the eight substitutions, for 256**8 or 2**64 possibilities. Therefore, the strength of 1x Fenced DES with a known DES key is 64 bits.
(Note that this attack finds just one transformation in each byte substitution, out of 256 total. But each successive attack is slightly easier, and this is a convenient lower bound.)
A 120-bit keysearch will identify the DES key and one element in each of eight small substitutions; for a complete break, the remaining 255 values in those eight substitutions must still be found. Thus, the strength of 1x Fenced DES exceeds 120 bits.
Try each key until the correct one is found.
We assume that there is really no need for excessive keyspace, provided the keyspace is too large to search. On the other hand, there is no particular reason to avoid a super-large keyspace, unless it happens to lead to inefficiency or weakness of another nature.
Preventing exhaustive search now apparently requires a keyspace substantially larger than 56 bits. Even 1x Fenced DES has a keyspace of 120 bits, which should be "large enough."
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 ciphertexts, which implies a large block size, like that in 4x Fenced DES.
Note that 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.
With a two-layered structure, search the top keyspace to find every possible result, and search the bottom keyspace to find every possible input value. When the correct key is used for each layer, the internal value must match. (Inevitable false matches can be rejected by testing with other known-plaintext pairs.) This is a keyspace search only twice as large as that needed for each layer, thus exhibiting a major design weakness. (In building a cipher, we generally intend to produce an overall complexity which is the product of the internal complexities, instead of their sum.)
Fenced-DES avoids this by using a three-level construction, and by having a huge "keyspace."
Given an iterative cipher, use any statistical unbalance found in known, fixed substitutions to peer back into previous iteration steps.
Clearly, the DES parts of Fenced DES might be attacked in this way, although, at present, Differential Cryptanalysis of DES does not seem to be much advantage over exhaustive key search. In any case, this would apply only after the Fenced DES substitutions had been resolved.
The Fenced DES substitutions avoid Differential Cryptanalysis by being keyed and therefore unknown.
DES is effectively weakening, and must be replaced soon. The classical alternative, Triple DES, is too expensive for many users, taking three times the computation of DES itself. And any completely new cipher design must raise the terrible prospect of a complete new certification, in an environment without an institution which both could and would perform this task.
Fenced DES is based on DES, yet seems stronger than DES, and operates almost as fast. 4x Fenced DES is not only stronger than DES, it also uses a much larger and inherently stronger data block, and still operates much faster than Triple-DES.
Fenced DES is also a particularly clean design, which allows us to reason about the strength of the cipher in a particularly satisfying way. This is an extremely unusual and desirable characteristic.
In several long series of messages on sci.crypt, Bryan Olson has presented an alternate attack. Although it is incomplete (it does not "break" Fenced DES), it does give one pause for what it can do. Consequently, some aspects of the Fenced DES design in particular, and mixing ciphers in general, should be enhanced.
In general, Bryan's attack uses the fact that having only two mixing stages mean that four input bytes mix to produce four output bytes (approximately). Since four bytes is only 2**32 values, it is possible to traverse all possible values and select those with particular significance.
It is desired to identify those values which keep 3 of the 4 DES operations unchanged (the rest of the DES input would also be unchanged). It appears that one might detect that situation as a statistically non-random output distribution. In this way we might be able to identify 4-byte input values which will keep 3 of the 4 DES operations unchanged, thus allowing us to explore each DES operation independently. While this seems to set up the desired "divide and conquer" situation, the fencing substitutions have not been handled, so we are not nearly ready to attack the DES operations.
It was also suggested that if the substitutions could be resolved, and if this would permit the shuffling (keying) RNG to be resolved, that would suffice to break the cipher -- independent of DES strength -- because the same RNG is currently used to produce DES keys. The primary effect of this is to show that the reasoning which states that Fenced DES cannot be weaker than DES is faulty, provided that the RNG can be resolved.
Note that the smallest keying RNG used in our Fenced DES prototypes has a 496-bit keyspace or state (31 elements of 16 bits each), and is also nonlinearized with our "Jitterizer" technology. The Jitterizer drops out segments of the sequence, and also provides an "offset" for each "take" group, which means that the obvious RNG attacks do not apply. It is not known how one might attack a Jitterized sequence.
Again, Bryan's attack has NOT broken Fenced DES. But it is relatively easy to extend the Fenced DES design (and, indeed, mixing ciphers in general) to avoid these problems entirely. One avoids the main attack simply by using more mixing layers: Using 5 sub-layers on each side means that this sort of attack will require traversing 2**256 values, which is beyond the design strength of the cipher. With this amount of mixing, however, it may be advantageous to use alternate mixing structures.
It is also reasonable to double-shuffle the substitutions during keying, to avoid revealing information about the shuffling sequence if a substitution somehow is resolved. And DES keys probably should not be developed from that same RNG. An alternate approach would have the hashed User Key value set up the DES keys, and use DES operations to transform the hashed value into the RNG initial state.