Advanced Encryption Standard

AES
	The substitution step, one of 4 sub-steps per round
developer	Joan Daemen , Vincent Rijmen
Released	1998, certification October 2000
Derived from	Square
Certification	NESSIE
Key length	128, 192 or 256 bits
Block size	128 bit
structure	Substitution-Permutation Network
Round	10, 12 or 14 (depending on key length)
Best known cryptanalysis
	The secret key can be found in steps for AES-128, in steps for AES-192 and in steps for AES-256 .

The Advanced Encryption Standard ( AES ) ( German as "advanced encryption standard" ) is a block cipher , as successor to DES in October 2000 by the National Institute of Standards and Technology was announced (NIST) as a standard. According to its developers Joan Daemen and Vincent Rijmen AES is also Rijndael - algorithm called.

It is a symmetrical encryption method , i. H. the key for encryption and decryption is identical. The Rijndael algorithm has variable, independent block and key lengths of 128, 160, 192, 224 or 256 bits. Rijndael offers a very high level of security; The first theoretically interesting, but practically irrelevant attack was not found until more than ten years after its standardization.

AES restricts the block length to 128 bits and the choice of key length to 128, 192 or 256 bits. The names of the three AES variants AES-128, AES-192 and AES-256 each refer to the selected key length. The algorithm is freely available and may be used without license fees and implemented in software and hardware. AES-192 and AES-256 are US approved for government documents with the highest level of secrecy .

Emergence

Until AES was used, the Data Encryption Standard (DES) was the most frequently used symmetric algorithm for encrypting data. Since the 1990s at the latest, with its key length of 56 bits, it was no longer considered sufficiently secure against attacks with the brute force method . A new, better algorithm had to be found.

Selection of a DES successor

The American Department of Commerce put the search for a successor algorithm out to tender internationally on January 2, 1997; the American National Institute of Standards and Technology in Gaithersburg, Maryland , was responsible for the selection . After an international conference on April 15, 1997, it published the final tender on September 12, 1997. The type of search and the selection criteria thus differed considerably from the DES development that took place behind closed doors. The winner of the tender, which was to be defined as the Advanced Encryption Standard (AES), had to meet the following criteria:

AES must be a symmetric algorithm , namely a block cipher .
AES must use 128-bit long blocks (this was only specified during the tender; at the beginning of the tender, block sizes of 192 and 256 bits were also required, these were only retained as possible extensions)
AES must be able to use keys of 128, 192 and 256 bits in length.
AES should be equally easy to implement in hardware and software .
AES is said to have above-average performance in both hardware and software .

AES should be able to withstand all known methods of cryptanalysis , especially power and timing attacks.

Small resources should be required especially for use in smart cards (short code length, low memory requirement ).

The algorithm must be free of claims under patent law and it must be possible for anyone to use it free of charge.

The selection criteria were divided into three main categories: security, cost, and algorithm and implementation characteristics. Security was the most important factor in the evaluation and included the properties of the algorithm's resistance to cryptanalysis, randomness of the cipher, soundness of the mathematical basis and the relative security compared to the other candidates.

Cost, the next important factor, should be understood as an umbrella term in the context of the selection process: This encompassed licensing requirements as well as computational efficiency on different platforms and memory consumption. Since one of the most important goals that NIST had worked out was the worldwide distribution on a royalty-free basis and that AES could be used by everyone free of charge, public comments and suggestions on license claims and related potential conflicts were specifically sought.

The requirement for the speed of the algorithm on various platforms was divided into three additional goals:

The computational speed with 128-bit keys.
The computational speed with 192-bit and 256-bit keys as well as the computational speed of various hardware implementations. Memory usage and the limitations of the candidates' software implementations were other important considerations.
The third objective, the algorithm and implementation characteristics, included flexibility, suitability for software and hardware implementations, and simplicity of the algorithm.

Flexibility was understood to mean the properties that AES had to support the key and block size above the minimum and that it could be implemented securely and efficiently in different types of environments as well as a stream cipher and cryptological hash function .

By the deadline on June 15, 1998, the call for proposals led to fifteen proposals from all over the world. These were presented at the AES conference from August 20-22, 1998 in Ventura (California) , discussed publicly and checked for compliance with the criteria mentioned. The AES conference on April 22 and 23, 1999 in Rome led to an initial discussion of the results and recommendations as to which of the fifteen algorithms should be further considered. The five best candidates ( MARS , RC6 , Rijndael, Serpent , Twofish ) made it to the next round.

