A Better Round Transformation

By Larry Loeb  |  Posted 2005-10-03 Print this article Print

Down with the Feistel Structure! In most ciphers, the round transformation has the well-known Feistel Structure. In this structure typically part of the bits of the intermediate state are simply transposed unchanged to another position. (Those tables we discussed back in the part about DES that substitute bits by a fixed tabular means are an example of this linear kind of structure.) The round transformation of Rijndael does not have this venerable Feistel structure, in which half the data block is used to modify the other, the two change places.
Instead, the round transformation is composed of three distinct invertible uniform transformations, called layers. (Uniform means here that every bit of the state is treated in a similar way.)
The linear mixing layer guarantees high diffusion over multiple rounds. The non-linear layer uses parallel application of S-boxes that have the desired (hence, optimum) worst-case nonlinearity properties. The S-boxes are non-linear. Thats the key conceptual difference between DES and Rijndael. The key addition layer is a simple EXOR of the Round Key to the intermediate State, as is noted below. The round transformation is composed of four different transformations. In pseudo C notation they are: Round(State,RoundKey)
{ ByteSub(State);
(EXORing a Round Key to the State) } The final round of the cipher is slightly different. It is defined by: FinalRound(State,RoundKey)
{ ByteSub(State) ;
ShiftRow(State) ;
} In this notation, the "functions" (Round, ByteSub, ShiftRow, …) operate on arrays to which pointers (State, RoundKey) are provided. The ByteSub Transformation is a non-linear byte substitution, operating on each of the State bytes independently. In ShiftRow, the rows of the State are cyclically shifted over different offsets. In MixColumn, the columns of the State are considered as polynomials over GF(2^8) and multiplied modulo x^4 + 1 with a fixed polynomial c( x ), given by c( x ) = 03 x^3 + 01 x^2+ 01 x + 02. This polynomial is coprime to x^4 + 1 and therefore invertible. The Round Keys are derived from the Cipher Key by means of the key schedule. This has two components: the Key Expansion and the Round Key Selection. The total number of Round Key bits is equal to the block length multiplied by the number of rounds plus 1. (e.g., for a block length of 128 bits and 10 rounds, 1408 Round Key bits are needed). The Cipher Key is expanded into an Expanded Key. Round Keys are taken from this Expanded Key in the following way: the first Round Key consists of the first Nb (Nb = block length ) words, the second one of the following Nb words, and so on. The cipher consists of: an initial Round Key addition, Nr-1 Rounds, a final round. In pseudo C code: Rijndael(State,CipherKey)
{ KeyExpansion(CipherKey,ExpandedKey) ;
For( i=1 ; i FinalRound(State,ExpandedKey + Nb*Nr);
} If the key expansion is done beforehand the cipher can be specified in terms of the Expanded Key. Rijndael(State,ExpandedKey)
{ AddRoundKey(State,ExpandedKey);
For( i=1 ; i FinalRound(State,ExpandedKey + Nb*Nr);
} Since Rijndael is invertible, the deciphering process just reverses the steps described above. Technical details can be found in the Rijndael specification. In closing, developers would do well to consider how to integrate the security advances that will follow the widespread use of Rijndael as a cryptoalgorithm. AES will soon supplant DES as the standard demanded by the general business community, and the art of the field will no doubt follow.


Submit a Comment

Loading Comments...
Manage your Newsletters: Login   Register My Newsletters

Rocket Fuel