Quadibloc III includes the round structure of SKIPJACK as a component. The cipher SKIPJACK may be protected by patents, preventing this cipher from being generally available for use in its present form. (Quadibloc III was designed some time after the SKIPJACK algorithm had been declassified, and it is of course from the publication of that algorithm following that event that I learned its inner workings.) |

Quadibloc III is an extension of Quadibloc II which uses a different type of block cipher as its inner core. It too uses a 128-bit block size. Unlike Quadibloc II, which, at least with only eight full rounds, is not too much slower than a typical AES candidate (although it isn't fully clear to me if eight rounds is enough for security), Quadibloc III, while secure, is clearly too slow and complicated to be useful for practical purposes. Its value is that it illustrates a number of concepts which may be useful in ciphers of a more practical size.

Here is a diagram giving an overview of the structure of Quadibloc III, to accompany a description of its rounds:

The steps in the cipher are symmetric, and they are as follows:

- Small Feistel rounds, using no subkeys, but using the key-dependent S-box S8 as their f-function, transforming 16-bit subkeys of the block.
- Key-dependent permutation (derived from the 0x elements of S8) of the bytes in the block.
- Four simple rounds, using a single-level f-function, that are aimed at obtaining high diffusion, and which use 32-bit subkeys K1 through K4.
- Key-dependent permutation (derived from the 1x elements of S8) of the bytes in the block.
- Eight normal Quadibloc II rounds, each of which uses nine subkeys, the first using subkeys K5 through K13, the last using subkeys K68 through K76.
- Key-dependent permutation (derived from the 2x elements of S8) of the bytes in the block.
- Two rounds of a form of Mishmash, whose large quantity of subkeys is generated after the contents of S10 and S11, and by the same process. These rounds use fixed Quadibloc subkeys for one half of the block, the subkeys being K77 through K88 for the encipherment of that block, and K89 through K100 for the f-functions applied to the intermediate f-function results, for the first Mishmash round, and K101 through K124 for the second Mishmash round.
- Key-dependent permutation (derived from the 3x elements of S8) of the bytes in the block.
- Sixteen rounds in which the block is enciphered as follows:
- one 16-bit subblock is enciphered by four Feistel rounds, using S8 as the f-function, but this time preceded by the XOR of a subkey byte;
- the results of the XOR are used as intermediate results, and are fed into the S-box S9.
- The four S9 outputs produce a 32-bit result whose first 16 bits are the first four bits of each of their outputs, and whose last 16 bits are the last four bits of each of their outputs.
- This result is then enciphered by means of four Feistel rounds, where the f-function consists of first XORing in a 16-bit half of a subkey, then using the two bytes of the result to index into two key-dependent S-boxes, S10 and S11, which each take an 8-bit input and give a 16-bit output. The sum of the two outputs is XORed with the other half of the 32-bit block.
- The 32-bit result of this process is used as a 32-bit subkey was used initially to encipher a further 16 bits of the block, and this continues until the entire 128-bit block has been enciphered in 16-bit pieces.

- Then, the preceding steps are done in reverse order, with the key-dependent byte permutations now being the inverses of the ones derived from the Bx, Ax, 9x, and 8x elements of S8, and with the two Mishmash rounds using subkeys K365 through K412, the eight normal Quadibloc II rounds using subkeys K413 through K484, and the set of four degenerate rounds using subkeys K485 through K488.

The following diagram illustrates the method used for the middle 16 rounds of Quadibloc III:

Using four eight-bit subkeys (derived from a single 32-bit subkey, to remain within the overall structure derived from Quadibloc II), 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 S9. 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).

If the first set of four Feistel rounds operating on a 16-bit subblock is denoted by 1, the second by 2, and angle brackets are used to show how one round provides the subkey input for the next, the pattern of rounds used in this phase is as follows:

