TWO WEEKS TO AES
FINITE FIELD ARITHMETIC
— In Advanced Encryption Standard (AES) all operations performed on 8-bit bytes
— The arithmetic operations of addition, multiplication, and division are performed over
the finite field GF(28)
— Field = a set in which we can do addition, subtraction, multiplication, and division
without leaving the set
— Division is defined with the following rule:
o a / b = a (b-1)
— An example of a finite field (one with a finite number of elements) is the set Z p
consisting of all the integers {0, 1, . . . . , p - 1}, where p is a prime number and in
which arithmetic is carried out modulo p
— Virtually all encryption algorithms, both conventional and public-key, involve
arithmetic operations on integers.
— Why finite field? Why polynomial arithmetic?
AES ENCRYPTION PROCESS
AES DATA STRUCTURES
AES PARAMETERS
AES ENCRYPTION AND DECRYPTION
DETAILED STRUCTURE
— Processes the entire data block as a single matrix during each round (Different from
Feistel in DES)
— The 128-bit key that is provided as input is expanded into an array of forty-four 32-
bit words
— Four different states per round:
o Substitute bytes, ShiftRows, MixColumns and AddRoundKey
— The cipher begins and ends with an AddRoundKey stage
— Can view the cipher as alternating operations of XOR encryption (AddRoundKey) of a
block, followed by scrambling of the block (the other three stages), followed by XOR
encryption
— Each stage is easily reversible
— The decryption algorithm makes use of the expanded key in reverse order, however
the decryption algorithm is not identical to the encryption algorithm
— State is the same for both encryption and decryption
— Final round of both encryption and decryption consists of only three stages
— State: 4 words / 16 bytes / 128 bits
1. Substitute bytes: Uses an S-box to perform a byte-by-byte substitution of the block
2. ShiftRows: a simple permutation
3. MixColumns: a substitution that makes use of arithmetic over GF(2 8)
4. AddRoundKey: a simple bitwise XOR of the current block with a portion of the
expanded key
— SubBytes and AddRoundKey are on bytes
AES BYTE LEVEL OPERATIONS
— Substitute bytes (SubBytes)
o Table lookup
LOOKUP TABLE FOR BYTES
INVERSE S-BOX FOR THE DECRYPTION
CONSTRUCTION OF S-BOX AND IS-BOX
— Key steps:
o Calculate multiplication inverse in GF(28) Transformation
— Note:
o Define the multiplicative inverse of 00 is 00
CONSTRUCTION OF S-BOX --- MULTIPLICATIVE INVERSE EXTENDED EUCLID [(x8
+ x4 + x3 + x + 1), (x7 + x + 1)]
TRANSFORMATION
S-BOX RATIONALE
— The S-box is designed to be resistant to known cryptanalytic attacks
— The Rijndael developers sought a design that has a low correlation between input bits
and output bits and the property that the output is not a linear mathematical function of
the input
— The nonlinearity is due to the use of the multiplicative inverse
SHIFT-ROW TRANSFORMATION
SHIFT ROW RATIONALE
— More substantial than it may first appear
— The State, as well as the cipher input and output, is treated as an array of four 4-byte
columns
— On encryption, the first 4 bytes of the plaintext are copied to the first column of State,
and so on
— The round key is applied to State column by column
o Thus, a row shift moves an individual byte from one column to another,
which is a linear distance of a multiple of 4 bytes
— Transformation ensures that the 4 bytes of one column are spread out to four different
columns
MIXCOLUMN TRANSFORMATION
MIXCOLUMN RATIONALE
— Coefficients of a matrix based on a linear code with maximal distance between code
words ensures a good mixing among the bytes of each column
— The mix column transformation combined with the shift row transformation ensures
that after a few rounds all output bits depend on all input bits
ADDROUNDKEY TRANSFORMATION
— The 128 bits of State are bitwise XOR with the 128 bits of the round key
— Operation is viewed as a columnwise operation between the 4 bytes of a State column
and one word of the round key
o Can also be viewed as a byte-level operation
— Rationale:
o Is as simple as possible and affects every bit of State
o The complexity of the round key expansion plus the complexity of the other
stages of AES ensure security
KEY EXPANSION
— Takes as input a four-word (16 byte) key and produces a linear array of 44 words (176
bytes)
— This is sufficient to provide a four-word round key for the initial AddRoundKey stage
and each of the 10 rounds of the cipher
— Key is copied into the first four words of the expanded key
— The remainder of the expanded key is filled in four words at a time
— Each added word w[i] depends on the immediately preceding word, w[i – 1], and the
word four positions back, w[i – 4]
— In three out of four cases a simple XOR is used
— For a word whose position in the w array is a multiple of 4, a more complex function is
used
KEY EXPANSION RATIONALE
— The Rijndael developers designed the expansion key algorithm to be resistant to
known cryptanalytic attacks
— Inclusion of a round-dependent round constant eliminates the symmetry between the
ways in which round keys are generated in different rounds
— The specific criteria that were used are:
o Knowledge of a part of the cipher key or round key does not enable calculation
of many other round-key bits
o An invertible transformation
o Speed on a wide range of processors
o Usage of round constants to eliminate symmetries
o Diffusion of cipher key differences into the round keys (each key bit affects
many round key bits)
o Enough nonlinearity to prohibit the full determination of round key differences
from cipher key differences only
o Simplicity of description
AES EXAMPLE
AVALANCHE EFFECT
— Change in plaintext:
o One-bit difference
0123456789abcdeffedcba9876543210 to
0023456789abcdeffedcba9876543210
AVALANCHE EFFECT (2)
AVALANCHE EFFECT (3)
— Change in key:
o One bit difference:
0f1571c947d9e8590cb7add6af7f6798 to
0e1571c947d9e8590cb7add6af7f6798
IMPLEMENTATION ASPECTS
— AES can be implemented very efficiently on an 8-bit processor, e.g., smart cards
— AddRoundKey is a bytewise XOR operation
— ShiftRows is a simple byte-shifting operation
— SubBytes operates at the byte level and only requires a table of 256 bytes
— MixColumns requires matrix multiplication in the field GF(28), which means that all
operations are carried out on bytes
— Can efficiently implement on a 32-bit processor:
o Redefine steps to use 32-bit words
o Can precompute 4 tables of 256-words
o Then each column in each round can be computed using 4 table lookups + 4
XORs
o At a cost of 4Kb to store tables
o Designers believe this very efficient implementation was a key factor in its
selection as the AES cipher
SUMMARY
— Finite field arithmetic
— AES structure
o General structure
o Detailed structure
— AES key expansion
o Key expansion algorithm
o Rationale
— AES transformation functions
o Substitute bytes
o ShiftRows
o MixColumns
o AddRoundKey
— AES implementation
o Equivalent inverse cipher
o Implementation aspects