All five candidates meet the above requirements, so additional criteria were used. This was followed by a check of the algorithms for theoretical weak points, which could possibly make the algorithm unsafe at a later point in time due to technical progress. Technically not feasible procedures could be applicable in a few years at the time, and such a risk should be minimized. The grading of the candidates according to resource consumption and performance was clearer. The Rijndael algorithm had in hardware - and software - implementation proved to be faster than average. The other candidates each have minor weaknesses in different areas.

In May 2000 the analyzes and public discussions were completed and on October 2, 2000 the winner was finally announced: the Belgian algorithm Rijndael. Rijndael impressed with its simplicity (the reference implementation comprises less than 500 lines of C-code ), security and speed, which is why the USA decided on a European algorithm despite security concerns.

The selection process fascinated many cryptographers around the world, especially because of its open design. To this day, this competition is regarded as exemplary.

Working method

Rijndael is a block cipher designed as a substitution-permutation network . With Rijndael, block length and key length can be assigned the values 128, 160, 192, 224 or 256 bits independently of one another, while with AES the restriction of the specified block size of 128 bits and the key size of 128, 192 or 256 bits applies. Each block is first written into a two-dimensional table with four rows, the cells of which are one byte in size. The number of columns thus varies from 4 (128 bits) to 8 (256 bits) depending on the block size. Each block is then subjected to certain transformations one after the other. But instead of encrypting each block once with the key , Rijndael applies different parts of the extended original key to the plaintext block one after the other. The number of these rounds varies and is dependent on the maximum of the key length and the block size (with the AES only on the key length): ${\ displaystyle r}$ ${\ displaystyle k}$ ${\ displaystyle b}$

Number of laps at Rijndael
max (b, k)	128	160	192	224	256
Round r	10	11	12	13	14th

S-box

A substitution box (S-Box) serves as the basis for monoalphabetic encryption . It is usually implemented as an array and indicates how each byte of a block is to be replaced by a different value in each round. The S-Box is typically used in block ciphers to blur the relationship between plain text and ciphertext ( called confusion in cryptological terminology ). The S-Box of the AES also partially implements the Shannon principle of diffusion . The values of the S-Box and the inverse S-Box can be calculated dynamically in order to save memory or they can be precalculated and saved in an array. The S-Box consists of 256 bytes, which are constructed by first replacing every byte except zero, interpreted as a representative of the finite field , by its multiplicative inverse. The construction of the S-Box is subject to design criteria that are intended to minimize the susceptibility to the methods of linear and differential cryptanalysis as well as to algebraic attacks. ${\ displaystyle \ mathbb {F} _ {2 ^ {8}}}$

procedure

Key expansion
Preliminary round
- AddRoundKey (round key [0])
Encryption rounds (r = 1 to R-1)
- SubBytes ()
- ShiftRows ()
- MixColumns ()
- AddRoundKey (round key [r])
Final round
- SubBytes ()
- ShiftRows ()
- AddRoundKey (round key [R])

(The final round also counts as a round, i.e. R = number of encryption rounds + 1 final round)

Key expansion

Principle of key expansion at AES

First, partial keys (also called round keys) must be generated from the key . The round keys must be the same length as the blocks. Thus, the user key must be expanded to the length where the block size indicates. The key is mapped in a two-dimensional table with four rows and cells with a size of 1 byte. The first columns of the table are filled with the user key. The other columns are recursively calculated as follows : To get the values for the cells in the next column, the columns, which are a multiple of the fourth, sixth or eighth column depending on the block size, are rotated to the left ( becomes ) and with Encrypted using the S-Box. Then the "foremost" value of the column is linked with the rcon table XOR and finally the entire column is linked with the XOR column that is one key length behind. Similar to the S-Box, the rcon table is a table in the form of an array that contains constant values, in this case the powers of two. Every other column is formed one key length beforehand from an XOR link with the column. AES-256 is a specialty. There every 4th column (i.e. a column that normally gets by without rotation and so on) is replaced by the S-Box and then XORed with the column one key length beforehand. ${\ displaystyle R + 1}$ ${\ displaystyle b \ cdot (R + 1)}$ ${\ displaystyle b}$ ${\ displaystyle [a0, a1, a2, a3]}$ ${\ displaystyle [a1, a2, a3, a0]}$

AddRoundKey

Bitwise XOR link between the block and the current round key

The key addition is carried out in the preliminary round and at the end of each further encryption round. A bit-by-bit XOR link is made between the block and the current round key. This is the only function in AES that makes the algorithm dependent on the user key.

SubBytes