1 > 2 > 3 > 4 > 5 > 6 > 7 > 8 < 7 < 6 < 5 < 4 < 3 < 2 < 1 8 < > 8 1 > 2 > 3 > 4 > 5 > 6 > 7 > 8 < 7 < 6 < 5 < 4 < 3 < 2 < 1 > 7 > 8 1 > 2 > 3 > 4 > 5 > 6 > < 1 8 < 7 < 6 < 5 < 4 < 3 < 2 < > 6 > 7 > 8 1 > 2 > 3 > 4 > 5 > < 2 < 1 8 < 7 < 6 < 5 < 4 < 3 < > 5 > 6 > 7 > 8 1 > 2 > 3 > 4 > < 3 < 2 < 1 8 < 7 < 6 < 5 < 4 < > 4 > 5 > 6 > 7 > 8 1 > 2 > 3 > < 4 < 3 < 2 < 1 8 < 7 < 6 < 5 < > 3 > 4 > 5 > 6 > 7 > 8 1 > 2 > < 5 < 4 < 3 < 2 < 1 8 < 7 < 6 < > 2 > 3 > 4 > 5 > 6 > 7 > 8 1 > < 6 < 5 < 4 < 3 < 2 < 1 8 < 7 <

The S-box S9 is fixed, and is generated by continuing the process used for generating S-boxes 1 through 7 from Euler's constant to generate one more permutation of the numbers 0 through 255, therefore this S-box is the one designated S11 on the page entitled Euler's Constant and the Quadibloc S-Boxes.

The concept of a cipher called Mishmash is noted in the conclusions section of this chapter, to which reference may be required.

The left half of the block (in the second round, the right half) is enciphered using four rounds of Quadibloc. The intermediate results, after XORing in the second of the three subkeys, of each of the four f-function outputs are then subjected to the Quadibloc f-function again, with another twelve subkeys, and the four 32-bit outputs are XORed together.

The 32-bit result controls the encipherment of the right half of the block. The right half of the block is enciphered by cipher steps 1 through 5. The first 25 bits of the 32-bit result is divided into five 5-bit values, indicating for each of the five cipher steps, in order of their numeric labels, which of 32 sets of subkey material is used for them.

The last 7 bits of the 32-bit result indicates the order in which the five cipher steps take place. Values 0 through 119 of these seven bits give the 120 permutations of the numbers from 1 through 5 in numerical order, as shown in the following table:

0 12345 24 21345 48 31245 72 41235 96 51234 1 12354 25 21354 49 31254 73 41253 97 51243 2 12435 26 21435 50 31425 74 41325 98 51324 3 12453 27 21453 51 31452 75 41352 99 51342 4 12534 28 21534 52 31524 76 41523 100 51423 5 12543 29 21543 53 31542 77 41532 101 51432 6 13245 30 23145 54 32145 78 42135 102 52134 7 13254 31 23154 55 32154 79 42153 103 52143 8 13425 32 23415 56 32415 80 42315 104 52314 9 13452 33 23451 57 32451 81 42351 105 52341 10 13524 34 23514 58 32514 82 42513 106 52413 11 13542 35 23541 59 32541 83 42531 107 52431 12 14235 36 24135 60 34125 84 43125 108 53124 13 14253 37 24153 61 34152 85 43152 109 53142 14 14325 38 24315 62 34215 86 43215 110 53214 15 14352 39 24351 63 34251 87 43251 111 53241 16 14523 40 24513 64 34512 88 43512 112 53412 17 14532 41 24531 65 34521 89 43521 113 53421 18 15234 42 25134 66 35124 90 45123 114 54123 19 15243 43 25143 67 35142 91 45132 115 54132 20 15324 44 25314 68 35214 92 45213 116 54213 21 15342 45 25341 69 35241 93 45231 117 54231 22 15423 46 25413 70 35412 94 45312 118 54312 23 15432 47 25431 71 35421 95 45321 119 54321

and the remaining values give the following eight preferred orders once again:

120 31425 121 32415 122 51423 123 52413 124 31524 125 32514 126 41523 127 42513

Only one pool of 32 subkey values is used by all four Mishmash rounds in the cipher (which is different from the Mishmash concept described in the conclusions section), despite the danger that a subkey may be used more than once.

The five cipher steps are:

