1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
\documentclass[a4paper]{article}
\usepackage{amsmath,amssymb,amsthm,url,graphicx,comment,enumerate,color,array,inconsolata,minted,subcaption,adjustbox}
\usepackage[margin=2cm]{geometry}
\title{Homework $3$}
\author{Camil Staps (s4498062)}
\newcommand{\R}{\mathbb R}
\newcommand{\Q}{\mathbb Q}
\newcommand{\Z}{\mathbb Z}
\newcommand{\N}{\mathbb N}
\newcommand{\F}{\mathbb F}
\newcommand{\Zstar}{\Z^{^*}}
\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
\begin{enumerate}
\item
\begin{minipage}[t]{\linewidth}
\centering
\adjustbox{valign=t}{%
\begin{tikzpicture}[LFSR/.style={rectangle split, rectangle split horizontal=true, rectangle split parts=#1, draw, anchor=center}, ARROW/.style={draw,thick,single arrow,single arrow head extend=3pt,transform shape}]]
\node[LFSR=5] (register) {\nodepart{one}$s_4$\nodepart{two}$s_3$\nodepart{three}$s_2$\nodepart{four}$s_1$\nodepart{five}$s_0$};
\node[circle, inner sep=0, below=6mm of register.one south] (xor) {\scalebox{1}{$\oplus$}};
\draw[->] (register.one south) -- (xor);
\draw[->] (register.two south) |- (xor);
\draw (register.three south) |- (xor);
\draw (register.five south) |- (xor);
\draw (xor.west) -- ++(left:4mm) node[anchor=north] (hook1) {};
\draw[->] (hook1) |- (register.one west);
\draw[->] (register.five east) -- ++(right:4mm) node[anchor=west] {$\dots$};
\end{tikzpicture}
}
\end{minipage}
\item
$$M = \begin{pmatrix}
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 \\
1 & 0 & 1 & 1 & 1
\end{pmatrix}$$
\item
That bit stream contains $0^L$. We know that $0 \oplus \dots \oplus 0 = 0$, so after $0^L$, only zeros can follow. However, this is not the case. Therefore, this bit stream cannot be a part of the output of this LFSR.
\item
% In figure \ref{fig:1ai} we see that $c_L=1$. We then check if $C(X)$ is an irreducible polynomial. Since $C(X)=\dots+1$ and $\deg(C(X))=5$, we only need to consider products of two polynomials $f_1,f_2$ for which $\deg(f_1)+\deg(f_2)=5$ and both polynomials have a term $1$. We then check all possible combinations:
% \begin{table}[h]
% \centering
% \begin{tabular}{>{$}l<{$} >{$}l<{$} | >{$}l<{$}}
% f_1(x) & f_2(x) & (f_1 \circ f_2)(x) = (f_2 \circ f_1)(x) \\\hline
% x^4 + x^3 + x^2 + x + 1 & x + 1 & x^5 + 1 \\
% x^4 + x^3 + x^2 + 1 & x + 1 & x^5 + x^2 + x + 1 \\
% x^4 + x^3 + x + 1 & x + 1 & x^5 + x^3 + x^2 + 1 \\
% x^4 + x^3 + 1 & x + 1 & x^5 + x^3 + x + 1\\
% x^4 + x^2 + x + 1 & x + 1 & x^5 + x^4 + x^3 + 1\\
% x^4 + x^2 + 1 & x + 1 & x^5 + x^4 + x^3 + x^2 + x + 1\\
% x^4 + x + 1 & x + 1 & x^5 + x^4 + x^2 + 1\\
% x^4 + 1 & x + 1 & x^5 + x^4 + x + 1\\
% x^3 + x^2 + x + 1 & x^2 + x + 1 & x^5 + x^3 + x^2 + 1\\
% x^3 + x^2 + x + 1 & x^2 + 1 & x^5 + x^4 + x + 1\\
% x^3 + x^2 + 1 & x^2 + x + 1 & x^5 + x + 1\\
% x^3 + x^2 + 1 & x^2 + 1 & x^5 + x^4 + x^3 + x + 1\\
% x^3 + x + 1 & x^2 + x + 1 & x^5 + x^4 + 1\\
% x^3 + x + 1 & x^2 + 1 & x^5 + x^2 + x + 1\\
% x^3 + 1 & x^2 + x + 1 & x^5 + x^4 + x^3 + x^2 + x + 1\\
% x^3 + 1 & x^2 + 1 & x^5 + x^3 + x^2 + 1\\
% \end{tabular}
% \end{table}
% Since $C(X)$ does not appear in the rightmost column of this table, it is an irreducible polynomial.
In the figure above we see that $c_L=1$. Using sage, we find that $C(X)$ is a primitive polynomial:
\begin{minted}[tabsize=0]{python}
sage: Z2P.<x> = GF(2)[]
sage: (x^5+x^3+x^2+x+1).is_primitive()
True
\end{minted}
The period of this LFSR is then $2^L-1=31$.
\item
We construct the states using matrix multiplication. As an example we show $M\cdot s_1$:
$$M\cdot s_1 = \begin{pmatrix}0 & 1 & 0 & 0 & 0 \\0 & 0 & 1 & 0 & 0 \\0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 1 \\1 & 0 & 1 & 1 & 1\end{pmatrix} \cdot \begin{pmatrix}0 \\ 0 \\ 0 \\ 0 \\ 1\end{pmatrix} = \begin{pmatrix}0 \\ 0 \\ 0 \\ 1 \\ 1\end{pmatrix} = s_3$$
We can then continue with $M\cdot s_3$. Using that method, we find the state sequence $s_1$, $s_3$, $s_6$, $s_{12}$, $s_{25}$, $s_{18}$, $s_4$, $s_9$, $s_{19}$, $s_7$, $s_{15}$, $s_{31}$, $s_{30}$, $s_{29}$, $s_{27}$, $s_{23}$, $s_{14}$, $s_{28}$, $s_{24}$, $s_{17}$, $s_2$, $s_5$, $s_{10}$, $s_{21}$, $s_{11}$, $s_{22}$, $s_{13}$, $s_{26}$, $s_{20}$, $s_8$, $s_{16}$, $s_1$, which indeed contains $31$ different states (all states except $s_0$).
\end{enumerate}
\item
We know with sage that these two polynomials are primitive:
\begin{minted}[tabsize=0]{python}
sage: (x^3+x+1).is_primitive()
True
sage: (x^5+x^2+1).is_primitive()
True
\end{minted}
Therefore, the two LFSRs have period $2^L-1$, that is, $7$ for $\text{LFSR}^f$ and $31$ for $\text{LFSR}^g$. Of course, there is also the obvious period $1$ for both LFSRs if we start with $s_0$.
Combining this we find the periods illustrated in table \ref{tab:1b}.
\begin{table}
\setlength\extrarowheight{2pt}
\centering
\begin{tabular}{l | l | l | l | l}
Period $\text{LFSR}^f$ & Initial state (e.g.) & Period $\text{LFSR}^g$ & Initial state (e.g.) & Combined period \\\hline
$1$ & \texttt{000} & $1$ & \texttt{00000} & $2^{1\cdot1}-1=1$ \\
$1$ & \texttt{000} & $31$ & \texttt{00001} & $2^{1\cdot31}-1=2^{31}-1$ \\
$7$ & \texttt{001} & $1$ & \texttt{00000} & $2^{7\cdot1}-1=2^7-1$ \\
$7$ & \texttt{001} & $31$ & \texttt{00001} & $2^{7\cdot31}-1=2^{217}-1$ \\
\end{tabular}
\caption{}
\label{tab:1b}
\end{table}
\end{enumerate}
\item
\begin{proof}
Given a certain ciphertext $c$ we define the set $M_c$ as the set with all plaintexts that could give $c$ using some key and this cipher:
$$M_c \stackrel{\text{def}}{=} \{m\in\pazocal{M} \mid \exists_{k\in\pazocal{K}}[E(k,m) = c]\}$$
For all $k\in\pazocal{K}, c\in\pazocal{C}$ we have $D(k,c) = c-k\pmod{256} \in \{0,\dots,255\} = \pazocal{M}$. Therefore, for any $c\in\pazocal{C}$, we have $|M_c| = |\pazocal{K}| = |\pazocal{M}|$, meaning that given a certain ciphertext, any plaintext in $\pazocal{M}$ could be the plaintext corresponding to that ciphertext. Hence, seeing the ciphertext does not give us information about the plaintext, or:
$$\forall_{m\in\pazocal{M},c\in\pazocal{C}}\left[\Prob(m = m' \mid c) = \Prob(m = m')\right].$$
Therefore, this cipher has perfect secrecy.
\end{proof}
\item
\begin{enumerate}
\item
$L_2 = R_1 = L_0 \oplus F(k_1,R_0)$ and $R_2 = L_1 \oplus F(k_2,R_1) = R_0 \oplus F(k_2, L_0 \oplus F(k_1, R_0))$.
\item
We are only interested in the left parts of the encryptions, which we shall denote as $L_{2,0}$ and $L_{2,1}$ for the left parts of the could-be encryptions of $m_0$ and $m_1$, respectively. Following the equations found in the last exercise, we have $L_{2,0} = 1^{32} \oplus F(k_1,1^{32}) = \overline{F(k_1,1^{32})}$ and $L_{2,1} = 0^{32} \oplus F(k_1,1^{32}) = F(k_1,1^{32})$. Therefore, in case $F_2$ was used, we have $L_{2,0} = \overline{L_{2,1}}$. For a random permutation this happening has the very small chance of $\frac1{2^{64}}$.
If an adversary thus checks whether $L_{2,0} \stackrel?= \overline{L_{2,1}}$ and finds out it's true, he has a non-negligible advantage with which he can assume $F_2$ was used. In case this equation does \emph{not} hold, he has a non-negligible advantage with which he can assume a random permutation was used.
\end{enumerate}
\item
\begin{enumerate}
\item
One key has an effective length of $56$ bits. With two keys we have an effective keylength of $2\cdot56=112$ bits. This gives $|\pazocal{K}| = 2^{112}$. The amount of encryptions we have to perform for exhaustive key search is then $2^{112-1}$.
\item
$D^{2DES}(k_1||k_2, c) = D^{DES}(k_1, D^{DES}(k_2, c))$.
\item
\begin{proof}
\begin{align*}
m &= D^{DES}(k_1, D^{DES}(k_2, c)) \\
E^{DES}(k_1, m) &= E^{DES}(k_1, D^{DES}(k_1, D^{DES}(k_2, c))) \\
&\qquad\text{(Encryption and decryption with $k_1$ cancel out)} \\
E^{DES}(k_1, m) &= D^{DES}(k_2, c)
\end{align*}
\end{proof}
\item
$A = 2^{56}$ since the keylength of one DES key is $56$. A ciphertext block encrypted with DES is $64$ bits long. Without overhead we have then $B=64\cdot2^{56}$.
We have a block length of $64$ and a key length of $56$. If we compute the encryptions of some plaintext using all possible keys, and the decryptions of some ciphertext using all possible keys, we have two lists of $2^{56}$ 64-bit candidates for a middle point in 2DES. Following the birthday paradox, the probability two values from the two lists are the same is high enough to reasonably expect false alarms\footnote{See \url{http://en.wikipedia.org/wiki/Birthday_problem#Probability_table}}.
\item
See the python files for the answers to exercise i through iv. See \texttt{Readme.md} for explanation and usage information.
I found the keypair $k_1=\mathtt{0101010101164613}, k_2=\mathtt{0101010102a719c2}$ using:
\begin{verbatim}
$ ./break.py -p 0123456789ABCDEF -c e0ac28c346fb8de5 -l 24
Making dictionary (p:0123456789abcdef;l:24)... 417.513822s
Finding matches... 419.125502s
Key generation: 102.954099s
Decryption: 269.473773s
Matching dictionary: 15.134741s
k1: 0101010101164613; k2: 0101010102a719c2
\end{verbatim}
This was done on a Lenovo U410, i7-3517U @ 1.9GHz with 8GB RAM and 16GB /swap. It takes about seven minutes to create the dictionary, and again seven minutes to try all keys for the second key and find matches. On lilo, this takes a bit less than five minutes each.
With $l=24$ we're likely to find only one possible keypair since the chance on false alarms is much lower. For higher $l$, in particular $l=56$, the chance on false alarms is much higher, meaning that the first keypair is most likely \emph{not} the actual keypair. More plaintext-ciphertext pairs can then help to find the right keypair. We do that in this case only for verification:
\begin{verbatim}
$ ./break.py -p 1122334455667788 -c 49e4857e94f9655d -l 24
Making dictionary (p:1122334455667788;l:24)... 386.554364s
Finding matches... 424.907323s
Key generation: 106.151418s
Decryption: 271.449573s
Matching dictionary: 15.2167599999s
k1: 0101010101164613; k2: 0101010102a719c2
$ ./break.py -p 99aabbccddeeff00 -c b5a2eefb51b04401 -l 24
Making dictionary (p:99aabbccddeeff00;l:24)... 394.505993s
Finding matches... 431.637707s
Key generation: 109.764972s
Decryption: 274.681545s
Matching dictionary: 14.4759990001s
k1: 0101010101164613; k2: 0101010102a719c2
\end{verbatim}
An adversary uses a method like \texttt{nthKey} instead of trying all $2^{64}$ possible 64-bit strings since some of the bits are parity bits. If he would try all $2^{64}$ possible 64-bit strings, he would waste time and storage on trying keys that aren't valid anyway.
\end{enumerate}
\end{enumerate}
\end{document}
|
