Assignment 5

The following is the input to the round 1 Byte Substitution

Layer in AES.

1111100111101001110010011110000111011001111011

0100111001111000001110000110000001100000011111

111111111001111110011110000111101111

1. What will be the output to the Byte Substitution

Layer?

2. What will be the output to the ShiftRows Layer?

For Byte Subtituition, please use the table posted below

S-Box: The s-box is designed to be resistant to known cryptanalytic attacks.

Therefore, the same byte should not ne substituted by itself and the sum of

two bytes X and Y should mot be substituted with Sub(X)+Sub(Y).

How to read S-Box: Each column and row entry is a 4 bit HEX number.

One Column Entry and one Row Entry together make one byte (8-bit). In

addition, each cell entry is a byte, represented in HEX.

Replace a “Byte” formed by a pair of “Column Entry-Row Entry” with the

corresponding “Cell Entry.” For instance: “71” is replaced by “A3”; in binary

01110001 is substituted with 10100011.

Understanding Cryptography

by Christof Paar and Jan Pelzl

www.crypto-textbook.com

Chapter 4 â€“ The Advanced Encryption

Standard (AES)

ver. October 28, 2009

These slides were prepared by Daehyun Strobel, Christof Paar and Jan Pelzl

Some legal stuff (sorry): Terms of Use

â€¢ The slides can used free of charge. All copyrights for the slides remain with

Christof Paar and Jan Pelzl.

â€¢ The title of the accompanying book â€œUnderstanding Cryptographyâ€ by

Springer and the authorâ€™s names must remain on each slide.

â€¢ If the slides are modified, appropriate credits to the book authors and the

book title must remain within the slides.

â€¢ It is not permitted to reproduce parts or all of the slides in printed form

whatsoever without written consent by the authors.

2/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Content of this Chapter

â€¢ Overview of the AES algorithm

â€¢ Internal structure of AES

â€¢ Byte Substitution layer

â€¢ Diffusion layer

â€¢ Key Addition layer

â€¢ Key schedule

â€¢ Decryption

â€¢ Practical issues

3/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Content of this Chapter

â€¢ Overview of the AES algorithm

â€¢ Internal structure of AES

â€¢ Byte Substitution layer

â€¢ Diffusion layer

â€¢ Key Addition layer

â€¢ Key schedule

â€¢ Decryption

â€¢ Practical issues

4/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Some Basic Facts

â€¢ AES is the most widely used symmetric cipher today

â€¢ The algorithm for AES was chosen by the US National Institute of Standards

and Technology (NIST) in a multi-year selection process

â€¢ The requirements for all AES candidate submissions were:

â€¢ Block cipher with 128-bit block size

â€¢ Three supported key lengths: 128, 192 and 256 bit

â€¢ Security relative to other submitted algorithms

â€¢ Efficiency in software and hardware

5/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Chronology of the AES Selection

â€¢ The need for a new block cipher announced by NIST in January, 1997

â€¢ 15 candidates algorithms accepted in August, 1998

â€¢ 5 finalists announced in August, 1999:

â€¢ Mars â€“ IBM Corporation

â€¢ RC6 â€“ RSA Laboratories

â€¢ Rijndael â€“ J. Daemen & V. Rijmen

â€¢ Serpent â€“ Eli Biham et al.

â€¢ Twofish â€“ B. Schneier et al.

â€¢ In October 2000, Rijndael was chosen as the AES

â€¢ AES was formally approved as a US federal standard in November 2001

6/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

AES: Overview

The number of rounds depends on the chosen key length:

7/28

Key length (bits)

Number of rounds

128

10

192

12

256

14

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

AES: Overview

â€¢ Iterated cipher with 10/12/14 rounds

â€¢ Each round consists of â€œLayersâ€

8/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Content of this Chapter

â€¢ Overview of the AES algorithm

â€¢ Internal structure of AES

â€¢ Byte Substitution layer

â€¢ Diffusion layer

â€¢ Key Addition layer

â€¢ Key schedule

â€¢ Decryption

â€¢ Practical issues

9/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Internal Structure of AES

â€¢ AES is a byte-oriented cipher

â€¢ The state A (i.e., the 128-bit data path) can be arranged in a 4×4 matrix:

A0

A4

A8

A12

A1

A5

A9

A13

A2

A6

A10 A14

A3

A7

A11

A15

with A0,â€¦, A15 denoting the 16-byte input of AES

10/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Internal Structure of AES

â€¢ Round function for rounds 1,2,â€¦,nr-1:

â€¢ Note: In the last round, the MixColumn tansformation is omitted

11/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Byte Substitution Layer

â€¢ The Byte Substitution layer consists of 16 S-Boxes with the

following properties:

The S-Boxes are

â€¢ identical

â€¢ the only nonlinear elements of AES, i.e.,

ByteSub(Ai) + ByteSub(Aj) â‰ ByteSub(Ai + Aj), for i,j = 0,â€¦,15

â€¢ bijective, i.e., there exists a one-to-one mapping of input and

output bytes

â‡’ S-Box can be uniquely reversed

â€¢ In software implementations, the S-Box is usually realized as a

lookup table

12/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Diffusion Layer

The Diffusion layer

â€¢ provides diffusion over all input state bits

â€¢ consists of two sublayers:

â€¢ ShiftRows Sublayer: Permutation of the data on a byte level

â€¢ MixColumn Sublayer: Matrix operation which combines (â€œmixesâ€) blocks of

four bytes

â€¢ performs a linear operation on state matrices A, B, i.e.,

DIFF(A) + DIFF(B) = DIFF(A + B)

13/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

ShiftRows Sublayer

â€¢ Rows of the state matrix are shifted cyclically:

Input matrix

Output matrix

14/28

B0

B4

B8

B12

B1

B5

B9

B13

B2

B6

B10 B14

B3

B7

B11

B15

B0

B4

B8

B12

B5

B9

B13 B1

no shift

â† one position left shift

B10 B14 B2

B6

â† two positions left shift

B15 B3

B11

â† three positions left shift

B7

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

MixColumn Sublayer

â€¢ Linear transformation which mixes each column of the

state matrix

â€¢ Each 4-byte column is considered as a vector and multiplied

by a fixed 4×4 matrix, e.g.,

ï£« C0 ï£¶ ï£« 02

ï£¬ ï£· ï£¬

ï£¬ C1 ï£· ï£¬ 01

ï£¬ C ï£· = ï£¬ 01

ï£¬ï£¬ 2 ï£·ï£· ï£¬ï£¬

ï£ C3 ï£¸ ï£ 03

03 01 01ï£¶ ï£« B0 ï£¶

ï£·

ï£· ï£¬

02 03 01ï£· ï£¬ B5 ï£·

â‹…ï£¬

ï£·

01 02 03 B10 ï£·

ï£·ï£·

ï£·ï£· ï£¬ï£¬

01 01 02 ï£¸ ï£ B15 ï£¸

where 01, 02 and 03 are given in hexadecimal notation

â€¢ All arithmetic is done in the Galois field GF(28) (for more information see

Chapter 4.3 in Understanding Cryptography)

15/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Key Addition Layer

â€¢ Inputs:

â€¢ 16-byte state matrix C

â€¢ 16-byte subkey ki

â€¢ Output: C âŠ• ki

â€¢ The subkeys are generated in the key schedule

16/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Key Schedule

â€¢ Subkeys are derived recursively from the original 128/192/256-bit input key

â€¢ Each round has 1 subkey, plus 1 subkey at the beginning of AES

Key length (bits)

Number of subkeys

128

11

192

13

256

15

â€¢ Key whitening: Subkey is used both at the input and output of AES

â‡’ # subkeys = # rounds + 1

â€¢ There are different key schedules for the different key sizes

17/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Key Schedule

Example: Key schedule for 128-bit key AES

â€¢ Word-oriented: 1 word = 32 bits

â€¢ 11 subkeys are stored in W[0]â€¦W[3],

W[4]â€¦W[7], â€¦ , W[40]â€¦W[43]

â€¢ First subkey W[0]â€¦W[3] is the original

AES key

18/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Key Schedule

â€¢ Function g rotates its four input bytes and performs a bytewise S-Box substitution

â‡’ nonlinearity

â€¢ The round coefficient RC is only added to the leftmost

byte and varies from round to round:

RC[1] = x0 = (00000001)2

RC[2] = x1 = (00000010)2

RC[3] = x2 = (00000100)2

…

RC[10] = x9 = (00110110)2

â€¢ xi represents an element in a Galois field

(again, cf. Chapter 4.3 of Understanding Cryptography)

19/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Content of this Chapter

â€¢ Overview of the AES algorithm

â€¢ Internal structure of AES

â€¢ Byte Substitution layer

â€¢ Diffusion layer

â€¢ Key Addition layer

â€¢ Key schedule

â€¢ Decryption

â€¢ Practical issues

20/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Decryption

â€¢ AES is not based on a Feistel network