- Two rounds of DES. Two 48-bit subkeys are the subkey material this uses.
- Two rounds of Quadibloc. Six 32-bit subkeys are the subkey material this uses.
- Four rounds of SKIPJACK. Sixteen 8-bit subkeys are the subkey material this uses.
- One round of SAFER. Two 64-bit subkeys are the subkey material this uses.
- Two rounds of GoodStuff. This consists of two rounds, similar to the middle rounds of this cipher, but acting on only four 16-bit subblocks each. The ordering of the operations is 1234 followed by 4321 (not 3214). This uses fourteen 32-bit subkeys as subkey material.

In the Mishmash rounds, the final interchange is not omitted after the
DES and Quadibloc rounds, since they are *part* of an ongoing
block cipher. This is true also of the Mishmash concept, as can be seen
from the diagrams, which show the ciphers in in-place form.

The four Skipjack rounds are type A in the first two Mishmash rounds in the cipher, and type B in the last two. In addition, the SAFER rounds in the last two Mishmash rounds are rounds of SAFER decryption instead of SAFER encryption, for the same reason.

Subkey generation for Quadibloc III follows the same general scheme as for Quadibloc II; initial subkeys are generated using a method similar to the one used in Quadibloc II, but somewhat more elaborate.

Fill A1, A2, and A3; B1, B2, B3, B4, and B5; and C1, C2, C3, C4, and C5 with the first thirteen bytes of the key in order. Initialize the variable Q to be zero.

Split the key into two pieces as follows, where L is the number of bytes in the key:

- If L is odd, the first piece consists of the first (L+1)/2 bytes of the key, the second piece is the remaining bytes of the key. Then increase each piece in length by one byte by appending the one's complement of the first byte in the piece to it.
- If L is an even number of the form 4n, the first piece consists of the first (L/2)+1 bytes of the key, the second piece is the remaining bytes of the key. Then increase each piece in length by two bytes by appending the one's complement of the first two bytes in the piece to it.
- If L is an even number of the form 4n+2, the first piece consists of the first (L/2)+2 bytes of the key, and the second piece is the remaining bytes of the key. Then increase each piece in length by two bytes by appending the one's complement of the first two bytes in the piece to it.

In the first case, the lengths of the two pieces of the key are two consecutive numbers, one even, and one odd. In the second case, the lengths of the two pieces of the key are two odd numbers, differing by two. In the third case, the lengths of the two pieces of the key are two odd numbers, differing by four. In all three cases, the lengths of the two pieces of the key are relatively prime, and uniquely identify the length of the original key.

Each group of bytes is then used as the initial contents of a shift register, which operates as follows:

The sum of the first and third bytes in the shift register is XORed with the second-last byte in the shift register. The result is used as the output of the shift register, and is also used as the new last byte in the shift register, all other bytes being moved to the next earlier place, the first byte being discarded.

For each byte generated by XORing the outputs from the two shift registers, that byte is then transformed by carrying out the following instructions:

For each of the numbers 0 to 4, do the following:

- Add the contents of A1 to the number, modulo 256.
- Replace that number by its substitute in S-box 5a (that is, the first half of S-box 5, an S-box with 8 bits of input as well as 8 bits of output, created by setting the MSB of the input to 0).
- Add the contents of A2 to the result, modulo 256.
- Replace that number by its substitute in S-box 5b (the second half of S-box 5).
- Add the contents of A3 to the result, modulo 256.

Modify the variables B1 through B5 by adding the results of this process for the numbers 0 to 4, respectively, to them. (This is a permanent change; for each byte generated, new values are added to them, and the totals are cumulative.)

Once that has been done, using the modified values of B1 through B5, we once again use the numbers 0 to 4 in order as inputs as we do the following:

- Add the contents of B1 to the number, modulo 256.
- Replace that number by its substitute in inverse S-box 7b (the inverse of the second half of S-box 7).
- XOR the result with the contents of B2.
- Replace that number by its substitute in inverse S-box 5b (the inverse of the second half of S-box 5).
- Add the contents of B3 to the result, modulo 256.
- Replace that number by its substitute in inverse S-box 7a (the inverse of the first half of S-box 7).
- XOR the result with the contents of B4.
- Replace that number by its substitute in inverse S-box 5a (the inverse of the first half of S-box 5).
- Add the contents of B5 to the result, modulo 256.

