Advanced Encryption Standard

Advanced Encryption Standard (AES), also known as Rijndael (pronounced "Rain Dahl" in English), is a block cipher scheme adopted as an encryption standard by the United States government, created in Belgium. AES was announced by the National Institute of Standards and Technology (NIST) as United States FIPS PUB 197 (FIPS 197) on November 26, 2001 after a 5-year standardization process. It became an effective standard on May 26, 2002. Since 2006, AES is one of the most popular algorithms used in symmetric cryptography.

The cipher was developed by two Belgian cryptologists, Joan Daemen and Vincent Rijmen, both students at Katholieke Universiteit Leuven, and was submitted to the AES selection process under the name "Rijndael&# 34;, as part of a contest.

History

In 1997, the National Institute of Standards and Technology (NIST) decided to hold a contest to choose a new encryption algorithm capable of protecting sensitive information for the 21st century. This contest was called Advanced Encryption Standard (AES).

On January 2, 1997, NIST announced its intention to develop AES, with the help of industry and the cryptographic community. On September 12 of that year the formal call was made. In this call, several conditions were indicated for the algorithms to be presented:

• Being public domain, available to everyone.
• Be a symmetric encryption algorithm and support blocks of at least 128 bits.
• Encryption keys could be 128, 192 and 256 bits.
• Be implementable both on hardware and software.

On August 20, 1998, NIST announced the 15 supported algorithms at the first AES conference:

• CAST-256 (Entrust Technologies, Inc.)
• CRYPTON (Future Systems, Inc.)
• DEAL (Richard Outerbridge, Lars Knudsen)
• DFC (CNRS – Centre National pour la Recherche Scientifique – École Normale Supérieure)
• E2 (NTT – Nippon Telegraph and Telephone Corporation)
• FROG (TecApro International, S.A.)
• HPC (Rich Schroeppel)
• LOKI97 (Lawrie Brown, Josef Pieprzyk, Jennifer Seberry)
• MAGENTA (Deutsche Telekom AG)
• MARS (IBM)
• RC6 (RSA Laboratories)
• RIJNDAEL (John Daemen, Vincent Rijmen)
• SAFER+ (Cylink Corporation)
• SERPENT (Ross Anderson, Eli Biham, Lars Knudsen)
• TWOFISH (Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson)

The second AES conference took place in March 1999 where the analyzes to which the candidates were submitted by the international cryptographic community were discussed. Comments were accepted until April 15. NIST decided in August 1999 which would be the 5 finalists:

• MARS
• RC6
• RIJNDAEL
• SERPENT
• TWOFISH

These algorithms were subjected to a second, more exhaustive review, which lasted until May 15, 2000. During this period, NIST accepted analysis of the finalist algorithms.

During April 13 and 14, 2000, the third AES conference took place where the latest analyzes of the finalist algorithms were discussed. The developers of the finalist algorithms were present at it.

On May 15, 2000, the public analysis period ended. NIST studied all the available information to decide which would be the winning algorithm. On October 2, 2000, the algorithm that would ultimately win the contest was voted on. The result was the following:

• MARS: 13 votes
• RC6: 23 votes
• RIJNDAEL: 86 votes
• SERPENT: 59 votes
• TWOFISH: 31 votes

The Rijndael algorithm won the contest and in November 2001 FIPS 197 was published where it was officially assumed.

Development

Rijndael was a refinement of an earlier design by Daemen and Rijmen, Square; Square was itself a development of Shark.

Unlike its predecessor DES, Rijndael is a substitution-permutation lattice, not a Feistel lattice. AES is fast in both software and hardware, is relatively easy to implement, and requires little memory. As a new encryption standard, it is currently being used on a large scale.

Description of encryption

In the phase SubBytes, each byte in the state is replaced with its entry into an 8-bit fixed search table, S; bij = S(aij).

In the step ShiftRows, the bytes in each row of the state are cyclically rotated to the left. The number of places that each byte is rotated differs for each row.

In the step MixColumns, each column of the state is multiplied by a constant polynomial c(x).

In the step AddRoundKey, each byte of the state is combined with a byte of the subclave using the XOR operation ().).

Strictly speaking, AES is not exactly Rijndael (although in practice they are called interchangeably) since Rijndael allows a greater range of block sizes and key lengths; AES has a fixed block size of 128 bits and key sizes of 128, 192 or 256 bits, while Rijndael can be specified by a key that is a multiple of 32 bits, with a minimum of 128 bits and a maximum of 256 bits..

