AES algorithm

The amount of processing capacity available at the end of the 1990s, as the result of technical progress and the international networking of computers, was sufficient to allow even ambitious private individuals with organizational abilities to mount successful brute-force attacks on the DES algorithm. As a result, the future viability of DES became so questionable that the relevant national authorities increasingly devoted their attention to specifying a new symmetrical cryptographic algorithm as the official successor to DES. In light of the never fully extinguished doubts about the integrity of DES arising from the fact that not all of the design criteria were made available for public inspection, in 1997 the US National Institute of Standards and Technology (NIST) requested the international cryptographic community to submit possible successors to DES, accompanied by all associated documentation, to the NIST for a sort of competitive evaluation. In 1998, the NIST announced that there were 15 candidates for the Advanced Encryption Standard (AES) and published all of the documentation so that it could be studied with regard to informatics and cryptanalytical aspects by the US National Security Agency (NSA), research institutes, experts and interested parties. Following detailed investigations of these methods and broad public discussion of the results, a candidate for the successor to the DES algorithm was announced by the NIST in 2000.5 This algorithm was developed by the Belgian cryptologists Joan Daemen and Vincent Rijmen and was already

known as the Rijndael algorithm prior to the announcement of the competition. AES is a symmetric block encryption algorithm with a block length of 128 bits (16 bytes)

that can be used with three different key lengths: 128 bits (16 bytes), 192 bits (24 bytes) and 256 bits (32 bytes). It is thus referred to as AES-128, AES-192 or AES-256, depending on the key length.AEScan be implemented in hardware logic, and good software implementations are also possible using relatively low-performance 8-bit processors as well as high-performance 16-and 32-bit processors. Furthermore, it can be used throughout the world free of licensing fees, and according to the official pronouncement its anticipated useful life is more than 20 years. AES is standardized by FIPS 197, which is available free of charge via the Internet [NIST]. The size of the key space of theAESalgorithm with a 128-bit key is approximately 3.4×1038 (2128), which makes it a factor of 4.7 × 1021 greater than the key space of DES with a 56-bit key. The large key space obtained with a key length of only 128 bits enormously increases the difficulty of attacks involving successively testing all possible keys. The software implementation of AES in a DPA-resistant form in a smart card occupies approximately 4 kB of ROM.

Operating modes for block-oriented encryption algorithms

The DES algorithm, like every block-oriented encryption algorithm, can be used in four different operating modes that are standardized in ISO 8372. Two of these operating modes, the CFB and OFB modes, are especially suitable for sequential text with no block structure. The other two, the ECB and CBC modes, are based on a block size of 8 bytes. These two block-oriented modes are most commonly used in smart card applications. The basic operating mode of the DES algorithm is designated as the ECB (electronic code book) mode. In this mode, 8-byte plaintext blocks are independently encrypted using a single key. This is the DES algorithm in its pure form, without extensions. The second block-oriented mode is known as the CBC (cipher block chaining) mode. In this mode, a data string consisting of several blocks is chained using XOR operations during the encryption such that each block becomes dependent on the block preceding it. This makes it possible to reliably detect interchanging, adding or deleting encrypted blocks. This is not possible with the ECB mode. If the plaintext blocks are suitably structured (with sequence counters in their headers or initialization vectors), a consequence of CBC chaining is that even identical plaintext blocks are converted into non-identical ciphertext blocks. This makes the cryptanalysis of intercepted data much more difficult, since codebook analysis (for example) is not possible. The first plaintext block is XOR-ed with an initialization vector (often called an IV), and then encrypted with the DES algorithm. The result is the ciphertext, which is in turn XOR-ed with following plaintext block. The process continues in this manner with the following blocks. As a rule, the initialization vector is preset to null. However, in some systems, a session-specific random number is written to the initialization vector as a substitute for a temporary key. This number must naturally be known when the data are subsequently deciphered.

Multiple encryption

In addition to the four operating modes of a block-oriented encryption algorithm, another variation is also used to improve security. However, it is actually only used with the DES algorithm, due to the small key space of this algorithm. In principle, it can be used with any block-oriented encryption algorithm that is not a group. If an encryption method has the group property, double encryption using two different keys will not increase the level of security, since the same result could be obtained by single encryption using a third key. The size of the key space is not increased by double encryption using an algorithm that has the group property, since an attacker would only have to discover the third key in order to obtain the result previously obtained by double encryption using two different keys: ciphertext = enc (key 2; (enc (key 1; plaintext)) Since DES is not a group, the result of double DES encryption using two different keys fundamentally cannot be duplicated by single encryption using a third key. However, in 1981 Ralph C. Merkle and Martin E. Hellman published a method of attack called the ‘meet-in-the-middle’ attack [Merkle 81], which can be used very successfully against every type of double encryption using a block-oriented encryption algorithm. It presupposes that the attacker knows several plaintext–ciphertext pairs. The operating principle of this attack is based on computing all possible encryptions of the plaintext using the first of the two keys, followed by decrypting the known result (the ciphertext) with every possible second key. The set of results from the first process is then compared with the set of results from the second process. If a match can be found, there is a certain probability that the two keys have been discovered. The level of confidence that the correct key has been found can be increased by making the same comparisons using additional known plaintext–ciphertext pairs. As can be seen, the amount of effort required for this attack is not significantly greater that the amount of effort needed for a normal attack that requires the entire key space to be searched. Consequently, cascaded double encryption is not used with the DES algorithm.

The process that is used instead is called triple-DES. In this mode, three sequential CBCmode DES operations are performed using alternating encryption and decryption. Blocks that have been encrypted in this manner are decrypted by reversing the order of the operations (in other words: decryption, encryption and then decryption). If all three keys are the same, the result of the alternating encryption and decryption operations is the same as that obtained by a single encryption. This is the reason for not using a sequence of three encryption operations. If the three DES operations using three keys are applied directly to each plaintext block in turn, the process is referred to as ‘DES in the inner CBC mode’. If instead the plaintext is first completely encrypted using the first key and the result is then further encrypted in a similar manner, the process is referred to as ‘DES in the outer CBC mode’. The outer CBC mode is more resistant to attack and is therefore generally recommended [Schneier 96]. The triple-DES algorithm has several other names, such as TDES, DES-3, 3-DES and 2-DES. Actually, the terms ‘triple-DES’ and ‘3-DES’ only mean that three 56-bit keys are used. If the first and third keys are the same, this is called 2-DES, but if the three keys are all different, the designation 3-DES is often used. The key length must always be stated with triple DES in order to unambiguously specify the algorithm. The triple-DES algorithm is significantly more secure than sequential double encryption using two different keys, since the meet-in-the-middle attack is not effective against this method. Three 56-bit keys are needed instead of only one, but the first and third keys are usually the same. This yields a key length of 2 × 56 bits. This means that this procedure is datacompatible with the normal DES algorithm and that it imposes no additional costs except for the doubled key size. This in particular is one of the main reasons for the widespread use of triple-DES in smart cards. It is primarily used for deriving keys and protecting very sensitive data, such as when transferring keys, due to its improved level of security compared with single encryption.