The basic round of Quadibloc VIII consists of two connected Feistel rounds, each performed on one half of the block. Every effort has been made to supply a complete description of the algorithm in the text, but reference to the illustrations may make it easier to understand. Also, if any ambiguity is left, it should be understood that this cipher was conceptualized according to big-endian conventions; in all cases, the leftmost bits of any byte or word correspond to its most significant bits when it is considered as a number.
The following diagram illustrates the part of a Quadibloc VIII round that acts on the left half of the block:
The left quarter of the left half of the block is first modified by being XORed with a 32-bit subkey (in the case of the first round, this is subkey 49, and the number is advanced by 2 with each round). Then it is subjected to one of two possible transformations: either it is divided into four bytes, and each pair of bytes is enciphered through a two small-scale Feistel rounds, using key-dependent S-box S8 as the f-function, or it is divided into two 16-bit portions which are enciphered by two Feistel rounds.
The result of that transformation is used as the input to the f-function.
Then, the other of the two possible transformations is performed on the left quarter of the left half of the block, and finally another 32-bit subkey is XORed with it (subkey 50 in the first round, advanced by 2 for each succeeding round).
The two small transformations of a 32-bit quarter of the block are, in detail, as follows:
In the first transformation, numbering the bytes from 1 to 4 from left to right, first byte 2 of the block is changed by being XORed with the byte of S8 indicated by byte 1 of the block XORed with byte 1 of the subkey, and at the same time byte 4 of the block is changed by being XORed with the byte of S8 indicated by byte 3 of the block XORed with byte 2 of the subkey. (These XORs, and those in the next paragraph, may be changed to modulo-256 addition, under circumstances to be noted below.)
Subsequently, byte 1 of the block is changed by being XORed with the byte of S8 indicated by byte 2 of the block (in its current modified state) XORed with subkey byte 3, and at the same time byte 3 of the block is changed by being XORed with the byte of S8 indicated by byte 4 of the block (in its current modified state) XORed with subkey byte 4.
Thus, the block is divided into two halves; each half is subjected to two Feistel rounds in place, and the input to the f-function comes first from the byte on the left, and then in the second round from the byte on the right. The key-dependent S-box provides the f-function.
In the second transformation, the 32-bit block is split into two 16-bit halves. Two Feistel rounds take place, with the left half initially supplying the input to the f-function. The f-function begins with the input being XORed to 16 bits of subkey (the left half in the first round, the right half in the second, of a 32-bit subkey); then, the left half of the result is used to index into key-dependent S-box S10, and the right half of the result is used to index into key-dependent S-box S11. The two items found are then added (with the left byte being the most significant), and the result is the f-function output. The round is completed by modifying the target half of the block by XORing it with the f-function output.
Considering 32-bit subkey 721 as being composed of bits numbered from 1 to 32 from left to right, bit 1, if it is a 1, changes all the XORs in the first transformation when it is applied to the left quarter of the left half of the 128-bit block in the first round to additions, both those where the subkey is XORed to the index into S8, and where the output from S8 is XORed to a byte of the block.
This is done by bits 2 through 16 in rounds 2 through 16.
Bit 17, if it is a 1, causes the second of the two transformations, the one which acts on 16-bit halves of the 32-bit quarter, to take place first, in the first round. Bits 18 through 32 do this for rounds 2 through 16.
The f-function used in Quadibloc VIII is essentially the same f-function as seen in Quadibloc II and Quadibloc S, except with the use of different S-boxes and, in the case of the left half, an intermediate result is taken, which is not the same as the one taken in Quadibloc III, which also uses an otherwise similar f-function.
The f-function consists of three general types of phase: S, for substitution, P, for bit-permutation, and X, for the XOR of subkey material. The f-function used here is of the type XSPXSPXS. By having two full SP layers, changing a single bit of the input always affects the entire f-function output, and therefore the avalanche property of Quadibloc S is considerably stronger than that of DES; in return for a slower f-function, a single bit change in the input block propagates to the whole block after only four rounds instead of eight.
The first S phase uses S-boxes 1, 1, 1, and 2 in order from left to right, and the second uses S-boxes 1, 2, 2, and 2 from left to right. S1 and S2 are as described in the description of previous ciphers in the Quadibloc series, having been generated from Euler's constant.
The bit permutation used is a straightforwards one, where the first (leftmost) two bits of each byte remain in position, the next two bits are rotated one byte to the right, the third pair of bits rotated 16 bits, and the last (rightmost) two bits of each byte are rotated one byte to the left. Again, this is given in the description of the original Quadibloc cipher.
The third S-phase replaces all the bytes with their substitutes in key-dependent S-box S8.
The subkeys XORed with the f-function input are subkeys 1, 2, and 3 in the first round, and the subkey numbers are offset by 3 with each succeding round (thus, subkeys 4, 5, and 6 are used in round 2).
An auxilliary result is also produced from the f-function for the left half of the block. This result is the XOR of the current values in the f-function after, of the complete f-function, in the form XSPXSPXS, the parts from the beginning labelled XSP and the parts XSPXSP have been done.
For the remaining three quarters of the block, the auxilliary result will be used to control the order of the two transformations applied to a single quarter, and whether, for the transformation of the first kind (which may be done first or second) XORs or single-byte additions are used, in the fashion that subkey 721 controlled this for the first quarter. Other bits of the auxilliary result will be used to select subkeys for use in subsequent encipherment from a set of four possible values, and to select S-boxes from two possibilities for the f-function used in the right half of the block.
First, the right quarter of the left half is subjected to one of the two available transformations. If the bits of the auxilliary output of the f-function are numbered from 1 to 32 from left to right, bit 28, if it is 0, indicates that the transformation of the first type, using S8 as the f-function, is done first; if it is 1, it indicates that the transformation with a 16-bit wide f-function is done first. Bit 27 indicates, if it is a 1, that the XORs in the transformation of the first type uses bytewise additions instead of XORs.
Bits 9 and 10 indicate, as a two bit number, bit 9 being more significant, which of the subkeys 145, 289, 433, or 577 is used for the transformation of the first type (whether it is done first or second), and bits 11 and 12 similarly indicate whether subkey 146, 290, 434, or 578 is used for the transformation of the second type. (In the next round, and each time one progresses from one round to the next, the number of each subkey in each of these groups of four subkeys is advanced by 9.)
After the first transformation is performed, the f-function output is XORed with the right quarter of the left half of the block. Then, the second transformation is performed.
This diagram illustrates the part of a Quadibloc VIII round that acts on the right half of the block:
In the upper left corner of this diagram, the 32-bit auxilliary output from the f-function in the right half is shown.
As can be seen from comparing the two diagrams, the operations that take place on the right half of the block are very similar to those which apply to the left half of the block. The main difference is that the 32-bit auxilliary f-function output came from the left half, and it is used extensively in modifying the encipherment of the right half (only six of its 32 bits were used to affect the transformations which applied to the right quarter of the left half).
Here, subkey 113 is first XORed with this quarter. This subkey number advances by 1 with each round, not by 2 as for the left half. Bit 30 of the auxilliary f-function output from the left half controls whether the transformation of the first type (if 0) or of the second type (if 1) is done first, and bit 29, if 1, selects the use of bytewise addition in the transformation of the first type.
Again, as before, the value between the two transformations is used as the f-function input. Bits 13 and 14 of the auxilliary f-function output select the subkey (from 147, 291, 435, and 579) to use for the transformation of the first type, and bits 15 and 16 select the subkey (from 148, 292, 436, and 580) to use for the transformation of the second type.
After both transformations, subkey 129 is XORed with this quarter.
Again, the same XSPXSPXS structure is used. For the first two S stages, S-boxes 3 and 4 in the sequence generated from Euler's constant are used. Bits 1 through 8 of the auxilliary f-function output from the left half determine (0=S-box 3, 1=S-box 4) which S-box is used, for the four bytes of the f-function input in order from left to right, first in the first stage and then in the second. The third S phase again just substitutes bytes from S-box S8.
The three subkeys used are selected (in the first round, and advanced by 9 for each succeeding round as previously noted) from subkeys 149, 293, 437, and 581 for the first XOR, guided by bits 21 and 22 of the auxilliary f-function output; from subkeys 150, 294, 438, and 582 (in the first round) for the second XOR by bits 23 and 24; from subkeys 151, 295, 439, and 583 (in the first round) for the third XOR by bits 25 and 26.
Again, here we have two transformations, with the XOR of the f-function output in the middle. Bit 32 controls which transformation comes first, and bit 30 controls whether XOR or addition is used in the transformation of the first type. The transformation of the first type uses, in the first round, a subkey from subkeys 152, 296, 440, and 584, as selected by bits 17 and 18 of the auxilliary output of the f-function in the left half, and the transformation of the second type uses a subkey from subkeys 153, 297, 441, and 585, as selected by bits 19 and 20 of the auxilliary output of the f-function from the left half.
After each round of Quadibloc VIII, except round 16, the 16 bytes of the block are rearranged from being in the order
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
to being in the order:
16 8 5 6 12 10 3 1 13 15 7 14 4 2 11 9
Start of Section
Skip to Next Chapter
Table of Contents