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

Quadibloc IV is a block cipher with a 128-bit blocksize with a simpler design than that of either Quadibloc III or even Quadibloc II. It has 32 rounds, numbered from 1 to 32, each using three 32-bit subkeys.

It uses the S-boxes S1, S2, and S3 (S3 is only used during key generation) derived from Euler's constant, as listed on the page entitled Euler's Constant and the Quadibloc S-Boxes.

It attempts - despite the fact that A xor B and B xor A are the same thing - to use a strategy derived from hash functions to produce a secure f-function; the quantity XORed to the first subblock in each round is the XOR of two f-functions, one which uses a subblock as input, and two subkeys as keys, and one which uses a subkey as input, and two subblocks as keys.

The Rounds

A round of Quadibloc IV proceeds as follows:

The 128-bit block is considered to be divided into four 32-bit subblocks, B1 through B4. The leftmost subblock, B1, is the only one modified in a round. It has two quantities XORed to it:

• An f-function, using B2 as input, with the first two subkeys for the round as keys, using S1 as the S-box.
• An f-function, using the third subkey for the round as input, with B3 and B4 as keys, using S2 as the S-box.

The f-function is essentially the basic Quadibloc f-function: XOR the input and the first key, substitute the bytes in the S-box, and then perform the following regular permutation of the bits:

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

Then, XOR the input and the second key and again perform the S and P steps. In Quadibloc IV, no third key is used.

The following diagram illustrates a typical round of Quadibloc IV: The diagram illustrates the way in which the subblocks are interchanged after a typical round:

3 4 2 1

No interchange is performed after the last round, round 32.

After round 4 and after round 28, the bytes of the 128-bit block are interchanged in the following order:

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

After round 16, the four subblocks are interchanged in this order:

3 2 1 4

After the other rounds whose numbers are divisible by 4, the four subblocks are interchanged in this order:

3 1 4 2

Hence, if one numbers the subblocks on entry to round 5 as 1, 2, 3, and 4, the orders in which they appear from round 5 to round 28 are as follows:

1 2 3 4  3 4 2 1  2 1 4 3  4 3 1 2
1 4 2 3  2 3 4 1  4 1 3 2  3 2 1 4
1 3 4 2  4 2 3 1  3 1 2 4  2 4 1 3
1 4 3 2  3 2 4 1  4 1 2 3  2 3 1 4
1 2 4 3  4 3 2 1  2 1 3 4  3 4 1 2
1 3 2 4  2 4 3 1  3 1 4 2  4 2 1 3

thus going through all 24 possible orders exactly once.

Because of the byte interchange after rounds 4 and 28, the first and last four rounds function as a whitening phase of the block cipher.

Key Generation

Two shift registers, one 64 bytes in length and one 65 bytes in length, are used to generate subkeys, and are loaded with the key, which can be from 2 to 63 bytes in length, as follows:

• If the key is 256 bits (32 bytes) in length or shorter:
• The 64-byte shift register is loaded with the key, followed with the one's complement of the key, followed by as many repetitions of the key as are needed to fill it.
• The 65-byte shift register is loaded with the bytes of the key in reverse order, followed by the one's complement of the key (in normal order), followed by as many repetitions of the key as are needed to fill its first 64 bytes, followed by the one's complement of the first byte of the key.
• If the key is from 33 to 63 bytes in length:
• The 64-byte shift register is loaded with the first half of the key (including one more byte than the second half, if the number of key bytes is odd), followed by the one's complement of the first half of the key and as many repetitions of the first half of the key as are needed to fill it.
• The 65-byte shift register is loaded with the second half of the key, followed by the one's complement of the second half of the key, and as many repetitions of the second half as are needed to fill its first 64 bytes, followed by the one's complement of the first byte of the second half of the key.

Initial values of subkey bytes are generated from these two shift registers as follows:

The first shift register is cycled as follows:

Take the 49th byte, add the 33rd byte, and XOR the 64th byte. Find the substitute for the result in S-box S3. XOR the 3rd byte, and add the 1st byte.

The result will be the new first byte of the shift register, the other bytes being advanced one place, and the old 64th byte being discarded.

The second shift register is cycled as follows:

Take the 23rd byte, add the 65th byte, and XOR the 11th byte. Find the substitute for the result in S-box S3. Add the 50th byte, and XOR the 1st byte.

The result will be the new 65th byte of the shift register, the other bytes being moved to the next earlier place, and the old 1st byte being discarded.

