Advanced Encryption Standard

Evaluation Criteria for AES

Essentially the cipher's submitted NIST for AES were judged on three broad categories

1. Security
   1. Actual security compared with other submitted algorithms
   2. Randomness
   3. Soundness (mathematical)
   4. Other security factors
2. Cost
   1. Licensing
   2. Computational Efficency
   3. Memory requirements
3. Algorithm and implementation characteristics
   1. Flexibility in key and block size, wide variety of plateforms and applications, and USE: implemented as a stream cipher, message authentication code, random number generator.
   2. Hareware and software suitable
   3. Simplicity

The AES Cipher

Below is a diagram of the AES cipher. Look through the review questions below for a good explaination of each step.

attachment:AES_Diagram.png

Review Questions

What was the original set of criteria used by NIST to evaluate candidate AES ciphers?

In general they said:
   1. Security strength equal to or greater than 3DES
   2. Significantly improved efficiency
   3. Symmetric block cipher with a block length of 128 bits.
   4. Support key lengths of 128, 192, and 256 bits.

The specific evaluation criteria:
   1. Security: This referes to the effort required to cryptanalyze an algorithm. 
   2. Cost: Practical, Efficient enough to use on high bandwidth links and high speed applications.
   3. Algorithm and Implementation Characteristics: flexibility, suitability for a variety of hardware and software implementations, simplicity

What was the final set?

General Security:
Software Implementations: Speed
Hardware Implementations: small hardware size to keep cost down.
Attacks on Implementations: timing attacks and power attacks.
Encryption versus decryption: Are they the same...
Key agility: ability to change keys quickly and efficiently
Other versatility and fexibility: Parameter flexibility (other key and block sizes, change in the number of rounds), 
                                  Implementation Flexibility (optimizing cipher elements for particular environments).
Potential for instruction-level parallelism:The ability to exploit ILP in processors.

What is the power analysis?

Observing the power used to detect a multiply or add operation or to see if ones or zeros are being written.

What is the difference between Rijndael and AES?

Rijndael took different blocks sizes of 128, 192, 256. AES only takes 128.

What is the purpose of the state array?

The state array holds the input block that is massaged through each round.

How is the S-Box constructed?

\usepackage{amsmath}%
\setcounter{MaxMatrixCols}{30}%
\usepackage{amsfonts}%
\usepackage{amssymb}%
\usepackage{graphicx}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
%%end-prologue%%
\begin{enumerate}
\item Initialize the $S-Box$ with the byte values in ascending sequence row
by row\newline
$\left[
\begin{array}{cccc}
00 & 01 & ... & 0F \\
10 & 11 & ... & 1F \\
\vdots  &  & \ddots  &  \\
F0 & F1 &  & FF%
\end{array}%
\right] $\newline
Thus any element value in row A element B is 0xAB

\item Map each byte in the S-Box to its multiplicative inverse in $GF(2^{8})$
where $00\rightarrow 00$.

\item Each byte in the S-Box consists of 8 bits labeled $%
(b_{7},b_{6},...,b_{0})$. Apply the following transformation to each bit of
each byte:%
\[
b_{i}^{\prime}=b_{i}\oplus b_{\left(  i+4\right)  \operatorname{mod}8}\oplus
b_{\left(  i+5\right)  \operatorname{mod}8}\oplus b_{\left(  i+6\right)
\operatorname{mod}8}\oplus b_{\left(  i+7\right)  \operatorname{mod}8}\oplus
c_{i}
\]
where $c_{i}$ is the $i^{th}$ bit of byte $c$ with the value $\left\{
63\right\}  $. That is $\left(  c_{7}c_{6}c_{5}c_{4}c_{3}c_{2}c_{1}%
c_{0}\right)  =\left(  01100011\right)  $.
\end{enumerate}

Briefly describe Sub Bytes.

SubBytes: Uses the S-box described above to perform a byte-by-byte substitution of the state (or input) block as show in attachment:AES-SubBytes.png

In the decryption algorithm an Inverse-S-Box is used. latex2($S:EA \rightarrow 87$ and $S^{-1}:87 \rightarrow EA$).

Briefly describe ShiftRow Transformation.

To perform the ShiftRow transformation, we take the state and ''left circular shift'' row 0 by 0 byts, 1 by 1 byte, row 2 by 2 bytes, and row 3 by 3 bytes. To perform the inverse we use right shifts instead of left shifts.

How many bytes in State are affected by Shift Rows?

12 Bytes

Briefly describe MixColumns.

