Mini AES Process

Mini Advanced Encryption Standard (Mini-AES):

A Testbed for Cryptanalysis Students

Raphael Chung-Wei Phan

ADDRESS: Swinburne Sarawak Institute of Technology, 1st Floor, State Complex, 93576 Kuching, Sarawak, Malaysia. rphan@swinburne.edu.my

ABSTRACT: In this paper, we present a mini version of Rijndael, the symmetric-key block cipher selected as the Advanced Encryption Standard (AES) recently. Mini-AES has all the parameters significantly reduced while at the same time preserving its original structure. It is meant to be a purely educational cipher and is not considered secure for actual applications. The purpose is such that once undergraduate students and amateur cryptanalysts have grasped the basic principles behind how Mini-AES works, it will be easy for them to move on to the real AES. At the same time, an illustration of how the Square attack can be applied to Mini- AES is presented in the hope that Mini-AES would also serve as a testbed for students to  begin their cryptanalysis efforts.

KEYWORDS: Advanced Encryption Standard, Rijndael, Block cipher, Cryptanalysis, Square attack

1          Introduction

The National Institute of Standards and Technology (NIST) issued in 1997 a call for  proposals for the Advanced Encryption Standard (AES) [7]. Twenty one proposals were submitted, out of which 15 were accepted. Two years later, after undergoing public review and analysis, the list was narrowed down to 5 finalists, and more extensive analysis ensued.   In October 2000, Rijndael emerged as the winner and was selected as the Advanced Encryption Standard [8]. The specifications of the AES are now available as a Federal Information Processing Standard (FIPS) [9].

The AES has a block size of 128 bits, and supports key sizes of 128, 192 and 256 bits. The number of rounds is 10, 12 or 14 for the three different key sizes respectively. Just like the DES, the AES is expected to draw much attention from cryptographers and cryptanalysts alike within the space of time from now until the next few decades. In order to aid undergraduate cryptography students and aspiring cryptanalysts in better understanding the internal workings of the AES, we present a mini version of the AES, with all the parameters significantly reduced while preserving its original structure. This mini version is purely educational and hence it is hoped to aid students in grasping the underlying concepts in the design of Rijndael-like ciphers and also to serve as a testbed for aspiring cryptanalysts to try out various cryptanalytic attacks.

In section 2, we present the mathematical background to help the student in understanding the components of Mini-AES. We then proceed to describe Mini-AES in Section 3. In Section 4, we relate Mini-AES to the real AES. The Square attack, a fairly new cryptanalytic attack popularised by Rijndael is presented in detail in Section 5. We conclude in Section 6.

2          Mathematical Background

Mini-AES has a component, NibbleSub, which operates on a nibble (4 bits) at a time. In addition, another component, MixColumn operates on words of 4 nibbles.  In this section,  we present the mathematical background needed for the reader to have a clearer understanding of the components of Mini-AES.

The Finite Field GF(24)

The nibbles of Mini-AES can be thought of as elements in the finite field GF(24).  Finite  fields have the special property that operations (+,-, ´ and ¸) on the field elements always cause the result to be also in the field. Consider a nibble n = (n3, n2, n1, n0) where ni Î {0,1}. Then, this nibble can be represented as a polynomial with binary coefficients  i.e  having values in the set {0,1}:

n = n3 x3 + n2 x2 + n1 x + n0

Example 1

Given a nibble, n = 1011, then this can be represented as

n = 1 x3 + 0 x2 + 1 x + 1 = x3 + x + 1

□

Note that when an element of GF(24) is represented in polynomial form, the resulting polynomial would have a degree of at most 3.

      Addition in GF(24)

When we represent elements of GF(24) as polynomials with coefficients in {0,1}, then addition of two such elements is simply addition of the coefficients of the two polynomials. Since the coefficients have values in {0,1}, then the addition of the coefficients is just modulo 2 addition or exclusive-OR denoted by the symbol Å. Hence, for the rest of this paper, the symbols + and Å are used interchangeably to denote addition of two elements in GF(24).

Example 2

Given two nibbles, n = 1011 and m = 0111, then the sum, n + m = 1011 + 0111 = 1100 or in polynomial notation:

n + m = (x3 + x + 1) + (x2 + x + 1) = x3 + x2

□

        Multiplication in GF(24)

Multiplication of two elements of GF(24) can be done by simply multiplying the two polynomials.  However, the product would be a polynomial with a degree possibly higher  than 3.

Example 3

Given two nibbles, n = 1011 and m = 0111, then the product is:

(x3 + x + 1) (x2 + x + 1) = x5 + x4 + x3 + x3 + x2 + x + x2 + x + 1

= x5 + x4 + 1

In order to ensure that the result of the multiplication is still within the field GF(24), it must be reduced by division with an irreducible polynomial of degree 4, the remainder of which will be taken as the final result. An irreducible polynomial is analogous to a prime number in arithmetic, and as such a polynomial is irreducible if it has no divisors other than 1 and itself. There are many such irreducible polynomials, but for Mini-AES, it is chosen to be:

m(x) = x4 + x + 1

Example 4

Given two nibbles, n = 1011 and m = 0111, then the final result after multiplication in GF(24), called the ‘product of n ´ m modulo m(x)’ and denoted as Ä, is:

(x3 + x + 1) Ä (x2 + x + 1)         = x5 + x4 + 1 modulo x4 + x + 1

= x2

This is because:

  x + 1                           (quotient) x4 + x + 1  x5 + x4 + 1

+  x5 + x2 + x

x4 + x2 + x + 1

+         x4 +         x + 1

x2                                    (remainder)

Note that since the coefficients of the polynomials are in {0,1}, then addition is simply exclusive-OR and hence subtraction is also exclusive-OR since exclusive-OR is its own inverse.