Most of the calculations of the AES algorithm are done in a given finite field.

AES operates on a 4×4 byte array, called state (some versions of Rijndael with a larger block size have additional columns in state).

Pseudocode

• Expansion of the key using the Rijndael key scheme.
• Initial phase:

1. AddRoundKey

• Rounds:

1. SubBytes — in this step a nonlinear replacement is made where each byte is replaced with another according to a search table.
2. ShiftRows — in this step a transposition is made where each row of the "state" is cyclically rotated a certain number of times.
3. MixColumns — mixed operation that operates in the columns of the "state", combining the four bytes in each column using a linear transformation.
4. AddRoundKey — each "state" byte is combined with the "round" key; each "round" key is derived from the encryption key using a key iteration.

• Final stage:

1. SubBytes
2. ShiftRows
3. AddRoundKey

Security

As of 2005, no successful attack against AES has been found. The US National Security Agency (NSA) reviewed all AES candidate finalists, including Rijndael, and declared all of them secure enough for use in unclassified US government information. In June 2003, the United States government announced that AES could be used for classified information:

"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. The implementation of AES in products intended to protect national security systems and/or information must be reviewed and certified by NSA prior to their acquisition and use."

This event marks the first time the public has had access to an NSA-approved TOP SECRET cipher. It is interesting to note that many public products use 128-bit keys by default; the NSA may suspect a fundamental weakness in keys this size, ^{[citation needed]} or they simply prefer to have a margin of security for top-secret documents (which should preserve the security for decades into the future).

The most common method of attacking a block cipher is to attempt several attacks on versions of the cipher with fewer rounds. AES has 10 rounds for 128-bit keys, 12 rounds for 192-bit keys, and 14 rounds for 256-bit keys. As of 2005, the best known attacks are on versions reduced to 7 rounds for 128-bit keys, 8 rounds for 192-bit keys, and 9 rounds for 256-bit keys (Ferguson et al, 2000).

Some cryptographers are concerned about the security of AES. They feel that the margin between the number of rounds specified in the cipher and the best known attacks is very small. The risk is that some way can be found to improve the attacks and if so, the encryption could be broken. In the cryptographic context it is considered "broken" an algorithm if there is any attack faster than an exhaustive search (brute force attack). So an attack against 128-bit key AES that requires 'only' 2¹²⁰ operations would be considered an attack that "breaks" the AES even taking into account that for now it would be an unrealizable attack. So far, such concerns can be ignored. The most widely publicized and well-known brute force attack has been against a 64-bit RC5 key by distributed.net.

Another concern is the mathematical structure of AES. Unlike most block ciphers, AES has a very neat mathematical description. This has not yet led to any attacks, but some researchers are concerned that future attacks might find a way to exploit this structure.

In 2002, a theoretical attack, dubbed the "XSL attack", was announced by Nicolas Courtois and Josef Pieprzyk, showing a potential weakness in the AES algorithm. Several cryptographic experts have found problems in the math behind the proposed attack, suggesting that the authors may have made a mistake in their estimates. Whether this line of attack can be taken against AES is still an open question. So far, the XSL attack against AES seems speculative; it is unlikely that anyone could carry out this attack in practice.

Side Channel Attacks

Side channel attacks do not attack the encryptor itself, but rather implementations of the encryptor on systems that inadvertently disclose data.

In April 2005, Daniel J. Bernstein announced a timed cache attack that used to break a server as it used AES encryption for OpenSSL. This server was designed to give as much information about execution times as possible, and the attack required about 200 million plaintext files. The attack is said to be impractical in real-world implementations; Bruce Schneier called this research a "nice timings attack".

In October 2005, Adi Shamir and two other researchers submitted a paper demonstrating various cache timing attacks against AES. One of the attacks obtained an entire AES key after just 800 writes, in 65 milliseconds. This attack requires the attacker to be able to run programs on the same system that performs the AES encryption.

Implementations

• AES calculator showing intermediate values in Javascript
• AES implementation by Brian Gladman with BSD license
• Implementation of Pablo Barreto's public domain AES written in C
• Implementation of public domain AES of D.J. Bernstein
• Source code with GPL license of Rijndael optimized algorithm in C
• GPL Nettle Library that also includes AES implementation
• Evolsystem: AES encryption algorithm example - Rijndael
• Rijndael Inspector: program made in Flash to encrypt and decipher using AES-128
• Cryptomator: open source program to encrypt files and upload them to the cloud