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

Quadibloc VI attempts to achieve the attractive characteristics of Quadibloc III, but with fewer rounds. The main intention in the design of Quadibloc VI is to make a block cipher that has the advantages of a stream cipher.

A typical block cipher subjects each block of data it enciphers to a series of manipulations, with the only variation in these manipulations due to the variable and secret key being that the data, while being manipulated, occasionally has subkey material XORed to it. Perhaps addition will also be used.

A stream cipher can resist analysis by applying different key material to the encipherment of each byte or block it encounters.

Thus, the Mishmash encipherment method used within Quadibloc III imitates a stream cipher, by choosing subkeys from a pool to encipher one half of a block, the choice being determined by the other half of the block. This principle is employed here as well, but with a simpler structure.

Quadibloc VI uses the same fixed S-boxes S1 and S2 derived from Euler's constant as QUADIBLOC and other ciphers in the Quadibloc series, whose contents have been listed in previous sections.

### Description of Mixing/Whitening

The first step in encipherment, when a 128-bit block is submitted to Quadibloc VI, is to ensure that every bit in the block affects, or potentially affects, every bit in every other block, through a short series of mixing and whitening transformations, as shown in the diagram below: First, the bytes, by pairs, go through four mini-Feistel rounds, using the key-dependent S-box S8 as the f-function.

Then, using 64-bit subkey LK1, the two halves of the block have selected corresponding bits swapped, in the manner originated by the block cipher ICE.

Then, to bring bytes that have not yet influenced each other into contact, the bytes are transposed so that after transposition, the bytes in order came from the following positions, from 1 to 16, as indicated by the numbers below:

``` 1 13  2 14  3 15  4 16  5  9  6 10  7 11 8 12
```

Once this is done, another four mini-Feistel rounds with the key-dependent S-box S8 used as the f-function are performed on adjacent pairs of bytes.

Then, once again bytes are moved to bring bytes that had not affected one another into contact. As a possible transposition to do so here is the one used previously, it is applied once again.

Then, a completely unkeyed step is used for the final merging of bytes, a set of Pseudo-Hadamard Transforms applied to pairs of bytes.

Finally, the bytes in the block are transposed according to a key-dependent byte transposition derived from the contents of key-dependent S-box S8.

### Description of Regular Rounds

In a regular round of Quadibloc VI, the leftmost six bytes of the block are enciphered by means of two rounds of the GoodStuff method, which proceeds as follows:

Using four eight-bit subkeys (derived from a single 32-bit subkey), four Feistel rounds are used to encipher a 16-bit subblock; in the first round, the right half is XORed with the first subkey, then replaced through S8, then added to the left half. The direction of the f-function alternates from right to left to left to right, and in the two outer rounds, the subkey is XORed and the f-function output added, and in the two inner rounds, the subkey is added and the f-function output XORed.

The four intermediate results of the f-functions, derived before S8 substitution, are used to index into the fixed S-box S2. The S-box outputs are used to form a 32-bit word consisting of the first nibbles of the four substituted results in order, then the second nibbles. (Since, looking sideways, the bottom, rather than the top, of the previous four rounds are to the left, the diagram shows that the order needs to be reversed when drawing a left-to-right round of this cipher, by means of a twist upon entry and exit from the horizontal Feistel rounds.)

The resulting 32-bit word is then itself enciphered by four Feistel rounds of a cipher which, like Blowfish, uses wide key-dependent S-boxes in the f-function. Here, four 16-bit subkeys are used, and so they are derived from two 32-bit regular subkeys.

The final interchange is not omitted, or the rounds can be thought of, as they are drawn, in in-place format, and the first round goes from right to left (or, in the diagram, top to bottom).

The following diagram illustrates the operations that take place during a regular round of Quadibloc VI upon the leftmost eight bytes of the block: The first six bytes are subjected to encipherment according to the GoodStuff algorithm, first in one direction, and then in another.

