The key material used by Quadibloc VIII consists of:

- Six 64-bit swap masks, M1 through M6, each produced from 48 bits of normal subkey material (specifically, the least significant 6 bits of each byte of 64 bits of normal subkey material) by the use of a 4 of 8 code;
- One key-dependent S-box, S8, consisting of a permutation of the numbers from 0 to 255;
- Two key-dependent S-boxes, S10 and S11, each consisting of 256 16-bit values;
- Seven hundred and twenty-one 32-bit subkeys, organized as follows:
- 48 subkeys, from K1 through K48, used with the f-function in the left half;
- 32 subkeys, from K49 through K80, used to XOR with the left quarter of the left half of the block at the beginning and end of each round;
- 16 subkeys, from K81 through K96, used as input to the transformation of the first type applied to the left quarter of the left half of the block;
- 16 subkeys, from K97 through K112, used as input to the transformation of the second type applied to the left quarter of the left half of the block;
- 16 subkeys, from K113 through K128, used to XOR with the left quarter of the right half of the block at the beginning of each round;
- 16 subkeys, from K129 through K144, used to XOR with the left quarter of the right half of the block at the end of each round;
- 144 subkeys, from K145 through K288, serving as the first of four entries in each of nine subkey pools per round;
- 144 subkeys, from K289 through K432, serving as the second of four entries in each of nine subkey pools per round;
- 144 subkeys, from K433 through K576, serving as the third of four entries in each of nine subkey pools per round;
- 144 subkeys, from K577 through K720, serving as the fourth of four entries in each of nine subkey pools per round;
- One subkey, K721, which determines the order of transformations, and the use of XOR or byte-wide addition in the transformation of the first kind, for the left quarter of the left half of the block in each round.

The key, which must be a multiple of 32 bits in length, is expanded into four different strings of bytes as follows:

- The first string consists of the key, with the one's complement of the modulo 256 sum of all the bytes in the key appended.
- The second string consists of the bytes in the key in normal order, alternating with the one's complement of the bytes of the key in reverse order.
- The third string consists of the bytes of the key in normal order, alternating with consecutive numbers starting with 1, and with the bytes of the key in reverse order, except that the last byte this would produce (a copy of the first byte of the key) is omitted.
- The fourth string consists of the bytes of the first half of the key, alternating with the one's complement of the bytes of the second half of the key, alternating with consecutive numbers starting with 128, alternating with the one's complement of the bytes in the first half of the key in reverse order, but with the last byte this would produce omitted.

Thus, four strings of different length are produced, and the bytes of the key are distributed through these strings with different spacings. Also, no string can be all zeroes.

For example, given a key consisting of eight bytes with the values 1 2 3 4 5 6 7 8, the four strings will be

1 2 3 4 5 6 7 8 219 1 247 2 248 3 249 4 250 5 251 6 252 7 253 8 254 1 1 8 2 2 7 3 3 6 4 4 5 5 5 4 6 6 3 7 7 2 8 8 1 251 128 250 2 252 129 249 3 253 130 248 4 254 131

Each of these four strings is used to produce bytes by chain addition. A cycle of chain addition proceeds as follows: The modulo-256 sum of the first two bytes of the string is calculated. This value is the current output from the process. The string is modified by having its first byte removed, and the calculated sum appended to the end of the string.

A source of subkey bytes is set up as follows:

- 256 bytes are produced by chain addition from the first string. These fill 256-byte buffer 1. 256 bytes are produced by chain addition from the second string. These fill 256-byte buffer 2.
- When bytes are produced, the four strings, from first to fourth, will be
rotated between the designations of string A, B, C, and D in the following
pattern, which repeats for each four bytes generated:
- A: first, B: second, C: third, D: fourth
- A: second, B: first, C: third, D: fourth
- A: first, B: second, C: fourth, D: third
- A: second, B: first, C: fourth, D: third