□

Refer to the Appendix for the table describing the multiplication of two elements in GF(24) modulo x4 + x + 1.

3                    Mini-AES

In order to encrypt messages with Mini-AES, the original input message, called the plaintext  is broken up into blocks of 16 bits each. At any one time, only one plaintext block is encrypted with Mini-AES into ciphertext, after which the next plaintext block is encrypted and the process repeats until all of the plaintext blocks have been encrypted. Mini-AES encryption is done with a secret key of 16 bits. Figure 1 illustrates the process of encrypting the plaintext message with Mini-AES. 

    Mini-AES Components

To make it easier to describe the internal process of the Mini-AES encryption, the input plaintext block of 16 bits, P = (p0, p1, p2, p3) is represented as a matrix of 2 rows and 2 columns of 4 bits (a nibble), as given in Figure 2.

Within the Mini-AES encryption process, there are 4 main components, namely NibbleSub, ShiftRow, MixColumn and KeyAddition. The application of these 4 components in sequence constitutes a round of Mini-AES.

    NibbleSub, g

 NibbleSub is a simple operation that substitutes each input nibble with an output nibble according to a 4 ´ 4 substitution table (S-box), as given in Table 1. The values in Table 1 are in fact taken from the 1st row of the first S-box in DES.

Input	Output		Input	Output
0000	1110		1000	0011
0001	0100		1001	1010
0010	1101		1010	0110
0011	0001		1011	1100
0100	0010		1100	0101
0101	1111		1101	1001
0110	1011		1110	0000
0111	1000		1111	0111

Table 1:  S-box of Mini-AES

The NibbleSub operation is illustrated in Figure 3, where A = (a0, a1, a2, a3) is the input block and B = (b0, b1, b2, b3) is the output.

Example 5

For an input nibble, a0 = 1111, then based on Table 1, the output nibble is b0 = 0111.

        ShiftRow, p

ShiftRow rotates each row of the input block to the left by different nibble amounts. The first row is unchanged while the second row is rotated left by one nibble. This is illustrated in Figure 4, where B = (b0, b1, b2, b3) and C = (c0, c1, c2, c3) are the input and  output respectively.

Example 6

With an input block B = (b0 , b1 , b2 , b3 ), the output block obtained after ShiftRow is C = (c0 , c1 , c2 , c3 ) = (b0 , b3 , b2 , b1 ).

        MixColumn, q

MixColumn takes each column of the input block and multiplies it with a constant matrix to obtain a new output column, as given in Figure 5. C = (c0, c1, c2, c3) and D = (d0, d1, d2, d3) denote the input and output respectively.

Example 7

Let an input block be C = ( c0 , c1 , c2 , c3 ), and the block at the output of MixColumn be D =   ( d0 , d1 , d2 , d3 ). We rearrange the input block as a 2 ´ 2 matrix as shown in Figure 5. Then, taking the first column and multiplying it with the constant matrix in Figure 5, we have the output column:

Hence, d0 = (0011Ä c0 ) + (0010Ä c1 ) and d1 = (0010Ä c0 ) + (0011Ä c1 )

 Similarly, taking the second column and multiplying it with the constant matrix, we obtain:

Hence, d2 = (0011Ä c2 ) + (0010Ä c3 ) and d3 = (0010Ä c2 ) + (0011Ä c3 ). We see that each output nibble is a function of the two input nibbles in that same column.

        KeyAddition, sKi

KeyAddition causes each bit of the input block, D = (d0, d1, d2, d3) to be exclusived-ORed with the corresponding bit of the ith round key, Ki = (k0, k1, k2, k3) to obtain the 16-bit output block E = (e0, e1, e2, e3) as shown in Figure 6.  The round key is derived from the secret key,  K by using the key schedule, which will be described in Section 3.6. For each bit, the exclusive-OR operation causes the output bit to be ‘1’ if the corresponding bits of the input

block and round key are different.  Otherwise, the output bit is ‘0’.

 

Example 8

Given an input block be D = ( d0 , d1 , d2 , d3 ) = 1111 0000 1010 1100, and the round key Ki = ( k0 , k1 , k2 , k3 ) = 0101 0011 1111 0000, then the output block, E = ( e0 , e1 , e2 , e3 ) is:

E = D Å Ki             = 1111 0000 1010 1100 Å 0101 0011 1111 0000

= 1010 0011 0101 1100

        The Mini-AES Key-schedule

In Mini-AES, the 16-bit secret key is passed through a key-schedule to produce one 16-bit round key, K0 to be used prior to the first round, and a 16-bit round key, Ki for use in each round of Mini-AES. Mini-AES encryption is defined to have 2 rounds, hence three round keys, K0, K1 and K2 are generated.

Round	Round Key Values
0	w0 = k0 w1 = k1 w2 = k2 w3 = k3
1	w4 = w0 Å NibbleSub( w3 ) Å rcon(1) w5 = w1 Å w4 w6 = w2 Å w5 w7 = w3 Å w6
2	w8 = w4 Å NibbleSub( w7 ) Å rcon(2) w9 = w5 Å w8 w10 = w6 Å w9 w11 = w7 Å w10

Table 2:  Generation of the Round Keys of Mini-AES

 Denote the 16-bit secret key, K as 4 nibbles, K = (k0, k1, k2, k3), and likewise, K0 = (w0, w1, w2, w3), K1 = (w4, w5, w6, w7) and K2 = (w8, w9, w10, w11).  Then, the round key   values are obtained from the secret key as in Table 2. Note that in each  round,  round constants rcon(i) are used, where  rcon(1) = 0001 and rcon(2) = 0010.