The final f-function outputs in the Feistel rounds applied to the 32 bit quantity that serves as subkeys for the 16-bit Feistel rounds in each of the GoodStuff encipherments are XORed to the last two of the first eight bytes. Before, between, and after these XORs, those two bytes are modified using the same type of mini-Feistel round as was used in the initial mixing/whitening phase.

Note that the first and last f-function (or S-box S8) outputs are XORed together to produce one byte of output.

This byte is used to control the encipherment of the other half of the block, which is enciphered using the modification of the original QUADIBLOC round used in Quadibloc S, to be described in the next section. A Quadibloc S round is illustrated below: The single byte of output has 256 possible values. 7 times 6 times 5 is 210, which is less than 256, therefore this byte can be used to choose three distinct subkeys from a pool of seven subkeys to be used as the three subkeys for the Quadibloc S round.

After the first three regular Quadibloc IV rounds in a group of four, the bytes are interchanged according to the following pattern, where each number denotes the position of a byte in the source to the permutation, the numbers being in the order of the bytes upon] output:

``` 3  4  5  6  7  8  1  2 13 14 15 16  9 10 11 12
```

The intent of this is to have the two bytes in the first half which are enciphered differently take on four different values, while the halves of the second half are swapped each time.

After every group of four regular Quadibloc IV rounds except the last four, the halves of the block are swapped.

It is assumed that a mere eight rounds of Quadibloc IV will suffice. At least sixteen rounds, however, would be absolutely required were it not for the initial mixing and whitening rounds. This is because four rounds are, in a sense, really only one round.

Finally, using 64-bit subkey LK2, the operations of the mixing/whitening rounds are performed in reverse order. The Pseudo-Hadamard Transform is replaced by its inverse, and so are the two fixed byte permutations. But the groups of four mini-Feistel rounds stay the same (instead of being inversed by having left and right bytes switched), and the ICE-style swap is its own inverse.

The steps involved in the final mixing/whitening step may be made clearer by this diagram: ### The Key Schedule

Although, when compared with the method for generating the key schedule for Quadibloc II and Quadibloc III, many shortcuts are taken in the method used for Quadibloc VI, it will be seen that key generation for Quadibloc VI is still long and complicated.

Quadibloc VI with eight regular rounds uses the following subkey material:

• Eighty 32-bit subkeys, designated K1 through K80, ten of which are used for each regular round which contains two rounds of GoodStuff encipherment;
• Eight banks of seven 32-bit subkeys used in the Quadibloc S type rounds which are applied to the right half of the block, which may be designated V1 through V56;
• The key-dependent S-boxes S10 and S11, each of which contains 256 random 16-bit entries;
• Two 64-bit subkeys, LK1 and LK2;
• The key-dependent S-box S8, which contains the bytes 0 to 255 in random order;
• A key-dependent table with 256 entries, each entry being a triple of three distinct integers from 1 to 7, which will contain all 210 possible arrangements once, and 46 of those arrangements twice, for use in selecting subkeys from the subkey pool for the Quadibloc S type rounds applied to the right half of the block.

For what follows, the first three items in the list above are to be considered to be stored in order contiguously in memory.

First, initially fill the key-dependent S-box S11 as follows:

```<key> 1 <key> 1 2 <key> 1 2 3 <key>
```

that is, repeat the key, following it each time by a series of bytes with successive values that is one byte longer.

Then generate initial values for subkeys K1 through K80, pooled subkeys V1 through V56, and the contents of key-dependent S-box S10 (as well as an initial value for key-dependent S-box S8) by generating 1056 bytes

```( (80*4) + (56*4) + (256*2) =
320 +    224 +     512 = 1056 )
```

through the following procedure: take a copy of the key, and appended to that copy, after its last byte, is a byte equal to the inverse, the bitwise negation, or one's complement, of the XOR of all the bytes of the original key. This ensures the key as expanded does not consist entirely of zeroes.

Bytes are then generated from the key by chain addition. This means that a byte is generated as follows: the sum, modulo 256, of the first two bytes of the key is the generated result; and it is also appended to the end of the key, whose first byte is then removed. (Note that the cipher itself uses XOR only, and not addition modulo 256.)

