Threats to computer and network security increase with each passing day and come from a growing number of sources. No computer or network is immune from attack. A recent concern is the susceptibility of the power grid and other national infrastructure to a systematic, organized attack on the United States from other nations or terrorist organizations.
Encryption, or the ability to store and transmit information in a form that is unreadable to anyone other than intended persons, is a critical element of our defense to these attacks. Indeed, man has spent thousands of years in the quest for strong encryption algorithms.
This article focuses on the Advanced Encryption Standard, or AES, the de facto standard today for symmetric encryption. In order to securely send data using a symmetric cipher, the sender and receiver use the same cryptographic key for encryption and decryption, respectively. Therefore, it is essential to maintain the key in a secure manner to avoid compromise.
Goodbye DES
AES is standardized as Federal Information Processing Standard 197 (FIPS 197, available here) by the National Institute of Standards and Technology (NIST), a non-regulatory federal agency. Prior to AES, the Data Encryption Standard (DES) became the federal standard for block symmetric encryption (FIPS 46) in 1977.
DES was based on an algorithm developed by IBM and modified by the National Security Agency (NSA). DES was considered unbreakable in the 1970s except by brute-force attack — that is, trying every possible key (DES uses a 56-bit key, so there are 256, or 72,057,594,037,927,936 of them). By the late 1990s, however, it was possible to break DES in a matter of several days. This was possible because of the relatively small block size (64 bits) and key size and advances in computing power according to Moore’s Law.
This achievement signaled the end of DES; although Triple DES, or DES repeated three times with different keys and therefore essentially a 168-bit key, is still acceptable for federal use until 2030.
Hello AES
In January 1997, NIST announced a competition for the successor to DES. To allay the suspicions that the NSA had placed “back doors” in DES, the competition was to be open and public, and the encryption algorithm was available for use royalty-free worldwide. The criteria included not only cryptographic strength (resistance to linear and differential cryptanalysis) but also ease of implementation and performance in software and hardware.
Over the course of three competitive rounds and intense cryptanalysis by the world’s foremost experts on encryption, NIST selected the winner, the Rijndael (pronounced “Rhine doll”) algorithm of Belgian cryptograhers Joan Daemen and Vincent Rijmen in October 2000. FIPS 197 was published on Nov. 26, 2001, and is the symmetric cipher of choice for government and commercial use today. Although originally approved for encryption of only non-classified governmental data, AES was approved for use with Secret and Top Secret classified information of the U.S. government in 2003.
Fundamentals of AES
AES is a symmetric block cipher, operating on fixed-size blocks of data. The goal of AES was not only to select a new cipher algorithm but also to dramatically increase both the block and key size compared with DES. Where DES used 64-bit blocks, AES uses 128-bit blocks. Doubling the block size increases the number of possible blocks by a factor of 264, a dramatic advantage over DES.
More importantly, in contrast to relatively short 56-bit DES key, AES supports 128-, 192-, and 256-bit keys. The length of these keys means that brute-force attacks on AES are infeasible, at least for the foreseeable future. A further advantage of AES is that there are no “weak” or “semi-weak” keys to be avoided (as in DES, which has 16 of them).
Details of AES Operation
AES is based on a substitution-permutation network, in which the input data (also called “plaintext”) and the cryptographic key are successively processed by substitution boxes (S-boxes) or permutation boxes (P-boxes), in mathematical operations. The 128-bit input block is divided into a 4×4 array of 8 bits (one byte) each, called the “State.”
The S-boxes effectively substitute one 8-bit number for another and were designed in such a manner that a change in one bit at the input changes at least half of the output bits, known as the “avalanche property.” In contrast, the P-boxes permute, or shuffle, the 8 input bits to produce an 8-bit output. The mathematical operations of the S-boxes and P-boxes are organized in a number of successive “rounds.”
Each round in AES is comprised of four transformations, or operations. These are called “SubBytes,” “ShiftRows,” “MixColumns,” and “AddRoundKey.” All bytes in AES, including the key, are considered to be finite field elements, not numbers, for purposes of the mathematical operations within these transformations. Specifically, the finite field in AES is defined as a Galois field of size 28, with 256 elements. FIPS 197 specifies the mathematical details of AES implementation.
Each round takes two inputs: the previous State and a Round Key. The Round Key is derived from the cryptographic key according to the Rijndael key schedule as defined in FIPS 197. There are a variable number of rounds according to the AES key length: 10 rounds for 128-bit keys, 12 rounds for 192-bit keys, and 14 rounds for 256-bit keys. The final round omits the MixColumns transformation; otherwise all of the rounds perform the same four transformations.
The result of the State after the final AES round is “ciphertext,” which bears no resemblance to the plaintext. Decryption of the ciphertext is the inverse of the encryption steps, using the same symmetric key used for encryption.
Success of AES
The open and collaborative process of selecting Rijndael as the AES algorithm was an unprecedented opportunity to ensure that it would withstand many types of sophisticated attacks. In their book The Design of Rijndael, its inventors discuss potential attacks against AES using truncated differentials, saturations attacks (also known as “square attacks”), Gilbert-Minier attacks, interpolation attacks, and related-key attacks.
Although related-key attacks are theoretically the most promising, they are still infeasible from a practical standpoint. To date, most attacks have focused on weaknesses or characteristics in specific implementations, called “side-channel attacks,” not on the algorithm itself. Beyond its cryptographic strength, AES is efficiently realized in hardware and software, an important consideration given its widespread adoption. The careful design and intense scrutiny paid to AES has resulted in an unqualified success — not only for today but decades into the future.
Barry K. Shelton is a partner at Bracewell & Giuliani. Chris R. Johnson is an associate at Bracewell & Giuliani.
Loading ...
