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

Quadibloc V is a straightforward and simple member of the Quadibloc family of ciphers. It operates on a 128-bit block, and has a key which must consist of number of bytes that is a multiple of four and which is equal or greater than 8. It uses S-box S1 derived from Euler's constant, as used in other ciphers of the Quadibloc series, and described on the page Euler's Constant and the Quadibloc S-Boxes, and it uses one key-dependent S-box, called S2, which has 16 entries, each 64 bits long.

It has four rounds, and each round uses 72 bytes of subkey material. The halves of the block are swapped after each of the first three rounds.

As encipherment and decipherment are different, and as the f-function only diffuses half of the information in the left half of the block, it might seem that there are opportunities for cryptanalysis. But what happens to the right half of the block, and the use of a key-dependent S-box, even if only a minimal one, appears to close any such opportunities. Also, the key schedule seems to be secure, although it too is greatly simplified over that of Quadibloc II or III.

### The Rounds

The following diagram illustrates what happens during a round of Quadibloc V:

The bytes in the left half of the block are used in pairs to generate bytes the nybbles of which are then used to select two entries from S-box S2.

One copy of the second byte in the pair is XORed with a byte of subkey material; the next copy has the next byte of subkey material added to it. Then both copies are replaced by their corresponding entries in S-box S1. The first byte in the pair first has the first copy of the other byte, as modified, added to it. This intermediate result is retained for later use. Then it is replaced by the entry it now selects in S-box S1. Finally, the second copy of the other byte, as modified, is XORed to it.

The first and second nybbles of this resulting byte are used to index to two elements of S-box S2. The entry chosen by the second nybble of a byte then has its halves swapped. The intermediate result saved for later use is also split into two nybbles, each used to index an element from S-box S2. The one chosen by the first nybble is rotated 16 bits left, and the one chosen by the second nybble is rotated 16 bits right.

These elements of S-box S2 are XORed with the right half of the block at various times.

This portion of the cipher uses the first eight subkey bytes for the round.

First, the bytes in the right half of the block are modified by going through tiny Feistel rounds, similar to permutation G of SKIPJACK, but here using S-box S1 as the f-function. First, each pair of bytes goes through two rounds of this, first the left-hand byte modifying the right-hand byte, then the right-hand byte modifying the left-hand byte. Two subkeys are used to perform these two rounds for one pair of bytes, then the next two subkeys are used for two rounds for the next pair of bytes, as is visible from the numbering in the diagram.

Then, four S2 outputs,

• the one from the first nybble of the byte generated from the first pair of bytes in the left half of the block
• the one (with its halves swapped) from the last nybble of the byte generated from the last pair of bytes in the left half of the block
• the one (rotated 16 bits to the left) from the first nybble of the intermediate result generated from the second pair of bytes in the left half of the block
• the one (rotated 16 bits to the right) from the second nybble of the intermediate result generated from the third pair of bytes in the left half of the block

are XORed to the right half of the block as currently modified.

Then, two more tiny Feistel rounds are applied to each pair of bytes in the right half, and then the bytes are interchanged as follows:

```  1  4  3  6  5  8  7  2
```

and then another two tiny Feistel rounds are applied. Note that this interchange, applied three times, ensures that each even byte is paired with each odd byte for four tiny Feistel rounds during this process.

Now, four S2 outputs

• the one from the first nybble of the byte generated from the second pair of bytes in the left half of the block
• the one (with its halves swapped) from the last nybble of the byte generated from the third pair of bytes in the left half of the block
• the one (rotated 16 bits to the left) from the first nybble of the intermediate result generated from the first pair of bytes in the left half of the block
• the one (rotated 16 bits to the right) from the second nybble of the intermediate result generated from the last pair of bytes in the left half of the block
are XORed to the right half of the block in its present state.

Then, another four tiny Feistel rounds with a byte interchange in the middle.

Now, four S2 outputs

• the one from the first nybble of the byte generated from the third pair of bytes in the left half of the block
• the one (with its halves swapped) from the last nybble of the byte generated from the second pair of bytes in the left half of the block
• the one (rotated 16 bits to the left) from the first nybble of the intermediate result generated from the last pair of bytes in the left half of the block
• the one (rotated 16 bits to the right) from the second nybble of the intermediate result generated from the first pair of bytes in the left half of the block
are XORed to the right half of the block.

Then, another four tiny Feistel rounds with a byte interchange in the middle.

And then the following four S2 outputs

• the one from the first nybble of the byte generated from the last pair of bytes in the left half of the block
• the one (with its halves swapped) from the last nybble of the byte generated from the first pair of bytes in the left half of the block
• the one (rotated 16 bits to the left) from the first nybble of the intermediate result generated from the third pair of bytes in the left half of the block
• the one (rotated 16 bits to the right) from the second nybble of the intermediate result generated from the second pair of bytes in the left half of the block
are XORed with the right half.