The method of producing subkey bytes is a degenerate form of the MacLaren-Marsaglia generator. An array with 256 byte positions, called A(0) to A(255), is filled by generating 256 bytes by means of chain addition.

Then, a subkey byte is generated as follows:

Generate two bytes by chain addition. Call these bytes p and q.

The byte to be used in a subkey is the current value of A(q).

Replace A(q) with p.

The initial value for the key-dependent S-box S8 is generated concurrently with subkey generation by means of the use of two additional arrays, B(0) to B(255) and C(0) to C(255).

These two arrays are initialized so that B(0) contains 0, B(1) contains 1, and so on, and C also contains the 255 byte values in order as well.

Then, each time a value is stored in a location of A, both the 256 initial values, and the value stored in A(q) each time a subkey byte is generated, the following procedure is performed:

Let p be the value being stored in the array A, and let q be the index in A of where it is being stored.

If B(q) equals p, then we are finished.

Otherwise:

Store the value of B(q) in v.

Swap element q and element C(p) of array B. (Element C(p) of array B will equal p.)

Store the value of C(p) in w.

Store q in C(p) (since B(q) now has p stored in it), and store w in C(v) (since our swap placed v, the former value of B(q), in B(w) which originally contained p).

Once all the subkeys are generated, starting from the first (most significant) byte of subkey 1, and ending with the last (least significant) byte of subkey 12, the contents of the array B are used as the key-dependent S-box.

Once these portions of the required subkey material have inital values assigned to them (LK1 and LK2, as well as the table used to choose subkey pool values for the Quadibloc S part of a round are still empty), we will encipher the contents of S-box S11 as follows:

Four entries in S-box S11, or eight bytes, will be enciphered at a time. Using the initial values of S8 and S10, and the value of S11 upon entry to the encipherment of four more entries in it, the encipherment of the right half of the block during a regular Quadibloc VI round will be performed, with the following subkeys:

```Subkey material       Entries in S11
used                  enciphered

K1 to K10             S11(0) to S11(3)
K11 to K20            S11(4) to S11(7)
...
K71 to K80            S11(28) to S11(31)
V1 to V10             S11(32) to S11(35)
...
V41 to V50            S11(48) to S11(51)
V51 to V56,
S10(0) to S10(7)      S11(52) to S11(55)
S10(8) to S10(27)     S11(56) to S11(59)
S10(28) to S10(47)    S11(60) to S11(63)
...
S10(108) to S10(127)  S11(76) to S11(79)
```

After the first encipherment, the entries in S11 to be enciphered will first be XORed with the result of the previous encipherment, after that result has been rotated left by two bytes.

Then, the first 80 (16-bit) entries in S11 are swapped with the first 40 (32-bit) subkeys for GoodStuff encipherment.

Starting with the first byte in K41, and continuing to the last byte in S11(255), each byte in this contiguous array of subkey material except for the first 40 GoodStuff subkeys is now modified as follows:

```New Byte(n) = Old Byte(n) XOR
Byte(n-1) XOR
S8( Byte(n-158) + Byte(n-160) )
```

Next, the second 80 entries in S11 are enciphered, S11(80) through S11(159), two at a time, using the left half of a regular Quadibloc VI round as above, once again using the subkeys in the order above for the encipherment, starting with subkeys K1 through K10, and are swapped after encipherment with the second group of 40 subkeys for GoodStuff encipherment.

Once again, after the first encipherment in this group of encipherments, the entries in S11 to be enciphered will first be XORed with the result of the previous encipherment, after that result has been rotated left by two bytes.

Then, the last 112 entries in S11, S11(144) through S11(255), are enciphered by the same method, and are afterwards swapped with V1 through V56. This time, the subkey material used will extend into the start of S11, as illustrated by the table below:

```Subkey material       Entries in S11
used                  enciphered

K1 to K10             S11(144) to S11(147)
K11 to K20            S11(148) to S11(151)
...
K71 to K80            S11(172) to S11(175)
V1 to V10             S11(176) to S11(179)
...
V41 to V50            S11(192) to S11(195)
V51 to V56,
S10(0) to S10(7)      S11(106) to S11(199)
S10(8) to S10(27)     S11(200) to S11(203)
S10(28) to S10(47)    S11(204) to S11(207)
...
S10(108) to S10(127)  S11(220) to S11(223)
...
S10(208) to S10(227)  S11(240) to S11(243)
S10(228) to S10(247)  S11(244) to S11(247)
S10(248) to S10(255),
S11(0) to S11(11)     S11(248) to S11(251)
S11(12) to S11(32)    S11(252) to S11(255)
```

And again, after the first encipherment in this final group of encipherments, the entries in S11 to be enciphered will first be XORed with the result of the previous encipherment, after that result has been rotated left by two bytes.

Starting with the first byte in S10(0), and continuing to the last byte in S11(255), the bytes in the array of subkey material are modified, possibly repeatedly, by the formula:

```New Byte(n) = Old Byte(n) XOR
Byte(n-1) XOR
S2( Byte(n-542) + Byte(n-544) )
```

where the values n-542 and n-544 begin, on the first pass, as pointing into K1 to K80, and then V1 to V56, but afterwards are confined to the area from the start of S10 to the end of S11. As this process is performed when the final value of S8 is produced, the fixed S-box S2 is now used.

The old value of Byte(n) is made available to other subkey generation processes, specifically the generation of the control table for Quadibloc S-type subkeys and of the final value of S8, and this process is repeated only as many times as these processes require input.

First, an array is filled with the first 46 numbers from 0 to 219 in the initial value of S8, followed by the numbers 0 to 219 in order.

Then, a permutation is produced from several blocks of 256 values generated as old Byte(n) values from the shift-register process above applied to the area from V1 to S11(255), utilizing the following procedure (as seen in Quadibloc II and Quadibloc III):

• Each permutation is generated by the use of either 512, or, under some rare circumstances, only 256, bytes.
• A permutation is generated as follows:
• 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 byte used: 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, take an additional 256 input 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.
• When this procedure is completed, the contents of the second array are the desired permutation.

Once the permutation is generated, replace every element in it as follows: if the value of that element is N, replace it with element N of the array filled, based on the initial value of S8, with numbers from 0 to 209, 46 of them twice.

These numbers from 0 to 209 then need to be converted to triples used for selecting subkeys from a group of seven subkeys in the V1 to V56 group. The numbers from 0 to 34 will be considered to represent triples of distinct numbers in ascending order in numerical order:

```  0  1 2 3    7  1 3 6   14  1 6 7   21  2 4 7   28  3 5 6
1  1 2 4    8  1 3 7   15  2 3 4   22  2 5 6   29  3 5 7
2  1 2 5    9  1 4 5   16  2 3 5   23  2 5 7   30  3 6 7
3  1 2 6   10  1 4 6   17  2 3 6   24  2 6 7   31  4 5 6
4  1 2 7   11  1 4 7   18  2 3 7   25  3 4 5   32  4 5 7
5  1 3 4   12  1 5 6   19  2 4 5   26  3 4 6   33  4 6 7
6  1 3 5   13  1 5 7   20  2 4 6   27  3 4 7   34  5 6 7
```

and then this sequence is repeated but with the three elements in each of the other five of the six possible orders to make all 210 combinations:

```  0  1 2 3    1  1 2 4  ...  34  5 6 7
35  1 3 2   36  1 4 2  ...  69  5 7 6
70  2 1 3   71  2 1 4  ... 104  6 5 7
105  2 3 1  106  2 4 1  ... 139  6 7 5
140  3 1 2  141  4 1 2  ... 174  7 5 6
175  3 2 1  176  4 2 1  ... 209  7 6 5
```

Now, generate another permutation by the method above. Then, the final value of S8 is produced as follows: for i from 0 to 255, let N equal element i of the old value of S8, and set element N of the final value of S8 (stored in another array) to be element i of this permutation.

