Generalized Feistel networks

From CryptoWiki
Jump to: navigation, search

Background. Feistel ciphers have several varieties in addition to the "classical" one, used in the DES [FNS75] [W99]. In particular, these are as follows: unbalanced Feistel networks with either expanding or contracting round functions as described by Schneier and Kelsey [SK96]; ]; alternating Feistel networks in which steps alternate in expanding and contracting rounds described by Anderson and Biham [AB96] and Lucks [L96];Feistel networks of type 1, 2 and 3 described by Zheng, Matsumoto, and Imai[ZMI90], each of which uses an n-bit to n-bit round function to create a kn-bit blockcipher for some k> = 2; and numerical variants of already described networks where numbers are encrypted in ZN, for some N ∈ N, instead of encrypting binary strings. The well-known block ciphers using generalized Feistel networks include Skipjack (unbalanced), BEAR/ LION (alternating), CAST-256 (Type 1), RC6 (type 2) and MARS (type 3).

Contents

Generalized Feistel networks

Generalized Feistel networks: one method of constructing block ciphers. The encryption algorithm is implemented in several iterations of the network transformation with MK key. The value of the method lies in the fact that the transformation of the Feistel network is reversible. The generalized Feistel networks are characterized by the fact that the input word is split into two or more sub-words, part of which is converted at each round under a specific law. If the lengths of sub-words coincide, such network is called balanced.

The Generalized Feistel Flavors

Feistel network analysis

Feistel network analysis proving their security began with the fundamental work of Luby and Rackoff [LR85]. It is supposed that r of the used round functions are selected independently from each other, uniformly and randomly (r = 3 and r = 4 [LR85]). Next, we consider how the resulting cipher is close to a random permutation. Further work in this information-theoretic direction (analysis of the classical Feistel structures) includes studies by Maurer [M93], Naor and Reingold [NR97], Vaudenay [V98], Maurer and Pietrzak [MP03], and several works by Patarin [P98][P01][P03][P92][P04]. The last of them ends with a statement that 6 rounds of (classical) Feistel cipher using the 2n-bit string is sufficient to prevent (i.e. the advantage tends to 0 as n → ∞) adaptive attacks using the known ciphertext for Киселева ОСФ10.JPGrequests for any ε> 0.

Balanced generalized Feistel network with r rounds

Let us consider a balanced scheme of generalized Feistel network with r rounds. The plain text P, cipher text C have the length of N bits, the key MK - M bit. The plain text is represented as n of m-bit sub-words ОСФ001.JPGОСФ002.JPG — intermediate cipher text after the i-th round, where i = 1, 2,. . . , r; ОСФ003.JPG- nonlinear round function. Round sub-ОСФ004.JPGof k bit length are uniquely defined by the MK key. The encryption process is carried out as follows.

1. The input plain text ОСФ001.JPG

2. For i from 1 to r 'ОСФ006.JPGОСФ007.JPG

3. The output cipher text ОСФ008.JPG

Generalized Feistel networks on the example of SMS4

Algorithms based on generalized Feistel networks

RC6

Cipher RC6 is presented by a group of developers led by the world known figure in the field of cryptography Ronald Rivest. Cipher is a Feistel network of 20 rounds with 4 mixed branches, such as - the result of forming functions computed by even branches, then superimposed on the odd branch, then the exchange of branch locations is made.

General view of the RC6 algorithm RC6
RC6 algorithm round RC6
T conversion - is a function: F (X) = LOW_32 (X × (2 × X + 1)) with 32-bit result (only 32 least significant bits of the result of multiplication return).

Multiplication operation exhibits good mixing capacity and this property is used at a maximum level in RC6. As can be seen from the scheme, the multiplication result comes as the cyclic shift parameter to a variable number of bits, cyclically shifted to the left by 5 bits, i.e. the actual value of the alternating shift is determined by the 27 ... 3th bits of the result of 32-bit multiplication - and these bits are those, which are in the centre of a 64-bit multiplication and, therefore, depend on all bits of the input parameter X. The feature of T conversion is its bijective capacity, i. e. reversibility – mutually univocal correspondence between the operand and the result. Such an operation is bijective and following it imposition of the multiplication result to the XOR-variable branch "carries" on it all 32-bit data capacity of the unchanged branch. RC6 encryption algorithm is performed by inverting the order of operations executed in the Feistel network and replacing the operation of addition to subtraction. Due to the mixed type of network environment and simplicity of the algorithm generally RC6 decryption is easier to implement as a separate item of the program block. [BT10]

MARS

