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

Design Rationale

Quadibloc VIII was designed to be a strong cipher not only against attacks which are currently understood, but also to be likely to be resistant against attacks which might be discovered in the future. It has been designed very conservatively; a full 16 rounds have been used, despite the fact that each round is considerably more elaborate than a single round in more conventional block ciphers: thus, its security does not depend on the merit of the somewhat unconventional measures I have included in the algorithm in hopes of achieving a very high level of security.

Such things as medical records, or other information related to the personal privacy of individuals, may be required to remain confidential for 50 or even 100 years. Because the speed and power of computers has been increasing at a fast pace for some time, it is very difficult to make a firm prediction of how powerful computers might be at such a distant time.

Although some fundamental physical limits, as well as physical laws which even limit the performance of quantum computers, do appear to imply that one can specify a key size that will leave one's messages forever immune to brute-force searching, it is even harder to predict what new and surprising discoveries may be made in the field of mathematics or in cryptanalysis that may allow attacks taking less time than a brute-force search (trying every possible key).

Hence, I felt that it was justified to attempt to design a cipher which, while remaining constrained to some extent to operate within limits at least comparable with those of more conventional designs, was still aimed at providing a very high level of security without attempting to justify the security aimed at as necessary. As with all the ciphers in the Quadibloc series, ease of implementation is another important consideration, and it is execution speed which has taken a back seat.

The most important step taken in the design of Quadibloc VIII to achieve the apparent potential for very high security was to, in every round, subject the 32-bit quarters of the block to two different transformations, making it variable which of those two transformations occurred first. As well, in one of those transformations, whether XOR or modulo-256 addition is used is variable.

This does create vulnerability to attacks based on monitoring the power consumption of a device carrying out this algorithm. Simultaneously (in hardware) or in a fixed order (in software) carrying out both possible operations, the one used and the one not used, is a measure that could be used to avoid this.

To achieve greater resistance to differential and linear cryptanalysis, key-dependent S-boxes are used. With the contents of the S-boxes unknown, characteristics cannot be found for the f-function in the normal manner used for simple differential cryptanalysis. This increases the amount of memory required to carry out the algorithm, again limiting its usefulness. The multi-stage nature of the f-function, in addition to giving this cipher a strong avalanche characteristic, also improves resistance to differential and linear cryptanalysis.

There are three basic possible ways in which weak keys could occur in the algorithm:

But I tend to view the threat from at least the second and third of these as negligible. With 16 rounds, and an f-function that has not one, but two SP stages based on fixed S-boxes, as well as the fact that there are two different groups of key-dependent S-boxes, both of which act on the entire block in every round, it should not be possible for an attacker to effectively exploit, or detect, a weakness in any one key-dependent S-box should it occur.

Some of the individual steps in the algorithm can also be further examined:

Algorithmic Variability

In each round, the algorithm can take one of 16 shapes by the interchange of two transformations applied to the 32-bit quarters of the block. In addition, there are 16 possibilities of using either XOR or bytewise addition in one of those transformations.

These 256 possibilities in each round are the product of four possibilities for the leftmost quarter of the block, which are key-dependent, and 64 possibilities for the remaining three quarters of the block, which are data-dependent.

It might be suggested that more of the variability in the algorithm ought to be key-dependent, since in this way, it could be said that only 2^32 different algorithms are used, and this number is susceptible to brute-force search, if there were some rapid way to solve the rest of the cipher.

However, data-dependence does seem to be stronger than key-dependence, so this does not appear to be a strong objection.

If one ignores the choice between four subkeys in various portions of the round, and the extra algorithmic variation caused by switching between addition or XOR, and only counts the sixteen possibilities in each round, for each of the four quarters of the block, of doing either of two 32-bit transformations first, then the key-dependent part of that involves only 2^16 possibilities. While it might be possible to simply ignore them, by trying an attack based each possibility, as there are 2^48 possibilities for the data-dependent part of that, it would seem that a conventional differential attack (actually, that is a misnomer, as other aspects of the design would require some extension to the original techniques of differential cryptanalysis) would require one to compare known plaintext-ciphertext pairs where the same one of the 2^48 possible algorithms was used.

Of course, as long as a characteristic is strong enough that its chance of occurring by accident is less than one in 2^48, even this is not totally impossible, and the identity of the pairs in which it is seen would then provide additional information.

Byte Interchange

As noted in the description of the algorithm, after each round of Quadibloc VIII, except round 16, the 16 bytes of the block are rearranged from being in the order

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

to being in the order:

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

This particular rearrangement was carefully designed. It has the following properties:

Since the main feature of the cipher is a Feistel round within each half of the block, parts of the block alternate regularly between being on the left and right sides of the f-function as in any normal Feistel cipher.

An irregular pattern of alternation between left and right halves of the block is used, so that for each round, bytes will be brought together in different combinations.

