diff options
Diffstat (limited to 'Assignment 4/CamilStaps-assignment4.tex')
| -rw-r--r-- | Assignment 4/CamilStaps-assignment4.tex | 218 |
1 files changed, 218 insertions, 0 deletions
diff --git a/Assignment 4/CamilStaps-assignment4.tex b/Assignment 4/CamilStaps-assignment4.tex new file mode 100644 index 0000000..a0a3bd8 --- /dev/null +++ b/Assignment 4/CamilStaps-assignment4.tex @@ -0,0 +1,218 @@ +\documentclass[a4paper]{article} + +\usepackage{amsmath,amssymb,amsthm,url,graphicx,comment,enumerate,color,array,inconsolata,minted,subcaption,adjustbox} +\usepackage[margin=2cm]{geometry} +\usepackage[hidelinks]{hyperref} +\usepackage{fancyvrb} + +\usepackage{fancyhdr} % Custom headers and footers +\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers +\fancyhead{} % No page header - if you want one, create it in the same way as the footers below +\fancyfoot[L]{} % Empty left footer +\fancyfoot[C]{Copyright {\footnotesize\copyright} 2015 Camil Staps} % Empty center footer +\fancyfoot[R]{\thepage} % Page numbering for right footer +\renewcommand{\headrulewidth}{0pt} % Remove header underlines +\renewcommand{\footrulewidth}{0pt} % Remove footer underlines +\setlength{\headheight}{13.6pt} % Customize the height of the header + +\title{Homework $4$} +\author{Camil Staps (s4498062)} + +\DeclareMathOperator{\ord}{ord} +\DeclareMathOperator{\lcm}{lcm} +\DeclareMathOperator{\lsb}{lsb} +\DeclareMathOperator{\Prob}{Pr} +\DeclareMathOperator{\Adv}{Adv} + +\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n} + +\usepackage{tikz} +\usetikzlibrary{shapes.multipart,shapes.gates.logic.IEC,shapes.arrows,positioning,decorations.markings} + +\begin{document} +\maketitle + +\section*{Solution} + +\begin{enumerate} +\item \begin{enumerate} + \item \texttt{0} + \item \texttt{c} + \item \texttt{3} + \item You find the right S-box ($\mathrm{S}_1$ -- $\mathrm{S}_8$), the right row (based on the first and final bit), and finally the right column (based on the other bits). + \end{enumerate} + +\item + We need to distinguish between 3DES with two keys ($K_1=K_3$) and 3DES with three keys. In both cases, we consider a plaintext-ciphertext pair $(P,C)$. I allow myself one paragraph for each case. + + If we consider the case where $K_1=K_3$, we can build a lookup table $\{(E(P,K'_1), D(C,K'_3)) \mid K'_1 \in \pazocal{K}, K'_3=K'_1\}$ (hence, the table contains both the encryption of $P$ with all possible values for $K_1$, and the decryption of $C$ using the same key). This table holds thus $2^{56}$ such pairs. We could then, for all of these pairs $(X,Y)$ see if $\{K'_2 \in \pazocal{K} \mid D(X,K'_2)=Y\} \neq \emptyset$ (since if this holds, we found a match). For this second step we also need $2^{56}$ encryptions. The total amount of encryptions we need in the worst case is then $2^{112}$, and $2^{111}$ on average. This is what we would expect since the cardinality of the keyspace for 3DES with two keys is $2^{112}$. + + If we consider the case where $K_1\neq K_3$, we again build a lookup table, but now with $\{D(E(P,K'_1),K'_2) \mid K'_1,K'_2 \in\pazocal{K}\}$. This uses a total effort of $2^{112}$ encryptions. We can then proceed by calculating $\{D(C,K'_3) \mid K'_3 \in\pazocal{K}\}$ and find the intersection of these two sets. This takes an \emph{additional} effort of $2^{56}$ encryptions, yielding a total effort of $2^{112} + 2^{56} \approx 2^{112}$ encryptions. Whilst this is slightly better than for the case where $K_1=K_3$, it is clear that this case does not meet our expectations of a 168-bit key cipher. The larger keyspace does not contribute substantially to the cipher's security with respect to two-key 3DES. + + Still, for both cases, $2^{112}$ is well above the conventional $2^{80}$ requirement. + +\item \begin{enumerate} + \item + \begin{minipage}[t]{\linewidth} + \centering + \adjustbox{valign=t}{% + \begin{tabular}{>{\ttfamily}r | >{\ttfamily}c >{\ttfamily}c >{\ttfamily}c >{\ttfamily}c} + $\oplus$ & 00 & 01 & 10 & 11 \\\hline + 00 & 00 & 01 & 10 & 11 \\ + 01 & 01 & 00 & 11 & 10 \\ + 10 & 10 & 11 & 00 & 01 \\ + 11 & 11 & 10 & 01 & 00 + \end{tabular} + } + \end{minipage} + \item %In all four columns all bitstrings of two bits in $\{0,1\}^2$ appear, which is quite rare (see numbers below). The adversary $A$ should send \texttt{00} through \texttt{11} and check if the results have this property or not. If they have, she should guess $b'=1$; if not, $b'=0$. + + %NB: this encryption function has other vulnerabilities. Due to key reuse, sending merely \texttt{00} and \texttt{11} and checking if the results are the inverse of each other would be sufficient as well. However, we don't focus on that here. + + He could send all possible bitstrings with length $2$ and check if the results match any column in the table above. If not, the challenger cannot be using the encryption. If the results do match, he is likely (but not certain) to be using -- see the numbers below for the exact probability. + \item $|\mathrm{Perms}(X)| = |X|! = 4! = 24$ and from the table above we see that $4$ of those are of the form $E(k,\cdot)$. + \item $\Adv_{\mathrm{PRP}}[A,E] = |\Prob[EXP(0)=1] - \Prob[EXP(1)=1]| = |\tfrac{4}{4} - \tfrac{4}{24}| = \tfrac{5}{6}$ (not negligible). + \item $|\mathrm{Funs}(X,Y)| = |Y|^{|X|} = 4^4 = 256$ and still $4$ of those are of the form $E(k,\cdot)$. + \item $\Adv_{\mathrm{PRF}}[A,E] = |\Prob[EXP(0)=1] - \Prob[EXP(1)=1]| = |\tfrac{4}{4} - \tfrac{4}{256}| = \tfrac{63}{64}$ (not negligible). + \end{enumerate} + +\item \begin{enumerate} + \item + \begin{minted}[fontsize=\small,tabsize=0]{python} + >>> from pypresent import Present + >>> cipher = Present("01010101010101010101".decode('hex')) + >>> cipher.encrypt("abcdef1234567890".decode('hex')).encode('hex') + '75220f3e39179245' + >>> cipher.encrypt("1234567890abcdef".decode('hex')).encode('hex') + '8ee60136b737d4b7' + >>> cipher.encrypt("1111111111111111".decode('hex')).encode('hex') + '3db1b90d4bc93766' + \end{minted} + \item + \begin{minted}[fontsize=\small,tabsize=0]{python} + >>> cipher = Present("6e5f2e61db0c1e456e5f".decode('hex')) + >>> cipher.decrypt("8ee60136b737d4b7".decode('hex')).encode('hex') + 'fe502ee3175140db' + \end{minted} + \item + \begin{minted}[fontsize=\small,tabsize=0,breaklines,breakbytoken]{python} + >>> ['6e5f2e61db0c1e456e5f6e5f2e51b0a' + ("%x" % i) for i in range(0,16) if Present(('6e5f2e61db0c1e456e5f6e5f2e51b0a' + ("%x" % i)).decode('hex')).encrypt("cd187ce631db6207".decode('hex')) == "8ee60136b737d4b7".decode('hex')][0] + '6e5f2e61db0c1e456e5f6e5f2e51b0a4' + \end{minted} + + This code is self-explanatory. There are four bits missing, so we check for all values in $\{0,1\}^4$ (all hexadecimal characters) if the prefix with those bits concatenated to it as PRESENT key encrypts the given plaintext as the given ciphertext. We then take the first key that matches. The lost bits are `\texttt{0100}'. + \end{enumerate} + +\item \begin{enumerate} + \item + \begin{description} + \item[FX construction] is a construction where a different key is used to XOR the data before and after the `real' encryption algorithm. With a an $n$-bit block cipher $F_K$ with a $\kappa$-bit key $K$ and two additional $n$-bit whitening keys $K_1,K_2$, we can build an FX construction with $FX_{K,K_1,K_2}(P) = K_2 \oplus F_K(K_1 \oplus P)$.\footnote{Itai Dinur. Cryptanalytic Time-Memory-Data Tradeoffs for FX-Constructions with Applications to PRINCE and PRIDE. \url{https://eprint.iacr.org/2014/656.pdf}} + + In PRIDE, the FX construction is used in the sense described under `Pre- and post-whitening'. + \item[Pre- and post-whitening] and more generally \emph{whitening}, is a method of combining the data to be encrypted with (parts of) the key. In this specific cipher a rather common method is used: a portion of the key is added to the data before and after the round iterations. The first time this is done (before the round iterations) is called \emph{pre}-whitening, the last time (after the round iterations) \emph{post}-whitening. + + In PRIDE, the first 64-bit half of the key is used for whitening: it is permuted and added to the data before and after the round iterations (for both encryption and decryption, but with inversed permutations). The second half of the key is used to generate the roundkeys. + \item[Diffusion] is a property of the operation a secure cipher. It means that changing one bit in the plaintext influences as many bits in the ciphertext as possible, or, equivalently, that every bit of ciphertext depends on as many bits from the plaintext as possible. + + In PRIDE, diffusion is created by the linear layer. The matrix multiplications of $L_0$ through $L_3$ (or there inverses in decryption) combine three bits of the input in every bit of the output. This, used several times (once per round), gives the encryption this property. + \end{description} + \item The linear layer consists of: + \begin{itemize} + \item A permutation $P$ (in hardware, this is merely rewiring). + \item Multiplication of every 16-bit substring of the state with `its own' binary matrix (i.e. the leftmost substring is multiplied with $L_0$, the rightmost with $L_3$). + \item The inverse of the first permutation $P^{-1}$. + \end{itemize} + \item The S-box is used once in every round (20 times). The linear layer is used once in every round but the last one (19 times). + \item I'm not very familiar with Python, but a working implementation is provided in appendix \ref{App:pypride}. That file, and a test program using the test vectors from appendix J of the PRIDE paper, may also be found on \url{https://github.com/camilstaps/pypride}. + + Initially, I used a `real' matrix multiplication using the software-friendly matrices in appendix G of the paper. However, this turned out to be rather slow. Using a python version of the AVR assembly codes from appendix H, I got over twice as fast results. + + This program counts 112 lines, ignoring whitespace and comments\footnote{Measured with CLOC, \url{http://cloc.sourceforge.net/}}. The PRESENT implementation by Cristophe Osterlynck and Philippe Teuwen uses 82 lines. Main differences are that this PRESENT implementation supports two keylengths, but does not have to deal with matrix multiplication. + + This implementation is just a little bit slower than the PRESENT implementation (using a 128-bit key). PRESENT uses 32 rounds instead of 20, but doesn't have the heavy matrix multiplication in the linear layer (but only a permutation). Both ciphers are hardware-oriented. With an i7-3517U core @1.90GHz I could encrypt a 100KB file with PRESENT in about 9s; this took 10s with PRIDE. + \end{enumerate} +\end{enumerate} + +\appendix + +\newpage +\section{Python PRIDE implementation: \texttt{pypride}} +\label{App:pypride} +\inputminted[fontsize=\footnotesize,breaklines=true,linenos=true,tabsize=4]{python}{pypride/pypride.py} + +\newpage +\section{Profiling \texttt{pypride}} + +Here's some profiling data made with \texttt{profiler} and the test file that can be found on GitHub, when creating 5000 \texttt{Pride} objects and encrypting and decrypting 5000 blocks with one key. The matrix multiplication and the \texttt{bin} and \texttt{count} functions (which are only used in the matrix multiplication) use the most time, which explains why \texttt{pypride} is twice as slow as \texttt{pypresent}. + +It takes approximately 1.5ms to generate roundkeys (which is a one-time effort), 2.4ms to encrypt one block, and 2.6ms to decrypt one block (the difference is in the matrices). + +\begin{Verbatim}[fontsize=\footnotesize] +All tests passed. +Generating round keys: 17.6654632092s +Encryption: 23.9269566536s +Decryption: 26.2635686398s + 6035024 function calls in 33.571 seconds + + Ordered by: standard name + + ncalls tottime percall cumtime percall filename:lineno(function) + 1 0.000 0.000 0.000 0.000 :0(__import__) + 1 0.000 0.000 0.000 0.000 :0(__new__) + 35000 0.094 0.000 0.094 0.000 :0(a2b_hex) + 120000 0.299 0.000 0.299 0.000 :0(b2a_hex) + 420000 0.693 0.000 0.693 0.000 :0(chr) + 35000 0.169 0.000 0.509 0.000 :0(decode) + 120000 0.534 0.000 1.757 0.000 :0(encode) + 2 0.000 0.000 0.000 0.000 :0(get) + 1 0.000 0.000 0.000 0.000 :0(hasattr) + 2 0.000 0.000 0.000 0.000 :0(isinstance) + 1 0.000 0.000 0.000 0.000 :0(join) + 160000 0.259 0.000 0.259 0.000 :0(len) + 420000 0.705 0.000 0.705 0.000 :0(ord) + 1 0.006 0.006 0.006 0.006 :0(setprofile) + 1 0.000 0.000 0.000 0.000 :0(split) + 705000 2.250 0.000 2.250 0.000 :0(sum) + 30000 0.067 0.000 0.067 0.000 :0(time) + 1 0.000 0.000 0.000 0.000 :0(translate) + 1 0.000 0.000 33.565 33.565 <string>:1(<module>) + 1 0.000 0.000 0.000 0.000 __init__.py:49(normalize_encoding) + 1 0.000 0.000 0.000 0.000 __init__.py:71(search_function) + 1 0.000 0.000 0.000 0.000 codecs.py:77(__new__) + 120000 0.724 0.000 1.223 0.000 hex_codec.py:13(hex_encode) + 35000 0.193 0.000 0.340 0.000 hex_codec.py:27(hex_decode) + 1 0.000 0.000 0.000 0.000 hex_codec.py:45(Codec) + 1 0.000 0.000 0.000 0.000 hex_codec.py:52(IncrementalEncoder) + 1 0.000 0.000 0.000 0.000 hex_codec.py:57(IncrementalDecoder) + 1 0.000 0.000 0.000 0.000 hex_codec.py:62(StreamWriter) + 1 0.000 0.000 0.000 0.000 hex_codec.py:65(StreamReader) + 1 0.000 0.000 0.000 0.000 hex_codec.py:70(getregentry) + 1 0.000 0.000 0.000 0.000 hex_codec.py:8(<module>) + 0 0.000 0.000 profile:0(profiler) + 1 0.000 0.000 33.571 33.571 profile:0(test()) + 760000 1.571 0.000 1.571 0.000 pypride.py:129(swap) + 190000 0.384 0.000 0.384 0.000 pypride.py:133(rol) + 760000 1.542 0.000 1.542 0.000 pypride.py:137(ror) + 190000 0.852 0.000 1.248 0.000 pypride.py:141(M_L0) + 95000 0.710 0.000 1.308 0.000 pypride.py:148(M_L1) + 95000 0.904 0.000 1.681 0.000 pypride.py:155(M_L1_inv) + 95000 0.748 0.000 1.322 0.000 pypride.py:162(M_L2) + 95000 0.925 0.000 1.687 0.000 pypride.py:169(M_L2_inv) + 190000 0.838 0.000 1.227 0.000 pypride.py:176(M_L3) + 105000 2.163 0.000 7.546 0.000 pypride.py:183(roundKey) + 220000 0.396 0.000 0.396 0.000 pypride.py:201(addRoundKey) + 100000 0.864 0.000 1.076 0.000 pypride.py:204(sBoxLayer) + 100000 0.907 0.000 1.108 0.000 pypride.py:212(sBoxLayer_dec) + 200000 3.652 0.000 4.351 0.000 pypride.py:220(pLayer) + 305000 5.811 0.000 6.947 0.000 pypride.py:228(pLayer_dec) + 95000 1.492 0.000 9.554 0.000 pypride.py:236(lLayer) + 95000 1.516 0.000 10.735 0.000 pypride.py:252(lLayer_dec) + 120000 0.484 0.000 2.241 0.000 pypride.py:268(string2number) + 10000 0.058 0.000 0.218 0.000 pypride.py:276(number2string_N) + 5000 0.278 0.000 7.927 0.002 pypride.py:61(__init__) + 5000 0.625 0.000 11.897 0.002 pypride.py:71(encrypt) + 5000 0.669 0.000 13.136 0.003 pypride.py:96(decrypt) + 1 0.189 0.189 33.565 33.565 test-vectors.py:26(test) +\end{Verbatim} + +\end{document} |