Finally, using our shift register method as applied to V1 through S11(255), acquire sixteen more bytes by replacing their old values with new ones; the old values taken will be LK1 and LK2.

The key-dependent byte permutations used between the mixing/whitening rounds and the regular rounds are generated as follows:

The one performed after the first mixing/whitening round is obtained by taking the bytes in the final form of S-box S8 of the form 0x, and using their least significant nibbles to indicate which position each byte of the block will be moved to. This is the dispatch form of the permutation, which is the opposite of the one used to describe bit and byte transpositions in the description of the Quadibloc ciphers. The one performed after the regular rounds is generated from the bytes of the form 8x, but is in fetch form, the least significant nibble of each of these bytes indicating the source from which each byte of the result is obtained.

Key generation is now complete.

Although Quadibloc VI would absolutely need sixteen rounds if the mixing/whitening stages were absent, that does not mean that sixteen rounds are not a good idea in any case. With sixteen rounds, the required key material consists of:

• One hundred and sixty 32-bit subkeys, designated K1 through K160, ten of which are used for each regular round which contains two rounds of GoodStuff encipherment;
• Sixteen banks of seven 32-bit subkeys used in the Quadibloc S type rounds which are applied to the right half of the block, which may be designated V1 through V112;
• The key-dependent S-boxes S10 and S11, each of which contains 256 random 16-bit entries;
• Two 64-bit subkeys, LK1 and LK2;
• The key-dependent S-box S8, which contains the bytes 0 to 255 in random order;
• A key-dependent table with 256 entries, each entry being a triple of three distinct integers from 1 to 7, which will contain all 210 possible arrangements once, and 46 of those arrangements twice, for use in selecting subkeys from the subkey pool for the Quadibloc S type rounds applied to the right half of the block.

The key generation process closely parallels that for eight rounds, with small changes as follows:

Once again, we begin by filling the key-dependent S-box S11 as follows:

```<key> 1 <key> 1 2 <key> 1 2 3 <key>
```

that is, repeat the key, following it each time by a series of bytes with successive values that is one byte longer.

Then generate initial values for subkeys K1 through K160, pooled subkeys V1 through V112, and the contents of key-dependent S-box S10 (as well as an initial value for key-dependent S-box S8) by generating 1376 bytes

```( (160*4) + (112*4) + (256*2) =
640 +     224 +     512 = 1376 )
```

through the degenerate MacLaren-Marsaglia procedure from Quadibloc S, and the permutation generated as its side effect is the initial value for S-box S8.

Once these portions of the required subkey material have inital values assigned to them (LK1 and LK2, as well as the table used to choose subkey pool values for the Quadibloc S part of a round are still empty), we will encipher the contents of S-box S11 as follows:

Four entries in S-box S11, or eight bytes, will be enciphered at a time. Using the initial values of S8 and S10, and the value of S11 upon entry to the encipherment of four more entries in it, the encipherment of the right half of the block during a regular Quadibloc VI round will be performed, with the following subkeys:

```Subkey material       Entries in S11
used                  enciphered

K1 to K10             S11(0) to S11(3)
K11 to K20            S11(4) to S11(7)
...
K151 to K160          S11(60) to S11(63)
V1 to V10             S11(64) to S11(67)
...
V101 to V110          S11(104) to S11(107)
V111 to V112,
S10(0) to S10(15)     S11(108) to S11(111)
S10(16) to S10(35)    S11(112) to S11(115)
S10(36) to S10(55)    S11(116) to S11(119)
...
S10(236) to S10(255)  S11(156) to S11(159)
```

After the first encipherment, the entries in S11 to be enciphered will first be XORed with the result of the previous encipherment, after that result has been rotated left by two bytes.

Then, the first 160 (16-bit) entries in S11 are swapped with the first 80 (32-bit) subkeys for GoodStuff encipherment.

Starting with the first byte in K81, and continuing to the last byte in S11(255), each byte in this contiguous array of subkey material except for the first 80 GoodStuff subkeys is now modified as follows:

```New Byte(n) = Old Byte(n) XOR
Byte(n-1) XOR
S8( Byte(n-318) + Byte(n-320) )
```

