Generalized Rijndael, schematics

Before to enter in deep on the questions remarked in the previous post about this series, I like to post some schemas that some day would be useful.

The Rijndael symmetric cryptosystem build by iteration using a network of permutations who follows the basic shannon's properties of "confusion and diffusion". The bits in the plain text are mixes and substituted by a group of operations do by an order. To decrypt, what have to be done is to do the same things but in the opposite way. For sure, there is a key to introduce here the secret to be able to undo the encrypt operation.

Diagram 1: Flow of the Rindael encrypt/decrypt

As in the diagram 1 shows, using only 4 operations (subBytes, shitfRows, mixcolumns, addRoundKey, and its inverses). But those operations are in a certain order to maintain a set of properties.

• subBytes: word substitution, where each element in the state matrix is replaced by its inverse and an affine mapping. Operations in
• shiftRows: cyclic left shift of the elements of the i'th row by i words.
• mixColumns: column linear transformation of the state matrix, where each column is given as an element of a polynomial ring, where the coefficients of this polynomial are polynomials in .
  This polynomial ring is: 
• addRoundKey: XORed transformation between the state matrix and the round key.

Is necessary to emphasize the use of a part of the key in the 'addRoundKey()' operation. This round key is much longer than the given key to encrypt/decrypt, and the process to generate this key expansion can be described in a iterative way:

Diagram 2: Iterator schema of the Rijndael key expansion

The first 4x4 matrix (the ) is the original key given with in a structure of a matrix of elements in the wordsize (8 bits, a byte in rijndael, AES). This example is using the 128 key option but the key matrix can have more columns: To build the key expansion its the same way, but remark that "#c" represents the number of columns for the message, not the key.

To build the following columns to have each round keys, an iterator is good to see how this is made. I have tried to get an schema from other webs sites, but the ones that I found haven't convinced to me. I hope this would help to someone who search on internet for a diagram of the rijndael key expansion.

Generalized Rijndael, a review

After a too long period of time with out working on this project I like to recover it.

I did a python implementation, that will be publish as free software (GPL) who is able to change the usual parameters of the Rijndael to work in a very different way than the 3 options of the standard. As a review:

Rijndael variable parameters:

• Number of rounds
• Number of rows
• Number of columns
• Wordsize (in bits)
• Number of columns in the key

The 3 standard sizes are: {10,4,4,8,4}, {12,4,4,8,6}, {14,4,4,8,8} and this means:

• Block size always 4x4 elements of 8 bits 128 bits
• Key size can have 4, 6 or 8 columns 128,192,256 bits
• And depending on this key size the number of rounds varies from 10, 12 or 14.

But this can be changed easily by something like: {40,2,2,8,8} and this means a Rijndael of 32 bits block with keys of 128 bits (doing 40 rounds, but this was set like this in the experiment because other small block ciphers have values like this).

But what means internally to the algorithm this change?

• A new irreducible polynomial is need for the mixColumn() transformation, because the polynomial ring have the same number of coefficients than the number of rows.

Are there other options in Rijndael to get this combination? Yes: this would be equivalent to {40,4,4,2,16} and what does this mean?

• A new Rijndael SBox must be build: the original is made to apply a substitution of works of 8 bits.

Pending demonstrations:

• Is the generalized Rijndael still a Pseudo-Random Permutation (PRP)
• How to build secure SBoxes?
• How to get irreducible polynomials to be able to change the number of rows?
• Is the invertible circulant matrix also valid for polynomial rings over , with ?
• How to calculate the number of rounds necessary? Not less than need to be insecure, but not more to do superfluous calculations.

Generalized Rijndael, an approach

Following the idea of the first post about a Generalized Rijndael, I have started an implementation with some constants of the standard implementations becomes variables.

An schematic for the Rijndael would be:

This operations uses a state matrix, it's the data structure who receives the transformations during the (de)cipher process. This state matrix, in the AES, contains words of 8 bits in a 4x4.

First of all the input (of 128 bits) is cut in this basic words of 8 bits:

There are two ways to modify the size of the input: change the size of the matrix or change the size of the word. Following the article Small Scale Variants of the AES, the two options to reduce the input size from 128 to 32 bits under a Rijndael model:

• Reduce the state matrix to 2x2 (in the AES is 4x4)
• Reduce the word size to 2 bits (in the AES is 8 bits)

But, what's the best way? And there is another question, how big would be the key?

In the AES there are 3 options: 128, 192, 256 bits:

This matrix will be the input of a keyExpansion() function to have the segments of this key to be used in each part of the rounds. 

Why this sizes? Like many of the times, the choice of this 3 sizes corresponds to standardisation reasons like set a small but enough number of them to choose. The original Rijndael supports much more options: you can set a key of 512 bits and structure it into 16 columns in the key matrix. Even 1024 bits key, with 32 columns, the key expanded will still be 44 elements if the number of rows and the number of rounds are still the same.

Furthermore, with a 128 bits block of plain text and key (matrix 4x4 and word size 8) there would be 40 rounds instead of 10. In this case the key expansion will have 164 elements instead of the 44 of the standard. (the number of elements in the key expansion is #columns*#rounds) 

But how to define this parameters in the good direction? Can be the number of rounds be less with in a safety way? Or can some day be necessary to increase this number?

The Rijndael have a good performance over 32 bit hardware. The word size of 8 bits together with the 4 rows who gives 32 bit operation in the ring: . But in deep, the most powerfull feature of the Rijndael from the computation point of view is that it works in the very basic and that means binary.

I hope I'll write soon answering this questions.

Generalization of Rijndael, an introduction

Long time a go I have received a request to prepare a system to encode some data in barcodes. I thought in two options: symmetric cryptography or hash algorithm. But, there where two requirements: "non collision (in between the same key)" and "recover information from the code". Then the choose is made, they can only complained by the symmetric algorithms.

The first symmetric algorithm was to simply operate with an xor operation. But this, as a Vernam type algorithm, is more to a stream ciphering or a one-time pad. Basically means is not the correct algorithm if a key is used more than one time.

To think in the block symmetric algorithms, the old DES, the new AES or any of the finalists in the trial are candidates. I have decided for the Rijndael, the winner of the AES contest. Usually the input/output size on the symmetric algorithms must be as big as possible because the data to cipher is much bigger. For example, in the implementations of the public key cryptosystems is usual to do a hybrid system, and the data is very big. Usually the problem on the symmetrics is to interlace the blocks to avoid patterns between them.

One of the goodness of the Rijndael is the capacity of extension, bigger of smaller. The state matrix, in the standard is 4x4, but the number of rows and columns can be changed. Even more, they can be different between them. The word size, is 8 bits (having operations in 32 bits because 8 bits * 4 elements in a column), but it's possible to do Rijndael with different word sizes.

In the application about I'm working the block size will be below 128 bits, but is not fix having the idea of 64 bits block size. DES is 64 bits block (54 bits effective key size). But why to use a replaced algorithm having the possibility to adapt the Rijndael? Even more, with Rijndael the key size can be also adapted to the needs. But in crypto, any modification must have a previous process of deep think, and a post-process of forever-think.

The Triple-DES was an extension to make bigger the key sizes like 112 or 168 (56 plus 2 or 3 of the simple-DES), and there is an extension for the AES with the name AESWrap (the rfc3394), what can be thing like a sextuple-AES.

There is a difference between DES and AES, and between Triple-DES and the AESWrap. The Rijndael is not only using the key, is also doing an expansion of this key to have more bits as a key. Furthermore, the AESWrap is doing a key derivation function to introduce more dispersion and confusion.

Lets go in the first step of this project: A Generalization of Rijndael to have the data block size parametrizable, also the key size and the number of rounds.

Lets start from the simplification, how to do an Small Rijndael Variant? I have found two articles very helpful on that task:

• Mini Advanced Encryption Standard (Mini-AES): A Testbed for Cryptanalysis (2002) by Raphael Chung-wei Phan
• Small Scale Variants of the AES (2005) by C. Cid , S. Murphy , M. J. B. Robshaw

One book for cryptography developers:

• Cryptography for Developers by Tom St. Denis

And the mandatory books for Rijndael:

• AES Proposal: Rijndael (v2) by Joan Daemen, Vincent Rijmen
• The Design of Rijndael AES - The Advanced Encryption Standard  by Joan Daemen, Vincent Rijmen