MARS is an algorithm developed by IBM company. It is a block cipher, the block size is equal to 128 bits and it has a variable key length. It is a traditional Feistel network of type 3 with 4 branches. However, to increase the resistance of the cipher to the known and possibly new schemes of cryptanalysis developers much more complicated input and output transformation of Feistel network. As a result, the entire encryption process can be represented by the following successive transformations.

1 Pre-position of the key: 4 fragments of extended key ОСФ010.JPG are applied for 32-bit sub-blocks A, B, C, D through modulo addition ОСФ012.JPG.

2. 8 rounds of forward mixing (without the encryption key) are performed.

3. 8 rounds of forward cryptographical transformation are performed.

4. 8 rounds of backwards cryptographical transformation are performed. Stages 3 and 4 are called "cryptographic core" of the MARS algorithm.

5. 8 rounds of backwards mixing without the encryption key are performed.

6 Final application of extended key fragments ОСФ011.JPG through the modulo subtractionОСФ012.JPG.

Structure of the algorithm MARS.

The algorithm is an extended Feistel network. In each round processing of one of the sub-blocks is performed and the application of the processing results to the rest of sub-blocks, then the sub-blocks are rotated. Type of transformation depends on the type of the round.

Round of forward mixing of the algorithm MARS.

Round of forward mixing is the following:

1. The value of A sub-block is run through the replacement table S0 and is applied to the B sub-block through the XOR operation.

2 The initial value of A sub-block is rotated to the right by 8 bits.

3 The result of the previous step is processed by the replacement table S1 and again is applied to the B sub-block through the addition modulo ОСФ012.JPG.

4 The result of step 2 is rotated by 8 bits to the right.

5 The result of the previous step is processed by the replacement table S0 and applied to the sub-block C through the operation of addition modulo ОСФ012.JPG.

6 The result of step 4 is rotated by 8 bits to the right.

7 The result of the previous step is processed through replacement table S1 and is applied to the sub-block D through the XOR operation.

8 The sub-blocks are rotated.


Round of forward mixing of the algorithm MARS.

The basis of the round is extensible cryptographical transformation E, which converts 32-bit input word A into three output 32-bit values, each of which is a certain way applied to the rest of the sub-blocks. After that the sub-unit A is rotated to the left by 13 bits, and then the sub-blocks are swapped round similar to the forward mixing round.

cryptographical transformation E of the algorithm MARS.
Backwards cryptographical of the algorithm MARS.

Backwards cryptographical transformation differs from forward cryptographical round only by the changed order of applying the output values of transformation E O1 ... O3 to the words B, C and D.

The round of backwards mixing of the algorithm MARS.

The round of backwards mixing is substantially different from the forward one. In fact, backwards mixing performs the reverse operations in the reverse order:

1 The value of A sub-block is run through the replacement table S1 and is applied to the B sub-block through the XOR operation.

2 The initial value of A sub-block is rotated to the left by 8 bits.

3 The result of the previous step is processed by the replacement table S0 and is applied to the C sub-block through the subtraction modulo ОСФ012.JPG.

4 Result of step 2 is rotated by 8 bits to the left.

5 The result of the previous step is processed by the replacement table S1 and applied to the sub-block D through the operation of subtraction modulo ОСФ012.JPG.

6 Result of step 4 is rotated by 8 bits to the left.

7 The result of the previous step is processed through replacement table S0 and is applied to the sub-block D through the XOR operation.

8 The sub-blocks are rotated

[B99]

CAST

The CAST-256 algorithm encrypts data with 128-bit blocks and uses multiple fixed encryption key sizes: 128, 160, 192, 224 or 256 bits. 128-bit block data is divided into 4 sub-blocks of 32 bits, each of which in each round is subjected to specific transformation algorithm and is applied to one of the neighboring sub-blocks. During the execution of the algorithm 12 rounds of transformations are performed, in the first 6 of which t1 transformation is made - forward function of the round, and in the last 6 rounds the t2 round function is executed.

t1 transformation
t2 transformation

The t1 function is described as follows: ОСФ019.JPGwhere i – number of the current


The t2 transformation consists of the following operation: ОСФ020.JPG

The functions f1, f2 and f3 perform several elementary operations of 32-bit sub-block. Each function takes three parameters:

- value of the processed sub-block

- 32-bit sub-key of the round ОСФ021.JPG(masking sub-key)

- 5-bit sub-key of the round ОСФ022.JPG (sub-key of the shift)

Addition and subtraction are performed by the 32-bit operands modulo ОСФ012.JPG.Functions S1, S2, S3 and S4 are table substitutions, replacing the input 8-bit value to 32-bit one. [W99]

The functions f1, f2 and f3 presented on figure: function f1function f2 function f3

Glossary

Bibliography

Go to Reference.

Back

Kiseleva A., 2015