The byte of the subkey generated from this step is the generated new first byte of the first shift register, replaced with its substitute from S-box S3, XORed with the generated new 65th byte of the second shift register.

Once all 96 subkeys have been filled with their initial values, key augmentation takes place. A normal encipherment cycle is performed, enciphering the 128-bit block

A5 C3 E1 2D B4 87 96 F0 0F 69 78 4B D2 1E 3C 5A

but after each round, the four intermediate values generated in the round are applied as follows:

The four intermediate values are:

1. The output of the SP operation following the use of the first subkey for the round;
2. The output of the SP operation following the use of the second subkey for the round;
3. The output of the SP operation following the use of the third subblock;
4. The output of the SP operation following the use of the fourth subblock;

Intermediate values 1, 2, and 4 of each round are XORed to the subkeys after the round is over, and the order in which the subkeys is modified is:

K1  K4  K7 K10 K13 ... K94
K2  K5  K8 K11 K14 ... K95
K3  K6  K9 K12 K15 ... K96

and then, intermediate value 3 from the round is added, using byte-wide addition (as well as creating no endian confusion, this is sure to be implementable, even on systems that support only 16-bit arithmetic with no way to disable integer overflow exceptions) to the following subkeys in this order:

K96 K93 K90 K87 K84 ...  K3

Use as a Hash Function

As this block cipher was designed using design principles from hash functions, it seemed appropriate to specify a mode in which it could be used to generate a hash of a file. However, only the simplest mode is specified here, generating a 128-bit hash, which is not considered adequately long to obtain collision resistance.

One iteration of the cipher will be used to hash a block consisting of 32 32-bit words, or 128 bytes. The string of bits to be hashed will be converted to a whole number of blocks by having a 1 appended to it, and then the result will be filled out with zeroes to fill the last block.

The starting value to be "enciphered" by the block cipher will be:

A5 C3 E1 2D B4 87 96 F0 0F 69 78 4B D2 1E 3C 5A

as used for key augmentation.

The subkeys for the encipherment will be supplied by the block to be hashed as follows:

Both subkeys

K3  K6  K9 K12 K15 ... K96

and subkeys

K95 K92 K89 K86 K83 ...  K2

will be supplied from the bytes of the block, taken in groups of four, in order. (The first byte is the leftmost byte of the word.)

Subkeys

K1  K4  K7 K10 K13 ... K94

will be the following:

K1: 243F6A88   K4: 85A308D3   K7: 13198A2E  K10: 03707344
K13: A4093822  K16: 299F31D0  K19: 082EFA98  K22: EC4E6C89
K25: 452821E6  K28: 38D01377  K31: BE5466CF  K34: 34E90C6C
K37: C0AC29B7  K40: C97C50DD  K43: 3F84D5B5  K46: B5470917
K49: 9216D5D9  K52: 8979FB1B  K55: D1310BA6  K58: 98DFB5AC
K61: 2FFD72DB  K64: D01ADFB7  K67: B8E1AFED  K70: 6A267E96
K73: BA7C9045  K76: F12C7F99  K79: 24A19947  K82: B3916CF7
K85: 0801F2E2  K88: 858EFC16  K91: 636920D8  K94: 71574E69

which are the hexadecimal digits in the fractional portion of pi (also used as the starting value of the S-boxes and subkeys in Blowfish, although it uses 784 of them, not just 32 of them).

After each block is hashed, the input to the encryption cycle is XORed with the output to produce the current value of the hash, which will be the input to the next encryption cycle.

A Variation of Quadibloc IV

In Quadibloc IV ER (Extra Resistance), after generating the initial values of the subkeys, an additional 1536 to 2304 bytes are generated to create S8 in the same fashion as the initial value of S8 was generated in Quadibloc II and Quadibloc III. This key-dependent S-box is not modified again after key augmentation, and it is used to perform a substitution on the four bytes of the two f-function outputs after the second SP portion. This modification makes Quadibloc IV considerably more secure against differential and linear cryptanalysis.

Revised Key Generation

The method used for generating subkeys for Quadibloc XI may be applied to this cipher as well, as it was applied to Quadibloc II and Quadibloc III. Here, S3 can be used as it was in Quadibloc XI, since in this cipher as well it is only used for key generation, either the normal kind, or this revised kind. For Quadibloc IV RK, subkeys K1 through K96 are generated, leftmost byte first, in numerical order by the method described below.

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

For Quadibloc IV ER RK, a key-dependent permutation S8 is required as well, and is generated after the subkeys are generated, using the same permutation generation method as described for Quadibloc IX:

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

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