attachment:Csce877Ch5Notes.tex of Csce877Ch5Notes

   1 \documentclass[]{article}
   2 \usepackage{times}
   3 \usepackage{amsmath}
   4 \usepackage{hyperref}
   5 \usepackage{url}
   6 \usepackage{graphicx}
   7 %opening
   8 \title{}
   9 \author{}
  10 
  11 \begin{document}
  12 
  13 \maketitle
  14 
  15 \begin{abstract}
  16 
  17 \end{abstract}
  18 
  19 \section{Advanced Encryption Standard}
  20 
  21 \subsection{Evaluation Criteria for AES}
  22 
  23 Essentially the cipher's submitted NIST for AES were judged on three broad categories
  24 
  25 \begin{enumerate}
  26 	\item Security
  27 	\begin{enumerate}
  28 		\item Actual security compared with other submitted algorithms
  29 		\item Randomness
  30 		\item Soundness (mathematical)
  31 		\item Other security factors
  32 	\end{enumerate}
  33 	\item Cost
  34 	\begin{enumerate}
  35 		\item Licensing
  36 		\item Computational Efficency
  37 		\item Memory Requirements
  38 	\end{enumerate}
  39 	\item Algorithm and implementation characteristics
  40 	\begin{enumerate}
  41 		\item 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.
  42 		\item Hareware and software suitable
  43 	 	\item Simplicity
  44 	\end{enumerate}
  45 \end{enumerate}
  46 
  47 \subsection{The AES Cipher}
  48 
  49 Figure \ref{fig:aes_diagram} shows a diagram of the AES cipher. Look through the review questions below for a good explanation of each step.
  50 
  51 \begin{figure}[htb]
  52 \centering
  53 \includegraphics[width=.65\textwidth]{AES_Diagram.png}
  54 \caption{AES cipher diagram.}\label{fig:aes_diagram}
  55 \end{figure}
  56 
  57 \subsection{Review Questions}
  58 
  59 \textbf{What was the original set of criteria used by NIST to evaluate candidate AES ciphers?}
  60 
  61 In general they said:
  62 \begin{enumerate}
  63 	\item Security strength equal to or greater than 3DES
  64 	\item Significantly improved efficiency
  65 	\item Symmetric block cipher with a block length of 128 bits.
  66 	\item Support key lengths of 128, 192, and 256 bits.
  67 \end{enumerate}
  68 
  69 \textbf{The specific evaluation criteria:}
  70 \begin{enumerate}
  71 	\item Security: This referes to the effort required to cryptanalyze an algorithm. 
  72 	\item Cost: Practical, Efficient enough to use on high bandwidth links and high speed applications.
  73 	\item Algorithm and Implementation Characteristics: flexibility, suitability for a variety of hardware and software implementations, simplicity
  74 \end{enumerate}
  75 
  76 \textbf{What was the final set?}
  77 
  78 \begin{enumerate}
  79 	\item General Security:
  80 	\begin{enumerate}
  81 		\item Software Implementations: Speed
  82 		\item Hardware Implementations: small hardware size to keep cost down.
  83 		\item Attacks on Implementations: timing attacks and power attacks.
  84 		\item Encryption versus decryption: Are they the same...
  85 		\item Key agility: ability to change keys quickly and efficiently
  86 	\end{enumerate}
  87 	\item Other versatility and fexibility: Parameter flexibility (other key and block sizes, change in the number of rounds), 
  88 	\item Implementation Flexibility (optimizing cipher elements for particular environments).
  89 	\item Potential for instruction-level parallelism:The ability to exploit ILP in processors.
  90 \end{enumerate}
  91 
  92 \textbf{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.
  93 
  94 \textbf{What is the difference between Rijndael and AES?} Rijndael took different blocks sizes of 128, 192, 256. AES only takes 128.
  95 
  96 \textbf{What is the purpose of the \textit{state} array?} The state array holds the input block that is massaged through each round.
  97 
  98 \textbf{How is the S-Box constructed?}
  99 
 100 \begin{enumerate}
 101 	\item Initialize the $S-Box$ with the byte values in ascending sequence row
 102 	by row\newline
 103 	$\left[
 104 	\begin{array}{cccc}
 105 	00 & 01 & ... & 0F \\
 106 	10 & 11 & ... & 1F \\
 107 	\vdots  &  & \ddots  &  \\
 108 	F0 & F1 &  & FF%
 109 	\end{array}%
 110 	\right] $\newline
 111 	Thus any element value in row A element B is 0xAB
 112 	
 113 	\item Map each byte in the S-Box to its multiplicative inverse in $GF(2^{8})$
 114 	where $00\rightarrow 00$.
 115 	
 116 	\item Each byte in the S-Box consists of 8 bits labeled $%
 117 	(b_{7},b_{6},...,b_{0})$. Apply the following transformation to each bit of
 118 	each byte:%
 119 	\[
 120 	b_{i}^{\prime}=b_{i}\oplus b_{\left(  i+4\right)  \operatorname{mod}8}\oplus
 121 	b_{\left(  i+5\right)  \operatorname{mod}8}\oplus b_{\left(  i+6\right)
 122 		\operatorname{mod}8}\oplus b_{\left(  i+7\right)  \operatorname{mod}8}\oplus
 123 	c_{i}
 124 	\]
 125 	where $c_{i}$ is the $i^{th}$ bit of byte $c$ with the value $\left\{
 126 	63\right\}  $. That is $\left(  c_{7}c_{6}c_{5}c_{4}c_{3}c_{2}c_{1}%
 127 	c_{0}\right)  =\left(  01100011\right)  $.
 128 \end{enumerate}
 129 
 130 
 131 \textbf{Briefly describe Sub Bytes.}
 132 
 133 SubBytes: Uses the S-box described above to perform a byte-by-byte substitution of the state (or input) block as show in Figure~\ref{fig:subbytes}
 134 
 135 \begin{figure}
 136 	\centering
 137 	\includegraphics{AES_SubBytes.png}
 138 	\caption{S-Box substitution}\label{fig:subbytes}
 139 \end{figure}
 140 
 141 In the decryption algorithm an Inverse-S-Box is used. $S:EA \rightarrow 87$ and $S^{-1}:87 \rightarrow EA$.
 142 
 143 \textbf{Briefly describe ShiftRow Transformation.}
 144 
 145 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.
 146 
 147 
 148 \textbf{How many bytes in ''State'' are affected by Shift Rows?} 12 Bytes
 149 
 150 
 151 \textbf{Briefly describe MixColumns.}
 152 
 153 MixColumns operates on each column individually and is defined by the
 154 following matrix multiplication on state:%
 155 \[
 156 \left[
 157 \begin{array}
 158 [c]{cccc}%
 159 02 & 03 & 01 & 01\\
 160 01 & 02 & 03 & 01\\
 161 01 & 01 & 02 & 03\\
 162 03 & 01 & 01 & 02
 163 \end{array}
 164 \right]  \left[
 165 \begin{array}
 166 [c]{cccc}%
 167 S_{0,0} & S_{0,1} & S_{0,2} & S_{0,3}\\
 168 S_{1,0} & S_{1,1} & S_{1,2} & S_{1,3}\\
 169 S_{2,0} & S_{2,1} & S_{2,2} & S_{2,3}\\
 170 S_{3,0} & S_{3,1} & S_{3,2} & S_{3,3}%
 171 \end{array}
 172 \right]  =%
 173 \begin{array}
 174 [c]{cccc}%
 175 S_{0,0}^{\prime} & S_{0,1}^{\prime} & S_{0,2}^{\prime} & S_{0,3}^{\prime}\\
 176 S_{1,0}^{\prime} & S_{1,1}^{\prime} & S_{1,2}^{\prime} & S_{1,3}^{\prime}\\
 177 S_{2,0}^{\prime} & S_{2,1}^{\prime} & S_{2,2}^{\prime} & S_{2,3}^{\prime}\\
 178 S_{3,0}^{\prime} & S_{3,1}^{\prime} & S_{3,2}^{\prime} & S_{3,3}^{\prime}%
 179 \end{array}
 180 \]
 181 
 182 In the matrix multiplication we must remember that we are doing multiplication
 183 in $G\left(  2^{8}\right)  $. We do multiplication as follows:%
 184 \begin{align*}
 185 01\ast S_{i,j}  & =S_{i,j}\\
 186 02\ast S_{i,j}  & =\left\{
 187 \begin{array}
 188 [c]{cc}%
 189 (b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}0) & if~~b_{7}=0\\
 190 (b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}0)\oplus(00011011) & if~~b_{7}=1
 191 \end{array}
 192 \right.  \\
 193 03\ast S_{i,j}  & =\left\{
 194 \begin{array}
 195 [c]{cc}%
 196 (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}%
 197 b_{2}b_{1}b_{0}) & if~~b_{7}=0\\
 198 (b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}0)\oplus(00011011)\oplus(b_{7}b_{6}%
 199 b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}) & if~~b_{7}=1
 200 \end{array}
 201 \right.
 202 \end{align*}
 203 
 204 The inverse matrix is even uglier because it contains elements such as $0x$ where $x \geq 9$.
 205 
 206 
 207 \textbf{Briefly describe Add Round Key.}
 208 
 209 Recall that the $key$ is $4-32$ bit words. and that the key block is arranged
 210 \[
 211 k=\left[
 212 \begin{array}
 213 [c]{cccc}%
 214 w_{0} & w_{1} & w_{2} & w_{3}%
 215 \end{array}
 216 \right]
 217 \]
 218 where each word is a column of 32 bits. to write this as a square we just
 219 break the 32 bits into 8 bit bytes per row. Then we can just $\oplus$ the
 220 state with the key to get the next state:%
 221 \[
 222 \left[
 223 \begin{array}
 224 [c]{cccc}%
 225 S_{0,0} & S_{0,1} & S_{0,2} & S_{0,3}\\
 226 S_{1,0} & S_{1,1} & S_{1,2} & S_{1,3}\\
 227 S_{2,0} & S_{2,1} & S_{2,2} & S_{2,3}\\
 228 S_{3,0} & S_{3,1} & S_{3,2} & S_{3,3}%
 229 \end{array}
 230 \right]  \oplus\left[
 231 \begin{array}
 232 [c]{cccc}%
 233 w_{0,0} & w_{1,0} & w_{2,0} & w_{3,0}\\
 234 w_{0,1} & w_{1,1} & w_{2,1} & w_{3,1}\\
 235 w_{0,2} & w_{1,2} & w_{2,2} & w_{3,2}\\
 236 w_{0,3} & w_{1,3} & w_{2,3} & w_{3,3}%
 237 \end{array}
 238 \right]
 239 \]
 240 
 241 \textbf{Breifly describe the key expansion algorithm.}
 242 
 243 \begin{tabbing}
 244 We start with a 16 byte (128 bit) key and perform the following: \smallskip		
 245    \= KeyExpansion(byte key[16], word w[44]) \\
 246    \> { \\
 247    \>   \= word temp \\
 248    \>   \> for (i=0; i<4; i++)  w[i] = (key[4*i], key[4*i+1], key[4*i+2], key[4*i+3]); \\
 249    \>   \>   \= for (i=4; i<44; i++)  \\
 250    \>   \>   \> { \\
 251    \>   \>   \>   \= temp = w[i-1]; \\
 252    \>   \>   \>   \> if (i mod 4 = 0)  temp = SubWord(RotWord(temp)) XOR Rcon[i/4]; \\
 253    \>   \>   \>   \> w[i] = w[i-4] XOR temp \\
 254    \>   \>   \> } \\
 255    \>   \> RotWord(word x) performs a left circular rotation by 1 word. \\
 256    \>   \> SubWord(word x) uses the S-Box as a lookup table to perform a substitution of each byte in the word. \\
 257    \> } \\
 258 \end{tabbing}
 259 
 260 
 261 \textbf{What is the difference between SubBytes and SubWord?}
 262 
 263 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.
 264 
 265 
 266 \textbf{What is the difference between ShiftRows and RotWord?}
 267 
 268 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.
 269 
 270 \textbf{What is the difference between the AES decryption algorithm and the equivalent inverse cipher?}
 271 
 272 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.
 273 
 274 \end{document}