Advanced Encryption Standard

Evaluation Criteria for AES

The AES Cipher

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*}

Briefly describe Add Round Key.

Breifly describe the key expansion algorithm.

What is the difference between Sub Bytes and Sub Word?

What is the difference between Shift Rows and Rot Word?

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