Next, entries S11(80) through S11(240) in S11 are enciphered, two at a time, using the left half of a regular Quadibloc VI round as above, once again using the subkeys in the order above for the encipherment, starting with subkeys K1 through K10, and are swapped after encipherment with the second group of 80 subkeys for GoodStuff encipherment.

Once again, after the first encipherment in this group of encipherments, the entries in S11 to be enciphered will first be XORed with the result of the previous encipherment, after that result has been rotated left by two bytes.

Then, the last 224 entries in S11, S11(32) through S11(255), are enciphered by the same method, and are afterwards swapped with V1 through V112. This time, the subkey material used will extend into the start of S11, as illustrated by the table below:

```Subkey material       Entries in S11
used                  enciphered

K1 to K10             S11(32) to S11(35)
K11 to K20            S11(36) to S11(39)
...
K151 to K160          S11(92) to S11(95)
V1 to V10             S11(96) to S11(99)
...
V101 to V110          S11(136) to S11(139)
V111 to V112,
S10(0) to S10(15)     S11(140) to S11(143)
S10(16) to S10(35)    S11(144) to S11(147)
S10(36) to S10(55)    S11(148) to S11(151)
...
S10(216) to S10(235)  S11(184) to S11(187)
S10(236) to S10(255)  S11(188) to S11(191)
S11(0) to S11(19)     S11(192) to S11(195)
...
S11(200) to S11(219)  S11(232) to S11(235)
```

At this point, the subkey material required has caught up with the bytes we are attempting to encipher, and so we return to the beginning of the available subkey material, as follows:

```Subkey material       Entries in S11
used                  enciphered

K6 to K15             S11(236) to S11(239)
K16 to K25            S11(240) to S11(244)
...
K46 to K55            S11(252) to S11(255)
```

And again, after the first encipherment in this final group of encipherments, the entries in S11 to be enciphered will first be XORed with the result of the previous encipherment, after that result has been rotated left by two bytes.

Starting with the first byte in S10(0), and continuing to the last byte in S11(255), the bytes in the array of subkey material are modified, possibly repeatedly, by the formula:

```New Byte(n) = Old Byte(n) XOR
Byte(n-1) XOR
S2( Byte(n-862) + Byte(n-864) )
```

where the values n-862 and n-864 begin, on the first pass, as pointing into K1 to K160, and then V1 to V112, but afterwards are confined to the area from the start of S10 to the end of S11. As this process is performed when the final value of S8 is produced, the fixed S-box S2 is now used.

The old value of Byte(n) is made available to other subkey generation processes, specifically the generation of the control table for Quadibloc S-type subkeys and of the final value of S8, and this process is repeated only as many times as these processes require input.

First, an array is filled with the first 46 numbers from 0 to 219 in the initial value of S8, followed by the numbers 0 to 219 in order.

Then, a permutation is produced from several blocks of 256 values generated as old Byte(n) values from the shift-register process above applied to the area from V1 to S11(255), utilizing the procedure for generating permutations from Quadibloc II and Quadibloc III.

Once the permutation is generated, replace every element in it as follows: if the value of that element is N, replace it with element N of the array filled, based on the initial value of S8, with numbers from 0 to 209, 46 of them twice.

These numbers from 0 to 209 then need to be converted to triples used for selecting subkeys from a group of seven subkeys in the V1 to V56 group.

Now, generate another permutation by the method above. Then, the final value of S8 is produced as follows: for i from 0 to 255, let N equal element i of the old value of S8, and set element N of the final value of S8 (stored in another array) to be element i of this permutation.

Finally, using our shift register method as applied to V1 through S11(255), acquire sixteen more bytes by replacing their old values with new ones; the old values taken will be LK1 and LK2.

And hence ends key generation for Quadibloc VI with sixteen rounds.

### Revised Key Generation