Modify the variables C1 through C5 by adding the results of this process for the numbers 0 to 4, respectively, to them. (This is a permanent change; for each byte generated, new values are added to them, and the totals are cumulative.)

Now, generate a byte from the two shift registers containing the two unequal pieces of the key as outlined above. Add Q to that byte. Put that byte through the following process:

- Add the contents of C1 to the number, modulo 256.
- Replace that number by its substitute in S-box 6a (the first half of S-box 6).
- XOR the result with the contents of C2.
- Replace that number by its substitute in S-box 6b (the second half of S-box 6).
- Add the contents of C3 to the result, modulo 256.
- Replace that number by its substitute in S-box 7a (the first half of S-box 7).
- XOR the result with the contents of C4.
- Replace that number by its substitute in S-box 7b (the second half of S-box 7).
- Add the contents of C5 to the result, modulo 256.

The result of this process is the output byte, to be placed in the subkeys. The output byte is also stored in the variable Q.

One more step, however, remains in the process; the variables A1, A2, and A3 are changed (just as B1 through B5 have already been changed) as follows: replace A1 with the former contents of A2; replace A2 with the former contents of A3; and replace A3 with the former contents of A3 XOR the current output byte (also stored in Q).

After generating the first 440 regular 32-bit subkeys, initial values of the remaining subkey material is generated in the following order:

- first, initial subkeys K441 through K488 (which will later be used for subkeys with different numbers), (192 bytes)
- then the contents of key-dependent S-box S8, (from 1536 to 2304 bytes are used to produce this, since it is generated from three permutations which require either 512 or 768 bytes to produce)
- then the 256 16-bit entries for each of S10 and S11; (1024 bytes)
- then the Mishmash subkeys; 32 sets of two 48-bit subkeys for the DES rounds, (384 bytes)
- 32 sets of six 32-bit subkeys for the Quadibloc rounds, (768 bytes)
- 32 sets of sixteen 8-bit subkeys for the Skipjack rounds, (512 bytes)
- 32 sets of two 64-bit subkeys for the SAFER rounds, (512 bytes)
- 32 sets of fourteen 32-bit subkeys for the GoodStuff rounds. (1792 bytes)
- An additional 2304 bytes of subkey material to be used later. (2304 bytes)

All the subkey material thus generated, except the material used to produce S-box S8, is retained in order in an array for later modification.

An initial value for S8, the key-dependent S-box is generated as follows:

- Generate three permutations of the numbers from 0 to 255 from the
subkeys by the following procedure:
- Use successive bytes from the subkeys, starting with the leftmost
(most significant) byte of subkey K1, and going through the subkeys
*in numerical order*, that is, K1, K2, K3, K4..., and then starting where one has left off for subsequent permutations. - 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.

- Use successive bytes from the subkeys, starting with the leftmost
(most significant) byte of subkey K1, and going through the subkeys
- The three permutations obtained in this manner are used to generate a
key dependent S-box as follows:
- For N from 0 to 255:
- Set A to be element N of the first permutation; set B to be element N
of the second permutation, and set C to be element
**B**of the third permutation. - Set element A of the S-box to equal C.

Only the first 440 subkeys, each 32-bits long, which are the first subkey material generated by this method, are modified by the key augmentation technique of performing an initial encipherment, and XORing subkeys with intermediate results. Because some of the rounds do not produce intermediate results suitable for this use, the key augmentation step undergoes an important change. Instead of modifying the 440 subkeys by performing a normal Quadibloc III encipherment, and using its intermediate results, a modified encipherment, using only normal rounds found in Quadibloc II is used.

The modified encipherment consists of one group of four degenerate rounds, forty-eight normal Quadibloc II rounds, and one more group of four degenerate rounds. This arrangement uses exactly 440 subkeys. Four key-dependent byte permutations are used, from 0x, 1x, and inverse 9x and 8x; only one unkeyed whitening step, followed by the 0x permutation, begins the cipher; the 1x permutation follows the first group of four degenerate rounds, preceding the first conventional Quadibloc II round.

