Layers may perform confusion (such as an array of keyed substitution tables), typically one-way diffusion (such as an exclusive-OR chain), or both (such as a Latin square chain).
Particular designs of 80 bit (10 byte) and 1600 bit (200 byte) wide ciphers were investigated experimentally. Results indicate that specific designs with four or more confusion layers, intermixed with diffusion layers in both directions, perform like the expected random permutation. In practice, more layers may be required for optimal strength.
Variable Size Block Ciphers have some significant advantages:
These ciphers are composed of horizontal rows or layers of similar components, and vertical columns which often contain different component types. The heart of each cipher is the vertical column composed only of operations which are one element in width. In these particular designs, each element is one byte wide; this means that all operations are byte-width operations, and all internal data paths are eight bits wide.
Each column in any one of these ciphers contains the same connections, table-positions and operations. The particular tables used in each column generally will vary. The columns differ in the particular adjacent columns (if any) to which their data and diffusion inputs and outputs are connected. Each cipher can be extended to arbitrary size by adding more columns of virtually identical structure. Dynamically variable size operation generally requires a dynamic selection among keyed substitutions for each particular substitution position.
Since diffusion is necessary across the width of the block, each column communicates with adjacent columns. This means that the leftmost and rightmost columns will produce diffusion carry outputs (which can be ignored) and will require external input values.
These constructions use simple invertible diffusion and confusion layers (or combined layers). Since each of the layers is separately invertible, the cipher itself is invertible, so that enciphered data may be deciphered. Deciphering occurs by producing the inverse of each layer and processing each layer in reverse order from that used in enciphering.
These ciphers are primarily keyed by permuting each of the substitution tables under the control of a keyed cryptographic RNG. Dynamically-variable block size operation generally requires selecting the particular substitutions used in each position from a heap of keyed substitutions. Additional methods for low or zero-overhead dynamic keying are also available.
The example figures are data-flow diagrams. That is, the figures represent the flow of data from some source through a data path to an operation, the operation itself, and the flow of the result through another data path to some data sink or user of the result value. In a hardware realization, a data path might be actual metallic connections. In a general-purpose computer realization, a data path might simply represent the movement of data from one operation to another.
Example 1 includes, in alternation, four layers of substitution operations and three layers of exclusive-OR operations. Like all of these variable size block cipher designs, the structure of each column is the same, although the actual substitution tables used will vary.
The 80-bit input block is split into ten 8-bit columns and processed by a confusion layer. All of these results are mixed by an exclusive-OR chain in a right-going diffusion layer. Subsequent diffusion layers are left-going. Each diffusion layer implies both an Initial Value from outside the cipher and a Carry value which can be used for expansion. In practice, yet another pair of layers might be needed for best strength.
To understand the purpose of the top three layers, it is useful to consider the operation in the case of two different input blocks: first, some random block, and second, the same block with only the leftmost bit changed. The different or changed bit produces a different value on the leftmost input substitution. Thus, at least one bit will change on the substitution output, and will be propagated across the full width of the block through the first diffusion layer. This will change the value into each of the substitutions in the second confusion layer, thus changing the result from each substitution. In this way, a change in any one input bit affects the column which includes that bit, and also each column to the right.
It is at least possible that two input changes could cancel, to produce no diffusion effect on subsequent substitution tables on one layer. While this appears to have little statistical impact, it could certainly be avoided with an additional set of confusion and diffusion layers with diffusion in the same direction.
The remaining confusion and diffusion layers have diffusion in the opposite direction to produce the overall diffusion results expected from a block cipher.
Unlike example 1, some of the diffusion paths used in example 2 include intermediate substitutions using substitutions already in place. Clearly, it would be possible to introduce new substitution operations between each exclusive-OR in the diffusion paths, but much of the benefit of such a structure is achieved here without added computation.
To decipher the block, again note that each layer is separately invertible. We simply produce the inverse tables of those used for enciphering, and process the block "up," from OUT to IN in example 2. The direction of diffusion in each diffusion layer remains unchanged.
The byte-width Balanced Block Mixing operations each take two input bytes, and produce two output bytes, in the direction indicated by the internal arrow.
Because the structure of the mixing component differs from the exclusive-OR used in examples 1 and 2, the diffusion architecture of example 3 is accordingly different. In particular, there is always one less Balanced Block Mixing in the diffusion layers than there are element-wide data paths and substitution elements in the confusion layers. We can think of the Balanced Block Mixing as fitting in the space between adjacent confusion columns.
To decipher the block we simply produce the inverse confusion tables of those used for enciphering, and process the block "up," or from OUT to IN in example 3. That is, a data-flow diagram for deciphering is the same as example 3 with all arrows reversed. The Balanced Block Mixer outputs are made inputs, and the inputs outputs, and diffusion occurs in the opposite direction.
In a byte-width Latin square, each of 256 rows and 256 columns will have exactly one occurrence of each byte value 0..255. Before operation, the needed Latin square (or squares) are constructed under the control of one or more cryptographic keys. Each operation in this example might well use the same keyed Latin square.
We can directly compare example 4 to example 1, if we consider a confusion layer and diffusion layer in example 1 as a single layer in example 4. In both cases, we first have one confusion and diffusion to the right, and two to the left. We are then left with a single confusion layer at the bottom of example 1, and a different sort of isolation layer in example 4.
To decipher the block, note that each layer is separately invertible. We simply produce the appropriate "inverse" square from that used for enciphering, and process the block "up," from OUT to IN in example 4. (Note that for a Latin square to be "invertible," one of the input values must be known, as is the case in this example.) A data-flow diagram for deciphering is exactly the same as example 4 with only the down-arrows changed to up-arrows. The direction of diffusion in each diffusion layer remains unchanged.
When substitution operations are indicated, the particular table used at each position could be fixed at design time, or selected dynamically, during operation, from among many such tables.
Note that strong block ciphering generally requires a block size of eight bytes or more. While the exact same VSBC structure could operate on smaller blocks, small blocks just are not strong cipherings. Thus, the external system should apply a dynamic VSBC in ways which will assure that each block has at least minimum size, if this is at all possible.
In all cases, deciphering is performed by very similar constructions which process data from the bottom to the top. In most cases, the diagram for deciphering is exactly the same as that for enciphering, with all downward data paths replaced by upward data paths.
Normally, with exclusive-OR or Latin square diffusion, the direction of diffusion does not change when deciphering. However, when Balanced Block Mixers are used, for each mixer, both outputs become inputs, and both inputs become outputs, meaning that the diffusion direction is also reversed.
When deciphering, each substitution table is replaced by its inverse, and each Latin square is replaced by its appropriate inverse. If the Balanced Block Mixers are keyed, each of those will be replaced by its inverse; like exclusive-OR, the usual Balanced Block Mixer is its own inverse.
We can support a huge keyspace by using a key of reasonable size to initialize the state of a random number generator. The sequence of values from the random number generator mechanism can shuffle all of the tables in the cipher. Both the design of random number generators and their use to shuffle invertible substitutions are well known and are not improved by the VSBC innovation.
Some dynamic keying may be provided by diffusion-layer inputs (these are the start of the diffusion channels on one or the other side of the block). More dynamic keying can be added by including a keying layer in the cipher. This layer would simply combine a key of the block width with the data. Combining could be additive, Latin square, or other cryptographic combining.
In a dynamically-variable size cipher, a key of any width can be produced by a keyed random number generator. While this would give us a sort of "stream cipher" layer, the sequence would "re-originate" for each block. The VSBC structure would provide overall diffusion which is not available in a stream cipher.
Additional dynamic keying can be provided by including a key as part of the data block. This would produce more ciphertext than message (enciphering would appear to expand the data), but the resulting key would be reproduced by deciphering, and could be used to authenticate the original data. Since, in a variable size block cipher, the data block can be as large as desired, even an 80-bit dynamic key could be a minor overhead. And it might well provide an authentication which may be necessary anyway.
The overall diffusion characteristics for a block cipher are relatively easy to check by experiment: For a random key we choose a random data block and encipher it. Then we change a bit in the original block, encipher that, and compare the result to the original ciphertext, counting the number of bits which changed. We do this for a large number of random blocks and a large number of keys, producing a distribution which is the number of occurrences of each possible number of bit-changes. We know what to expect because the probability of finding any particular number of bit changes c in a block of b bits is:
b
( )
c
Prob( c ) = -----
b
2
With a reasonable number of experiments (e.g., 160,000 encipherings of 200-byte blocks) large blocks produce an especially clear and distinct diffusion signature.
In a 1600-bit block, the vast majority of bit-changes are confined to only 10% of the possible range. In fact, 99.98% of the time, the observed bit-changes should fall in the range of 725..874. This is just the three middle bars of a 31-bar display.
Each bar represents the summed probability of 50 adjacent bit counts. The slight unbalance in the two sides is an artifact of summing an even number of bits per bar.
Although it may not seem so, this is in fact the expected binomial curve, it is just a very narrow curve.
For comparison, we have the similar graph for an ideal 64-bit block:
And the graph for an ideal 80-bit block:
Although the overall diffusion signatures for the smaller blocks is certainly clear enough for testing, the diffusion signature is clearer in the larger blocks.
These computations mean that even a huge number of experiments should produce a very narrow range of expected values. Finding this sort of experimental distribution is a clear and obvious indication that something is working right.
Overall diffusion tests of examples 1 through 4 have shown particularly good results, sometimes surprisingly better than very similar architectures.
For example, all of the substitution tables in these variable size block ciphers are just different arrangements or permutations of the same values. Among other things, this means that we can guarantee that any input change must select a different output value, and thus produce an output change. More general confusion functions, such as those supported in Feistel architectures, do not have this property and do not support this sort of reasoning unless limited to particular functions.
Similarly, the use of layers which provide diffusion across the width of the block simplifies diffusion questions compared to other ciphers. For example, most conventional Feistel designs apparently find the number of rounds needed to for complete diffusion by experiment. In the variable size block cipher examples given here, we can do the same sort of experiments, but also can reason about the effect of each separate layer, and there are relatively few layers to analyze.
Since there is no way to measure or guarantee the strength of any practical cipher, any improvement in the ability to reason about the mechanism is a big advantage.
These constructions are fast, efficient, scalable, and are relatively easy to work with in analysis.
This is the original public exposition of this sort of ciphering construct. Further research may indicate changes in the given constructions. But the general concept that Variable Size Block Ciphers can exist, that some efficient realizations do exist, is itself a significant step.