Quadibloc 2002E: Key Schedule and Decipherment

The Key Schedule

The subkey materials used by this cipher consist of:

• Four hundred and ninety-six 32-bit subkeys, K1 through K496
• Twenty-two 128-bit subkeys, LK1 through LK22 (long keys)
• Twenty-eight 64-bit subkeys the bytes of which are the outputs of a 4 of 8 code, EK1 through EK28 (exchange keys)
• Sixteen S-boxes containing 256 8-bit elements, forming a permutation of the values from 0 to 255, SB1 through SB16 (bijective S-boxes)
• Two S-boxes containing 256 16-bit elements, having no special properties, SR1 through SR2 (random S-boxes)

The subkey material is produced by a modification of the alternative byte subkey generation procedure outlined in the description of Quadibloc 2002D, and is produced in the following order:

• Subkeys K1 through K192
• S-boxes SB1 and SB2
• Subkeys LK1 through LK22
• S-boxes SB3 and SB4
• Subkeys EK1 through EK12
• Subkeys K193 through K240
• S-box SB5
• Subkeys K241 through K496
• S-boxes SB6 through SB11
• Subkeys EK13 through EK20
• S-boxes SB12 through SB15
• Subkeys EK21 through EK28
• S-box SB16
• S-boxes SR1 and SR2

Each of the exchange keys, from EK1 through EK28, is produced by first generating eight subkey bytes, and then passing the least significant six bits of each byte, ignoring the two most significant bits, through the following 4 of 8 bit code, as introduced in the description of the key schedule of the original QUADIBLOC:

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 modified subkey byte generation procedure is as illustrated in the diagram below:

The positions of the buffers A through D in the diagram above are as follows:

C A
D B

and the steps involved in the procedure as illustrated are:

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.

The cipher uses four buffers, each of which 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, and then buffer C is filled with another 256 bytes generated from 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, and then buffer D is filled with another 256 bytes generated from the first string.

Subkey Byte Generation

• Three bytes are generated from the first string by its associated nonlinear shift register operation, and they will be called U, V, and W in order.
• Three bytes are generated from the second string by its associated nonlinear shift register operation, and they will be called F, G, and H in order.
• Five bytes are generated from the third string by its associated nonlinear shift register operation, and they will be called J, K, L, M, and N in order.
• The byte at the position in buffer A indicated by the value U is taken, and called P.
• The byte at the position in buffer C indicated by the value V is taken, and it is XORed with both the value H and the value K, and the result is placed in buffer A, at the position indicated by the value U, replacing the value taken from the buffer A.
• The byte at the position in buffer B indicated by the value F is taken, and called Q.
• The byte at the position in buffer D indicated by the value G is taken, and it is XORed with both the value W and the value M, and the result is placed in buffer B, at the position indicated by the value F, replacing the value taken from the buffer B.
• The value J is placed in buffer C, replacing the value taken from that buffer, by being placed at the location indicated by the value V.
• The value L is placed in buffer D, replacing the value taken from that buffer, by being placed at the location indicated by the value G.
• The subkey byte generated is the XOR of P and Q and N.

Permutation Generation

To generate bijective S-boxes, which in the case of this cipher are the S-boxes SB1 through SB16, 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. Note that this is a procedure, introduced for Quadibloc X, is more straightforwards than the other two basic procedures used previously to produce S8 in other ciphers in this series.

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

Long Keys

The subkey generation procedure given above works well for keys from 64 bits to 1,024 bits in length. When the length of the key approaches 2,048 bits in length, however, the first two shift registers are no longer thoroughly mixed by filling the buffers initially.

Thus, the following modified subkey generation procedure is given for keys which are more than 1,024 bits long. A key must still be a multiple of 32 bits in length.

• (1) Divide the key into blocks of 512 bits until the remaining part of the key is from 512 to 992 bits in length.
• (2) Use the first block of the key as the key for the normal Quadibloc 2002E key schedule.
• (3) Continue to generate enough additional subkey bytes to XOR these with the next block into which the key was divided.
• (4) Use the next block, after the XOR, to carry out the Quadibloc 2002E key schedule except:
  • Exclude the exchange keys (EK1 ... EKn) [and, in the variants, the short and tiny exchange keys, (SEK1 ... SEKn) and (TEK1 ... TEKn) as well] entirely from generation;
  • The subkey material generated is XORed with the previously generated values of the subkeys in the case of subkeys of any length (K1 ... Kn, LK1 ... LKn) and of S-boxes with random contents (SR1 ... SRn);
  • When using the second block, the first four bytes of subkey material generated are XORed with the subkey material starting after the fourth byte of the subkeys, which indeed is after K1. For each succeeding block, start 32 bits later in the key schedule, until one has used one block to modify the subkey material beginning with after the 1,024th byte of subkey material, and then revert to starting with the first byte of the normal key schedule again;
  • Generate permutations for the bijective S-boxes (SB1 ... SBn) in the normal sequence of generation, and then modify the bijective S-boxes to be used in the cipher as follows: go through the newly-generated bijective S-boxes and the previously calculated bijective S-boxes from positions 0 to 255; in a new array, place the value in the new permutation in the position indicated by the value in the original permutation. Once this is finished, the new array is the replacement permutation.
• (5) If there are any additional blocks remaining in the key, go back to step 3.

This method ensures that the key schedule is a function of the entire key.

Deciphering

The block cipher Quadibloc 2002E has been carefully designed so that its inverse consists of the same algorithm, but with the subkeys modified.

The required modifications are:

The order of groups of eight subkeys within subkeys K1 through K192 is reversed, with the order of subkeys within each group staying the same, and in addition the order of the four bytes within each subkey is reversed.

The order of subkeys LK1 through LK22 is reversed.

The order of subkeys EK1 through EK12 is reversed.

S-boxes SB1 and SB2 are exchanged.

The order of groups of three subkeys within subkeys K193 through K240 is reversed.

The order of groups of thirty-two subkeys within subkeys K241 through K496 is reversed.

The order of subkeys EK13 through EK20 is reversed, and in addition the bits of each of these subkeys are inverted. (This refers to the actual subkey, not the input to the 4 of 8 code.)

The order of subkeys EK21 through EK28 is reversed, and in addition the bits of each of these subkeys are inverted.

Next
Start of Section
Skip to Next Chapter
Table of Contents
Main Page