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

The Decorrelated Fast Cipher

The Decorrelated Fast Cipher is an eight-round Feistel cipher with a somewhat different f-function. It uses one S-box, with bits taken from the expansion of e, having 64 entries, each 32 bits long.

The original version of its specification is available on its designer Serge Vaudenay's web site.

The arrangement of the Feistel rounds is like that of DES, with halves swapped after all rounds but the last one.

The f-function has two steps.

First, two 64-bit subkeys (considered as two halves of a single 128-bit round subkey) are applied to the right half of the block by multiplication and addition, modulo 2^64+13. Then the last 64 bits of the result are used.

Then, the right and left halves of the 64-bit result are swapped. The new left half has an S-box entry, chosen by the rightmost 6 bits of the new right half, XORed to it. The new right half is only XORed with a constant.

Finally, the 64-bit result has a 64-bit constant added to it.

Although this description is short and simple, using multiplication with an odd modulus in the f-function ensures that every bit of the f-function output depends on every bit of its input.

More importantly, the use of both multiplication and addition has an important property, which explains the meaning of the word 'decorrelation' in the name of this cipher, and which also is connected with the use of Galois field multiplication in some other ciphers in this section, such as Rijndael and Twofish.

Because of the distributive property involving both multiplication and addition, that a*x + a*y = a*(x+y), thus multiplication distributes over addition, the following is true:

Let us suppose the input p produces the output q, and r produces the output s, after being first multiplied by a and then having b added to it. If you change a, and then change b so that p still produces q, r can produce anything, because the difference between q and s is proportional to the multiplier a.

This also works when Galois field multiplication is used, with XOR taking on the role of addition. This subject is more extensively discussed in a section entitled A Note on the Importance of the Galois Field.

In the case of multiplication modulo 2^64+13, followed by truncation to 64 bits, the property is only followed approximately, and with Galois field multiplication, one cannot include zero as a multiplier.

Using two additions, separated by an S-box corresponding to a permutation corresponding to wiring a rotor by the interval method seems like it might work, since a somewhat similar property is involved. But the property is not the same, since it involves adding something to one of the two values considered instead of to both. However, note that multiplication under a prime modulus is isomorphic to addition, so there are S-boxes that would approximate this property for two additions.

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

Chapter Start
Table of Contents
Home Page