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).
Advanced Encryption Standard (AES)
Contents
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 n^{th} round, all operations but MixColumns() are performed
– Decryption is near-reverse, by order of operations (not structure), using Inv*() functions:
– InvShiftRows()
– InvSubBytes()
– AddRoundKey()
– 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
AddRoundKey(state, w[0, Nb-1])
for round = 1 step 1 to Nr–1
SubBytes(state)
ShiftRows(state)
MixColumns(state)
AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])
end for
SubBytes(state)
ShiftRows(state)
AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])
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
AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])
for round = Nr-1 step -1 downto 1
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])
InvMixColumns(state)
end for
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, w[0, Nb-1])
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 => 2^{128} = ~3.4 x 10^{38} possible keys
- 192-bit => 2^{192} = ~6.2 x 10^{57} possible keys
- 256-bit => 2^{256} = ~1.1 x 10^{77} 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]
Several software applications implement the AES, using any of or all
of AES-128, AES-192, and AES-256. Some are given below:
- [1,5] Robinson, C. “AES: Questions and Answers”. 2 October 2000. Accessed 16 March 2007.
URL: <http://www.nist.gov/public_affairs/releases/aesq&a.htm>
- [2,12] Farmer, Dr. W. “07 Overview of Cryptography”. 10 March 2007. Accessed 13 March 2007. Slide 9.
URL: <http://www.cas.mcmaster.ca/~wmfarmer/SE-4C03-07/slides/07-cryptography.pdf>
- [3] Gladman, Dr. Brian. “Implementation Experience with AES Candidate Algorithms”. Second AES Conference. February 1999. Accessed 18 March 2007. p. 3.
URL: <http://jya.com/bg/gladman.pdf>
- [4] Roback, E., Dworkin, M. “FIRST ADVANCED ENCRYPTION STANDARD (AES) CANDIDATE CONFERENCE”. August 1998. Accessed 16 March 2007.
URL: <http://www.ieee-security.org/Cipher/ConfReports/conf-rep-aes.html>
- [6] Barker, E. “Federal Information Processing Standards Publication 197”. 26 November 2001. Accessed 16 March 2007. pp. 9, 18-25.
URL: <http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf>
- [7] Wikipedia volunteers. “Substitution box”. 20 February 2007. Accessed 26 March 2007.
URL: <http://en.wikipedia.org/wiki/S-box>
- [8] Wikipedia volunteers. “Key schedule”. 26 January 2007. Accessed 26 March 2007.
URL: <http://en.wikipedia.org/wiki/Key_schedule>
- [9,10] Wikipedia volunteers. “Advanced Encryption Standard”. 27 March 2007. Accessed 16 March 2007.
URL: <http://en.wikipedia.org/wiki/Advanced_Encryption_Standard>
Author: Alan Sia
Last Updated: April 5, 2007