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

Quadibloc XII

Quadibloc XII is a block cipher designed with one goal in mind as completely paramount. It must be possible to memorize the cipher, so that one can code an implementation of it at any time in any place one has access to a reasonably programmable computer.

It's still designed around binary input and output, in order to fill the role of a standard 'block cipher', so it does exclude the case where you have access to a computer programmable in a language that only allows numerical operations but not bitwise AND and XOR, as is the case in some early database languages: but I've added a decimal version of the cipher for this case.

To achieve this one overriding goal, both the security and the efficiency of this cipher have been significantly compromised. It is hoped, however, that the security remains adequate. Although based on a simple algorithm I suggested in response to a request for something like this, it has been modified to improve its prospects of security; I am indebted to suggestions made in the discussions about that design for the nature of the changes.

Example source code is not provided for a reason that should be obvious: the only way to memorize this cipher is to understand the algorithm, and attempt to code it.

Key Generation

To get bytes that appear random for the subkeys of this cipher, we use a nonlinear shift register as a "raw generator", and it feeds into a 256-byte buffer which is used in the degenerate MacLaren-Marsaglia scheme seen before in some earlier ciphers in the Quadibloc series.

The Raw Generator

Think of your key (which doesn't have to be exactly 26 bytes long) as being placed in a row of bytes labelled:

a b ... w x y z

Running the raw generator to produce one byte consists of two steps:

Step 1: calculate

((x * y) + 1) xor z

where the multiplication and addition are done modulo 256.

This result is the output value for the raw generator.

Step 2: shift the values in the shift register, introducing the raw generator output value as follows:

     y -> z
     x -> y
     w -> x
...
     a -> b
output -> a

The full generator

Use an array with 256 spaces in it, numbered from 0 to 255.

Initialize it by filling it with 256 values from the raw generator.

To generate one subkey byte, do the following:

Step 1: generate one byte with the raw generator. Use that byte as a pointer to the array. Save the pointer for the next step. The value in the array in the spot the pointer is pointing to is the output from the full generator.

Step 2: generate another byte with the raw generator. Put that value in the array, at the same position from which the byte used as the output was taken.

The key schedule

The first 256 bytes generated are a non-bijective S-box. This S-box, with 8 bits in and out, is called the small S-box; the large S-box is a fixed (and therefore not key-dependent) mathematical function with 16 bits in and out. Then, 32 subkeys are generated, each one 16 bytes long. In each case, the first byte generated for a subkey is the leftmost and most significant byte.

The Block Cipher

A block cipher needs a nonlinear f-function to be secure. It is difficult to memorize a large S-box, so the f-function is based on two components: a small S-box that is generated from the key in a simple fashion, and a simple nonlinear mathematical function.

The f-function

The middle-of-the-square method, used by John von Neumann as a pseudorandom number generator in the early days of computing, is the basis of this cipher. While poor as a PRNG, because it settles down into a short period, this does not affect its use as an S-box, although it is imperfect for that purpose as well.

For a halfword value from 0 to 65535, called h, the large S-box is the function:

( ( h * h ) / 256 ) and 65535

It is biased, but it is nonlinear and without an obvious pattern.

The output of the large S-box with the 16-bit value as input is XORed with the input value, with its bytes individually substituted using the key-dependent small S-box, and swapped. Swapping the bytes provides the diffusion which is "missing" from the middle of the square function, which diffuses the MSB of the input only to the first half of the output, and which diffuses the LSB of the input only to the second half of the output.

Note that a pair of bytes, when taken as a halfword numerical value, always has the value:

 first byte * 256 + second byte

that is, a consistent big-endian interpretation is to be given to values.

Thus, the f-function looks like this:

         ----- -----
        |     |     |
         ----- -----
           |     |
           |     |----------------------------
           |---- | -----------------          |
           |     |                  |         |
            -----                   |         |
              |                   -----     -----
           -------                | S |     | S |
           |   2 |                -----     -----
           |  x  |                  |         |
           -------                   --     --
              |                        \   /
      -----------------                 \ /
     |     |     |     |                 \
     |     |     |     |                / \
   ----- ----- ----- -----             /   \
  |     |     |     |     |          --     --
   ----- ----- ----- -----          |         |
           |     |                  |         |
           |     |                  |         |
          XOR<----------------------          |
           |     |                            |
           |    XOR<--------------------------
           |     |
         ----- -----
        |     |     |
         ----- -----

The Basic Transformation

This f-function is used to perform an invertible substitution on groups of four bytes using a two-round Feistel cipher.

First, you use the first of the two 16-bit halfwords as input to the f-function, and you XOR the result with the second 16-bit halfword.

Then, you use the second of the two 16-bit halfwords as input to the S-function, and you XOR the result with the first 16-bit halfword.

This looks like the following:

halfword 1        halfword 2
  |                 |
  |-----S--------->XOR
  |                 |
 XOR<--------S------|
  |                 |
halfword 1        halfword 2

The Rounds

The cipher alternates between two kinds of rounds. There are sixteen main rounds, and fifteen in-between rounds. They alternate, with the first and last rounds being main rounds.

In a main round:

  1. XOR every halfword of the block with two subkey bytes. This is done by using the subkey bytes in order. Thus, in the first round, the first halfword of the block is XORed with the halfword formed by taking subkey byte 1 times 256 plus subkey byte 2.
  2. Transform the halfwords of the block in pairs. Thus, halfwords 1 and 2 are transformed, then halfwords 3 and 4, then halfwords 5 and 6, and finally halfwords 7 and 8.
  3. XOR every halfword of the block with two subkey bytes.

In an in-between round:


1) Every halfword of the block can also be considered as two bytes. A halfword value always equals (256 times the first byte) plus the second byte. This is called 'big-endian' byte order.

Move the bytes of the block around so that each group of four bytes that was involved in a transform previously is scattered, so that each byte now participates in a different transform, and so that each of the four bytes to participate in a transform will have come from a different previous transform.

To do this, and also to ensure that bytes alternate strictly between being on the left and right sides of the f-function, the same basic method as used in the Shift Row step of Rijndael will be used, but in this case, it will be applied to columns; if we think of the bytes as originally having the order:

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

we will now move them so that they are in this order:

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

Thus, of the four bytes in a group of four bytes, the first remains in place, the second is moved to the corresponding position in the next group, the third is moved to the corresponding position in the group two groups ahead, and the fourth is moved to the corresponding position in the previous group.


2) Transform the halfwords of the block in pairs.


3) Change the order of the bytes in the block in the same way as before.


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

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