The subkeys are initially filled in the following order, consistent with Quadibloc II practice:

K1 K2 K3 K4 K5 K8 K11 K6 K9 K12 K7 K10 K13 K14 K17 K20 K15 K18 K21 K16 K19 K22 ... K428 K431 K434 K429 K432 K435 K430 K433 K436 K437 K438 K439 K440

and are modified during key enrichment in the following order (although the subkeys are aligned in columns to illustrate their pattern, the order used is that found by reading across):

K440 K436 ... K22 K13 K439 K435 ... K21 K12 K438 K434 ... K20 K11 K437 K433 ... K19 K10 K432 ... K18 K9 K431 ... K17 K8 K4 K430 ... K16 K7 K3 K429 ... K15 K6 K2 K428 ... K14 K5 K1

Bytes for use in the 48 additional subkeys, S10 and S11, and in Mishmash, are generated during the initial part of subkey generation, even though these parts of the cipher aren't used in key-enrichment; then, during the key-enrichment phase, nine bytes of output from the same shift register process as was used to fill all the subkey material with its initial values, but modified in an analogous fashion to that used for Quadibloc II (the last 13 bytes of the 440 regular subkeys are used to fill A1 through C5, and one shift register, rather than two, is used, consisting of the rest of the subkey material), are used to modify eight bytes in this additional subkey material.

This is done as follows: the first byte determines the use of the next eight bytes; if its most significant bit is a 1, the next byte is XORed to the previously generated byte, if its most significant bit is a 0, the next byte replaces the corresponding previously generated byte, and so on through the bits of the first byte and the bytes following.

The additional subkey material being modified in this step consists of 7488 bytes. For the purpose of an additional operation to be performed concurrently with the XOR or replacement of these bytes in groups of eight using generated bytes in groups of nine, these bytes are to be considered as 20 blocks of 256 bytes each, plus 64 extra bytes.

The additional manipulation to be performed consists of two steps. Only during the processing of the second through the 19th of the 20 complete blocks are both steps done; one is done during the processing of the first block.

For each of the first 256 generated bytes of the 288 generated bytes required to modify the 256 bytes of the current block, the next block is modified as follows:

Letting c be a counter, 0 for the first generated byte, and incremented by one as we change to use each additional generated byte, and letting n be the value of the current generated byte, we swap byte c and byte n of the next block.

This only requires the existence of a following block, and is therefore done when the current block is any block from the first through the nineteenth.

For each of the last 256 generated bytes of the 288 generated bytes we use in modifying the 256-byte current block, immediately following the use of that same byte for modifying the next block during the period when both operations overlap, we modify the preceding block as follows:

Letting c be a counter, 0 for the first generated byte used by this step,
the 33rd of the 288 generated bytes for the current block, and letting n
be the value of the current generated byte, we let p be the value of
byte c of the *next* block, and let q be the value of byte n
of the previous block.

We then swap bytes p and q of the previous block. Letting k be the XOR of the values of the two bytes so swapped, byte n of the previous block is then modified by being XORed with byte k of the next block.

This requires both a preceding and a following block, and is done for the second block through the nineteenth.

Performing these transposition steps on the subkey material helps to destroy any pattern it might contain.

