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

Quadibloc 2002C

Quadibloc 2002C is a block cipher with a block size of 80 bits. This unusual block size makes it simple to devise a cipher illustrating the particular type of unbalanced Feistel round which serves as the underlying principle of this cipher.

There are two types of round in Quadibloc 2002C. The first type of round, which shall be referred to as the Type A round, uses an f-function of 16 bits of the block to control two Feistel rounds using the standard Quadibloc f-function which modify the other 64 bits of the block, and is as illustrated below:

The second type of round uses two Feistel rounds with the standard Quadibloc f-function as an f-function in itself, by means of which 64 bits of the block produce a 64 bit value used to modify the other 16 bits of the block. This round, the type B round, is illustrated here:

The type B round is felt to contribute to the strength of the cipher because it shares with some of the better stream ciphers the characteristic that the modification of the block which it produces, while it contains only 16 bits of information, depends on 64 bits of input, and on 192 bits of subkey, thus making it difficult to work backwards to make deductions concerning the subkeys. However, the fact that the effects of the subkeys are confined to 16 bits of the block means that this round produces slow diffusion by itself, and thus it is complemented by the type A round.

The Cipher in Detail

The encipherment of an 80-bit block of plaintext by means of Quadibloc 2002C shall consist of the following steps:

A plain byte permutation takes the ten bytes in a block from the order:

  1  2  3  4  5  6  7  8  9 10

to the order:

  3  4  9  1  8 10  5  6  2  7

and a twisted byte permutation takes the ten bytes in a block from the order:

  1  2  3  4  5  6  7  8  9 10

to the order:

 10  1  2  3  9  5  6  7  4  8

thus, the plain byte permutations are used between type A rounds so as to preserve alternation between the left and right halves of the Feistel round, while the twisted byte permutation is used when type B rounds are also present, since in that case, the two additional bytes are modified together, and thus they can be swapped between streams. Also note that the plain byte permutation rotates the two groups of five bytes by either two or three bytes per step, while the twisted byte permutation rotates a loop including all ten bytes by only one byte per step. Thus, the plain byte permutation brings different bytes of each half of the block into corresponding positions in succeeding rounds.

The type A round proceeds as follows:

The block is divided into ten bytes, numbered 0 through 9 from left to right.

The type B round proceeds as follows:

The Key Schedule

The subkey material used by Quadibloc 2002C is as follows:

Subkey generation proceeds in the following order:

The purpose of the noninvertibility operation is to serve as a one-way function, like a hash function, so that even if information about K76 through K165, the subkeys used in the most conventional manner in Feistel rounds whose result is directly manifest in the relation between plaintext and ciphertext, can be obtained through methods such as differential cryptanalysis, this information will not lead to information about subkeys K1 through K60, which are in the portion of the cipher which is hidden away from analysis because it affects only 16 bits of the block at a time.

The key will be a multiple of four bytes in length, and must be at least eight bytes in length.

Once again, the methods used to generate subkey bytes and key-dependent permutations are as follows:

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 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:

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 a 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:

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 bringing about large changes in the subkeys from the very beginning, although it is still true, since the bytes used to select buffer contents could be the same by coincidence, that subkeys generated from very similar keys have a slightly enhanced probability of having bytes in common.

Permutation Generation

During subkey generation, the key-dependent S-boxes S7, S8, S9 and S10 must be generated. To generate each bijective S-box, the following procedure is used:

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.

The Noninvertibility Operation

The noninvertibility operation, a step in this plan of subkey generation introduced especially for Quadibloc 2002C, consists of generating as many bytes of subkey material as there are bytes in the three shift registers used the initial contents of which were derived from the keys, as well as an additional 512 bytes of subkey material, and then XORing this subkey material, in order, with the bytes of those three shift registers, the bytes of buffer A, and the bytes of buffer B.

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 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:

This method ensures that the key schedule is a function of the entire key. It also is expected to ensure that there is no usable relationship between the groups of keys separated by noninvertibility operations.


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

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