18 Advanced Encryption Standard(part1)

AES (Part 1)

Availability of advanced computing systems make ease to break the ciphers that we have discussed so far. A replacement of DES was needed because of small key size. Triple DES is too slow because we have to run 48 rounds effectively. So it is not a good solution. The Advanced Encryption Standard (AES) is a successor of many algorithms which are later proved to be vulnerable. The AES algorithm is a symmetric encryption algorithm which uses a single key for both encryption and decryption process. AES is also the official encryption used by the government of United States of America and Canada. It is used for both encryption of data in transit (data uploading and downloading) and for data at rest (Data in Hard Drive and other storage devices). Though they will use a 256 bit encryption key to encrypt the data.

In 1997, National Institute for Standards and Technology send out for an open call for ciphers. Private key symmetric block cipher ,128-bit data, 128/192/256-bit keys ,Stronger & faster than Triple-DES ,Provide full specification & design details ,Both C and Java implementations were NIST’s requirements for the AES candidate submissions. In fact, two set of criteria evolved. When NIST issued its original request for candidate algorithm nominations in 1997, the request stated that candidate algorithms would be compared based on the factors shown in Stallings Table5.1, which were used to evaluate field of 15 candidates to select shortlist of 5. These had categories of security, cost, and algorithm & implementation characteristics. The final criteria evolved during the evaluation process, and were used to select Rijndael from that short-list and different categories of: general security, ease of software & hardware implementation, implementation attacks, & flexibility (in en/decrypt,keying, other factors).

The AES shortlist of 5 ciphers as:

MARS (IBM) – complex, fast, high security margin

RC6 (USA) – v. simple, v. fast, low security margin

Rijndael (Belgium) – clean, fast, good security margin

Serpent (Euro) – slow, clean, v. high security margin

Twofish (USA) – complex, v. fast, high security margin

Note mix of commercial (MARS, RC6, Twofish) verses academic (Rijndael, Serpent) proposals, sourced from various countries.

All were thought to be good – it came down to the best balance of attributes to meet criteria, in particular the balance between speed, security & flexibility.

Rijndael was selected as the AES in Oct-2000. It was designed by Vincent Rijmen and Joan Daemen in Belgium and issued as FIPS PUB 197 standard in Nov-2001 .AES isaAn iterative rather than Feistel cipher.ie, processes data as block of 4 columns of 4 bytes (128 bits) and operates on entire data block in every round .

Rounds in AES

Rounds are (almost) identical
- First and last round are a little different

The input to the AES encryption and decryption algorithms is a single 128-bit block, depicted in FIPS PUB 197, as a square matrix of bytes .This block is copied into the State array, which is modified at each stage of encryption or decryption. After the final stage, State is copied to an output.

The key is expanded into 44/52/60 lots of 32-bit words (see later), with 4 used in each round.

The data computation then consists of an “add round key” step, then 9/11/13 rounds with all 4 steps, and a final 10th/12th/14th step of byte subs + mix cols + add round key. This can be viewed as alternating XOR key & scramble data bytes operations. All of the steps are easily reversed, and can be efficiently implemented using XOR’s & table lookups.

The above figure shows the overall structure of AES.

Data block viewed as 4-by-4 table of bytes and it is represented as 4 by 4 matrix of 8-bit bytes. Key is expanded to array of 32 bits words

Data Unit

The above figure shows the data unit. Block to state transformation is done as shown in figure below.

Now we are going see how the plaintext is converted to state.

Details of Each Round.

Each round consists of four operations namely SubBytes, ShiftRows , MixColumns, Add Round key as shown in figure.

Now discuss each of the four stages used in AES. The Substitute bytes stage uses an S-box to perform a byte-by-byte substitution of the block. There is a single 8-bit wide S-box used on every byte. This S-box is a permutation of all 256 8-bit values, constructed using a transformation which treats the values as polynomials in GF(28) – however it is fixed, so really only need to know the table when implementing. Decryption requires the inverse of the table. These tables are given in Stallings Table 4.5.

The table was designed to be resistant to known cryptanalytic attacks. Specifically, the Rijndael developers sought a design that has a low correlation between input bits and output bits, with the property that the output cannot be described as a simple mathematical function of the input, with no fixed points and no “opposite fixed points”.

SubBytes: Byte Substitution

The SubBytes and InvSubBytes transformations are inverses of each other.

A simple substitution of each byte provide a confusion. Uses one S-box of 16×16 bytes containing a permutation of all 256 8-bit values. Each byte of state is replaced by byte indexed by row (left 4-bits) & column (right 4-bits).

For eg. byte {95} is replaced by byte in row 9 column 5 which has value {2A}

The SubBytes operation involves 16 independent byte-to-byte transformations.