- To produce a byte of subkey material, string B is subjected to chain addition, and the value it produces is used as an index into buffer 1. The value in buffer 1 at that point is removed, and called output X. String A is subjected to chain addition, and the value it produces replaces the value removed from buffer 1. (This is, of course, the classic MacLaren-Marsaglia technique.) Similarly, string D is subjected to chain addition, and the value it produces is used as an index into buffer 2. The value at this point is removed, and becomes output Y, and is replaced by the output from subjecting string C to chain addition.
- The XOR of outputs X and Y is used as the desired byte of subkey material.

At this point, the bytes of subkey material are subjected to a further
operation during *key revision*, to be described below.

The required subkey material is produced from this byte generator as follows:

- 1024 bytes are generated, to form the contents of S10 and S11.
- A permutation of the bytes from 0 to 255 is produced from generator output, in a fashion to be described below, and this permutation will be called P.
- 2884 bytes are generated, forming the 721 32-bit subkeys.
- Another permutation of the byte values from 0 to 255 is produced. This permutation is called Q. The S-box S8 can now be calculated, and satisfies the equation Q(S8(x)) = P(x). Thus, it is produced by applying the inverse of Q to P.
- Six groups of eight bytes are calculated. The first two bits of these
bytes are ignored; the last six bits are used to index into the 4 of 8 code
used with Quadibloc, and thus the masks M1 through M6 are formed. (The original
bytes used as input to the 4 of 8 code must be retained if a subsequent
*key revision*phase is to be performed.)

The first byte generated is always used to fill the leftmost byte of a multi-byte subkey.

Here is the 4 of 8 code used for producing the masks:

55 56 59 5A 65 66 69 6A 95 96 99 9A A5 A6 A9 AA 35 36 39 3A C5 C6 C9 CA 53 5C 63 6C 93 9C A3 AC 4D 4E 71 72 8D 8E B1 B2 17 1B 27 2B D4 D8 E4 E8 1D 1E 2D 2E D1 D2 E1 E2 47 4B 74 78 87 8B B4 B8

The basic procedure for generating a permutation, used to produce permutations P and Q from generator output, is, as used with Quadibloc II, the following:

- Begin with three arrays of 256 numbers, the first of which is filled with the numbers from 0 to 255 in order. The arrays must also be able to hold the value -1. The second and third arrays are filled with -1.
- For each of 256 bytes produced by the generator: let the value of the byte be called N, and let I be a counter which starts at 0 for the first byte, incrementing with each byte used, and ending at 255.
- Then, for each byte:
- If element N of the first array is not -1, set element N of the first array to -1, and set element I of the second array to N.
- Otherwise, store N in the first unused position (the first position containing -1) in the third array.

- Once this has been done, if the third array contains any numbers other than -1, proceed as follows:
- If there is only one filled (not equal to -1) element in the third array, then there is only one remaining element in the first array, and one element of the second array equal to -1, so fill the second array with the one available byte, and finish.
- If there are only two filled elements in the third array, take the least significant bit of the first filled element. If it is zero, fill the -1 elements of the second array with the remaining elements of the first array in order; if it is one, do so in reverse order, and finish.
- If there are less than 256 filled elements in the third array, repeat them over and over to fill the array. Then, generate an additional 256 bytes (thus, 512 bytes are used except when the first 256 bytes contain two or fewer duplicate bytes) and XOR them with the bytes of the third array.
- Now, use the third array to complete the second array by doing the
following for II from 0 to 255:
- Let the value of element II of the third array be XX.
- Swap elements II and XX of the first array.

- Then, scan through the second array. When an element of the second array is -1, fill it with the corresponding element of the first array (if it is not also -1) and set that element of the first array to -1.
- If there are any -1 elements left in the second array, fill them with the elements of the first array that are not -1 in order.

Whether the procedure finishes after 256 bytes, or after 512 bytes, from the generator are used, the contents of the second array when the procedure is concluded are the permutation produced.

There are ten intermediate results within a round that can be used for key augmentation. These are:

