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

The Key Schedule

The key material used by Quadibloc VIII consists of:

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

  1. 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.
  2. 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.
  3. 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.
  4. 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:

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:

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:

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.

Key Augmentation

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

  1. 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;
  2. 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;
  3. 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;
  4. The left half f-function output;
  5. 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;
  6. 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;
  7. 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;
  8. 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;
  9. The right half f-function output;
  10. 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.

Modified Key Augmentation

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.)

Key Revision

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:

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:

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:

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