â‡’ All layers must be inverted for decryption:

â€¢ MixColumn layer â†’ Inv MixColumn layer

â€¢ ShiftRows layerâ†’ Inv ShiftRows layer

â€¢ Byte Substitution layer â†’ Inv Byte

Substitution layer

â€¢ Key Addition layer is its own inverse

21/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Decryption

â€¢ Inv MixColumn layer:

â€¢ To reverse the MixColumn operation, each column of the state matrix C

must be multiplied with the inverse of the 4×4 matrix, e.g.,

ï£« B0 ï£¶ ï£« 0E 0B 0D 09 ï£¶ ï£« C0 ï£¶

ï£¬ ï£· ï£¬

ï£· ï£¬ ï£·

B

09

0

E

0

B

0

D

ï£¬ 1ï£· ï£¬

ï£· ï£¬ C1 ï£·

ï£¬ B ï£· = ï£¬ 0D 09 0E 0B ï£· â‹… ï£¬ C ï£·

ï£¬ï£¬ 2 ï£·ï£· ï£¬ï£¬

ï£·ï£· ï£¬ï£¬ 2 ï£·ï£·

ï£ B3 ï£¸ ï£ 0B 0D 09 0E ï£¸ ï£ C3 ï£¸

where 09, 0B, 0D and 0E are given in hexadecimal notation

â€¢ Again, all arithmetic is done in the Galois field GF(28) (for more information

see Chapter 4.3 in Understanding Cryptography)

22/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Decryption

â€¢ Inv ShiftRows layer:

â€¢ All rows of the state matrix B are shifted to the opposite direction:

Input matrix

Output matrix

B0

B4

B8

B12

B1

B5

B9

B13

B2

B6

B10 B14

B3

B7

B11

B15

B0

B4

B8

B12

B13 B1

B5

B9

â†’ one position right shift

B10 B14 B2

B6

â†’ two positions right shift

B7

23/28

B11

B15 B3

no shift

â†’ three positions right shift

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Decryption

â€¢ Inv Byte Substitution layer:

â€¢ Since the S-Box is bijective, it is possible to construct an inverse, such that

Ai = S-1(Bi) = S-1(S(Ai))

â‡’ The inverse S-Box is used for decryption. It is usually realized as a lookup

table

â€¢ Decryption key schedule:

â€¢ Subkeys are needed in reversed order (compared to encryption)

â€¢ In practice, for encryption and decryption, the same key schedule is used.

This requires that all subkeys must be computed before the encryption of the

first block can begin

24/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Content of this Chapter

â€¢ Overview of the AES algorithm

â€¢ Internal structure of AES

â€¢ Byte Substitution layer

â€¢ Diffusion layer

â€¢ Key Addition layer

â€¢ Key schedule

â€¢ Decryption

â€¢ Practical issues

25/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Implementation in Software

â€¢ One requirement of AES was the possibility of an efficient software implementation

â€¢ Straightforward implementation is well suited for 8-bit processors (e.g., smart cards),

but inefficient on 32-bit or 64-bit processors

â€¢ A more sophisticated approach: Merge all round functions (except the key addition)

into one table look-up

â€¢ This results in four tables with 256 entries, where each entry is 32 bits wide

â€¢ One round can be computed with 16 table look-ups

â€¢ Typical SW speeds are more than 1.6 Gbit/s on modern 64-bit processors

26/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Security

â€¢ Brute-force attack: Due to the key length of 128, 192 or 256

bits, a brute-force attack is not possible

â€¢ Analytical attacks: There is no analytical attack known that is

better than brute-force

â€¢ Side-channel attacks:

â€¢ Several side-channel attacks have been published

â€¢ Note that side-channel attacks do not attack the underlying

algorithm but the implementation of it

27/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Lessons Learned

â€¢ AES is a modern block cipher which supports three key lengths of 128, 192 and 256 bit. It

provides excellent long-term security against brute-force attacks.

â€¢ AES has been studied intensively since the late 1990s and no attacks have been found that

are better than brute-force.

â€¢ AES is not based on Feistel networks. Its basic operations use Galois field arithmetic and

provide strong diffusion and confusion.

â€¢ AES is part of numerous open standards such as IPsec or TLS, in addition to being the

mandatory encryption algorithm for US government applications. It seems likely that the

cipher will be the dominant encryption algorithm for many years to come.

â€¢ AES is efficient in software and hardware.

28/28

Chapter 4 of Understanding Cryptography by Christof Paar and Jan Pelzl

Purchase answer to see full

attachment