Thus, let us consider byte 5, and where it appears in odd-numbered rounds only, when it is on the right quarter in its half, and thus on the recieving end of the f-function. Let us depict, with the bytes identified by their positions in round 1, the input and output of the f-function, but rotating both by corresponding amounts so that byte 5 appears first on the right quarter, so we see what it looks like from the viewpoint of byte 5.

 1  2  3  4   5  6  7  8  Round  1: left half
12 10  9  1   5 16 14 15  Round  3: left half
12  1 10  3   5  6 15 16  Round  5: right half
 4  1  3 10   5  8  6 16  Round  7: left half
 3  2  1  4   5  6  8  7  Round  9: right half
10 12  1  9   5 14 15 16  Round 11: right half
 1 12  3 10   5 15 16  6  Round 13: left half
 4 10  3  1   5  6  8 16  Round 15: right half

While this only brings the bytes together in four distinct possible configurations, although in different orders in each of the two times, that is still about as irregular as is possible given that the only device available in this uniform and consistent permutation between rounds to bring different bytes together is dispatching them to the other half of the block for differing periods of time.

These are the positions of the bytes in the 16 rounds of Quadibloc VIII:

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

Mixing and Whitening

In addition to complicating analysis by swapping the two basic operations of a two-round Feistel cipher between 16-bit subblocks and a pair of two-round Feistel ciphers between 8-bit bytes, the mixing and whitening phase of the cipher is designed to ensure that without knowledge of the key, it is not possible to determine the path of a single bit through the cipher.

But does this provide blanket protection against differential and linear cryptanalysis? No, I cannot claim that. But because differential and linear cryptanalysis attacks are often only small improvements on brute-force cryptanalysis, even making them only slightly more difficult is worthwhile.

The example given in David Kahn's book The Codebreakers of an amateur cipher that might be wrongly claimed unbreakable may indicate the danger here: it was a form of fractionation, where letters were translated to pairs of digits from 1 to 5 by a Polybius square, and then back to letters after a single digit of padding is added to the beginning. It might be thought impregnable, because nothing is left for the cryptanalyst to grasp. Yet, a Playfair cipher in its most common case consists of switching the column coordinates of a pair of letters, so it can be seen that this cipher is actually similar in difficulty.

If we consider a block cipher with a strong differential characteristic, and then precede and follow it by ICE-style bit swaps, but without the small-scale Feistel rounds also used in Quadibloc VIII, a differential cryptanalysis attack can still be mounted.

If blocks that are identical, except for bit 21 being inverted, on input lead to a particular difference between output blocks that is more likely, then with bit swaps before and after, simply use pairs of blocks that differ only in one bit, but with all possible bits that could be swapped to position 21. The output result would also be jumbled, but the fact that a difference between pairs of output blocks would be the same, even if its shape could not be predicted, would show that the fact about the key indicated by the characteristic was likely to be true.

And, of course, the way in which the characteristic was jumbled would give information about the swap used, which gives additional information about the subkeys.

The use of a MacLaren-Marsaglia construct as the basis for subkey generation, however, makes it difficult to use one or more subkeys as a basis to deduce information about other subkeys.

It should also be noted that the primary design goal of the mixing and whitening phase was to ensure uncertainty about which portion of the algorithm any particular bit would be subjected to, not to provide diffusion, since the conventional rounds provide strong diffusion themselves.

After the first bit swap and mini-Feistel layer, the 16 bytes of the block can be thought of as divided into the following eight independent groups:

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

After the second bit swap and mini-Feistel layer, the number of groups decreases to four:

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

and after the third layer, to two:

1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2

so two groups of 64 bits go through this phase without in any way affecting each other. Since the normal rounds deal with the block in four quarters, the last two bit swaps are sufficient to place an input bit in any part of the normal round; the first bit swap creates a corresponding uncertainty for the mini-Feistel rounds in the mixing and whitening phase itself.

The Key Schedule

Because I aimed at a high level of security for Quadibloc VIII, I tried to ensure that the key schedule was strong. Yet, I still wanted to keep the process of key generation relatively simple.

Thus, from the key, I first produced initial values for four simple shift registers of different lengths. Although there is no guarantee that chain addition will produce a maximal period, the amount of subkey material to be generated, while large, is still limited.

As can be seen from the description of the key schedule, measures were taken to ensure that even with an all-zero key, no shift register would start out with all-zero contents, or contents uniform in other ways.

By using the XOR of the output of two MacLaren-Marsaglia generators, I hoped to make it difficult to use the subkeys to draw any useful conclusions about the shift register contents and hence other subkeys. Using four shift registers, and alternating their roles, also helps to limit the consequences if, for some key, one of the shift registers begins producing a sequence of poor quality.

However, the key augmentation and key revision phases were added to provide a key schedule that should be completely safe.

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

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