In the first step of each round, an equivalent is searched for in the S-box for each byte in the block. Thus, the data is encrypted in mono-alphabet .

ShiftRows

Rows are shifted left by a specified number of columns

As mentioned above, a block is in the form of a two-dimensional table with four rows. In this step, the rows are shifted to the left by a certain number of columns. Overflowing cells are continued from the right. The number of shifts depends on the row and block length:

r	b = 128	b = 160	b = 192	b = 224	b = 256
line 1	0	0	0	0	0
line 2	1	1	1	1	1
Line 3	2	2	2	2	3
Line 4	3	3	3	4th	4th

Depending on the block length b and the row in the data table, the row is shifted by 1 to 4 columns.
Only the values marked in bold are relevant for the AES.

MixColumns

The columns are shuffled

Eventually the data within the columns is merged. To calculate a byte of the new column, each byte of the old is multiplied by a constant (1, 2 or 3). This happens modulo of the irreducible polynomial in the Galois field . Then the results are XOR- linked: ${\ displaystyle b_ {j}}$ ${\ displaystyle a_ {j}}$ ${\ displaystyle x ^ {8} + x ^ {4} + x ^ {3} + x + 1}$ ${\ displaystyle GF (2 ^ {8})}$

{\ displaystyle b_ {0} = (a_ {0} \ cdot 2) \ oplus (a_ {1} \ cdot 3) \ oplus (a_ {2} \ cdot 1) \ oplus (a_ {3} \ cdot 1) }

{\ displaystyle b_ {1} = (a_ {0} \ cdot 1) \ oplus (a_ {1} \ cdot 2) \ oplus (a_ {2} \ cdot 3) \ oplus (a_ {3} \ cdot 1) }

{\ displaystyle b_ {2} = (a_ {0} \ cdot 1) \ oplus (a_ {1} \ cdot 1) \ oplus (a_ {2} \ cdot 2) \ oplus (a_ {3} \ cdot 3) }

{\ displaystyle b_ {3} = (a_ {0} \ cdot 3) \ oplus (a_ {1} \ cdot 1) \ oplus (a_ {2} \ cdot 1) \ oplus (a_ {3} \ cdot 2) }

In matrix notation:

{\ displaystyle {\ begin {pmatrix} b_ {0} \\ b_ {1} \\ b_ {2} \\ b_ {3} \ end {pmatrix}} = {\ begin {pmatrix} 2 & 3 & 1 & 1 \\ 1 & 2 & 3 & 1 \\ 1 & 1 & 2 & 3 \\ 3 & 1 & 1 & 2 \ end {pmatrix}} {\ begin {pmatrix} a_ {0} \\ a_ {1} \\ a_ {2} \\ a_ {3} \ end {pmatrix}}}

According to the laws of calculation in this Galois field, the following applies to multiplication:

${\ displaystyle a \ cdot 1 = a}$
${\ displaystyle a \ cdot 2 = {\ begin {cases} 2a & {\ text {if}} a <2 ^ {7} \\ 2a \ oplus (1 {\ text {b}}) _ {\ text {hex }} & {\ text {if}} a \ geq 2 ^ {7} \ end {cases}}}$
${\ displaystyle a \ cdot 3 = (a \ cdot 2) \ oplus a}$

The normal multiplication of a by 2 and the bit-wise XOR operation denotes . ${\ displaystyle 2a}$ ${\ displaystyle \ oplus}$

Decryption

The decryption of data is exactly backwards. The data is first read back into two-dimensional tables and the lap key is generated. However, the final round is now started and all functions are called in the reverse order in each round. Due to the many XOR operations, most functions for decryption do not differ from those for encryption. However, a different S-Box must be used (which can be calculated from the original S-Box) and the line shifts take place in the other direction.

application

AES will u. a. used by the IEEE 802.11i encryption standard for wireless LAN and its Wi-Fi equivalent WPA2 , for IEEE802.16 m ( WiMAX ), as well as for SSH and IPsec . Also in the IP telephony AES comes in both open protocols such as SRTP and proprietary systems such as Skype used. Mac OS X uses AES as the default encryption method for disk images, and the FileVault service uses AES. The transparent EFS encryption in Windows XP from SP 1 also uses this method. The algorithm is also used to encrypt various compressed file archives, e.g. B. 7-Zip and RAR . In PGP and GnuPG AES is also a wide range of applications. The Linear Tape Open Standard specifies an interface for AES encryption by the tape drive from LTO-4 and thus enables tape compression with simultaneous encryption.

AES is one of the cryptographic algorithms recommended by the NESSIE project and is part of Suite B of the NSA.

