Quadibloc 2002 is a block cipher designed to incorporate the ideas introduced in several of the other ciphers in the Quadibloc series.
This diagram illustrates the Quadibloc 2002 round.
It has some resemblance to the round in Quadibloc XI.
In addition to embodying the principle of indirection, as illustrated in Quadibloc IX and Quadibloc XI, it uses bit swaps which, by directing bits between inputs which were formed through different algorithms to outputs which are used for different purposes, make the cipher's algorithm variable in a data-dependent way, recalling Quadibloc III and VIII, but without creating vulnerability to timing or power consumption monitoring attacks, and it uses pools of subkeys as did Quadibloc VII; also, the distinction between the input to a Feistel structure and its subkeys is employed in a manner reminiscent of Quadibloc IV.
Thus, it can be said to sum up the lessons learned from the Quadibloc series of ciphers, except that I never seemed to learn the lesson that ciphers should be simple and fast rather than large and elaborate.
Because the elaborate f-function of this cipher only modifies 32 bits of the 128-bit block, diffusion is slow enough that 16 rounds are required.
In a Quadibloc 2002 round, the 128-bit block is considered to be divided into four 32-bit subblocks.
First, the leftmost subblock is changed by alternately applying two different transformations, one three times and the other two times. This leads to that subblock having four intermediate values, which are used in other parts of the round.
Then, the second and third subblocks are used as input to a form of the standard Quadibloc f-function. The two intermediate results are also used; in one case, the second one is XORed with the input to the f-function (the value of the second subblock) and in the other case, the first one is XORed with the final f-function output.
The first of the intermediate values of the first subblock is used to select subkeys from subkey pools for these f-functions, as well as for some of the later manipulations. Because of this, the first subblock must be transformed before the two f-functions are performed, the reverse of the order required by some of the variations of Quadibloc XI, such as Quadibloc XI HD.
The intermediate result values are then transformed, using operations similar to those used on the first subblock. In one of them, instead of using the constant S-box S4, key-dependent S-boxes S8 and S9 are used.
This leaves us with six values; for each of the second and third subblocks, an f-function output, and two scrambled intermediate results. The algorithm used to scramble the first intermediate result of the second subblock is used to scramble the second intermediate result of the third subblock, to create an additional degree of diversity in the algorithms which produced each value.
The second intermediate value of the first subblock is then used to control an ICE-style bit swap, between the scrambled first intermediate result of the second subblock and the f-function output of the third subblock. The two outputs of this bit swap are each used to control two further bit swaps, one between the f-function output of the second subblock and the scrambled first intermediate result of the third subblock, and the other between the two scrambled second intermediate results (but each one is scrambled by a different algorithm, and only one second intermediate result was XORed with the initial input).
These four results, together with the third and fourth intermediate values of the first subblock, are used to produce the f-function output of the round as a whole by means of two four-round Feistel structures. The first of the last two bit swaps directed bits between the subkeys of the first two rounds of the first structure and the input to the second structure; the second of those bit swaps directed bits between the input to the first structure and the subkeys of the last two rounds of the second structure. The two intermediate results were used as subkeys for the last two rounds of the first structure, and the first two rounds of the second structure.
The outputs of the two Feistel structures are then applied to the fourth subblock using a combiner similar to that used with Quadibloc XI, in which each 32-bit input is used as subkeys for four small-scale Feistel rounds that produces subkeys for two small-scale Feistel rounds acting on half of the 32-bit subblock.
Because of the heavy use of key-dependent S-boxes, and because the bit swaps vary the algorithmic function of bits of disparate algorithmic origins, this round is highly resistant to analysis.
After each round except the last, subblocks are interchanged using the same tire-rotation pattern as in Quadibloc XI.
The 128-bit block to be enciphered is split into four 32-bit subblocks for the purposes of this block cipher.
The first, or leftmost, subblock is subjected to five transformations.
The first transformation proceeds as follows:
The value of the leftmost subblock after this transformation is the first intermediate value.
The second transformation proceeds as follows:
The value of the leftmost subblock after this transformation is the second intermediate value.
The third transformation is identical to the first transformation, except that subkey K3 (K10, K17... K108) is used instead of K1.
The value of the leftmost subblock after this transformation is the third intermediate value.
The fourth transformation is identical to the second transformation, except that subkey K4 (K11, K18... K109) is used instead of K2.
The value of the leftmost subblock after this transformation is the fourth intermediate value.
The fifth transformation is identical to the first transformation, except that subkey K5 (K12, K19... K110) is used instead of K1.
The value of the leftmost subblock after this transformation is the value on exit from the round.
The second and third subblocks are not modified by the round, but they are used as inputs to a calculation, along with the first two intermediate values of the first subblock, which produces six values which are then used to derive four values, which along with the second two intermediate values of the first subblock to calculate two 32-bit values which are used to modify the fourth subblock.
The process for deriving three values from the value of the second subblock proceeds as follows:
A copy of the value of the second subblock is used as input into a version of the standard Quadibloc f-function. This function proceeds as follows:
1 2 27 28 21 22 15 16 9 10 3 4 29 30 23 24 17 18 11 12 5 6 31 32 25 26 19 20 13 14 7 8
The first temporary value is calculated by forming the XOR of the input to the f-function and the second intermediate result.
The second temporary value is the first intermediate result.
The first temporary value is transformed by means of a transformation identical to the first transformation applied to the first subblock except that subkey K6 is used in place of subkey K1 (and so on for later rounds).
The second temporary value is transformed by means of a transformation identical to the second transformation applied to the first subblock, except that a value obtained by using the fourth nybble of the first intermediate value of the first subblock as an index into subkey pool SP4 is used instead of K2 (a value from SP12 used instead of K9 in the second round, and so on), and with key-dependent S-box S8 used instead of the constant S-box S4.
A similar calculation is then performed on a copy of the value of the third subblock, but with some important differences.
First, it is subjected to the same version of the standard Quadibloc f-function as used with the second subblock. However, the subkeys are different: now, the fifth, sixth, and seventh nybbles of the first intermediate result are used as indexes into SP5, SP6, and SP7 respectively (instead of the first, second, and third nybbles into SP1, SP2, and SP3), again using later subkey pools in later rounds.
The first temporary value is now formed from the second intermediate result of this f-function of the third subblock alone; the second temporary value is the XOR of the first intermediate result and the f-function output.
Now, the first temporary value is transformed by means of a transformation similar to the second transformation applied to the first subblock. But instead of K2, the value selected from SP8 by the eighth nybble of the first intermediate value of the first subblock is used, and instead of S-box S4 (or S8), the key-dependent S-box S9 is used.
And it is the second temporary value that is transformed by means of a transformation identical to the first transformation applied to the first subblock, except that subkey K7 is used instead of subkey K1.
We now have six values; the f-function output, the transformed first temporary value, and the transformed second temporary value, from the second subblock, and the f-function output, the transformed first temporary value, and the transformed second temporary value, from the third subblock.
The second intermediate value of the first subblock is used to control a bit swap of the type pioneered by the block cipher ICE, wherein bits in the two other inputs corresponding to bits having the value of 1 in this control input are exchanged between them. The two inputs consist of the transformed second temporary value from the second subblock, and the f-function output from the third subblock. The outputs after swapping shall be called the first and second swap outputs (thus, the first swap output consists of those bits of the transformed second temporary value from the second subblock corresponding to zero bits in the second intermediate value of the first subblock, and those bits of the f-function output from the third subblock corresponding to one bits in the second intermediate value of the first subblock).
The first swap output is used as the control word for another ICE-style bit swap, whose two inputs are the f-function output from the second subblock and the transformed second temporary value from the third subblock, and whose two outputs will be the third and fourth swap outputs.
The second swap output is used as the control word for another ICE-style bit swap, whose two inputs are the transformed first temporary value from the second subblock and the transformed first temporary value from the third subblock, and whose two outputs will be the fifth and sixth swap outputs.
These swap outputs, together with the third and fourth intermediate values of the first subblock, are used to calculate the primary f-function value for the round in two 32-bit halves by the following procedure:
Each of the two final 32-bit output values is created by means of four Feistel rounds similar to the two Feistel rounds which made up the first transformation applied to the first subblock.
For the first 32-bit final output value, the input is the fifth swap output, for the first two rounds, K1 is replaced by the fourth swap output, and for the last two rounds, K1 is replaced by the third intermediate value of the first subblock.
For the second 32-bit final output value, the input is the third swap output, for the first two rounds K1 is replaced by the fourth intermediate value of the first subblock, and for the last two rounds K1 is replaced by the sixth swap output.
The two final output values are then applied to the fourth subblock, changing its value, by means of a combiner similar to that seen in some of the later variants of Quadibloc XI.
The application of the final output values to the fourth subblock proceeds as follows:
This transformation consists of two rounds.
In each round, one half of the fourth subblock is used as input to four Feistel rounds, keyed by the input to be combined with the value being modified. The output of those Feistel rounds is then used to supply subkey input to two more Feistel rounds of the same type which modify the other half of the subblock. Thus, the input functions as a subkey in a cipher that produces a subkey.
The first round proceeds as follows:
In the second round, bytes 3, 4, 1 and 2 serve the same functions as bytes 1, 2, 3, and 4 respectively did in the first round, and the four bytes of the second final output value perform the same function as the four bytes of the first final output value performed in the first round. The rounds are performed in place, so there is no interchange of bytes to move them into the positions of the bytes whose roles they now perform.
After each round, except the last, the four subblocks are to be interchanged as follows:
From the order: 1 2 3 4 to the order: 3 1 4 2
Quadibloc 2002 uses the following key material:
The methods used to generate normal subkey materials and key-dependent permutations will be the same ones as developed for Quadibloc XI and subsequently applied as an option to several of the earlier ciphers in the series. Using them, first subkeys K1 through K112 will be generated, and then the contents of subkey pools SP1 through SP128. Then, S8 will be generated, followed by the contents of S10, and then S9, followed by the contents of S11.
The key will be a multiple of four bytes in length, and must be at least eight bytes in length.
Once again, the methods used to generate subkey bytes and key-dependent permutations are as follows:
Three strings of bytes of different length are produced from the key.
The first string consists of the key, followed by one byte containing the one's complement of the XOR of all the bytes of the key.
The second string consists of the one's complements of the bytes of the key in reverse order, with three bytes appended containing the following three quantities:
The third string consists of alternating bytes, taken from the bytes of the key in reverse order, and then from the bytes of the one's complement of the key, and then that string is followed by the one's complements of the first four bytes of the key.
Thus, if the key is:
128 64 32 16 8 4 2 1 1 2 3 4 5 6 7 8
then the strings generated from it are as follows:
First string: 128 64 32 16 8 4 2 1 1 2 3 4 5 6 7 8 8 Second string: 247 248 249 250 251 252 253 254 254 253 251 247 239 223 191 127 37 170 93 Third string: 8 127 7 191 6 223 5 239 4 247 3 251 2 253 1 254 1 254 2 253 4 252 8 251 16 250 32 249 64 248 128 247 127 191 223 239
Given that the length of the key is 4n, the lengths of the three strings are 4n+1, 4n+3, and 8n+4, and hence all three are relatively prime, since both 4n+1 and 4n+3 are odd, and 8n+4 is two times 4n+2.
Two buffers, each containing room for 256 bytes, are filled by generating bytes from the first and second strings by placing them in a nonlinear shift register.
The form of that shift register is shown in the following illustration, showing its precise form for the first string.
Five bytes are read from the string at each step. For the first string, they are, as shown in the diagram, the eighth-last, fifth-last, third-last, and second-last bytes and the last byte. For the second string, they are the eighth-last, seventh-last, fourth-last, and second-last bytes, and the last byte. For the third string, they are the twelfth-last, tenth-last, seventh-last, and fourth-last bytes, and the last byte.
Each time the shift register produces a byte, it does so as follows:
Both buffers contain 256 bytes. The first buffer, called buffer A, is filled with 256 successive bytes generated from the second string by means of the nonlinear shift register filled with the second string. The second buffer, called buffer B, is filled with 256 successive bytes generated from the first string by means of the nonlinear shift register filled with the first string.
Once the setup is complete, subkey material is generated one byte at a time, the first byte generated being the leftmost byte of subkey K1, and so on.
A subkey byte is generated as follows:
The following diagram attempts to illustrate the complete process of subkey byte generation:
Note that this procedure, since it exercises the two strings used to select bytes, rather than the string used to generate values, results in a small change in the key resulting in large changes in the subkeys from the very beginning.
Once all the required 32-bit subkey words are generated, the key-dependent S-boxes S8 and S9 must be generated. To generate each bijective S-box, the following procedure is used:
The resulting contents of buffer D are used as the key-dependent bijective S-box intended to be produced. Note that this is a procedure, introduced for Quadibloc X, is more straightforwards than the other two basic procedures used previously to produce S8 in other ciphers in this series.
This procedure, although it uses buffers A and B, leaves them undisturbed; thus, byte generation may continue after one S-box is produced.
The subkey generation procedure given above works well for keys from 64 bits to 1,024 bits in length. When the length of the key approaches 2,048 bits in length, however, the first two shift registers are no longer thoroughly mixed by filling the buffers initially.
Thus, the following modified subkey generation procedure is given for keys which are more than 1,024 bits long. A key must still be a multiple of 32 bits in length.
This method ensures that the key schedule is a function of the entire key.
The first variant of the cipher defined is Quadibloc 2002 ED (Enhanced Diffusion). In this variant, the round is modified by performing the following additional operations:
Prior to being used as an input to the f-function computation, the second subblock is modified by being XORed with the XOR of the first intermediate value of the first subblock and the third intermediate value of the first subblock.
Subsequent to being used as an input to the f-function computation, the third subblock is modified by being XORed with the XOR of the second intermediate value of the first subblock and the fourth intermediate value of the first subblock.
This, at a cost of four 32-bit XOR operations, considerably increases the speed of diffusion in the cipher, as the two subblocks which originally were not changed by a round are now both modified based on the contents of the first subblock. Although the intermediate values of the first subblock are somewhat more exposed by this change by being used in this manner in addition to being used deep within the involved f-function computation, the fact that they are only used this way when XORed in pairs reduces the problem.
Although 16 rounds are still recommended, if it is desired to use the cipher with only 8 rounds, the ED variant should be used.
A second variant of this cipher, Quadibloc 2002 BT (Byte Transpose) attempts, without defining a special round type, to achieve what is achieved by the mixing and whitening phases of Quadibloc VI and VIII, as well as the special rounds at the beginning and end of Quadibloc II and III.
In Quadibloc 2002 BT, after rounds 4, 8, and 12, instead of transposing the four subblocks in the "tire rotation" pattern normally used, the sixteen bytes of the block are transposed from the order
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
to the order
1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16
Note that this byte transposition is its own inverse. In this way, because the parts of a subblock are thoroughly combined by the outer rounds, the role any bit will be in within the inner rounds is assumed to be obscured by this.
In addition, rounds 1 through 4, and rounds 13 through 16 are of the ED type, while rounds 5 through 12 are normal.
The byte transpose also speeds diffusion, because now even the transformations of the first subblock by itself serve to encipher the block as a unified whole. Think of Square, the predecessor of Rijndael, but with only four rounds (but without the special type of round that allows a specific saturation attack against it). However, since the byte transpose doesn't include the "tire-rotation" transpose of the subblocks as an implicit part, when it is reversed, the phase of the subblock arrangement is changed, and this may seem to be a weakness.
With only eight rounds, a byte transposition in the middle would not strengthen the cipher appreciably, due to the boomerang attack, and in that case making the succession of rounds unbalanced for some bytes, it may even weaken the cipher. But for sixteen rounds, it should strengthen it, and strengthen it appreciably, particularly in terms of its strength under severe weak key conditions.
The Quadibloc 2002 round is large and elaborate. Yet, it is proposed that this cipher have 16 rounds, the same number as was used by DES, with its much simpler round structure. Why can't one take advantage of this complexity to still have a secure cipher with only four rounds?
The diagram at right gives a high-level overview of the cipher. And it shows what can happen in the case of a certain kind of chosen-plaintext attack.
Each round is shown here very simply; the first subblock is subjected to a transformation that depends on itself alone (and, of course, the key) and the fourth subblock is subjected to a transformation that depends on all three other subblocks.
If one keeps the first three subblocks constant, in a series of plaintext blocks varying only in the fourth subblock, then the transformation depending on the other subblocks which takes place in the first round, shown in blue, never changes. And the only other time this subblock will change is in the transformation which is independent of the other subblocks, shown in green, that takes place in the third round.
The complicated transformations that the other subblocks undergo, shown in light blue-green, are not a problem. However the other subblocks may change differently because the fourth subblock changed on input, the output subblock corresponding to the fourth subblock, which is the second subblock, will run through all possible values, without duplicates, if one runs through all the values of the fourth subblock on input while holding the other three constant.
If it were not for the fact that the first subblock is changed as a unit in a complicated way, it would not be necessary to mount a saturation attack with 2^32 chosen plaintexts to observe this, since if you look at the combiner operating on the fourth subblock in detail, its fourth byte is the first one modified by the XOR of a value obtained from the three other bytes. Thus, changing that fourth byte by a pattern of bits, while it results in the rest of the subblock changing in a complicated way, and then other subblocks changing in a complicated way in later rounds, has the immediate result of changing that fourth byte in the output by that pattern of bits. (Of course, this "weakness" applies to the entire half of the block being modified in a classical Feistel round cipher.) But because the first subblock does also change, this simpler distinguisher works only after two rounds.
The same thing can be done for the fourth subblock of ciphertext blocks in a chosen-ciphertext attack.
The only time that subblock is changed in a way that depends on the other subblocks is in the fourth round. So if ciphertext blocks are changed only in the fourth subblock, as it is deciphered, it is subjected to the same two transformations; the one in the fourth round that is the same because the other subblocks are constant, and the one in the second round that is independent of the other subblocks.
Thus, the plaintext block output which corresponds to it, the third subblock, is in this case connected to the fourth subblock by a substitution.
What about the other two blocks? The situation is not so simple in their case.
Let us say that one wants to mount a chosen plaintext attack where the second subblock is varied. In this case, the substitution depending on the other three subblocks takes place in the second round, where the second subblock becomes the fourth.
Holding the third and first subblocks constant in the plaintext ensures that the first and second subblocks remain the same in the second round.
But because the second subblock has changed, the fourth subblock, transformed in the first round in a way that depends on the second subblock, in the box shown in red in the diagram, will, as the third subblock in the second round, be different.
However, it is possible to identify its distinct values, since the output from that transformation, which is what we would like to keep constant, only goes through one other transformation, the one in the third round that is independent of the other subblocks.
So, for each input value of the second subblock, we can try to find the value for the fourth subblock that produces a desired constant value of the second subblock on output. For these values, the transformation of the second subblock on input to the first subblock on output will be a substitution.
Thus, substitutions for two of the subblocks can be obtained for a particular case in 2^32 tries, and for the other two in 2^64 tries. By themselves, of course, these substitutions won't allow one to decipher any part of blocks corresponding to other cases.
Not shown in the small overview diagram is the fact that there are only 2^64 possible transformations of the fourth subblock in a round; although it depends on the three other subblocks, two 32-bit values are derived from them which alone control how the fourth subblock is modified. This bottleneck also may simplify the process of searching for structure in this cipher for a given key.
None of this makes it easy to read plaintext, even for the four-round version of this cipher; but the fact that there is any visible structure at all, instead of a substitution that is completely opaque, against which nothing can be done short of recording the output for all 2^128 possible inputs, means that the four round version cannot be considered to be completely devoid of weaknesses.
Start of Section
Skip to Next Chapter
Skip to Next Section
Table of Contents