Telenet Coding: Data and Network Security

The application of the four components NibbleSub, ShiftRow, MixColumn and KeyAddition in sequence constitutes one round. The full Mini-AES encryption consists of two such rounds, with the exclusion of MixColumn from the last round and the inclusion of an extra KeyAddition prior to the first round. Hence, Mini-AES encryption can be denoted by:

Mini-AESEncrypt = sK2 o p o g o sK1 o q o p o g o sK0

Note that the symbol o refers to the composition of functions and the order of execution is from right to left, which means that sK0 is executed first. Figure 7 provides a pictorial view of Mini-AES encryption.

Figure 7: The Mini-AES Encryption Process

Example 9

To provide an illustrative example for the student, suppose that the input 16-bit plaintext block is P = 1001 1100 0110 0011. Expressed as a matrix of 2 ´ 2 of nibbles, it is then

Suppose also that the secret key, K = 1100 0011 1111 0000. This is also expressed as a 2 ´ 2 matrix.

Firstly, the round keys are derived from the secret key, K by way of the key schedule.

Derivation of the Round Keys

K0 = (w0, w1, w2, w3) = (k0, k1, k2, k3) = K = 1100 0011 1111 0000

K1 = (w4, w5, w6, w7) is calculated as follows:

w4 = w0 Å NibbleSub( w3 ) Å 0001

= 1100 Å NibbleSub(0000) Å 0001

= 1100 Å 1110 Å 0001

= 0011

w5 = w1 Å w4

= 0011 Å 0011

= 0000

w6 = w2 Å w5

= 1111 Å 0000

= 1111

w7 = w3 Å w6

= 0000 Å 1111

= 1111

K2 = (w8, w9, w10, w11) is calculated as follows:

w8 = w4 Å NibbleSub( w7 ) Å 0010

= 0011 Å NibbleSub(1111) Å 0010

= 0011 Å 0111 Å 0010

= 0110

w9 = w5 Å w8

= 0000 Å 0110

= 0110

w10 = w6 Å w9

= 1111 Å 0110

= 1001

w11 = w7 Å w10

= 1111 Å 1001

= 0110

Encryption of the Plaintext

Next, we proceed with encryption. Given plaintext, P = 1001 1100 0110 0011, then after the first KeyAddition with the 0th round key, K0, the output is

A = P Å K0 = 1001 1100 0110 0011 Å 1100 0011 1111 0000

= 0101 1111 1001 0011

Round 1

After NibbleSub, the output is

B = NibbleSub(0101), NibbleSub(1111), NibbleSub(1001), NibbleSub(0011)

= 1111 0111 1010 0001

After ShiftRow, the output is

C = ShiftRow (1111 0111 1010 0001)

= 1111 0001 1010 0111

MixColumn is a bit more involved. The input block is rearranged as a 2 ´ 2 matrix, hence:

Taking the first column and multiplying it with the constant matrix, we get:

Taking the second column and multiplying it with the constant matrix, we get:

Therefore, the output after MixColumn is

or D = 0000 1110 0011 1110

After KeyAddition with K1, the output is

E = D Å K1 = 0000 1110 0011 1110 Å 0011 0000 1111 1111

= 0011 1110 1100 0001

Round 2

After NibbleSub, the output is

F = NibbleSub(0011), NibbleSub(1110), NibbleSub(1100), NibbleSub(0001)

= 0001 0000 0101 0100

After ShiftRow, the output is

G = ShiftRow (0001 0000 0101 0100)

= 0001 0100 0101 0000

Note that in the last round, there is no MixColumn. After KeyAddition, the output is H = G Å K2 = 0001 0100 0101 0000 Å 0110 0110 1001 0110

= 0111 0010 1100 0110

Therefore, the final ciphertext is H = 0111 0010 1100 0110

Mini-AES Decryption

In order to get back the original plaintext, the reverse process of encryption must be performed on the ciphertext. This is called decryption. Noting that decryption is the inverse of encryption, then

Mini-AESDecrypt = (sK2 o p o g o sK1 o q o p o g o sK0) –1

= sK0 -1 o g -1 o p -1 o q -1 o sK1 -1 o g -1 o p -1 o sK2 -1

= sK0 o g -1 o p o q o sK1 o g -1 o p o sK2

We arrive at this expression since sKi is an XOR operation, which is its own inverse. We have also specially chosen the constant matrix in MixColumn, q such that the inverse of MixColumn, q -1 is the same as MixColumn itself. Since ShiftRow simply causes the second row to be rotated left by one nibble amount, then the inverse of ShiftRow, p -1 causes the second row to be rotated right by one nibble. Rotating the nibble left or right are one and the same operation because one row only has two nibbles, therefore inverse ShiftRow is the same as ShiftRow. NibbleSub is a nibble substitution operation based on Table 1. The inverse of Table 1 is easily computed by interchanging the input nibble with the output nibble, and then resorting it based on the new input nibble, as given in Table 3 below.

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

Table 3: Inverse S-box of Mini-AES

Example 10

For an input nibble, a0 = 1111, then based on Table 1, the output nibble is b0 = 0111. To get back the original nibble a0 given the value of b0, we use the inverse of Table 1, which is Table

3. Referring to Table 3, then given the input b0 = 0111, the output is a0 = 1111.

Observe also that the order in which inverse NibbleSub, g -1 and ShiftRow, p is carried out is not important, since inverse NibbleSub operates on each individual nibble whereas ShiftRow simply shifts the nibbles around. Hence, the final expression for Mini- AES decryption is:

Mini-AESDecrypt = sK0 o p o g -1 o q o sK1 o p o g -1 o sK2

Comparing the expression for decryption and encryption, we see that they are similar in structure, except that the round keys and the round constants are applied in reverse order, and the NibbleSub component is replaced by its inverse.

As an exercise, the student can try by pen and paper to decrypt the ciphertext, H obtained in Example 9 to get back the original plaintext, P.

Mini AES Process

On 03:28 by Unknown in Data and Network Security No comments

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.

Saturday, 13 August 2016

Thursday, 11 August 2016

Saturday, 4 June 2016

Example Mini-AES Encryption

Example 9

Round 1

Thursday, 2 June 2016

1 Introduction

2 Mathematical Background

The Finite Field GF(24)

Example 1

Addition in GF(24)

Example 2

Example 3

Example 4

□

3 Mini-AES

Mini-AES Components

NibbleSub, g

Search

Popular Posts

Categories

Editorial

Sample Text

Blog Archive

My Traffic

Labels

Contact Form