As many of the last 2304 bytes of subkey material as required are used to generate a permutation following the steps used for generating the initial value of S8. The generated result, however, is not used as the final value of S8. Instead, each element of S8 is replaced by the value it points to in this result; that is, for N from 0 to 255, S8(N) becomes R(S8(N)). (Thus, S8 depends on both the old and new subkeys, and doesn't relate to the current subkeys in a simple way.)

Then, the 488 subkeys required for Quadibloc III are produced from the 440 subkeys generated normally and the 48 additional ones by using the 48 additional subkeys in order as the ones for the f-functions that are used to modify the f-function results before being XORed together in the Mishmash rounds.

Hence,

- subkeys K1 through K88 retain their identity,
- subkeys K441 through K452 are moved to subkeys K89 through K100,
- subkeys K89 through K100 are moved to subkeys K101 through K112,
- subkeys K453 through K464 are moved to subkeys K113 through K124,
- subkeys K101 through K352 are moved to subkeys K125 through K376,
- subkeys K465 through K476 are moved to subkeys K377 through K388,
- subkeys K353 through K364 are moved to subkeys K389 through K400,
- subkeys K477 through K488 are moved to subkeys K401 through K412,
- and, finally, subkeys K365 through K440 are moved to subkeys K413 through K488.

Note that implementations need not actually move the subkeys around, but merely need to ensure that each encipherment step uses the correct subkeys from those stored in memory.

Specific named variations of Quadibloc III are provided here to broaden its range of applicability.

The first variation is Quadibloc III SC (Short Cycle). This version retains the complexity of Quadibloc III, but eliminates the large number of rounds of the GoodStuff kind in the middle of the cipher. Instead, only two such rounds are retained, with the following arrangement:

1 > 2 > 3 > 4 > 5 > 6 > 7 > 8 8 < 7 < 6 < 5 < 4 < 3 < 2 < 1

This, by reducing the amount of required subkey material from 488 subkeys to 278, and hence the key augmentation phase of key generation is modified as follows: eight regular Quadibloc II rounds are used, the first 10 words of S10 are also modified, and there is no shifting of subkeys out of numerical order, as was required to exclude a particular 48 subkeys from key augmentation in the normal version. The unkeyed whitening step, and the initial and final byte transposes (0x and 8x) are also retained in the modified encipherment.

The next variation is Quadibloc III MD (Maximum Dispersion). This version adds eight 64-bit words of subkey material to what is used by the cipher. They are not used during the modified encipherment cycle performed for key augmentation, but they are generated initially, like other parts of the subkey material not then used. They are generated immediately after the 32 extra normal subkeys which are modified after, instead of during, key augmentation, and immediately before calculating S-box S8. Otherwise, since the key schedule is only lengthened, key augmentation is not otherwise modified for this variation.

These 64-bit words are used to perform an ICE-style interchange of the left and right halves of the block, immediately after the first four key-dependent byte interchanges derived from S-box S8 and immediately before the last four such byte interchanges. A 1 bit corresponds to a bit to be interchanged, and the words are used in order during encipherment.

Finally, Quadibloc III SD (Short/Dispersive) combines the modifications in Quadibloc III SC and Quadibloc III MD. As it has 294 32-bit words of normal subkey, the key augmentation phase of its key generation is based on a modified encipherment involving a byte transpose based on the 0x row of S8, an unkeyed whitening step, a set of four degenerate rounds, a byte transpose based on the 1x row of S8, eight normal Quadibloc II rounds, the 9x transpose, four degenerate rounds, inverse whitening, and the 8x transpose. The first two words of S10 are also included in the key augmentation for this variation.

A variation in the round structure, like those illustrated for Quadibloc II, will also be illustrated here, but in this case it is for the Mishmash portion of the cipher.

This diagram gives an overview of the Mishmash rounds as modified. Instead of placing the intermediate results of the four QUADIBLOC 96 rounds on the left side through an additional QUADIBLOC f-function, these results are used to produce a 32-bit result by means of the 32-bit Feistel structure used within the GoodStuff portion of the cipher. This reduces the number of additional subkeys required for this part of the cipher to 8 from 48, but the strength of the modified cipher appears fully satisfactory.

Another variation on Quadibloc III uses the modified Mishmash rounds described above, but in addition changes the order of the rounds in line with insights that have come out of looking at how some differential attacks, including the boomerang attack work. The idea is that parts of the cipher that are analytically simple are put on the outside, and parts that are harder to analyze, but possibly leaving room for new probing attacks, are put in the center. A diagram giving an overview of the variation, accompanied by its description, are below:

- Small Feistel rounds, using no subkeys, but using the key-dependent S-box S8 as their f-function, transforming 16-bit subkeys of the block.
- Key-dependent permutation (derived from the 0x elements of S8) of the bytes in the block.
- Four simple rounds, using a single-level f-function, that are aimed at obtaining high diffusion, and which use 32-bit subkeys K1 through K4.
- Key-dependent permutation (derived from the 1x elements of S8) of the bytes in the block.
- Two rounds in which the block is enciphered as follows:
- one 16-bit subblock is enciphered by four Feistel rounds, using S8 as the f-function, but this time preceded by the XOR of a subkey byte;
- the results of the XOR are used as intermediate results, and are fed into the S-box S9.
- The four S9 outputs produce a 32-bit result whose first 16 bits are the first four bits of each of their outputs, and whose last 16 bits are the last four bits of each of their outputs.
- This result is then enciphered by means of four Feistel rounds, where the f-function consists of first XORing in a 16-bit half of a subkey, then using the two bytes of the result to index into two key-dependent S-boxes, S10 and S11, which each take an 8-bit input and give a 16-bit output. The sum of the two outputs is XORed with the other half of the 32-bit block.
- The 32-bit result of this process is used as a 32-bit subkey was used initially to encipher a further 16 bits of the block, and this continues until the entire 128-bit block has been enciphered in 16-bit pieces.

- Key-dependent permutation (derived from the 2x elements of S8) of the bytes in the block.
- Eight normal Quadibloc II rounds, each of which uses nine subkeys, the first using subkeys K35 through K43, the last using subkeys K98 through K106.
- Key-dependent permutation (derived from the 3x elements of S8) of the bytes in the block.
- Four rounds of a form of Mishmash, whose large quantity of subkeys is generated after the contents of S10 and S11, and by the same process. These rounds use fixed Quadibloc subkeys for one half of the block, the subkeys being K107 through K118 for the encipherment of that block, and K119 through K120 for the Feistel rounds with a 32-bit block using S-boxes S10 and S11 that modify its intermedate results, for the first Mishmash round, and the remaining Mishmash rounds use subkeys K121 through K162.
- Then, the preceding steps are done in reverse order, with the key-dependent byte permutations now being the inverses of the ones derived from the Bx, Ax, 9x, and 8x elements of S8, and with the eight normal Quadibloc II rounds using subkeys K163 through K234, the two GoodStuff rounds using subkeys K235 through K264, and the set of four degenerate rounds using subkeys K265 through K268.

The 268 subkeys required, plus the first 20 32-bit words of the S-box S11, are modified after initial subkey generation by key augmentation through 32 normal Quadibloc II rounds with no degenerate rounds, (and two byte transposes, based on the 0x and 8x rows, instead of four, and two unkeyed whitening steps, as for the regular cipher) and there is no shifting of subkeys out of numerical order, as was required to exclude a particular 48 subkeys from key augmentation in the normal version.

The block cipher Quadibloc XI in this series has a secure key schedule which appears to me both efficient and secure. Quadibloc III RK (Revised Keys) may denote the variant which uses that key schedule as follows: generate the four bytes of each subkey in order, most significant (leftmost) first, generating the normal subkeys in simple numerical order from K1 to K488, and then use the method for generating a permutation to produce S8, and then generate the bytes of S10 and S11, and the subkey pools for the DES, 64-bit Quadibloc, SKIPJACK, SAFER and GoodStuff rounds in that order as for the regular key schedule for this cipher.

One modification is required, however; instead of using S3 as the S-box, one that is never used in the cipher itself is to be used; and the first one satisfying that criterion is the constant S-box produced from Euler's Constant listed on the page Euler's Constant and the Quadibloc S-boxes as S12, since the S5, S6, and S7 referred to on this page are (S5, S6), (S7, S8), and (S9, S10) as noted on that page, and the S-box denoted as S9 on this page is the one noted as S11 on that page.

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

This revised form of subkey generation proceeds 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 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 (but with S12 replaced by S3, as this is the diagram from the page on Quadibloc XI).

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 S12, 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 S12, 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 S12, 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 S12, 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 S12, 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 S12, 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.

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 (but with S-box S12 replaced by S-box S3, because it is the diagram from the page on Quadibloc XI):

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-box S8 must be 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]

Next

Start of Section

Skip to Next Chapter

Table of Contents

Main Page
Home Page