Advanced Encryption Standard (AES)

Contents

• Introduction
• The AES Algorithm – Rijndael
  • For the Mathematicians / Cryptographers
  • For the Software Engineers
• Security of the AES Algorithm
• Software Applications
• References
• See Also
• External Links

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 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]

– 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()

– 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

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¹²⁸ = ~3.4 x 10³⁸ possible keys
• 192-bit => 2¹⁹² = ~6.2 x 10⁵⁷ possible keys
• 256-bit => 2²⁵⁶ = ~1.1 x 10⁷⁷ 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:

• TrueCrypt – Free, open-source
• SSH Secure Shell – Commercial (formerly free and commercial)
• PGP – Pretty Good Privacy. Commercial

• [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>

• Ian McCombe - Block Ciphers

• http://www.nist.gov
• http://jya.com
• http://www.ieee-security.org
• Wikipedia

Author: Alan Sia
Last Updated: April 5, 2007