- The left quarter of the left half of the block, after being subjected to the first of the two possible alternate operations, and as serves as the input to the f-function;
- The intermediate result of the left half f-function after the first S-P layer, and before the XOR of the second subkey input to the f-function;
- The intermediate result of the left half f-function after the second S-P layer, and before the XOR of the thirs subkey input to the f-function;
- The left half f-function output;
- The right quarter of the left half of the block, after being subjected to the first of the two possible alternate operations, and before being XORed with the f-function output;
- The left quarter of the right half of the block, after being subjected to the first of the two possible alternate operations, and as serves as the input to the f-function;
- The intermediate result of the right half f-function after the first S-P layer, and before the XOR of the second subkey input to the f-function;
- The intermediate result of the right half f-function after the second S-P layer, and before the XOR of the thirs subkey input to the f-function;
- The right half f-function output;
- The right quarter of the right half of the block, after being subjected to the first of the two possible alternate operations, and before being XORed with the f-function output;

After a key is set up using the key schedule as previously described, the 721 32-bit subkeys can be modified through key augmentation steps.

A key augmentation step consists of the following:

With the subkey array in whatever state is to be subjected to augmentation:

Encrypt the 128-bit block

00FF0F0F333355550123456789ABCDEF

using Quadibloc VIII, normally, but during each round retain the ten intermediate results listed above. After the round is concluded, XOR the ten intermediate results, in the order given, with ten successive subkeys, starting with subkey K145 in the first round. Thus, the ten intermediate results from the first round are XORed with subkeys K145 through K154, the ten intermediate results from the second round are XORed with subkeys K155 through K164, and so on.

After the block encryption is complete, move the subkeys backwards 160 positions in the list of subkeys. Thus, the former subkeys K1 through K160 become subkeys K562 through K721; the former subkeys K161 through K721 become subkeys K1 through K561.

Although five key augmentation steps are required to modify all the subkeys, a single key augmentation step ensures that subkeys K1 through K144, as well as K721, are among the 160 subkeys modified by being XORed with intermediate results, these subkeys being the most critical, as they are the ones not contained in a group of four subkeys, any one of which may be used in a given encipherment.

Quadibloc VIII with one key augmentation step is to be called Quadibloc VIII A1, and with five key augmentations steps, the other standard number, Quadibloc VIII A5.

With 721 regular subkeys, including the 1024 bytes contained in the two key-dependent S-boxes S10 and S11, which are the equivalent of 256 additional subkeys, in what is modified by key augmentation is not, in fact, impractical.

A modified key augmentation step proceeds exactly as a regular key augmentation step, except that the buffer moved backwards by 160 subkeys now consists of the 721 subkeys K1 through K721 followed by the 256 entries in S-box S10, where each consecutive pair of entries forms a subkey, the earliest entry being leftmost, followed by the 256 entries in S-box S11 in the same form.

Seven key augmentation steps are now required to modify all the subkey material now exposed to change, and this leads to the variant of Quadibloc VIII to be called Quadibloc VIII M7. (Alternating regular and modified key augmentation rounds is possible; any pattern of the form aMMaaaaa where M is a modified key augmentation round, and a is either regular or modified key augmentation, will result in all the subkey material being fully modified.)

Also, Quadibloc VIII M3 is sufficient to modify the fixed subkeys K1 through K144, the subkey K721, and all of S10 and S11. (Again, Quadibloc VII A M2 would suffice for this as well.)

Because modifying the other portions of subkey material is not simple
enough to be done during a process such as key augmentation, a further process
of subkey modification is provided, called *key revision*. A key
revision step, which is optional, may only be performed immediately following
a key augmentation step. The 128-bit output from the block encipherment
performed to provide a key, which is then used as input to a slightly modified
version of the normal initial key generation process for Quadibloc VIII.

The key used as input for the modified key generation process is the following:

- For the first key revision step, the key is the 160-bit quantity consisting of the 128-bit block cipher output from the immediately preceding key augmentation step, followed by its first (leftmost) 32 bits repeated, unless the original key was 160 bits long, in which case the 128-bit block cipher output is used without being lengthened;
- For the second key revision step, the key is the 192-bit quantity consisting of the 128-bit block cipher output from the immediately preceding key augmentation step, followed by its first (leftmost) 64 bits repeated, unless the original key was 192 bits long, in which case the 128-bit block cipher output is used without being lengthened;
- For the third key revision step, the key is the 224-bit quantity consisting of the 128-bit block cipher output from the immediately preceding key augmentation step, followed by its first (leftmost) 96 bits repeated, unless the original key was 224 bits long, in which case the 128-bit block cipher output is used without being lengthened;
- For the fourth key revision step, the key is the 256-bit quantity consisting of two repetitions of the 128-bit block cipher output from the immediately preceding key augmentation step, unless the original key was 256 bits long, in which case the 128-bit block cipher output is used without being lengthened;
- For the fifth key revision step, the key is the 288-bit quantity consisting of two repetitions of the 128-bit block cipher output from the immediately preceding key augmentation step, followed by its first (leftmost) 32 bits repeated, unless the original key was 288 bits long, in which case the 128-bit block cipher output is used without being lengthened;

