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

# 3-Way

The diagram to the right fully describes both the algorithm and the key schedule of the block cipher 3-Way, as designed by Joan Daemen (his first name is simply a variant of "John", closely related to "Johann", and is presumably pronounced something like "Yo-ahn"), so nothing more needs to be said.

Well, perhaps it isn't quite that simple. A few things need to be noted. For example, the recommended number of rounds for 3-Way is 11, it has a 96-bit block size and a 96-bit key size, and the diagram at the right depicts a single round, and the step involving XORing the key and the round constant to the block is repeated one extra time after the last round, as well as the first unkeyed step designated as "theta"; the extra use of theta is required so that encipherment and decipherment will be related in a simple fashion.

One way to implement decipherment with 3-Way is to implement it as encipherment with a modified key schedule, preceded and followed by a step reversing the order of all the bits in the 96-bit block; this is the scheme shown in the C code given in Bruce Schneier's famed book Applied Cryptography. The reason the bit reversal step is needed, of course, is due to the structure of the "pi-1" and "pi-2" steps shown in the diagram; also, the matrix multiply in the "theta" step is necessarily such that its transpose is its inverse for this to work.

The Galois-configuration shift register shown in the diagram with its starting value is indeed what is used to produce the 16-bit round constants used to protect the cipher against slide attacks.

As can be seen from the diagram, a round consists of a number of distinct steps.

The first step is the XOR of key material with a round constant. Since the key material is simply the entire key, with the exception of the round constant, the key schedule is very simple. Of course, SKIPJACK has an even simpler scheme of round constants.

The round constants for the eleven rounds, and the final additional key XOR operation, of 3-Way are:

``` 1) 0000 1011 0000 1011     0B0B
2) 0001 0110 0001 0110     1616
3) 0010 1100 0010 1100     2C2C
4) 0101 1000 0101 1000     5858
5) 1011 0000 1011 0000     B0B0
6) 0111 0001 0111 0001     7171
7) 1110 0010 1110 0010     E2E2
8) 1101 0101 1101 0101     D5D5
9) 1011 1011 1011 1011     BBBB
10) 0110 0111 0110 0111     6767
11) 1100 1110 1100 1110     CECE
12) 1000 1101 1000 1101     8D8D
```

Were one more round added to the cipher, the shift register producing the round constants would produce:

```    0000 1011 0000 1011     0B0B
```

so the symmetry does not break down, but the period is not maximal.

The second step, called theta, is a matrix multiplication using XORs; it is indeed a matrix multiplication, modulo 2, carried out in parallel eight times, for each of the eight bits each of the twelve bytes in the block contains. This use of matrix multiplication was, of course, echoed in Rijndael, of which Joan Daemen was one of the designers, although in the case of Rijndael, Galois Field multiplication rather than a simple XOR was used.

The matrix multiplication involves the matrix:

``` 1 1 1 1  0 0 1 0  0 1 1 0
0 1 1 1  0 0 0 1  1 0 1 1
1 0 1 1  1 0 0 0  1 1 0 1
0 1 0 1  1 1 0 0  1 1 1 0

0 1 1 0  1 1 1 1  0 0 1 0
1 0 1 1  0 1 1 1  0 0 0 1
1 1 0 1  1 0 1 1  1 0 0 0
1 1 1 0  0 1 0 1  1 1 0 0

0 0 1 0  0 1 1 0  1 1 1 1
0 0 0 1  1 0 1 1  0 1 1 1
1 0 0 0  1 1 0 1  1 0 1 1
1 1 0 0  1 1 1 0  0 1 0 1
```

The matrix multiplication has a structure that allows it to be implemented in terms of shifts and XORs of 32-bit words. Note that since the diagram shows an operation with rows in, and column sums out, it follows the opposite convention to that of normal matrix multiplication, and thus the arrangement of XOR cells in the diagram appears to follow the transpose of this matrix.

The third step, pi-1, now provides diffusion between the bits of the bytes by performing two different rotations on two of the 32-bit subblocks of the 96-bit block.

In this step, the first 32-bit subblock is rotated 10 bits to the right, and the third 32-bit subblock is rotated 1 bit to the left. The second subblock is not modified.

The fourth step, gamma, applies a nonlinear S-box with three inputs and three outputs to corresponding bits of the three subblocks. This construct was later used in the AES candidtate SERPENT, but with a larger S-box having four inputs and four outputs.

Each bit is XORed with the OR of the next bit and the inverse of the bit after that, leading to an S-box with the table:

```000 | 111
001 | 010
010 | 100
011 | 101
100 | 001
101 | 110
110 | 011
111 | 000
```

In effect, combinations with all three bits the same are inverted; combinations with a single 1 bit are rotated one place left; combinations with two 1 bits are rotated one place right, making the operation both invertible and nonlinear. Reversing the order of bits in input and output doesn't change the number of 1 bits, but it does reverse the direction of the rotations, so this provides the inverse as well.

The fifth step, pi-2, provides diffusion between bits, as well as maintaining the symmetry that relates decipherment to encipherment.

Here, it is the first 32-bit subblock that is rotated 1 bit to the left, and the third 32-bit subblock that is rotated 10 bits to the right.

Because of the small size of the S-box, 3-Way is likely to be vulnerable to the attack of Courtois and Pieprzyk which was initially proposed as usable against Rijndael and SERPENT.

### Decipherment

The cipher 3-Way is very ingeniously designed to serve as its own inverse subject to two modifications to the algorithm in addition to modifications to the key schedule. The theta and gamma operations both become their own inverses when the 96 bits of the block are handled in reverse order, and pi-2 with bits reversed becomes the inverse of the original pi-1, and so on.

To invert a cipher, one has to perform the inverses of each of the steps in reverse order. The fact that the XOR of the key precedes the theta step is the only complication; in addition to being used in reverse order, and with bits reversed, the key for each round must go through the theta step.

Because both bytes of each round constant are identical, the theta matrix, having an even number of ones in the first two and last two cells of each row except the first two and last two, avoids diffusing the round constants. This allows the 96-bit key to be subjected to the theta matrix for decipherment, and then to have its bits reversed, with simply a different set of round constants being XORed to it for decipherment. (When I first saw this in the C code for 3-Way in Applied Cryptography, I had thought this an error, so subtle and ingenious was the design of 3-Way.)

The round constants for decryption are:

``` 1) 1011 0001 1011 0001     B1B1
2) 0111 0011 0111 0011     7373
3) 1110 0110 1110 0110     E6E6
4) 1101 1101 1101 1101     DDDD
5) 1010 1011 1010 1011     ABAB
6) 0100 0111 0100 0111     4747
7) 1000 1110 1000 1110     8E8E
8) 0000 1101 0000 1101     0D0D
9) 0001 1010 0001 1010     1A1A
10) 0011 0100 0011 0100     3434
11) 0110 1000 0110 1000     6868
12) 1101 0000 1101 0000     D0D0
```

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