The AES algorithm is now supported in a number of CPUs from Intel or AMD by additional specialized machine commands , which means that encryption is 5 times and decryption 25 times faster than with non-specialized machine commands. This means that AES can also be used in a battery-saving manner for mobile applications and is suitable for mass use. Programming software libraries such as OpenSSL automatically detect whether the hardware supports AES and then use the hardware AES implementation instead of the slower software implementation.

AES-encrypted communication is also used to encrypt data transmission between electronic identity documents and inspection devices, for example with newer passports or the German ID card. This prevents eavesdropping on this communication. Here the calculation is mostly done in dedicated coprocessors for DES and AES, both considerably faster and more securely than possible in a CPU.

Weaknesses and attacks

Criticisms

Rijndael won the AES competition with its mathematically elegant and simple structure and its efficiency. However, some cryptographers saw this as a problem:

Depending on the key used, there is only a security margin of three (with a 128-bit key length) to five rounds (with a 256-bit key length).
Another point of criticism was the simple algebraic description of the S-boxes, which in turn are the only non-linear components of the cipher. This allows the entire algorithm to be described as a system of equations.
With the simple key schedule, 128 bits of the process key would also be compromised with any round key .

Biclique attack

At the rump session of the CRYPTO conference in August 2011, the cryptologists Andrey Bogdanov, Dmitry Khovratovich and Christian Rechberger presented the first attack on the full AES algorithm. With the different key lengths, this attack is on average around a factor of 4 faster than a complete search of the key space . This shows that AES can be attacked in principle, but is not relevant for practical security. The attack calculates the secret key of AES-128 in ^2,126.1 steps. AES-192 ^requires 2 ^189.7 steps and AES-256 2 ^254.4 steps.

XSL attack

In 2002 Courtois and Pieprzyk presented a theoretical attack called XSL ("eXtended Sparse Linearization") against Serpent and Rijndael (see Serpent ). According to the authors, a complexity in the range of ^2,100 operations can be achieved with the XSL attack . XSL is the further development of a heuristic technique called XL (“eXtended Linearization”), with which it is sometimes possible to efficiently solve large nonlinear systems of equations. XL was originally developed for the analysis of public key processes. The use in the context of symmetrical cryptosystems is an innovation by Courtois and Pieprzyk. The technology and its application to symmetrical cryptosystems can be roughly described as follows:

The block cipher is described as an over-specified system of quadratic equations in GF (2). Over-specified means that there are more equations than variables. Variables and constants can only have the values 0 and 1. The addition corresponds to the logical exclusive OdeR (XOR), the multiplication to the logical AND. Such an equation could look like this:

x ₁ + x ₂ x ₃ + x ₂ x ₄ = 1 (mod 2).

This equation consists of a linear term (the variable “x ₁ ”), two quadratic terms (“x ₂ x ₃ ” and “x ₂ x ₄ ”) and a constant term (“1”).

Some scientists, however, question the correctness of the estimates by Courtois and Pieprzyk:

“I believe that the Courtois-Pieprzyk work is flawed. They overcount the number of linearly independent equations. The result is that they do not in fact have enough linear equations to solve the system, and the method does not break Rijndael… The method has some merit, and is worth investigating, but it does not break Rijndael as it stands. "

“I think Courtois and Pieprzyk's work is flawed; they overestimate the number of linearly independent equations. The result is that in reality you don't get enough linear equations to solve the system, so Rijndael doesn't crack the method […] The method has its merits and is worth investigating further, but it cracks hers current form Rijndael not "

- Don Coppersmith

This type of system can typically become very large; in the case of the 128-bit AES variant, it grows to 8,000 quadratic equations with 1,600 variables, which means that the XSL attack cannot be used in practice. Solving systems of quadratic equations is an NP-hard problem with various fields of application in cryptography.

More attacks

Shortly before the announcement of the AES competition, various authors presented a simple algebraic representation of AES as a continued fraction . This could be used for successful attacks. There is a video lecture by Niels Ferguson at HAL 2001.

In 2003, Sean Murphy and Matt Robshaw discovered an alternative description of the AES by embedding it in a block cipher called BES, which works on data blocks of 128 bytes instead of data bits. The application of the XSL algorithm to BES reduced its complexity 2 ¹⁰⁰ when the cryptanalysis of Courtois and Pieprzyk is correct.

In May 2005, Daniel Bernstein published an article about an unexpectedly simple timing attack (a type of side channel attack ) on the Advanced Encryption Standard.