and so on. This ensures that, if multiple key revision steps are performed, each key revision step uses a key which is different in length both from the original key and from the key used in all other key revision steps.

With this key, the procedure for initial Quadibloc VIII is followed, except for these changes:

Since a value for the S-box S8 now exists, the bytes generated by the subkey byte generator are additionally subjected to the following encipherment step before being used, and the bytes being used begin with that corresponding to the third byte of output from the original subkey byte generator:

For each byte of output from the original subkey byte generator, the preceding two bytes of output are enciphered using a two-round Feistel cipher which uses S8 as the f-function. First, a counter, initialized at 1 and incrementing by 1 is is XORed with the eldest byte, the result being used to index into S8, and the value found in S8 is XORed with the immediately preceding byte, modifying it. Then, a counter, initialized at 0 and incrementing by 1, except that the value 255 is skipped, is XORed with the immediately preceding byte, as modified, and the result is used to index into S8, and the value found in S8 is XORed with the eldest byte, modifying it.

The current byte is then used to produce the byte to be used in subkey generation as follows:

- It is replaced by its substitute from S8.
- The modified eldest byte is added to it, modulo 256.
- It is replaced by its substitute from S8.
- The modified immediately preceding byte is added to it, modulo 256.
- It is replaced by its substitute from S8.

This is as illustrated below:

Thus, the keystream is enciphered in essentially a simple form of CFB mode, except that the block cipher used is really a stream cipher, since its subkeys are continually changing.

The subkey bytes thus generated are used to modify the existing key schedule, instead of to replace it, as follows:

- The first 1024 bytes generated are XORed with the contents of S10 and S11.
- A permutation called P is again produced from generator output.
- The next 2884 bytes generated are XORed with the bytes of the 721 32-bit subkeys.
- A permutation called Q is again produced from generator output.
- Six groups of eight bytes are calculated. These are XORed with the raw mask value, before 4 of 8 coding, left by either the original key schedule or by the previous key revision step, and then subjected to 4 of 8 coding to provide the six 64-bit mask values M1 through M6.
- The permutations P and Q are then used to produce the new S8 permutation, S8'(x), from the previous one, S8(x), such that the following equation is true: S8'(Q(x))=S8(P(x)). This can be done as follows: for each byte x from 0 to 255, use x as an index into P; use the result as an index into S8; store the result in the location within S8' found by using x as an index into Q.

Quadibloc VIII with one key augmentation step, followed by one key revision step, is to be called Quadibloc VIII A1 R; Quadibloc VIII with seven modified key augmentation steps, the last of which is followed by a key revision step, is to be called Quadibloc VIII M7 R; Quadibloc VIII with seven modified key augmentation steps, each of which is followed by a key revision step, is to be called Quadibloc VIII MR7. Quadibloc VIII with five key augmentation steps, the last of which is followed by a key revision step, is to be called Quadibloc VIII A5 R; Quadibloc VIII with five key augmentation steps, each of which is followed by a key revision step, is to be called Quadibloc VIII AR5.

The key schedule of Quadibloc VIII A1 R should be entirely satisfactory; the more lengthy variants should not be required for security, although Quadibloc VIII M7 R has, at least, the argument in its favor that its key schedule tends towards that of Blowfish (which, of course, however, used only the result of a complete encipherment to modify subkeys, rather than intermediate results within each round).

[Next] [Up] [Previous] [Index]

Next

Start of Section

Skip to Next Chapter

Table of Contents

Main Page