DISCLAIMER: Among other things, this page will investigate the algorithm's mathematics on a fairly shallow level. I AM NOT A MATHEMATICIAN OR A CRYPTOGRAPHER (though I have an interest in encryption).

Contents

Introduction

The Advanced Encryption Standard (AES) was devised by the United States National Institute of Standards and Technology (NIST), and specified an encryption algorithm which was strong, openly defined, reliable (secure for a long time), and fast. [1] The current slower standard, Data Encryption Standard (DES), used 56-bit keys which could be brute-forced. Thus, a successor was needed which could overcome these weaknesses and protect data for many years into the future.

The AES Algorithm - Rijndael

The Rijndael algorithm, designed by Joan Daemen and Vincent Rijmen and standardized by NIST as FIPS PUB 197 in 2001 by an algorithms competition, is a free symmetric block cipher supporting 128-bit block size and 128-, 192-, 256-bit key lengths. Encryption and decryption use the same key. [2]

Some advantages include no algorithm setup, compact implementation code (not necessarily simple without supplied sources [3]), room for parallelism (can be very efficient on a distributed system), [4] and small memory footprint. [5]

How the algorithm works, on a shallow level:[6]

• For the Mathematicians / Cryptographers:
– The input data block is broken into a 4x4 byte array (128-bit key)
– The initial subkey (derived from the cipher key via key schedule [8]) is XOR'd to the byte array by an AddRoundKey() operation (Nb = block size)

– For each encryption “round”/iteration to n-1 (128-bit, n=10; 192-bit, n=12; 256-bit, n=14):
– Each array byte is substituted using a SubBytes() S-box [7] operation

– A ShiftRows() cyclic shift operation is done on the last three rows of the byte array

– The array columns are then modified by a MixColumns() operation

AddRoundKey() is used again for the next round before SubBytes()
– In the nth round, all operations but MixColumns() are performed

– Decryption is near-reverse, by order of operations (not structure), using Inv*() functions:
– InvShiftRows()
– InvSubBytes()
– InvMixColumns()
• For the Software Engineers, the official pseudo-code as published by NIST follows:
– The primary encryption module calling every other function:
Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
begin
byte state[4,Nb]
state = in
for round = 1 step 1 to Nr–1
SubBytes(state)
ShiftRows(state)
MixColumns(state)
end for
SubBytes(state)
ShiftRows(state)
out = state
end

– Key expansion to generate the key schedule (refer to PDF reference, p. 24)

– The primary decryption module calling every other function:
InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
begin
byte state[4,Nb]
state = in
for round = Nr-1 step -1 downto 1
InvShiftRows(state)
InvSubBytes(state)
InvMixColumns(state)
end for
InvShiftRows(state)
InvSubBytes(state)
out = state
end

Security of the AES Algorithm

The AES key lengths are large (nigh unbreakable by brute force, at least “mathematically infeasible” given current computing technology). These translate to (rounded down):

• 128-bit => 2128 = ~3.4 x 1038 possible keys
• 192-bit => 2192 = ~6.2 x 1057 possible keys
• 256-bit => 2256 = ~1.1 x 1077 possible keys

As of 2005, “timing attacks” (subset of “side channel attacks”, below) have been shown [9] but some have drawbacks, including the need to execute programs on the target machine. [10]

As of 2006, attacks to get an entire AES key have been confined to side channel attacks. [12]

Software Applications

Several software applications implement the AES, using any of or all of AES-128, AES-192, and AES-256. Some are given below:

References