The researchers Alex Biryukov and Dmitry Khovratovich published an attack with a related key on the AES variants with 192 and 256 bit key length in mid-2009. They exploited weaknesses in the key expansion and were able to achieve a complexity of ^2,119 . This means that the AES variant with a 256-bit key length is formally weaker than the variant with a 128-bit key length. At the end of 2009, with an improvement in the attack, a complexity of only 2 ^{99.5 was} achieved. However, this attack has little relevance in practice, because AES remains practically computationally secure.

In March 2012 it was announced that the NSA was working on cracking AES in its new Utah data center, in addition to storing large parts of all Internet communications with enormous computing resources. The data center has been opening gradually since September 2013.

Craig Ramsay & Jasper Lohuis, as a research team from the two companies Fox-IT and Riscure, describe an attack in 2017 in which they use the radio signals emitted by the CPU for decryption. This means that the AES key can be determined in a maximum of five minutes if the sniffer and the attacked CPU are about 1 meter apart. At a distance of 30 centimeters, the process shrinks to about 50 seconds. Note: this attack relates to a single implementation of the algorithm on a particular CPU, not the algorithm itself. Such an attack can only be carried out under very limited conditions and cannot necessarily be generalized.

literature

Joan Daemen , Vincent Rijmen : The Design of Rijndael. AES: The Advanced Encryption Standard . Springer, Berlin a. a. 2002, ISBN 3-540-42580-2 ( Information Security and Cryptography ), (English).

Web links

Official specification of the AES from NIST, doi: 10.6028 / NIST.FIPS.197
Attacks on the security of AES
Description by Markus Repges of the AES candidates (finalists)
NIST, Report on the Development of the Advanced Encryption Standard (AES), October 2, 2000 (PDF; 383 kB)
Animation of AES in English - AES explained and animated with Flash (Flash animation by Enrique Zabala / University ORT / Montevideo / Uruguay). Also available in German as a ZIP file . This animation is (in German, English and Spanish) also part of CrypTool 1 , menu Individual procedures -> Visualization of algorithms -> AES.
AESPipe - Convenient encryption / decryption of data streams for the Linux shell (StdIn to StdOut)
AES article - Very detailed German explanation of the AES including calculation examples and implementation in the C programming language
Applied Crypto ++: Block Ciphers An article about Crypto ++ on codeproject.com entitled Encrypt Data using Symmetric Encryption with Crypto ++

Individual evidence

↑ In the Rijndael algorithm, block sizes of 128, 160, 192, 224, and 256 bits are supported, but in the AES standard only a 128-bit block size is specified.

^ ^A ^b Andrey Bogdanov, Dmitry Khovratovich, Christian Rechberger: Biclique Cryptanalysis of the Full AES . In: ASIACRYPT 2011 (= Lecture Notes in Computer Science ). tape 7073 . Springer, 2011, p. 344-371 ( microsoft.com [PDF; accessed November 29, 2012]). Biclique Cryptanalysis of the Full AES ( Memento from March 6, 2016 in the Internet Archive )

^ Committee on National Security Systems: CNSS Policy No. 15, Fact Sheet No. 1 . 2003, p. 2 ( nist.gov [PDF]).

↑ Tom Berson: Skype Security Evaluation ( Memento from October 25, 2005 in the Internet Archive ) on skype.com with signature , October 18, 2005, English, PDF

↑ Oliver Lau (2013): “Special command. Fast AES ciphers with intrinsics ”in: c't 2013, issue 14, pages 174–177. Quoted statement see pages 176 and 177.

^ ^A ^b Niels Ferguson , Bruce Schneier : Practical Cryptography . Wiley Publishing, Indianapolis 2003, ISBN 978-0-471-22357-3 , pp. 56 .

↑ Comments from Readers

↑ ftp.ccc.de

↑ Cache-timing attacks on AES (PDF version; 426 kB)

↑ FAQ on the attack ( Memento from November 13, 2013 in the Internet Archive )

↑ ^a ^b Biryukov, Alex; Khovratovich, Dmitry: "Related-key Cryptanalysis of the Full AES-192 and AES-256" , (December 4, 2009)

↑ The NSA Is Building the Country's Biggest Spy Center (Watch What You Say)

↑ Report: Largest NSA data center is warming up

↑ fox-it.com

↑ Dusan Zivadinovic: Stealing AES keys: Van Eck phreaking for 200 euros. Retrieved September 18, 2017 .

[blocksize-1] In the Rijndael algorithm, block sizes of 128, 160, 192, 224, and 256 bits are supported, but in the AES standard only a 128-bit block size is specified.