The method used for generating subkeys for Quadibloc XI may be applied to this cipher as well. As this cipher uses fixed S-boxes S1 and S2 only, S3 may be used in key generation exactly as it was in Quadibloc XI. First K1 through K80 are generated in numerical order, and then V1 through V56 in order. Then, the key-dependent permutation S8 is generated using the permutation-generation method, and the bytes of the entries of the key-dependent S-box S10 are generated directly. Then, the permutation used to produce a table containing 256 numbers from 0 to 209, in the manner otherwise described above (apply the permutation to a table containing the first 46 numbers from 0 to 209 in S8, followed by the numbers 0 through 209 in order) is generated, again using the permutation-generation method described below, and then the bytes of S-box S11 are generated.

For this method of subkey generation, the key must be a multiple of four bytes in length.

### Initialization

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 sum, modulo 255, of the bytes of the key, incremented by one by normal addition. (Thus, this produces a number from 1 to 255.)
• The XOR of all the bytes at odd numbered positions in the key, where the first byte in the key is considered to be byte 1, and odd.
• The one's complement of the XOR of all the bytes at even numbered positions in the key.

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:

• The second byte read is used to select an entry in S-box S3, and the value of this entry is XORed to the first byte. Then the first byte is used to select an entry in S-box S3, and the value of this entry is XORed to the second byte.
• The fourth byte read is used to select an entry in S-box S3, and the value of this entry is XORed to the third byte. Then the third byte is used to select an entry in S-box S3, and the value of this entry is XORed to the fourth byte.
• The first and second bytes, as modified, are added together using modulo-256 addition to form a first result.
• The third and fourth bytes, as modified, are added together using modulo 256 addition to form a second result.
• The second result is used to select an entry in S-box S3, and the value of this entry is XORed to the first result. Then the first result is used to select an entry in S-box S3, and the value of this entry is XORed to the second result.
• The two results as modified are added together using modulo 256 addition to form a third result.
• The fifth byte read, which is always the last byte in the shift register, is XORed with the third result. The resulting value is output as the byte produced by operating the shift register.
• The values in the shift register are modified by removing the last byte, advancing the bytes in the shift register to the next later position, and appending the output result as the new first byte of the shift register contents.

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.

### Subkey Byte Generation

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:

• A byte is generated from the first string by the nonlinear shift register operation.
• The byte at the position in buffer A indicated by this value is taken, and called P.
• A byte is generated from the third string by the nonlinear shift register operation. In the case of the third string, the shift register operation involves reading the following five bytes: the twelfth, tenth, seventh, and fourth last bytes, and the last byte. The value of the byte thus produced is placed in buffer A, replacing the value taken.
• A byte is generated from the second string by the nonlinear shift register operation.
• The byte at the position in buffer B indicated by this value is taken, and called Q.
• A byte is generated from the third string by the nonlinear shift register operation. Its value is placed in buffer B, replacing the value taken.
• The subkey byte generated is the XOR of P and Q and an additional byte generated from the third string by the nonlinear shift register operation. (The use of an additional byte from the third string ensures that all the bytes of the key particpate directly in the key schedule; otherwise, some could be skipped over in a sense by the selection of bytes to use from the buffers.)

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.

### Permutation Generation

After the 32-bit subkey words K1 through K80, and the subkey pool values V1 through V56 are generated, the key-dependent S-box S8 is generated. To generate this bijective S-box, the following procedure is used:

• 256 bytes are generated following the same procedure as for subkey byte generation, and these bytes are placed in a 256-byte buffer called buffer C.
• A 256-byte buffer called buffer D is filled with the numbers from 0 to 255 in order.
• For every i from 0 to 255, if element i of buffer C (hereinafter called C(i)) is not equal to i, swap elements i and C(i) of buffer D.
• For every i from 0 to 255, if B(i) is not equal to i, swap elements i and B(i) of buffer D.
• For every i from 0 to 255, if A(i) is not equal to i, swap elements i and A(i) of buffer D.

The resulting contents of buffer D are used as the key-dependent bijective S-box intended to be produced.

This procedure, although it uses buffers A and B, leaves them undisturbed; thus, byte generation may continue after one S-box is produced.

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