· 7 years ago · Jan 11, 2019, 04:00 PM
1\documentclass[a4paper,10pt]{article}
2%\documentclass[a4paper,10pt]{scrartcl}
3
4\usepackage[utf8]{inputenc}
5
6\pdfinfo{%
7 /Title (Homework 1)
8 /Author (Gr\'egory Essertel)
9 /Creator ()
10 /Producer ()
11 /Subject (CS 526)
12 /Keywords ()
13}
14
15\usepackage{geometry}
16\geometry{
17left=15mm,
18right=15mm,
19top=22mm,
20bottom=22mm,
21% headheight = -15mm,
22}
23
24\usepackage{amsfonts}
25\usepackage{amsmath}
26\usepackage{mathtools}
27\usepackage{multirow}
28\usepackage{amsfonts}
29\usepackage{mathabx}
30\usepackage{listings}
31\usepackage[linesnumbered,ruled,vlined]{algorithm2e}
32
33\usepackage{fancyhdr}
34\pagestyle{fancy}
35\fancyhf{}
36\rhead{Gr\'egory Essertel}
37\lhead{Information Security - Homework \#1}
38\rfoot{Page \thepage}
39
40\begin{document}
41\newgeometry{left=2cm,right=2cm, bottom=1cm, top = 3cm}
42\begin{titlepage}
43
44\newcommand{\HRule}{\rule{\linewidth}{0.5mm}} % Defines a new command for the horizontal lines, change thickness here
45
46\center % Center everything on the page
47 \includegraphics[scale = 0.6]{logo_purdue.png}\\[2cm] % Include a department/university logo - this will require the graphicx package
48
49%----------------------------------------------------------------------------------------
50% HEADING SECTIONS
51%----------------------------------------------------------------------------------------
52
53%\textsc{\LARGE ISAE - Supaero, Universit\'e Paul Sabatier}\\[1.3cm] % Name of your university/college
54%\textsc{\Large Purdue University - e-Lab}\\[0.5cm] % Major heading such as course name
55%\textsc{\large Minor Heading}\\[0.5cm] % Minor heading such as course title
56
57%----------------------------------------------------------------------------------------
58% TITLE SECTION
59%----------------------------------------------------------------------------------------
60
61\HRule \\[0.5cm]
62{ \huge \bfseries Information Security \\ Homework \#1}\\[0.4cm] % Title of your document
63\HRule \\[4cm]
64
65%----------------------------------------------------------------------------------------
66% AUTHOR SECTION
67%----------------------------------------------------------------------------------------
68
69\begin{minipage}{0.4\textwidth}
70\begin{flushleft} \large
71\emph{Author:}\\
72Gr\'egory \textsc{Essertel}\\%Your name
73\end{flushleft}
74\end{minipage}
75~
76\begin{minipage}{0.4\textwidth}
77\begin{flushright} \large
78\emph{Professor:} \\
79Ninghui \textsc{Li}\\ % Supervisor's Name
80\end{flushright}
81\end{minipage}\\[5cm]
82
83% If you don't want a supervisor, uncomment the two lines below and remove the section above
84% \Large \emph{Author:}\\
85% Gr\'egory \textsc{Essertel}\\[3cm] % Your name
86
87%----------------------------------------------------------------------------------------
88% DATE SECTION
89%----------------------------------------------------------------------------------------
90
91{\large \today}\\[1cm] % Date, change the \today to a set date if you want to be precise
92
93%----------------------------------------------------------------------------------------
94% LOGO SECTION
95%----------------------------------------------------------------------------------------
96
97%\includegraphics{Logo}\\[1cm] % Include a department/university logo - this will require the graphicx package
98%----------------------------------------------------------------------------------------
99
100\end{titlepage}
101\restoregeometry
102
103\section{Problem 1}
104
105\begin{itemize}
106\item \textbf{Confidentiality} is the fact that a data is only be accessible by people who should have access,
107and if the data is intercepted it should not be understandable for the attacker.
108
109 \textbf{Integrity} means that the data can not be modify without authorization, and if the data is modified it should be detected.
110
111 \textbf{Availability} means that the data should be accessible by the people who should have access.
112
113 \item The confidentiality is violated when an attacker stole data on a personal storage,
114 or when an authorized person sell confidential data to someone who can not have access.
115
116 The integrity is violated if the meaning of a message is modified without detection, or when we open a attached file on
117 an email thinking it is a friend but it is a virus or a worm.
118
119 Availability can be violated if the server on which we saved our data is unavailable, or if the communication medium is down.
120
121 \item On my computer, there is first the login through a password and a second system is the firewall. The password should protect the confidentiality and the integrity of
122 my data, the firewall is doing the same for an attacker coming from the network.
123 They can't defend against a physical attacker, the integrity of my data rely on the integrity of my hard-drive, as well as the confidentiality because someone can
124 probe my hard drive, and of course availability if my laptop is stolen.
125\end{itemize}
126
127\section{Problem 2}
128
129\begin{enumerate}
130\item We are using two fair 6-slided dice. As they are fair, the probability of an event can be computed with the ratio: number
131of possibility for the event to occur by total number of events. With two 6-slided dice, there are $6 \times 6 = 36$ different events possible.
132\begin{enumerate}
133 \item We note ``D: doubles are rolled''. A double can be made with two 1, two 2, \dots, two 6: 6 possibilities.
134
135 \begin{align}
136 \Pr[D] &= \frac{6}{36} \\
137 \Aboxed{\Pr[D] &= \frac{1}{6}}
138 \end{align}
139
140 \item "S : sum less or equal to 6".
141
142 If the first die is 1, then the second die can be 1, 2, 3, 4 or 5.
143
144 If the first die is 2, then the second die can be 1, 2, 3 or 4.
145
146 If the first die is 3, then the second die can be 1, 2 or 3.
147
148 If the first die is 4, then the second die can be 1 or 2.
149
150 If the first die is 5, then the second die can be 1.
151
152 If the first die is 6, the sum can't be less or equal to 6.
153
154 Then:
155
156 \begin{align}
157 \Pr[S] &= \frac{5 + 4 + 3 + 2 + 1}{36} \\
158 \Pr[S] &= \frac{5}{12}
159 \end{align}
160
161
162
163 Let's compute $\Pr[D \wedge S]$. If the sum of the dice is 6 or less,
164 the only double possible are two 1, two 2 or two 3.
165
166 \begin{align}
167 \Pr[D \wedge S] &= \frac{3}{36} \\
168 \Pr[D \wedge S] &= \frac{1}{12}
169 \end{align}
170
171
172 Finnaly,
173
174 \begin{align}
175 \Pr[D \mid S] &= \frac{\Pr[D \wedge S]}{\Pr[S]} \\
176 \Aboxed{\Pr[D \mid S] &= \frac{1}{5}}
177 \end{align}
178
179 \item "A: The larger of the two dice's outcomes is a least 4.``
180
181 If the larger die's outcome value is 6, the other die can take the value: 1, 2, 3, 4, 5 or 6.
182
183 If the larger die's outcome value is 5, the other die can take the value: 1, 2, 3, 4 or 5.
184
185 If the larger die's outcome value is 4, the other die can take the value: 1, 2, 3 or 4.
186
187 Then there are $6 + 5 + 4$ possibilities for the event A to occurs, then:
188
189 \begin{align}
190 \Pr[A] &= \frac{15}{36} \\
191 \Aboxed{\Pr[A] &= \frac{5}{12}}
192 \end{align}
193
194
195 \item "B: At least one die is one", "C: The two dice have different value".
196
197 If the first die is the one with the value 1, then the other die can take 5 values: all but 1.
198
199 If the second die is the one with the value 1, then the other die can take 5 values: all but 1.
200
201 Therefore there are 10 possibilities for the event $B \wedge C$ to occur:
202 \begin{align}
203 \Pr[B \wedge C] &= \frac{10}{36} \\
204 \Pr[B \wedge C] &= \frac{5}{18}
205 \end{align}
206
207
208 Let's compute $\Pr[C]$, for each possible value for the first die, there are 5 possibilities for the second: all but itself.
209
210 Then:
211
212 \begin{align}
213 \Pr[C] &= \frac{6 \times 5}{36} \\
214 \Pr[C]&= \frac{5}{6}
215 \end{align}
216
217
218 Finnally,
219
220 \begin{align}
221 \Pr[B \mid C] &= \frac{\Pr[B \wedge C]}{\Pr[C]} \\
222 \Aboxed{\Pr[B \mid C] &= \frac{1}{3}}
223 \end{align}
224
225
226
227 \item "X: the first die result is an odd number".
228
229 There are 3 possibilities for the first die: 1, 3 or 5, and 6 for the second:
230
231 \begin{align}
232 \Pr[X] &= \frac{3 \times 6}{36} \\
233 \Aboxed{\Pr[X]&= \frac{1}{2}}
234 \end{align}
235
236
237 "Y: The rolled sum is an event number".
238
239 If the first die is even, then the second has to be even too: $3 \times 3 = 9$ possibilities.
240
241 If the first die is odd, then the second has to be odd has well: $3 \times 3 = 9$ possibilities.
242
243 Then:
244
245 \begin{align}
246 \Pr[Y] &= \frac{9 + 9}{36} \\
247 \Aboxed{\Pr[Y] &= \frac{1}{2}}
248 \end{align}
249
250
251 Now lets consider, $X \wedge Y$. Based on what we said for $Y$ alone, there is 9 possibilities if the first die is odd:
252
253 \begin{align}
254 \Pr[X \wedge Y] &= \frac{9}{36} \\
255 \Aboxed{\Pr[X \wedge Y] &= \frac{1}{4}}
256 \end{align}
257
258 As we have $\Pr[X \wedge Y] = \Pr[X] \times \Pr[Y]$, \fbox{$X$ and $Y$ are independent}.
259
260 \item This question is almost the same than the previous one,
261
262 X: the first die result is a multiple of 2".
263
264 There are 3 possibilities for the first die: 2, 4 or 6, and 6 for the second:
265
266 \begin{align}
267 \Pr[X] &= \frac{3 \times 6}{36} \\
268 \Aboxed{\Pr[X] &= \frac{1}{2}}
269 \end{align}
270
271 "Y: The rolled sum is a multiple of 2".
272
273 It is the same event than the previous question:
274
275 \begin{align}
276 \Aboxed{\Pr[Y] &= \frac{1}{2}}
277 \end{align}
278
279 Now lets consider, $X \wedge Y$. Based on what we said for $Y$ alone, there is 9 possibilities if the first die is even:
280
281 \begin{align}
282 \Pr[X \wedge Y] &= \frac{9}{36} \\
283 \Aboxed{\Pr[X \wedge Y] &= \frac{1}{4}}
284 \end{align}
285
286
287 As we have $\Pr[X \wedge Y] = \Pr[X] \times \Pr[Y]$, $X$ and $Y$ are independent.
288
289 \item "X: the first die result is a multiple of 3"
290
291 There are two possibilities for the first die: 3 or 6 and 6 for the second.
292
293 \begin{align}
294 \Pr[X] &= \frac{2 \times 6}{36} \\
295 \Aboxed{\Pr[X] &= \frac{1}{3}}
296 \end{align}
297
298
299 "Y: The rolled sum is a multiple of 2"
300
301 We already computed it:
302
303 \begin{align}
304 \Aboxed{\Pr[Y] &= \frac{1}{2}}
305 \end{align}
306
307
308 Now let's compute, $\Pr[X \wedge Y]$.
309
310 If the first die is 3, then the second die has to be odd: 3 possibilities.
311
312 If the first die is 6, then the second die has to be even: 3 possibilities.
313
314 \begin{align}
315 \Pr[X \wedge Y] &= \frac{3 + 3}{36} \\
316 \Aboxed{\Pr[X \wedge Y] &= \frac{1}{6}}
317 \end{align}
318
319 We have then
320 \begin{align}
321 \Pr[X \mid Y] &= \frac{\Pr[X \wedge Y]}{\Pr[Y]} \\
322 \Aboxed{\Pr[X \mid Y] &= \frac{1}{3}}
323 \end{align}
324
325 and
326
327 \begin{align}
328 \Pr[Y \mid X] &= \frac{\Pr[X \wedge Y]}{\Pr[X]} \\
329 \Aboxed{\Pr[Y \mid X] &= \frac{1}{2}}
330 \end{align}
331
332
333 Like we obtain $\Pr[X \mid Y] = \Pr[X]$ and $\Pr[Y \mid X] = \Pr[Y]$, \fbox{$X$ and $Y$ are independent}.
334\end{enumerate}
335\item "X: student pass the midterm exam in a course" and "Y: student pass the final exam."
336
337\begin{itemize}
338 \item Compute $\Pr[X \wedge Y]$:
339\begin{equation}
340 \Pr[Y \mid X] = \frac{\Pr[X \wedge Y]}{\Pr[X]}
341\end{equation}
342then
343\begin{align}
344 \Pr[X \wedge Y] &= \Pr[Y \mid X]\Pr[X]\\
345 \implies \Aboxed{\Pr[X \wedge Y] &= 0.675}
346\end{align}
347 \item Compute $\Pr[\neg X \mid Y]$:
348 \begin{align}
349 1 - \Pr[\neg X \mid Y] &= \Pr[X \mid Y] \\
350 &= \frac{\Pr[X \wedge Y]}{\Pr[Y]}
351\end{align}
352then
353\begin{align}
354 \Pr[\neg X \mid Y] &= 1 - \frac{\Pr[X \wedge Y]}{\Pr[Y]} \\
355 \implies \Aboxed{\Pr[\neg X \mid Y] &= 0.15625}
356\end{align}
357 \item Compute $\Pr[Y\mid \neg X ]$ using Bayes theorem:
358 \begin{align}
359 \Pr[Y\mid \neg X ] &= \frac{\Pr[\neg X \mid Y]\Pr[Y]}{\Pr[\neg X]}\\
360 &= \frac{\Pr[\neg X \mid Y]\Pr[Y]}{1 - \Pr[X]} \\
361 \implies \Aboxed{\Pr[Y\mid \neg X ] &= 0.5}
362\end{align}
363
364\item $\Pr[Y] \neq \Pr[Y \mid X]$ then \fbox{$X$ and $Y$ are not independent}.
365\end{itemize}
366
367\item I remind:
368\begin{center}
369 \begin{tabular}{|c|c|c|}
370 \hline
371 ~ & Married & Single \\ \hline
372 At least five years teaching experience & 18 & 12 \\ \hline
373 Less than five years teaching experience & 30 & 18 \\ \hline
374 \end{tabular}
375 \end{center}
376 \begin{enumerate}
377 \item "M: The first applicant interviwed is married.", "F: The first applicant intervied has at least five years teaching experience."
378 \begin{itemize}
379 \item Computing $\Pr[M]$.
380 \begin{align}
381 \Pr[M] &= \frac{18 + 30}{18 + 12 + 30 + 18} \\
382 \Aboxed{\Pr[M] &= \frac{8}{13}}
383 \end{align}
384 \item Computing $\Pr[F]$.
385 \begin{align}
386 \Pr[F] &= \frac{18 + 12}{18 + 12 + 30 + 18} \\
387 \Aboxed{\Pr[F] &= \frac{5}{13}}
388 \end{align}
389 \item Computing $\Pr[F \wedge M]$.
390 \begin{align}
391 \Pr[F \wedge M] &= \frac{18}{18 + 12 + 30 + 18} \\
392 \Aboxed{\Pr[F \wedge M] &= \frac{3}{13}}
393 \end{align}
394 \item Computing $\Pr[F\mid M]$.
395 \begin{align}
396 \Pr[F \mid M] &= \frac{\Pr[F \wedge M]}{\Pr[M]} \\
397 \Aboxed{\Pr[F\mid M] &= \frac{3}{8}}
398 \end{align}
399 \item Computing $\Pr[M\mid F]$.
400 \begin{align}
401 \Pr[M \mid F] &= \frac{\Pr[M \wedge F]}{\Pr[F]} \\
402 \Aboxed{\Pr[M \mid F] &= \frac{3}{5}}
403 \end{align}
404 \item $\Pr[M \mid F] \neq \Pr[M]$ and $\Pr[F \mid M] \neq \Pr[F]$ then \fbox{$M$ and $F$ are not independent}.
405 \end{itemize}
406 \item We suppose that a person with at least five years of experience has twixe the chance of an application with less. If they were balls in a bag with each
407 a number, his or her number would be pesent twice. Therefore I computed the probability with the next table:
408 \begin{center}
409 \begin{tabular}{|c|c|c|}
410 \hline
411 ~ & Married & Single \\ \hline
412 At least five years teaching experience & 36 & 24 \\ \hline
413 Less than five years teaching experience & 30 & 18 \\ \hline
414 \end{tabular}
415 \end{center}
416 "U: the job goes to one of the single applicant", "V: the job goes to one of the applicant woth less than five years teaching experience".
417 \begin{itemize}
418 \item Computing $\Pr[U]$:
419 \begin{align}
420 \Pr[U] &= \frac{24 + 18}{36 + 24 + 30 + 18} \\
421 \Aboxed{\Pr[U] &= \frac{7}{18}}
422 \end{align}
423 \item Computing $\Pr[V]$:
424 \begin{align}
425 \Pr[V] &= \frac{30 + 18}{108} \\
426 \Aboxed{\Pr[V] &= \frac{4}{9}}
427 \end{align}
428 \item Computing $\Pr[U \wedge V]$:
429 \begin{align}
430 \Pr[U \wedge V] &= \frac{18}{108} \\
431 \Aboxed{\Pr[U \wedge V] &= \frac{1}{6}}
432 \end{align}
433 \item Computing $\Pr[U \mid V]$:
434 \begin{align}
435 \Pr[U \mid V] &= \frac{\Pr[U \wedge V]}{\Pr[V]} \\
436 \Aboxed{\Pr[U \mid V] &= \frac{3}{8}}
437 \end{align}
438 \item Computing $\Pr[V \mid U]$:
439 \begin{align}
440 \Pr[V \mid U] &= \frac{\Pr[U \wedge V]}{\Pr[U]} \\
441 \Aboxed{\Pr[V \mid U] &= \frac{3}{7}}
442 \end{align}
443 \item $\Pr[U \mid V] \neq \Pr[U]$ and $\Pr[V \mid U] \neq \Pr[V]$ then \fbox{$U$ and $V$ are not independent}.
444 \end{itemize}
445
446 \end{enumerate}
447 \item ''S: a person has the disease", "T: test is positive". \\
448 We have $\Pr[T \mid S] = 0.95$, $\Pr[\neg T \mid \neg S] = 0.95$ and $\Pr[S] = 0.001$.
449 \begin{enumerate}
450 \item \begin{align}
451 \Pr[S \mid T] &= \frac{\Pr[T \mid S]\Pr[S]}{\Pr[T]}
452 \end{align}
453 and we know:
454 \begin{align}
455 \Pr[T] &= \Pr[T \mid S]\Pr[S] + \Pr[T \mid \neg S]\Pr[\neg S] \\
456 &= \Pr[T \mid S]\Pr[S] + (1 - \Pr[\neg T \mid \neg S])\times (1 - \Pr[S])
457 \end{align}
458 then
459 \begin{align}
460 \label{eq1}\Pr[S \mid T] &= \frac{\Pr[T \mid S]\Pr[S]}{\Pr[T \mid S]\Pr[S] + (1 - \Pr[\neg T \mid \neg S])\times (1 - \Pr[S])} \\
461 \Aboxed{\Pr[S \mid T] &= 0.0187}
462 \end{align}
463 \item Using the Equation \ref{eq1} again with the new values,
464 \begin{align}
465 \Aboxed{\Pr[S \mid T] &= 0.0196}
466 \end{align}
467 \item Using the Equation \ref{eq1} again with the new values,
468 \begin{align}
469 \Aboxed{\Pr[S \mid T] &= 0.322}
470 \end{align}
471 \end{enumerate}
472\end{enumerate}
473
474\section{Problem 3}
475
476For all the definition we will see, the attacker now the cipher and also the language in which the plaintext is written.
477
478\begin{itemize}
479 \item \begin{itemize}
480 \item \textbf{ciphertext-only attack} means the attacker has only access to some ciphertexts but doesn't know the corresponding
481 plaintexts.
482 \item \textbf{known-plaintext attack} means the attacker has access some ciphertexts with their corresponding plaintext.
483 \item \textbf{chosen plaintext} means the attacker can obtain the ciphertext of plaintext he can chose.
484 \end{itemize}
485 \item Under ciphertext-only attack, one way to break a substitution cipher is to make a frequency analysis. A letter is encrypted everytime with the same letter,
486 therefore the frequency will be kept during the encryption process. It may need several guess but it will narrow the possibilities a lot.
487
488 If it is a known plaintext attack, we can retrieve a part of the permutation used with the known plaintext and the corresponding ciphertext. Even if it is not complete
489 the missing letter will be few and therefor easy to guess.
490 \item The Internet packet have a well define header, therefore a known plaintext attack can be carried out with only considering the headers of the packets. For example
491 we can have access to the MAC address of the router in our own packet, and the corresponding encryption in the ciphertext sniffed on the network.
492
493 A chosen plaintext can be carried out with emails. By default emails are not encrypted and the text is visible by sniffing. Sending an email to the owner of the
494 laptop with the chosen characters and then sniffing the communication the email can be detected an the corresponding ciphertext is known.
495\end{itemize}
496
497
498\section{Problem 4}
499
500We are considering a "Double Vigen\`ere cipher" with two randomly chosen keys $K_{1}$ and $K_{2}$ of length $l$ and $l+1$. The message is first encrypted
501with $K_{1}$ then the ciphertext obtained is encrypted with $K_{2}$.
502
503\begin{itemize}
504 \item The double encryption can be perform by a single encryption with the key $K_{3}$ of length $l \times (l + 1)$ where $K_{3}$ is the ciphertext through
505 the Vigen\`ere cipher of the plaintext $K_{2}\dots K_{2}$ ($l$ times $K_{2}$) by the key $K_{1}$.
506
507 Therefore under a ciphertext only attack, the usual attack again the Vigen\`ere cipher is working, only $K_{3}$ has to be discovered. First looking for the
508 key length and then frequency analysis.
509
510 However it is weaker than a single Vigen\`ere cipher:
511 \begin{itemize}
512 \item First the length of the key $K_{3}$ will be is the set :
513 \[\{i \times (i + 1), \forall i \in \mathbb{N}\} = \{2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, \dots\}\]
514 \item Secondly the space of the $K_{3}$ key is much smaller than the space of a single key of length $l \times (l + 1)$. The $K_{3}$ key can't be random.
515 \end{itemize}
516
517 These two reasons are decreasing the entropy of the key generation, it would be better to use a Vigen\`ere cipher with a single random key of length $l \times (l + 1)$
518 in the first place.
519
520 \item Let's first suppose we know the length of the first key, ie $l$. Then we note $\forall i \in \ldbrack 1, 50 \rdbrack, \delta_{i} = CT_{i} - PT_{i}$. Then $\delta$
521 is the sum of $K_{1}$ and $K_{2}$, let's note $x_{i}$ the character of $K_{1}$ and $y_{i}$ the character of $K_{2}$.
522
523 Then we can write (modulo the number of character):
524 \begin{equation}
525 \label{equ1}\forall i \in \ldbrack 1, l \rdbrack, y_{i} = \delta_{i} - x_{i}
526 \end{equation}
527 and
528 \begin{equation}
529 \label{equ2}\forall i \in \ldbrack 1, l-1 \rdbrack, x_{i+1} = \delta_{(l+1) + i} - y_{i}
530 \end{equation}
531 and finally,
532 \begin{equation}
533 \label{equ3}y_{l+1} = \delta_{l+1} - x_{1}
534 \end{equation}
535
536 Therefore choosing, $x_{1}$ give $y_{1}$ (Equation \ref{equ1}) and $y_{l+1}$ (Equation \ref{equ3}).
537
538 Then $y_{1}$ give $x_{2}$ (Equation \ref{equ2}), and again Equation \ref{equ1}\dots. We can then just chose all possibilities for $x_{1}$ and found the keys very easily.
539 It is working because we need only the first $2\times l$ values of the plaintext and ciphertext (in Equation \ref{equ2}), and the key length is less or equal to 19 therefore
540 we need 38 characters at most and we have 50.
541
542 Now if we don't know the size of the key, then we can try all of them, with the English alphabet it would require at most $26 \times 10 = 260$ attempts.
543
544\end{itemize}
545
546\section{Problem 5}
547
548\begin{itemize}
549 \item In the following function, byte is just an integer on 8 bits with the values between 0 and 25.
550
551 Encryption function:
552 \begin{lstlisting}[frame=single,language=C]
553/* Encryption algorithm */
554byte* encrypt(byte* msg, int msg_length, byte* key, int key_length) {
555
556 int index; /* Loop index */
557 byte* res = calloc(msg_length + 17, sizeof(byte)); /* result array */
558
559 /* init false random generator */
560 struct timeval tv;
561 gettimeofday(&tv,NULL);
562 srand(tv.tv_usec);
563
564 /* generate random string and add it in the beginning of the ciphertext */
565 for (index = 0 ; index < 17 ; ++index) {
566 res[index] = rand()%26;
567 }
568
569 /* apply IV */
570 for (index = 0 ; index < msg_length ; ++index) {
571 res[17 + index] = (msg[index] + res[index])%26;
572 }
573
574 /* Apply Vigenere cipher */
575 for (index = 0 ; index < msg_length + 17 ; ++index) {
576 res[index] = (res[index] + key[index%key_length])%26;
577 }
578
579 return res;
580}
581
582\end{lstlisting}
583Decryption function:
584 \begin{lstlisting}[frame=single,language=C]
585/* decryption algorithm */
586byte* decrypt(byte* msg, int msg_length, byte* key, int key_length) {
587
588 int index; /* loop index */
589 byte* tmp = calloc(msg_length, sizeof(byte)); /* temporary array*/
590 byte* res = calloc(msg_length-17, sizeof(byte)); /* result array */
591
592 /* Apply Vigenere decryption */
593 for (index = 0; index < msg_length ; ++index) {
594 tmp[index] = (26 + msg[index] - key[index%key_length])%26;
595 }
596
597 /* reconstruct x (as in subject) */
598 for (index = 1; index <= msg_length ; ++index) {
599 tmp[msg_length - index] =
600 (26 + tmp[msg_length - index] - tmp[msg_length - 17 - index])%26;
601 }
602
603 /* suppress the 17th first random characters */
604 for (index = 0 ; index < msg_length-17 ; ++index) {
605 res[index] = tmp[index+17];
606 }
607
608 /* cleaning */
609 free(tmp);
610
611 return res;
612}
613\end{lstlisting}
614
615 \item \begin{lstlisting}[frame=single]
616 The plaintext (length 53) used is:
617 welcometopurdueforthissemesterfalltwothousandfourteen
618
619 With the key (length 8): cspurdue
620
621 The following text are corresponding ciphertexts (length 70):
622 - ntavqbvwywrpzlvopzuquqejnciqdowjrtnsuozglpdfgtwlhsblluyqsveipvpudoikmk
623 - ffwpphpnqpnksoqlergmopkdeubmyhzeoifeqiymfgvycopocpqdxqspypvairkngjfzew
624 - gonrnnptdzeisvsxespdqnqdkhldwhggaignhkwsfmiitmpvebqeghunepbnsiinnlrzff
625
626\end{lstlisting}
627\item The following pseudo code extract a plaintext under a known plaintext attack against the cipher described in the subject. We know $(M_{1}, C_{1})$ a pairs
628plaintext ciphertext, and $C_{2}$ encrypted under the same key than $C_{1}$.
629
630In order to fcilitate the reading of the code, I am separtion the ciphertext and plaintext in block of length 17, and suppose the two messages have the same length and
631is multiple of 17. The general case will be the same.
632
633\begin{align}
634 M_{1} &= M_{1}^{(1)}\dots M_{1}^{(n)} \\
635 C_{1} &= C_{1}^{(1)}\dots C_{1}^{(n+1)} \\
636 C_{2} &= C_{2}^{(1)}\dots C_{2}^{(n+1)} \\
637\end{align}
638
639We know $M_{2}$ will be of the same shape :
640
641\begin{equation}
642 M_{2} = M_{2}^{(1)}\dots M_{2}^{(n)}
643\end{equation}
644
645Operations on the vector are made block to block module 26.
646
647\begin{algorithm}[H] \label{alg}
648 \KwIn{$M_{1}$, $C_{1}$, $C_{2}$}
649 \KwOut{$M_{2}$}
650 $RES\gets C_{1}$ - $C_{2}$ \tcp*{Delete Vigen\`ere keys}
651
652 \For{$i \gets n$ \textbf{to} $1$}{
653 $RES^{(i+1)} \gets RES^{(i+1)} - RES^{(i)}$ \tcp*{Now $RES^{(i+1)} = M_{1}^{(i)} - M_{2}^{(i)}$}
654 $M_{2}^{(i)} \gets M_{1}^{(i)} - RES^{(i+1)}$ \tcp*{$M_{2}^{(i)}$ is retrieve easily}
655 }
656 \Return{$M_{2}$}
657 \caption{Known plaintext attack algorithm}
658\end{algorithm}
659
660If the length of $C_{2}$ is grater than the length of $C_{1}$, we first decrypt the same length $n$ (block of 17)
661and subtract $\sum_{i = 1}^{n} C_{2}^{(i)}$ to the rest of the cyphertext $C_{2}$. Now the rest of $C_{2}$ is almost a new
662ciphertext, there will be some adjustment in order to make the Vigen\`ere key to be aligned but the idea is the same.
663The only unknow is the Vigen\`ere key, once deleted with the subtraction of two ciphertext, everything else is known.
664
665\item For a ciphertext attack only, if the same key is used, then with the same algorithm than Algorithm \ref{alg}, but without the line 4 because we don't know a plaintext, give us the
666difference between two plaintexts. This give use a cyphertext from a stream cipher with a non-random keystream (one of the two plaintexts).
667
668I was thinking that using a frequency analysis on the difference of two letters will give good result and narrow the possibilities a lot, then we will be able to
669decrypt the first blocks of each plaintext and then using the known plaintext attack we describe previously.
670
671Now if we tried to attack only one ciphertext or multiple without the same key, I don't think of any easy ways.
672\end{itemize}
673
674
675\section{Problem 6}
676I create the table of all possibilities:
677 \begin{center}
678 \begin{tabular}{|c|c||c|c|c|c|c|c|}
679 \hline
680 \multicolumn{2}{|l||}{\multirow{2}{*}{~}} & \multicolumn{6}{|c|}{Key values}\\ \cline{3-8}
681 \multicolumn{2}{|l||}{} & 1 & 2 & 3 & 4 & 5 & 6\\ \hline\hline
682 \multirow{4}{*}{Dice Values} & 1 & 1 & 2 & 3 & 4 & 5 & 6 \\\cline{2-8}
683 & 2 & 2 & 4 & 6 & 8 & 10 & 12 \\ \cline{2-8}
684 & 3 & 3 & 6 & 9 & 12 & 2 & 5 \\ \cline{2-8}
685 & 4 & 4 & 8 & 12 & 3 & 7 & 11 \\ \cline{2-8}
686 & 5 & 5 & 10 & 2 & 7 & 12 & 4 \\ \cline{2-8}
687 & 6 & 6 & 12 & 5 & 11 & 4 & 10 \\ \hline
688 \end{tabular}
689 \end{center}
690\begin{itemize}
691 \item If we know the dices values are 5 or 6, then looking at the two last lines of the table we see that,
692 \begin{itemize}
693 \item 5, 10, 12 and 4 can be cyphertext from both 5 and 6, therefore we won't be able to know which one is the good one with these values.
694 \item 2 and 7 are possible ciphertexts only for 5.
695 \item 6 and 11 are possible ciphertextes only for 6.
696 \item any other ciphertexts would mean our assumption is false.
697 \end{itemize}
698
699 Therefore we can learn the value of M if C is 2, 6, 7 or 11.
700 \item We want to compute $\Pr[PT \mid CT = i]$ for every $i$. For that I check the line $k$ and count how many $i$ there are, note $n^{i}_k$,
701 then how many $i$ there are in the whole table, noted $n^{(i)}$
702 and compute the probability with the rule:
703 \begin{equation}
704 \Pr[PT = k \mid CT = i] = \frac{n^{i}_k}{n^{(i)}}
705 \end{equation}
706 \begin{itemize}
707 \item $\Pr[PT \mid CT = 1] = \langle 1, 0, 0, 0, 0, 0 \rangle$
708 \item $\Pr[PT \mid CT = 2] = \langle \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, 0, \frac{1}{4}, 0 \rangle$
709 \item $\Pr[PT \mid CT = 3] = \langle \frac{1}{3}, 0, \frac{1}{3}, \frac{1}{3}, 0, 0 \rangle$
710 \item $\Pr[PT \mid CT = 4] = \langle \frac{1}{5}, \frac{1}{5}, 0, \frac{1}{5}, \frac{1}{5}, \frac{1}{5} \rangle$
711 \item $\Pr[PT \mid CT = 5] = \langle \frac{1}{4}, 0, \frac{1}{4}, 0, \frac{1}{4}, \frac{1}{4}\rangle$
712 \item $\Pr[PT \mid CT = 6] = \langle \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, 0, 0, \frac{1}{4}\rangle$
713 \item $\Pr[PT \mid CT = 7] = \langle 0, 0, 0, \frac{1}{2}, \frac{1}{2}, 0 \rangle$
714 \item $\Pr[PT \mid CT = 8] = \langle 0, \frac{1}{2}, 0, \frac{1}{2}, 0, 0 \rangle$
715 \item $\Pr[PT \mid CT = 9] = \langle 0, 0, 1, 0, 0, 0 \rangle$
716 \item $\Pr[PT \mid CT = 10] = \langle 0, \frac{1}{3}, 0, 0, \frac{1}{3}, \frac{1}{3} \rangle$
717 \item $\Pr[PT \mid CT = 11] = \langle 0, 0, 0, \frac{1}{2}, 0, \frac{1}{2} \rangle$
718 \item $\Pr[PT \mid CT = 12] = \langle 0, \frac{1}{5}, \frac{1}{5}, \frac{1}{5}, \frac{1}{5}, \frac{1}{5}\rangle$
719 \end{itemize}
720 \item If we make the same table than we did in the beginning of the exercise but with
721 $K \in \ldbrack 1, 12 \rdbrack$, we would see that there is one and only one possible key for each $(CT,PT)$ pairs, therefore under the assumption that the key $K$
722 is chosen randomly we can assess the cipher offers perfect secrecy (Theorem in the lecture slide).
723
724 In other word, every message can be encrypted into every ciphertext with one and one key, therefore $\Pr[CT = c \mid PT = m] = \frac{1}{12}, \forall c, m$.
725 \begin{center}
726 \begin{tabular}{|c|c||c|c|c|c|c|c|c|c|c|c|c|c|}
727 \hline
728 \multicolumn{2}{|l||}{\multirow{2}{*}{~}} & \multicolumn{12}{|c|}{Key values}\\ \cline{3-14}
729 \multicolumn{2}{|l||}{} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ \hline\hline
730 \multirow{4}{*}{Dice Values} & 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\\cline{2-14}
731 & 2 & 2 & 4 & 6 & 8 & 10 & 12 & 1 & 3 & 5 & 7 & 9 & 11 \\ \cline{2-14}
732 & 3 & 3 & 6 & 9 & 12 & 2 & 5 & 8 & 11 & 1 & 4 & 7 & 10\\ \cline{2-14}
733 & 4 & 4 & 8 & 12 & 3 & 7 & 11 & 2 & 6 & 10 & 1 & 5 & 9\\ \cline{2-14}
734 & 5 & 5 & 10 & 2 & 7 & 12 & 4 & 9 & 1 & 6 & 11 & 3 & 8\\ \cline{2-14}
735 & 6 & 6 & 12 & 5 & 11 & 4 & 10 & 3 & 9 & 2 & 8 & 1 & 7\\ \hline
736 \end{tabular}
737 \end{center}
738
739 NB: It is easy to show that $\forall i, j \in \ldbrack 1, 12 \rdbrack, \exists n \in \mathbb{Z} / i \times n = j \mod 13$, with the B\'ezout identity as 13 is prime with
740 all number between 1 and 12.
741
742\end{itemize}
743
744\section{Problem 7}
745
746The cipher is a Vignere Cipher with a random key of length 50 and the plain text is an English text of length 10.
747If we take $M_{1} = a \dots a$ (100 $a$), and $M_{2} = a \dots ab \dots b$ (50 $a$, 50 $b$).\\
748If $C = c\dots c$ (100 c), then $\Pr[CT = C \mid PT = M_{1}] > 0$, it is possible with the key $K = b\dots b$.\\
749But $\Pr[CT = C \mid PT = M_{2}] = 0$, the first fifty characters of the ciphertext have to be different form the last fifty.\\
750
751\section{Problem 8}
752
753Let's take cipher that offers perfect secrecy. Therefore:
754\begin{equation}
755 \forall M_{1}, M_{2}, \Pr[CT = C \mid PT = M_{1}] = \Pr[CT = C \mid PT = M_{2}]
756\end{equation}
757We note $C$ the ciphertext of the plaintext $M^{+}$ encrypted by the key $K^{+}$.
758Let's suppose the number of possible keys is less than the number of plaintext, there is a plaintext $M^{-}$ which can not be encrypted into $C$. Otherwise two different plaintexts
759would be encypted into the same ciphertext with the same key.
760
761Therefore
762\[ \Pr[CT = C \mid PT = M_{-}] = 0 < \Pr[CT = C \mid PT = M_{+}]\]
763
764We have a contradiction, therefore our hypothesis is false, we can't have a number of keys less than the number of plaintext.
765
766\section{Problem 9}
767
768I wrote the program in C. For generating IV I use the random generator ISAAC-64 (Indirection, Shift, Accumulate, Add, and Count)
769\footnote{http://burtleburtle.net/bob/rand/isaacafa.html}. Here is the description of the
770algorithm:
771
772\begin{quotation}
773The results are uniformly distributed, unbiased, and unpredictable unless you know the seed. Cycles are guaranteed to be at least
774$2^{72}$ values long, and they are $2^{16583}$ values long on average.
775\end{quotation}
776
777A seed has to be given, for that I was thinking using the microsecond processor time, but it was too small and is not random enough. I preferred
778using the $rand$ function is the C library with the microsecond as seed. And then I fill the 2048 bytes of the ISAAC-64 taking the lowest byte of the
779result of $rand$, 2048 times.
780
781ISAAC-64 generates a 64 bits integer, I initialize IV byte per byte using the lower byte of each ISAAC-64 number. It is to make the implementation
782simpler if IV length is not a multiple of 64 bits.
783
784Here is the complete code:
785
786NB: the $rand$ function from the ISAAC library has been rename $rand\_isaac$ because of the conflict with the C library rand.
787
788\begin{lstlisting}[frame=single, language=C]
789#include <time.h>
790#include <stdlib.h>
791#include <stdio.h>
792#include "isaac64.h"
793
794#define NB_SKIP 3072 /* number of bytes skipped in the RC4 stream */
795#define IV_LENGTH 32 /* size of the initial vector */
796
797typedef unsigned char byte;
798
799/* RC4 algorithm variables */
800byte S[256];
801byte PRGAi;
802byte PRGAj;
803
804/* Debug function - print a byte array in hexadecimal representation */
805void print_byte(byte* tab, int length) {
806 int index;
807
808 for (index = 0 ; index < length ; ++index)
809 printf("%.2x", tab[index]);
810
811 printf("\n");
812}
813
814/* Debug function - print a byte array in character */
815void print_char(byte* tab, int length) {
816 int index;
817
818 for (index = 0 ; index < length ; ++index)
819 printf("%c", tab[index]);
820
821 printf("\n");
822}
823
824/*
825 Key-scheduling algorithm initializes the S array
826 and other variables for the PRGA function.
827 */
828void KSA(byte* key, int key_length) {
829 int index;
830 byte tmp;
831
832 for (index = 0 ; index < 256 ; ++index)
833 S[index] = (byte) index;
834
835 byte j = 0;
836
837 for (index = 0 ; index < 256 ; ++index) {
838 j = (j + S[index] + key[index%key_length]);
839 tmp = S[j];
840 S[j] = S[index];
841 S[index] = tmp;
842 }
843
844 PRGAi = 0;
845 PRGAj = 0;
846}
847
848/* Pseudo-random generation algorithm */
849byte PRGA() {
850 byte tmp;
851
852 PRGAi++;
853 PRGAj += S[PRGAi];
854
855 /* Swap S[i] and S[j] */
856 tmp = S[PRGAj];
857 S[PRGAj] = S[PRGAi];
858 S[PRGAi] = tmp;
859
860 tmp = S[PRGAi] + S[PRGAj];
861
862 return S[tmp];
863}
864
865/* Initialize S array with the key
866 and skip the first NB_SKIP values
867 */
868void init_KSA(byte* key, int key_length) {
869 int index; /* Loop index */
870 KSA(key, key_length); /* Init S array */
871
872 /* skip values */
873 for (index = 0 ; index < NB_SKIP ; ++index)
874 PRGA();
875}
876
877/* Initialization of isaac generator.
878 The seed is generated from the C rand library.
879 */
880void init_generator() {
881 int index;
882 char* ptr;
883
884 /* init false random generator */
885 struct timeval tv;
886 gettimeofday(&tv,NULL);
887 srand(tv.tv_usec);
888
889 /* init random generator seed */
890 ptr = (char*) randrsl;
891 for (index = 0 ; index < (int) sizeof(ub8) * RANDSIZ ; ++index)
892 ptr[index] = (char) (rand() & 0xFF);
893
894 /* init ISAAC-64 generator */
895 randinit(TRUE);
896
897 return;
898}
899
900/* encryption function */
901byte* encrypt(byte* pt, int pt_length, byte* key, int key_length) {
902 int index; /* Loop index */
903 byte mixed_key[IV_LENGTH + key_length]; /* Mixed key and IV */
904 byte* ct = calloc(IV_LENGTH + pt_length, sizeof(byte)); /* Output stream */
905
906 /* generate IV and copy it in the ct header */
907 for (index = 0 ; index < IV_LENGTH ; ++index) {
908 ct[index] = (byte) (isaac_rand() & 0xFF);
909 mixed_key[key_length + index] = ct[index];
910 }
911
912 /* Mix key and IV */
913 for (index = 0 ; index < key_length ; ++index)
914 mixed_key[index] = key[index];
915
916 /* Init KSA with IV and key mixed */
917 init_KSA(mixed_key, IV_LENGTH + key_length);
918
919 /* Encrypt the message */
920 for (index = 0 ; index < pt_length ; ++index) {
921 ct[IV_LENGTH + index] = pt[index] ^ PRGA();
922 }
923
924 return ct;
925}
926
927/* Decrypt function */
928byte* decrypt(byte* ct, int ct_length, byte* key, int key_length) {
929 int index; /* Loop index */
930 byte mixed_key[IV_LENGTH + key_length]; /* Initial vector mixed with key */
931 byte* pt = calloc(ct_length - IV_LENGTH, sizeof(byte)); /* Output stream */
932
933 /* Mix key and IV */
934 for (index = 0 ; index < key_length ; ++index)
935 mixed_key[index] = key[index];
936
937 for (index = 0 ; index < IV_LENGTH ; ++index)
938 mixed_key[key_length + index] = ct[index];
939
940 /* Init KSA */
941 init_KSA(mixed_key, IV_LENGTH + key_length);
942
943 /* Decrypt the message */
944 for (index = 0 ; index < ct_length - IV_LENGTH ; ++index) {
945 pt[index] = ct[IV_LENGTH + index] ^ PRGA();
946 }
947
948 return pt;
949}
950
951/* Test */
952int main() {
953 /* FILE */
954 FILE* fkey;
955 FILE* fplaintext;
956
957 /* Streams */
958 int index;
959 int key_length;
960 int pt_length;
961 byte* key;
962 byte* pt;
963 byte* ct;
964 byte* res;
965
966 /* init generator for IV generation */
967 init_generator();
968
969 /* extract key */
970 fkey = fopen("key.txt", "r");
971 fseek(fkey, 0L, SEEK_END);
972 key_length = ftell(fkey) - 1;
973 rewind(fkey);
974 index = 0;
975
976 if (key_length > 32) {
977 printf("The key is too long.\n");
978 fclose(fkey);
979 return 0;
980 } else if (key_length < 16) {
981 fclose(fkey);
982 printf("The key is too short.\n");
983 return 0;
984 }
985
986 key = calloc(key_length, sizeof(byte));
987 while (index < key_length && fscanf(fkey, "%c", key + index) != EOF) {
988 ++index;
989 }
990 fclose(fkey);
991
992 printf("The key (length %d) is:\n", key_length);
993 print_char(key, key_length);
994 print_byte(key, key_length);
995 printf("\n");
996
997 /* get plain text */
998 fplaintext = fopen("message.txt", "r");
999 index = 0;
1000
1001 /* get message length */
1002 fseek(fplaintext, 0L, SEEK_END);
1003 pt_length = ftell(fplaintext) - 1;
1004 rewind(fplaintext);
1005 pt = calloc(pt_length, sizeof(byte));
1006
1007 /* get message from file */
1008 while (index < pt_length && fscanf(fplaintext, "%c", pt + index) != EOF) {
1009 ++index;
1010 }
1011
1012 fclose(fplaintext);
1013
1014 printf("The message (length %d) before encryption is:\n", pt_length);
1015 print_char(pt, pt_length);
1016 printf("\n");
1017
1018 /* encrypte the nessage */
1019 ct = encrypt(pt, pt_length, key, key_length);
1020
1021 printf("The cihertext (length %d) is:\n", pt_length + IV_LENGTH);
1022 print_byte(ct, pt_length + IV_LENGTH);
1023 printf("\n");
1024
1025 /* decrypt the message */
1026 res = decrypt(ct, pt_length + IV_LENGTH, key, key_length);
1027
1028 printf("The message after decryption is:\n");
1029 print_char(res, pt_length);
1030 printf("\n");
1031
1032 /* Clean up */
1033 free(key);
1034 free(ct);
1035 free(pt);
1036 free(res);
1037
1038 return 1;
1039}
1040\end{lstlisting}
1041
1042
1043
1044
1045\end{document}