Advanced Encryption Standard
In effect since 2002, the Advanced Encryption Standard (AES) is a widely adopted data encryption standard from the United States government AES is a block cipher, which means it operates on fixed-length chunks of data with an unvarying transformation. The National Institute of Standards and Technology (NIST) chose AES from numerous candidates during a five-year process that was notable for its openness and transparency.
AES is significant because the United States government has approved it. This means that it is the only practical alternative for commercial applications requiring encrypted information that can be sold to US government agencies. This is an enormous market. Further, because of the way AES was selected and reviewed in a high-profile process, it is highly respected by the international cryptographic community. AES is already the choice of many commercial and government organizations internationally. It is the basis of data security for numerous vendors, and its uptake continues to increase. AES will be a key element of encryption systems for years to come.
History of AES
Any discussion of AES must begin with DES, the original Data Encryption Standard. DES was selected as a Federal Information Processing Standard (FIPS) for the United States in 1976, and it became widely used internationally. DES was used in many commercial applications, including financial transactions. The algorithm remained controversial because of suspicions that the National Security Agency had introduced deliberate weaknesses.
In 1997, the NIST announced its desire to choose a successor to DES that could no longer be considered secure because of its small key size and the increased availability of computing power. NIST invited the cryptographic community to recommend how the process should work and what algorithms should be considered. In response to this community input, the NIST then issued a call for block cipher algorithms, supporting a block size of 128 bits and key sizes of 128, 192, and 256 bits. AES was selected from among 15 contenders. The winning algorithm, known as Rijndael, was submitted by the Belgian cryptographers Joan Daemen and Vincent Rijmen. Strictly speaking, AES is a subset of the many possible implementations of the Rijndael algorithm.
The NIST process was widely praised by the cryptographic community as a model of how such a standard should be achieved. Many of the finest minds in the field submitted candidates, and the candidate algorithms were widely reviewed, criticized, and discussed by experts around the world. As a result, AES is considered to be a high quality and trustworthy solution for data encryption.
AES became a government standard in 2002. In 2003, the U.S. Government approved AES for use with classified information. Today, it is one of the most popular algorithms used in symmetric key cryptography.
The Algorithm
AES is a block cipher. This means that it operates on fixed-length chunks of data (for example, blocks), applying the same transformation to each block. The transformation is controlled by use of the encryption key. Block ciphers (and thus AES) use symmetric keys, which means that the same key used to encrypt data is also used to decrypt it (or in some cases, a key only trivially different). In operation, a user inputs 128 bytes of plaintext, along with a key, and receives as output 128 bytes of ciphertext. To decrypt the ciphertext, the user inputs it and the key to the algorithm to retrieve the original 128 bytes of plaintext. Encryption proceeds via a number of rounds. For 128-bit keys, AES prescribes 1ten rounds; for 192-bit keys, it uses 12 rounds; and for 256-bit keys, it uses 14 rounds.
AES has a fixed block size of 128 bits and a key size of 128, 192, or 256 bits. In contrast, the parent Rijndael algorithm can have both key and block sizes of 128, 160, 192, 224, or 256 bits. The 128 bits in a block are arranged in a grid of 4 x 4 bytes (also known as the state). Each round of encryption consists of four steps to generate a new state:
- AddRoundKey
- SubBytes
- ShiftRows
- MixColumn
In the final round of encryption, the MixColumn step is replaced with another AddRoundKey step.
In Step 1, AddRoundKey, a subkey is combined with the state. The subkey is derived from the main key using a key schedule, which generates an endless supply of subkeys using a well defined set of rotations, exponents, and multiplications. The subkey is the same size as the state, and the two are combined using the logical exclusive OR operation (XOR). This state obscures the original state and provides a new encrypted state.
In Step 2, SubBytes, each byte in the state is substituted using an S-Box. The S-Box (or substitution box) is another transformation, this time achieved by finding the multiplicative inverse of the byte in Rijndael's finite field, then transforming that result using binary linear algebra (an affine transform). Choosing good S-Box transforms is critical to the security of an encryption algorithm. Again, the result of this step is to obscure the original state and provide a new, encrypted state.
In Step 3, ShiftRows, the bytes in the rows of the 4 x 4 state are shifted within the row. The first row is left unchanged, the second row is shifted left one byte, and the third and fourth rows are shifted left two and three bytes, respectively.
Finally, in Step 4, MixColumns, the four bytes of each column are combined using an invertible linear transform. Four input bytes generate four output bytes, with each input byte influencing each output byte. You can view this as a matrix multiply within a finite field. An equivalent view is that it is a modulo multiply of a pair of polynomials. This operation provides diffusion, meaning that it spreads the input of a single character of plaintext across several characters. Repetition of the ShiftRows and MixColumns steps ensures that changing a single letter of the plaintext changes every character in the output block of ciphertext.
Performance is an issue with any piece of software; however, it is especially important in cryptography. AES was designed with 32-bit processors in mind, and is extremely efficient. In particular, the transforms in Steps 2, 3, and 4 can all be achieved using lookup tables, so that a particular state or part of a state is used as an index into the pre-calculated table, and the result is read from the table rather than calculated. This ability to "pre-calculate" most of the transformations makes AES computationally efficient. Four tables of 256 32-bit entries, for a total of 4096 bytes, can be used, so that the computation required for a round is a series of table lookups and XOR operations. In addition, this can be implemented in hardware.
The Security of AES
The entire point of cryptography is keeping secrets safe. An algorithm is useful only to the extent that breaking the encryption is difficult and expensive. In other words, if someone can easily break the encryption, what is the point of protecting the data in the first place? AES has been reviewed by many of the world's best code breakers, and no significant flaws have been reported. The National Security Agency of the U.S. government reviewed all the AES finalists, including Rijndael, and pronounced all of them adequate for federal non-classified data. In 2003, the U.S. Government announced that AES was appropriate for encrypting classified data. This is the first time in history that the general public has had access to a NSA-approved cipher for top secret information.
To date, the known attacks against AES have been side-channel attacks. A side-channel attack uses information about the implementation of the algorithm, rather than a theoretical weakness of the algorithm. Side-channel attacks use things, such as audio information, power consumption, radiation leaks, and timing information, to deduce whole or partial solutions. Side-channel attacks require significant technical skill. An "open" algorithm, such as AES, is vulnerable to these attacks because the algorithm is available to attackers and to legitimate users.
The only known successful attacks against AES to date are side-channel attacks relying on the precise timing of an AES system. These attacks are against specific implementations of the algorithm. Attention to timing security in the design phase of an implementation can negate or greatly reduce the chances of a successful timing attack.
Some cryptographers still have concerns about AES. A common attack on block ciphers is to attack the algorithm with a reduced number of rounds. At the time of this writing, attacks on AES exist for seven rounds with 128-bit keys, eight rounds with 192-bit keys, and nine rounds with 256-bit keys. Recall that the full implementation of AES uses ten, 12, and 14 rounds with 128-, 192-, and 256-bit keys, respectively. There is concern that there is not enough distance between the attack for a seven-round encryption and the actual ten-round implementation and that there is a risk these attacks could be improved to break the cipher. Another worry results from the mathematical structure of AES. In contrast to most ciphers, AES has a concise and elegant algebraic structure. There is concern among some cryptographers that an attack based on new insights into this formulation could be successful.
AES appears to be secure as of this writing in late 2006. The largest well-known brute force attack occurred in 2002 against a 64-bit RC5 key. With a key size of at least 128 bits, AES is well out of reach of brute force attacks by normal adversaries for years if not decades.
Applications
Vendors of both hardware and software have enthusiastically adopted AES. Because AES uses a simple and efficient algorithm, using it as an encryption specification decreases system complexity, lowers costs, and promotes interoperability.
There are many areas where AES is now in commercial use. Most high-end VPN software contains implementations of AES, including offerings from Checkpoint, Cisco, and Symantec. AES is now commonly found in network appliances. Voice Over IP vendors are using AES for telephone security. Vendors now use AES to provide security for process control (SCADA) systems. AES has even been added to common file compression programs, such as WinZip. Dozens of hardware implementations are available that use both FPGAs and ASICs. There are multiple implementations in software in the public domain.
Summary
AES is one of the newest and most well known encryption standards. It was developed and analyzed in a thorough, lengthy, and widely respected process by NIST. AES is approved by the U.S. government for classified data, and numerous hardware and software vendors have implemented it.
AES uses 128-, 192-, or 256-bit keys. Encryption consists of ten, 12, or 14 rounds, where each round consists of four steps: AddRoundKey, SubBytes, ShiftRows, and MixColumns. The known attacks against AES to date have involved timing, where keys are guessed by analyzing how long particular steps require. Because AES has a well defined algebraic structure, some cryptographers worry that there might be attacks on the algorithm itself possible, but none have publicly emerged to date.
AES is efficient, elegant, and secure. It will be a top choice for data security in the next decade and beyond[6].