History of AES
AES had its start as the result of NIST’s quest to replace the aging and vulnerable DES (Data Encryption Standard). By the summer of 1997, DES had been compromised however NIST was not ready with a new standard. NIST extended DES’s useful life by enacting FIPS 46-3 while it vetted out a new standard through a submission process. NIST’s requirements for the new encryption standard included (Kramer, 1996).
1. AES shall be publicly defined.
2. AES shall be a symmetric block cipher.
3. AES shall be designed so that the key length may be increased as needed.
4. AES shall be implementable in both hardware and software.
5. AES shall either be
a. Freely available or
b. Available under terms consistent with the American National Standards Institute (ANSI) patent policy.
6. Algorithms which meet the above requirements will be judged based on the following factors:
a. Security (i.e., the effort required to cryptanalyze)
b. Computational efficiency
c. Memory requirements
d. Hardware and software suitability
e. Simplicity
f. Flexibility
g. Licensing requirements
Fifteen algorithms were submitted which five were selected for further review. The review cycle was carried out for more than a year before the candidate was selected. The winning algorithm that was selected is named Rijndael (pronounced rain-dahl). The cipher was developed/submitted for consideration by two Belgian cryptographers, Joan Daemen and Vincent Rijmen. It is interesting to note that among the finalist that were selected for the second round, two algorithms have survived and are used with some frequency today, Serpent and Two Fish. Two Fish is supported in PGP. Serpent (deemed by many to be more secure than Rijndael) is implemented within Visual Basic as well as being popular in many academic communities. In May of 2002, AES became effective as FIPS 197. Three year later on May 19, 2005 NIST withdraws FIPS 46-3 effectively bringing an end to DES.
AES in Detail
Advanced Encryption Standard is a block cipher that uses a substitution-permutation network as opposed to DES’s Feistel network. In its original form, Rijndael can process data in various block sizes (128, 192, and 256-bits) using keys sizes of 128, 192, and 256-bits. However in it’s reiteration as AES it has a fixed block size of 128 bits and a key size of 128, 192, or 256 bits! AES contains four different transformations processes (SubBytes, ShiftRows, MixColumns, and AddRoundKey). The SubBytes operation takes the data (otherwise known as the state) that is presented to it and substitutes out a value from the S-Box lookup table. The ShiftRows operation takes the data that is presented to it a transposes it by 1 byte based on the row it is operating on. The first row is considered 0 therefore no transformation is done. The second is considered 1 so the data is manipulated 1 byte. The third row is considered the 2 so the third row is transposed 2 bytes. The MixColumns operation takes the first column of the state and multiples it by a fixed polynomial. The operation is then preformed on each column. Together with ShiftRows, MixColumns provides diffusion in the cipher (Wikipedia.org, 2008). Lastly is the AddRoundKey operation. In this operation each byte of the presented state is combined with a byte of the round subkey using an XOR operation. So why use the term presented state? Each time the state is to be worked on, a prior operation has taken place so the state is no longer in plaintext but that a preliminary form of the ciphertext (one that is in a less secure state than the final output of the algorithm). The above mentioned transformations are applied is a prescribed order:
Key Expansion
Initial Round
AddRoundKey
Rounds (The number of rounds at this stage is determine by the number of bits in the key)
SubBytes
ShiftRows
MixColumns
AddRoundKey
Final Round (Note – The MixColumns operation is deleted from this round)
SubBytes
ShiftRows
AddRoundKey
Attacks on AES
As part of the original requirements for AES, it needed it to remain secure for the next 30 years. Certainly, this sets up the challenge as to whether AES could be “broken” before the 30 years have expired. Whenever anyone starts to look at determining whether an encryption algorithm could be broken, one must look at the theoretical verses the practical. One must also determine if the algorithm is computationally secure. Does the cost of breaking the code exceed the value of the data protected? Does the time required to break the code exceed the lifetime of the information protected? Similarly, Does a theoretical break true constitute a successful attack? In December of 2002, two cryptographic researchers, Nicolas Courtois and Josef Pieprzyk, presented an attacked on AES dubbed XSL. The XSL attacked claimed to be faster at getting the key than an exhaustive brute force attack. A few years after Courtois and Pieprzyk presented their finding it was proven that their findings were incorrect. This did however cause many cryptographers reevaluate AES and the math that unlies the algorithm. With all that being said, is there a computer that can perform the computations necessary to break AES? Not today!
Interesting Tidbits
The design and strength of all key lengths of the AES algorithm (i.e., 128, 192 and 256) are sufficient to protect classified information up to the SECRET level. TOP SECRET information will require use of either the 192 or 256 key lengths (Hathaway, 2003).
During my research for this article I came across a Flash animation that really helps with the understanding of the Rijndael encryption process.
It can be found at http://www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf
Resources:
Hathaway, L., (2003, June). National Policy on the Use of the Advanced Encryption Standard (AES) to Protect National Security Systems and National Security Information, Retrieved on November 13, 2008 from http://www.cnss.gov/Assets/pdf/cnssp_15_fs.pdf
Kramer, S., (1996, December 16), Advanced Encryption Standard Notice 1/97, Retrieved on November 13, 2008 from http://epic.org/crypto/aes_notice.html
Various, (2008, November 13), Advanced Encryption Standard, Retrieved on November 13, 2008 from http://en.wikipedia.org/wiki/Advanced_Encryption_Standard