And now, two tiny Feistel rounds are applied to each pair of bytes in the right half of the block. Finally, the bytes are interchanged as follows:

```  1  3  5  7  2  4  6  8
```

This final interchange sorts the odd and even bytes into groups, so that pairs will later be made on a different basis.

### The Key Schedule

The key material used during encipherment consists of a 512 byte key-dependent S-box S2, and 288 bytes of subkey material.

Initially, this key material is loaded as follows:

• The key is split into two parts, the first having one byte less than half the bytes in the key, and the second having the remaining bytes.
• Bytes of subkey material are alternately filled from each half of the key.
• Each time one returns to the first byte of a part of the key, after using the last byte previously, one adds 1 to a constant (initially zero) which is added to each byte as it is taken.

Thus, if the key is initially:

``` 200 160 001 100 080 020 140 120
```

it is split into the two parts

``` 200 160 001
100 080 020 140 120
```

and the subkey material is initially filled as follows from it:

``` 200 100 160 080 001 020 201 140
161 120 002 101 202 081 162 021
003 141...
```

Using this initial subkey material, a block is enciphered consisting of the first sixteen bytes of the key, or, if the key is shorter than sixteen bytes, the key followed by the key with each byte XORed with 1, followed by the key XORed with 2 if necessary, all the bytes then replaced with their substitutes in S-box S1.

Each round of encipherment produces eight 64-bit intermediate results: an intermediate result is obtained by taking the current value of the right half of the block after each pair of tiny Feistel rounds, except that in the case of those rounds followed by XORing in S-box S2 entries, the intermediate value is taken after that XOR.

After each round is completed, and five rounds are performed, rather than the four used for normal encipherment, the fifth using the same subkeys as the first, the intermediate results are used to modify the subkeys.

The first 36 of the 40 intermediate results generated are XORed with the subkey material, in the following order:

```Result:  Subkey bytes:

1      K1   K2   ... K8
2      K73  K74  ... K80
3      K145 K146 ... K152
4      K217 K218 ... K224
5      K9   K10  ... K16
6      K81  K82  ... K88
...
36      K281 K282 ... K288
```

In addition, each byte of all but the first eight intermediate results (leaving the last 32 intermediate results, which amount to 256 bytes) is used to modify the 512-byte S-box S2, as follows:

• The S-box S2 is to be considered as consisting of two halves, each 256 bytes in length, called H0 and H1. H0(n) is the (n+1)th byte of H0; that is, H0(0) is the first byte of H0.
• Let the byte being used to modify the S-box have the value X.
• Let a counter, initially equal to 0, and increasing by 1 each time be noted by N. This counter will run from 0 to 255 as the process below takes place.
• Let W=N xor X.
• Let P=H0(W) xor X and Q=H1(W) xor X
• In all cases, first modify H1(P) by XORing it with H0(P) and with X, then modify H0(Q) by XORing it with H1(Q) and with X.
• Modify H0(X) by XORing it with Q and with W, and modify H1(X) by XORing it with P and with W.
• If N and X are not equal, swap H0(N), H0(X), H1(N), and H1(X) as follows: H0(N) is replaced by H0(X), which is replaced by H1(N), which is replaced by H1(X), which is replaced by the former value of H0(N).

### Variations

If one wishes to use Quadibloc V with eight rounds, then the key augmentation step of the key schedule is modified as follows:

The encipherment step used to generate intermediate results now runs for nine rounds. All intermediate results are used to XOR with subkey bytes, and the order is similar to that for the four-round version: first, an XOR is done to the first eight bytes in each of the eight rounds, then the next eight bytes in each of the eight rounds. The ninth round uses the subkeys for the first round.

The last 512 bytes so generated, which involve all but the first eight intermediate results, are used to carry out the modification of the S-box S2, but this time twice.

With sixteen rounds, the key augmentation step will involve encipherment with eighteen rounds, the last two using the subkeys of the first two rounds. Again, all intermediate results are used to XOR with subkey bytes. The last 1024 bytes generated, which exclude the first sixteen intermediate results (or those from the first two rounds) are used to modify S-box S2 four times.

### Revised Key Generation

The method used for generating subkeys for Quadibloc XI may be applied to this cipher as well. Here, for simplicity and to avoid confusion, S3 will be used as it was in Quadibloc XI (although the fixed S-box S2 is also potentially available). For Quadibloc V RK, the 288 subkey bytes are generated in order, followed by the 128 bytes of the key-dependent S-box S2.

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.

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