diff options
Diffstat (limited to 'Assignment3')
| -rwxr-xr-x | Assignment3/2des-demo.py | 74 | ||||
| -rw-r--r-- | Assignment3/CamilStaps-assignment3.tex | 219 | ||||
| -rw-r--r-- | Assignment3/LICENSE | 1 | ||||
| -rw-r--r-- | Assignment3/Readme.md | 103 | ||||
| -rwxr-xr-x | Assignment3/break.py | 141 | ||||
| -rwxr-xr-x | Assignment3/des-demo.py | 62 | ||||
| -rwxr-xr-x | Assignment3/des-test.sh | 22 | ||||
| -rwxr-xr-x | Assignment3/nthkey.py | 37 |
8 files changed, 659 insertions, 0 deletions
diff --git a/Assignment3/2des-demo.py b/Assignment3/2des-demo.py new file mode 100755 index 0000000..b5b7247 --- /dev/null +++ b/Assignment3/2des-demo.py @@ -0,0 +1,74 @@ +#!/usr/bin/python +import sys, getopt, binascii, random +from Crypto.Cipher import DES + +# From http://stackoverflow.com/a/843846/1544337 +# 1 for odd parity, 0 for even parity +# Was used only in a previous version of nthByte +# def parity(b): +# c = 0 +# while b != 0: +# c += 1 +# b &= b - 1 +# return c % 2 + +# Find the nth possibility for a byte with odd parity +oddBytes = [1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,50,52,55,56,59,61,62,64,67,69,70,73,74,76,79,81,82,84,87,88,91,93,94,97,98,100,103,104,107,109,110,112,115,117,118,121,122,124,127,128,131,133,134,137,138,140,143,145,146,148,151,152,155,157,158,161,162,164,167,168,171,173,174,176,179,181,182,185,186,188,191,193,194,196,199,200,203,205,206,208,211,213,214,217,218,220,223,224,227,229,230,233,234,236,239,241,242,244,247,248,251,253,254] +def nthByte(n): + return oddBytes[n] + # c = -1 # This is the old version. The new version uses a faster lookup table. + # b = 0 + # while c != n: + # b += 1 + # if parity(b) == 1: + # c += 1 + # return b + +# Find the nth key in which all bytes have odd parity +def nthKey(n): + key = '' + for b in range(7,-1,-1): + key += chr(nthByte((n >> b*7) & 0x7f)) + return key + +def main(argv): + l = 24 + + # Parse arguments. Use -h for help. + try: + opts, args = getopt.getopt(argv, "hl:") + except getopt.GetoptError: + usage() + sys.exit(2) + + for opt, arg in opts: + if opt == '-h': + usage() + sys.exit() + elif opt == '-l': + l = int(arg) + + # generate two keys + r = random.SystemRandom() + k1 = nthKey(r.randint(0, pow(2, l) - 1)) + k2 = nthKey(r.randint(0, pow(2, l) - 1)) + + print 'k_1: %s' % binascii.b2a_hex(k1) + print 'k_2: %s' % binascii.b2a_hex(k2) + + round1 = DES.new(k1, DES.MODE_ECB) + round2 = DES.new(k2, DES.MODE_ECB) + + # Some random plaintext - ciphertext pairs to verify the working of this code + print 'plaintext : ciphertext' + for n in range(0,10): + pt = '{:016x}'.format(r.randint(0, pow(2, 64) -1)) + ct = round2.encrypt(round1.encrypt(binascii.a2b_hex(pt))) + print pt + ' : ' + binascii.b2a_hex(ct) + +def usage(): + print 'Usage: 2des-demo.py [-l <keylength>]' + print ' keylength : pick keys from the first 2^l keys (default: 24)' + +if __name__ == "__main__": + main(sys.argv[1:])
\ No newline at end of file diff --git a/Assignment3/CamilStaps-assignment3.tex b/Assignment3/CamilStaps-assignment3.tex new file mode 100644 index 0000000..da7d433 --- /dev/null +++ b/Assignment3/CamilStaps-assignment3.tex @@ -0,0 +1,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} diff --git a/Assignment3/LICENSE b/Assignment3/LICENSE new file mode 100644 index 0000000..7de325f --- /dev/null +++ b/Assignment3/LICENSE @@ -0,0 +1 @@ +Copyright (c) 2015 Camil Staps <info@camilstaps.nl>
\ No newline at end of file diff --git a/Assignment3/Readme.md b/Assignment3/Readme.md new file mode 100644 index 0000000..c7ac538 --- /dev/null +++ b/Assignment3/Readme.md @@ -0,0 +1,103 @@ +# Breaking DES with Python +Solutions to the third homework assignment for the NWI-IBC023 Cryptography course, spring 2015, Radboud University Nijmegen. + +See the LICENSE file for the license & copyright information. + +## Dependencies +Python 2.7.6 (other versions may work) with libraries: Crypto, sys, getopt, os.path, binascii, random, time + +## Files + +### des-demo.py (exercise i) +Encrypt or decrypt a specified message using a specified key with DES. See `des-demo.py -h` for usage. + +### des-test.sh +Test des-demo.py using the test vectors from the assignment. + +### nthkey.py (exercise ii) +Demonstration of the working of the `nthKey(n)` method. No command line parameters, edit the number on the last line for another `n`. + +### 2des-demo.py (exercise iii) +2DES using two random keys: chooses two random keys with the right parity using `nthKey(n)`, then performs 2DES on ten random plaintexts using those keys. See `2des-demo.py -h` for usage. + +### break.py (exercise iv) +Breaking 2DES using a known-plaintext attack. Supply at least a plaintext (`-p`) and a ciphertext (`-c`), possibly also a keylength (`-l`). There is an option to save the dictionary to a file (`-s`) if you're planning to reuse it. + +There is detailed timing information for the second stage of the attack: the time used by `nthKey()`, `DES.decrypt()` and finding values in the dictionary. + +Example: + + $ ./break.py -p 6be6065663da8d2c -c 4d0ed7812caeee83 -l 16 + Making dictionary (p:6be6065663da8d2c;l:16)... 1.429026s + Finding matches... 1.618808s + Key generation: 0.403714s + Decryption: 1.048049s + Matching dictionary: 0.046321s + k1: 0101010101011afb; k2: 0101010101012073 + +## Concrete break +I was given the following plaintext-ciphertext pairs: + + 0123456789ABCDEF e0ac28c346fb8de5 + 1122334455667788 49e4857e94f9655d + 99aabbccddeeff00 b5a2eefb51b04401 + +Breaking these (on the Lenovo described under Benchmarks): + + $ ./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 + $ ./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 + +We find k1 = `0101010101164613`; k2 = `0101010102a719c2`. + +## Benchmarks + +### Lenovo U410, i7-3517U @ 1.9GHz, 8GB RAM, 16GB /swap, Ubuntu 14.04 +Creating dictionary: 417.5s, 386.5s, 394.5s (**avg: 399.5s**) +Finding matches: 419.1s, 424.9s, 431.6s (**avg: 425.2s**) + +The exact log is in the Concrete Break section above. + +### Lilo +Creating dictionary: 286.8s, 283.6s, 273.0s (**avg: 281.1s**) +Finding matches: 301.6s, 285.6s, 292.2s (**avg: 293.1s**) + + $ ./break.py -p 0123456789ABCDEF -c e0ac28c346fb8de5 -l 24 + Making dictionary (p:0123456789abcdef;l:24)... 286.83s + Finding matches... 301.56s + Key generation: 64.47s + Decryption: 200.23s + Matching dictionary: 9.27s + k1: 0101010101164613; k2: 0101010102a719c2 + $ ./break.py -p 1122334455667788 -c 49e4857e94f9655d -l 24 + Making dictionary (p:1122334455667788;l:24)... 283.55s + Finding matches... 285.63s + Key generation: 60.66s + Decryption: 189.44s + Matching dictionary: 9.27s + k1: 0101010101164613; k2: 0101010102a719c2 + $ ./break.py -p 99aabbccddeeff00 -c b5a2eefb51b04401 -l 24 + Making dictionary (p:99aabbccddeeff00;l:24)... 272.96s + Finding matches... 292.21s + Key generation: 63.89s + Decryption: 191.04s + Matching dictionary: 9.41s + k1: 0101010101164613; k2: 0101010102a719c2
\ No newline at end of file diff --git a/Assignment3/break.py b/Assignment3/break.py new file mode 100755 index 0000000..7666d33 --- /dev/null +++ b/Assignment3/break.py @@ -0,0 +1,141 @@ +#!/usr/bin/python +import sys, getopt, binascii, random, time, os.path, time +from Crypto.Cipher import DES + +dictionary = {} + +# From http://stackoverflow.com/a/843846/1544337 +# 1 for odd parity, 0 for even parity +# Was used only in a previous version of nthByte +# def parity(b): +# c = 0 +# while b != 0: +# c += 1 +# b &= b - 1 +# return c % 2 + +# Find the nth possibility for a byte with odd parity +oddBytes = [1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,50,52,55,56,59,61,62,64,67,69,70,73,74,76,79,81,82,84,87,88,91,93,94,97,98,100,103,104,107,109,110,112,115,117,118,121,122,124,127,128,131,133,134,137,138,140,143,145,146,148,151,152,155,157,158,161,162,164,167,168,171,173,174,176,179,181,182,185,186,188,191,193,194,196,199,200,203,205,206,208,211,213,214,217,218,220,223,224,227,229,230,233,234,236,239,241,242,244,247,248,251,253,254] +def nthByte(n): + return oddBytes[n] + # c = -1 # This is the old version. The new version uses a faster lookup table. + # b = 0 + # while c != n: + # b += 1 + # if parity(b) == 1: + # c += 1 + # return b + +# Find the nth key in which all bytes have odd parity +def nthKey(n): + key = '' + for b in range(7,-1,-1): + key += chr(nthByte((n >> b*7) & 0x7f)) + return key + +# Create a dictionary for the first 2^l keys and a given plaintext +def createDictionary(plaintext, l): + for n in range(0, pow(2, l)): + encryption = DES.new(nthKey(n), DES.MODE_ECB).encrypt(plaintext) + if encryption in dictionary: + dictionary[encryption].append(n) + else: + dictionary[encryption] = [n] + +# Read the dictionary from a file if it exists, or generate it +def readOrMakeDictionary(plaintext, l): + if os.path.isfile('dict-' + binascii.b2a_hex(plaintext) + '-' + str(l) + '.txt'): + with open('dict-' + binascii.b2a_hex(plaintext) + '-' + str(l) + '.txt') as f: + for line in f: + dictionary[binascii.a2b_hex(line[:16])] = [int(x) for x in line[17:-1].split(',')] + return False + else: + createDictionary(plaintext, l) + return True + +# Save the dictionary to a file +def saveDictionary(plaintext, l): + dictionary_file = open('dict-' + binascii.b2a_hex(plaintext) + '-' + str(l) + '.txt', 'w') + for encryption in dictionary: + dictionary_file.write(binascii.b2a_hex(encryption) + ':' + ','.join(str(x) for x in dictionary[encryption]) + '\n') + print 'Saved dictionary as dict-' + binascii.b2a_hex(plaintext) + '-' + str(l) + '.txt' + +def main(argv): + l = 24 + plaintext = '' + ciphertext = '' + save_dictionary = False + + # Parse arguments. Use -h for help. + try: + opts, args = getopt.getopt(argv, "hl:p:c:s") + except getopt.GetoptError: + usage() + sys.exit(2) + + for opt, arg in opts: + if opt == '-h': + usage() + sys.exit() + elif opt == '-l': + l = int(arg) + elif opt == '-p': + plaintext = binascii.a2b_hex(arg) + elif opt == '-c': + ciphertext = binascii.a2b_hex(arg) + elif opt == '-s': + save_dictionary = True + + assert plaintext != '' + assert ciphertext != '' + + # Make the dictionary if it doesn't exist yet + print 'Making dictionary (p:' + binascii.b2a_hex(plaintext) + ';l:' + str(l) + ')...', + timer = time.clock() + if not readOrMakeDictionary(plaintext, l): + save_dictionary = False + print str(time.clock() - timer) + 's' + + if save_dictionary: + saveDictionary(plaintext, l) + + # Find matches + print 'Finding matches...', + timer = time.clock() + time_key = time_decryption = time_matching = 0 + matches = [] + for k in range(0, pow(2,l)): + # Generate key + time_t = time.clock() + key = nthKey(k) + time_key += time.clock() - time_t + + # Decrypt + time_t = time.clock() + des = DES.new(key, DES.MODE_ECB) + decryption = des.decrypt(ciphertext) + time_decryption += time.clock() - time_t + + # Find matches + time_t = time.clock() + if decryption in dictionary: + [matches.append({'k1': nthKey(i), 'k2': key}) for i in dictionary[decryption]] + time_matching += time.clock() - time_t + print str(time.clock() - timer) + 's' + + print 'Key generation: ' + str(time_key) + 's' + print 'Decryption: ' + str(time_decryption) + 's' + print 'Matching dictionary: ' + str(time_matching) + 's' + + for match in matches: + print 'k1: ' + binascii.b2a_hex(match['k1']) + '; k2: ' + binascii.b2a_hex(match['k2']) + +def usage(): + print 'Usage: break.py -p <plaintext> -c <ciphertext> [-l <keylength>] [-s]' + print ' plaintext : plaintext of the known-plaintext attack' + print ' ciphertext : ciphertext of the known-plaintext attack' + print ' keylength : pick keys from the first 2^l keys (default: 24)' + print ' -s : save the dictionary for this plaintext and keylength to a file' + +if __name__ == "__main__": + main(sys.argv[1:])
\ No newline at end of file diff --git a/Assignment3/des-demo.py b/Assignment3/des-demo.py new file mode 100755 index 0000000..0a4954f --- /dev/null +++ b/Assignment3/des-demo.py @@ -0,0 +1,62 @@ +#!/usr/bin/python + +# Copyright (c) 2015 Camil Staps <info@camilstaps.nl> + +import sys, getopt, binascii +from Crypto.Cipher import DES + +def main(argv): + key = '' + plaintext = '' + ciphertext = '' + + # Parse arguments. Use -h for help. + try: + opts, args = getopt.getopt(argv, "hk:p:c:", ["key=","plaintext=","ciphertext="]) + except getopt.GetoptError: + usage() + sys.exit(2) + + for opt, arg in opts: + if opt == '-h': + usage() + sys.exit() + elif opt in ("-k", "--key"): + key = binascii.a2b_hex(arg) + elif opt in ("-p", "--plaintext"): + plaintext = binascii.a2b_hex(arg) + elif opt in ("-c", "--ciphertext"): + ciphertext = binascii.a2b_hex(arg) + + if key == '' or plaintext == '' and ciphertext == '': + usage() + sys.exit(2) + + # PyCrypto does the hard work + cipher = DES.new(key, DES.MODE_ECB) + + encryption = '' + decryption = '' + + if plaintext != '': + encryption = cipher.encrypt(plaintext) + if ciphertext != '': + decryption = cipher.decrypt(ciphertext) + + # When plaintext and ciphertext are provided, output if DES[k](p) = c. Otherwise, output the encryption / decryption. + if encryption != '' and decryption != '': + print encryption == ciphertext + elif encryption != '': + print binascii.b2a_hex(encryption) + elif decryption != '': + print binascii.b2a_hex(decryption) + +def usage(): + print 'Usage: des-demo.py -k <key> [-p <plaintext>] [-c <ciphertext>]' + print ' key : an 8-byte value entered as hexadecimal numbers' + print ' plaintext : an 8-byte value entered as hexadecimal numbers' + print ' ciphertext : an 8-byte value entered as hexadecimal numbers' + print 'At least one of plaintext and ciphertext should be provided. When both are provided, we check if DES[k](p) = c.' + +if __name__ == "__main__": + main(sys.argv[1:]) diff --git a/Assignment3/des-test.sh b/Assignment3/des-test.sh new file mode 100755 index 0000000..15a5402 --- /dev/null +++ b/Assignment3/des-test.sh @@ -0,0 +1,22 @@ +#!/bin/sh + +echo "Testing encryption:" +./des-demo.py -k 133457799BBCDFF1 -p 0123456789abcdef +./des-demo.py -k 752878397493CB70 -p 1122334455667788 +./des-demo.py -k 752878397493CB70 -p 99AABBCCDDEEFF00 +./des-demo.py -k 5B5A57676A56676E -p 675A69675E5A6B5A +./des-demo.py -k 0101010101010102 -p 0102030405060708 + +echo "Testing decryption:" +./des-demo.py -k 133457799BBCDFF1 -c 85E813540F0AB405 +./des-demo.py -k 752878397493CB70 -c B5219EE81AA7499D +./des-demo.py -k 752878397493CB70 -c 2196687E13973856 +./des-demo.py -k 5B5A57676A56676E -c 974AFFBF86022D1F +./des-demo.py -k 0101010101010102 -c 6613fc98d6d2f56b + +echo "Testing comparison:" +./des-demo.py -k 133457799BBCDFF1 -p 0123456789abcdef -c 85E813540F0AB405 +./des-demo.py -k 752878397493CB70 -p 1122334455667788 -c B5219EE81AA7499D +./des-demo.py -k 752878397493CB70 -p 99AABBCCDDEEFF00 -c 2196687E13973856 +./des-demo.py -k 5B5A57676A56676E -p 675A69675E5A6B5A -c 974AFFBF86022D1F +./des-demo.py -k 0101010101010102 -p 0102030405060708 -c 6613fc98d6d2f56b
\ No newline at end of file diff --git a/Assignment3/nthkey.py b/Assignment3/nthkey.py new file mode 100755 index 0000000..40cf0cf --- /dev/null +++ b/Assignment3/nthkey.py @@ -0,0 +1,37 @@ +#!/usr/bin/python + +# Copyright (c) 2015 Camil Staps <info@camilstaps.nl> + +import binascii + +# From http://stackoverflow.com/a/843846/1544337 +# 1 for odd parity, 0 for even parity +# Was used only in a previous version of nthByte +# def parity(b): +# c = 0 +# while b != 0: +# c += 1 +# b &= b - 1 +# return c % 2 + +# Find the nth possibility for a byte with odd parity +oddBytes = [1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,50,52,55,56,59,61,62,64,67,69,70,73,74,76,79,81,82,84,87,88,91,93,94,97,98,100,103,104,107,109,110,112,115,117,118,121,122,124,127,128,131,133,134,137,138,140,143,145,146,148,151,152,155,157,158,161,162,164,167,168,171,173,174,176,179,181,182,185,186,188,191,193,194,196,199,200,203,205,206,208,211,213,214,217,218,220,223,224,227,229,230,233,234,236,239,241,242,244,247,248,251,253,254] +def nthByte(n): + return oddBytes[n] + # c = -1 # This is the old version. The new version uses a faster lookup table. + # b = 0 + # while c != n: + # b += 1 + # if parity(b) == 1: + # c += 1 + # return b + +# Find the nth key in which all bytes have odd parity +def nthKey(n): + key = '' + for b in range(7,-1,-1): + key += chr(nthByte((n >> b*7) & 0x7f)) + return key + +# Example +print binascii.b2a_hex(nthKey(765637))
\ No newline at end of file |