\usepackage{amsmath}%
\setcounter{MaxMatrixCols}{30}%
\usepackage{amsfonts}%
\usepackage{amssymb}%
\usepackage{graphicx}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
%%end-prologue%%
MixColumns operates on each column individually and is defined by the
following matrix multiplication on state:%
\[
\left[
\begin{array}
[c]{cccc}%
02 & 03 & 01 & 01\\
01 & 02 & 03 & 01\\
01 & 01 & 02 & 03\\
03 & 01 & 01 & 02
\end{array}
\right]  \left[
\begin{array}
[c]{cccc}%
S_{0,0} & S_{0,1} & S_{0,2} & S_{0,3}\\
S_{1,0} & S_{1,1} & S_{1,2} & S_{1,3}\\
S_{2,0} & S_{2,1} & S_{2,2} & S_{2,3}\\
S_{3,0} & S_{3,1} & S_{3,2} & S_{3,3}%
\end{array}
\right]  =%
\begin{array}
[c]{cccc}%
S_{0,0}^{\prime} & S_{0,1}^{\prime} & S_{0,2}^{\prime} & S_{0,3}^{\prime}\\
S_{1,0}^{\prime} & S_{1,1}^{\prime} & S_{1,2}^{\prime} & S_{1,3}^{\prime}\\
S_{2,0}^{\prime} & S_{2,1}^{\prime} & S_{2,2}^{\prime} & S_{2,3}^{\prime}\\
S_{3,0}^{\prime} & S_{3,1}^{\prime} & S_{3,2}^{\prime} & S_{3,3}^{\prime}%
\end{array}
\]

In the matrix multiplication we must remember that we are doing multiplication
in $G\left(  2^{8}\right)  $. We do multiplication as follows:%
\begin{align*}
01\ast S_{i,j}  & =S_{i,j}\\
02\ast S_{i,j}  & =\left\{
\begin{array}
[c]{cc}%
(b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}0) & if~~b_{7}=0\\
(b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}0)\oplus(00011011) & if~~b_{7}=1
\end{array}
\right.  \\
03\ast S_{i,j}  & =\left\{
\begin{array}
[c]{cc}%
(b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}0)\oplus(b_{7}b_{6}b_{5}b_{4}b_{3}%
b_{2}b_{1}b_{0}) & if~~b_{7}=0\\
(b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}0)\oplus(00011011)\oplus(b_{7}b_{6}%
b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}) & if~~b_{7}=1
\end{array}
\right.
\end{align*}

The inverse matrix is even uglier because it contains elements such as $0x$ where $x \geq 9$.

Briefly describe Add Round Key.

Recall that the $key$ is $4-32$ bit words. and that the key block is arranged
\[
k=\left[
\begin{array}
[c]{cccc}%
w_{0} & w_{1} & w_{2} & w_{3}%
\end{array}
\right]
\]
where each word is a column of 32 bits. to write this as a square we just
break the 32 bits into 8 bit bytes per row. Then we can just $\oplus$ the
state with the key to get the next state:%
\[
\left[
\begin{array}
[c]{cccc}%
S_{0,0} & S_{0,1} & S_{0,2} & S_{0,3}\\
S_{1,0} & S_{1,1} & S_{1,2} & S_{1,3}\\
S_{2,0} & S_{2,1} & S_{2,2} & S_{2,3}\\
S_{3,0} & S_{3,1} & S_{3,2} & S_{3,3}%
\end{array}
\right]  \oplus\left[
\begin{array}
[c]{cccc}%
w_{0,0} & w_{1,0} & w_{2,0} & w_{3,0}\\
w_{0,1} & w_{1,1} & w_{2,1} & w_{3,1}\\
w_{0,2} & w_{1,2} & w_{2,2} & w_{3,2}\\
w_{0,3} & w_{1,3} & w_{2,3} & w_{3,3}%
\end{array}
\right]
\]

Breifly describe the key expansion algorithm.

We start with a 16 byte (128 bit) key and perform the following:

KeyExpansion(byte key[16], word w[44])
{
     word temp
     for (i=0; i<4; i++)  w[i] = (key[4*i], key[4*i+1], key[4*i+2], key[4*i+3]);
     for (i=4; i<44; i++) 
     {
          temp = w[i-1];
          if (i mod 4 = 0)  temp = SubWord(RotWord(temp)) XOR Rcon[i/4];
          w[i] = w[i-4] XOR temp
     }
}

RotWord(word x) performs a left circular rotation by 1 word.
SubWord(word x) uses the S-Box as a lookup table to perform a substitution of each byte in the word.

What is the difference between SubBytes and SubWord?

SubBytes performs takes a byte and performs the substitution using the S-Box. SubWord takes a word (4 bytes) and performs SubBytes on each byte in place.

What is the difference between ShiftRows and RotWord?

Nothing really except that Shift Rows really does shift a row, and the words are stored in a column which for RotWord we can view as a row.

What is the difference between the AES decryption algorithm and the equivalent inverse cipher?

Because Round 10 is different than the other rounds you can not just reverse the process. Plus you must use inverse S-box which is not the same as the original S-Box. similarly the SubBytes and MixCols are not there own inverse, thus the decryption can not be the same as the encryption.