Chapter 7 The Advanced Encryption Standard (AES)

1 Chapter 7 The Advanced Encryption Standard (AES)All of the cryptographic algorithms we have looked at so far have some problem. Theearlier ciphers can be broken with ease on modern computation systems. The DESalgorithm was broken in 1998 using a system that cost about $250,000. It was also fartoo slow in software as it was developed for mid-1970 s hardware and does not produceefficient software code. Triple DES on the other hand, has three times as many roundsas DES and is correspondingly slower. As well as this, the 64 bit block size of tripleDES and DES is not very efficient and is questionable when it comes to was required was a brand new Encryption algorithm. One that would be resis-tant to all known attacks.

2 The National Institute of standards and Technology (NIST)wanted to help in the creation of a new Standard . However, because of the controversythat went with the DES algorithm, and the years of some branches of the govern-ment trying everything they could to hinder deployment of secure cryptography thiswas likely to raise strong skepticism. The problem was that NIST did actually wantto help create a new excellent Encryption Standard but they couldn t get involved di-rectly. Unfortunately they were really the only ones with the technical reputation andresources to the lead the of designing or helping to design a cipher, what they did instead was to set upa contest in which anyone in the world could take part.

3 The contest was announced onthe 2nd of January 1997 and the idea was to develop a new Encryption algorithm thatwould be used for protecting sensitive, non-classified, government ciphers had to meet a lot of requirements and the whole design had to be fully doc-umented (unlike the DES cipher). Once the candidate algorithms had been submitted,several years of scrutinisation in the form of cryptographic conferences took place. Inthe first round of the competition15algorithms were accepted and this was narrowedto5in the second round. The fifteen algorithms are shown in table 7 of which the5that were selected are shown in bold. The algorithms were tested for efficiency andsecurity both by some of the worlds best publicly renowned cryptographers and all this investigation NIST finally chose an algorithm known asRijndael.

4 Rijn-dael was named after the two Belgian cryptographers who developed and submitted it- Dr. Joan Daemen of Proton World International and Dr. Vincent Rijmen, a postdoc-toral researcher in the Electrical Engineering Department of Katholieke UniversisteitLeuven. On the 26 November 2001, AES (which is a standarised version of Rijndael)58 Chapter 7 The AES AlgorithmALGORITHM NAMESUBMITTERCAST-256 Entrust Technologies, Systems, Outerbridge, Lars KnudsenCNRS - Centre NationalDFCpour la Recherche Scientifique -Ecole Normale SuperieureE2 NTT - Nippon Telegraph and Telephone CorporationFROGTecApro Internacional SchroeppelLOKI97 Lawrie Brown, Josef Pieprzyk, Jennifer SeberryMAGENTAD eutsche Telekom AGMARSIBMRC 6 RSA LaboratoriesRijndaelJoaen Daemen, Vincent RijmenSAFER+Cylink CorporationSerpentRoss Anderson, Eli Biham, Lars KnudsenBruce Schneier, John Kelsey,TwofishDoug Whiting, David Wagner,Chris Hall, Niels Fergusonbecame a FIPS Standard (FIPS 197).

5 The AES cipherLike DES, AES is a symmetric block cipher. This means that it uses the same keyfor both Encryption and decryption. However, AES is quite different from DES in anumber of ways. The algorithm Rijndael allows for a variety of block and key sizesand not just the 64 and 56 bits of DES block and key size. The block and key canin fact be chosen independently from128,160,192,224,256bits and need not be thesame. However, the AES Standard states that the algorithm can only accept a blocksize of 128 bits and a choice of three keys -128,192,256bits. Depending on whichversion is used, the name of the Standard is modified to AES-128, AES-192 or AES-256 respectively. As well as these differences AES differs from DES in that it is nota feistel structure.

6 Recall that in a feistel structure, half of the data block is used tomodify the other half of the data block and then the halves are swapped. In this casethe entire data block is processed in parallel during each round using substitutions number of AES parameters depend on the key length. For example, if the key sizeused is 128 then the number of rounds is 10 whereas it is 12 and 14 for 192 and256 bits respectively. At present the most common key size likely to be used is the128 bit key. This description of the AES algorithm therefore describes this particular59 Chapter 7 The AES was designed to have the following characteristics: Resistance against all known attacks.

7 Speed and code compactness on a wide range of platforms. Design overall structure of AES can be seen in The input is a single 128 bit blockboth for decryption and Encryption and is known as theinmatrix. This block is copiedinto astatearray which is modified at each stage of the algorithm and then copied toan output matrix (see figure ). Both the plaintext and key are depicted as a 128 bitsquare matrix of bytes. This key is then expanded into an array of key schedule words(thewmatrix). It must be noted that the ordering of bytes within theinmatrix is bycolumn. The same applies to Inner Workings of a RoundThe algorithm begins with anAdd round keystage followed by 9 rounds of four stagesand a tenth round of three stages.

8 This applies for both Encryption and decryption withthe exception that each stage of a round the decryption algorithm is the inverse of it scounterpart in the Encryption algorithm. The four stages are as Round KeyThe tenth round simply leaves out theMix Columnsstage. The first nine rounds ofthe decryption algorithm consist of the Shift Substitute Add Round Mix ColumnsAgain, the tenth round simply leaves out theInverse Mix Columnsstage. Each ofthese stages will now be considered in more 7 The AES AlgorithmFigure :Overall structure of the AES Substitute BytesThis stage (known as SubBytes) is simply a table lookup using a16 16matrix of bytevalues called ans-box. This matrix consists of all the possible combinations of an8bitsequence (28= 16 16 = 256).

9 However, the s-box is not just a random permutationof these values and there is a well defined method for creating the s-box tables. Thedesigners of Rijndael showed how this was done unlike the s-boxes in DES for whichno rationale was given. We will not be too concerned here how the s-boxes are madeup and can simply take them as table the matrix that gets operated upon throughout the Encryption is known will be concerned with how this matrix is effected in each round. For this particular61 Chapter 7 The AES AlgorithmFigure : data structures in the AES each byte is mapped into a new byte in the following way: the leftmost nibbleof the byte is used to specify a particular row of the s-box and the rightmost nibblespecifies a column.

10 For example, the byte{95}(curly brackets represent hex valuesin FIPS PUB 197) selects row9column5which turns out to contain the value{2A}.This is then used to update thestatematrix. Figure depicts this :Substitute Bytes Stage of the AES Inverse substitute byte transformation (known as InvSubBytes) makes use of aninverse s-box. In this case what is desired is to select the value{2A}and get the value{95}. Table shows the two s-boxes and it can be verified that this is in fact the 7 The AES AlgorithmThe s-box is designed to be resistant to known cryptanalytic attacks. Specifically, theRijndael developers sought a design that has a low correlation between input bits andoutput bits, and the property that the output cannot be described as a simple mathemat-ical function of the input.