Course F21CN: Computer Network Security

Exercises for F21CN: Computer Network Security

This page summarises lab exercises for the course F21CN Computer Network Security. If you are looking for coursework on that course, which is mandatory, follow this link.

Cryptography

The primary goal of the following exercises is to deepen your understanding on basic cyptography, by running concrete examples, using the GHCi interpreter, which is installed on all lab machines. The first part uses a symmetric key cipher, they give you an opportunity to test a simple Caesar cipher and to perform a statistical attack that is strong enough to crack most ciphertexts. Using a public-key cipher, they give you an opportunity to step through the parts of RSA key generation, encryption and decryption. These examples use GHCi, an interpreter for the programming language Haskell. You don't have to know Haskell to run the examples, though: just cut-and-paste the examples marked in the code. These examples show how to use variables (let), how to perform basic arithmetic (eg. on modular domains), and how to call basic functions of number theory. This should be sufficient background to answer the questions embedded in the source code, which comprise this set of exercises. If you need more help with ghci, check out this getting started with ghci chapter of an on-line, introductory book on Haskell.

Installation and Setup

GHCi is installed on the Linux lab machines. You can download a version (Linux/Windows/etc) from this web page. In any case, your should run the install script below to install additional packages. If you use your laptop, you can download the packages separately (and adjust the paths in f21cn.sh accordingly): HaskellForMaths-0.4.5, QuickCheck-2.4.1.1.

Before you run the exercises you need to install some additional packages. This process is automated in a shell script (f21cn.sh) for this course. (Side remark: this is a typical, small Linux shell script, covering software installation, and you might want to take a closer look as part of the Linux introduction.) Now, do the following:

 wget http://www.macs.hw.ac.uk/~hwloidl/Courses/F21CN/Labs/f21cn.sh
 source f21cn.sh
 f21cn_install_ghc_pkgs

Installation is successful, if you see these lines at the end:

   You should now find 'QuickCheck' and 'HaskellForMaths' in the list below:
    QuickCheck-2.4.1.1
    HaskellForMaths-0.4.5

You should have a file caesar.hs in your directory. If not, you can download caesar.hs separately like this

   wget http://www.macs.hw.ac.uk/~hwloidl/Courses/F21CN/Labs/CryptoI/caesar.hs

See the appendix for a complete log of the commands and replies when installing the software.

Exercise 1: Caesar cipher

Now, start the caesar.hs program like this, using the GHCi interpreter, decrypting and cracking some sample text:

  ghci -package HaskellForMaths -package QuickCheck caesar.hs

and do your own examples of encrypting, for example by assigning some text to a variable s0, encode this text using a shift factor of 5 (encode 5), and then trying to crack the encrypted text (crack):

*Caesar> let s0 = "a simple test"
*Caesar> let c0 = encode 5 s0
Loading package haskell98 ... linking ... done.
*Caesar> c0
"f xnruqj yjxy"
*Caesar> crack c0
"a simple test"
*Caesar> s0==(crack c0)
True

You can see, that the cracking, which doesn't know the key and simple tries all possible shifts, was successful.

What is the fundamental weakness in the Caesar cipher, that allows for such a simple approach to cracking?

Now, launch an editor and load caesar.hs into the editor. You should now see the implementation of the Caesar cipher, which is in Haskell. Don't worry if you don't understand the program code itself, it should mainly give you an idea about how small the implementation of encrypting, decrypting and even cracking is.

The examples in this file show how to use variables (let), how to perform basic arithmetic (eg. on modular domains), and how to call basic functions of number theory. This should be sufficient background to answer the questions embedded in the source code, which comprise this set of exercises. Now, go through this file and test code snippets, by cut-and-paste of lines starting with

-- #>

which represents the GHCi prompt. Copy everything after this prompt, paste it into your terminal running ghci and observe the results. Then, play around by slightly modifying the examples, for example use text with an unusual frequency of characters, encrypt it and try to crack it.

Do all examples up to the line Vernam cipher. Then as a final example, take the following text, first in its English (cut-and-paste the entire line)

If he had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out. If anyone wishes to decipher these, and get at their meaning, he must substitute the fourth letter of the alphabet, namely D, for A, and so with the others --- Suetonius, Life of Julius Caesar 56

then in its Latin version (cut-and-paste the entire line)

si qua occultius perferenda erant, per notas scripsit, id est sic structo litterarum ordine, ut nullum verbum effici posset; quae si qui investigare et persequi velit, quartam elementorum litteram, id est D pro A et perinde reliquas commutet --- Suetonius, Julius Caesar 56

Do the same sequence of encrypting, cracking and checking for equality as above.

What can you conclude about the language-dependence of the attack against the Caesar cipher?

Appendix: Sample execution

Here is a complete example of download, installation, and test session, run on one of the Linux lab machines (complete trace of the execution).

Download

linux03[156](3.2)> wget -q http://www.macs.hw.ac.uk/~hwloidl/Courses/F21CN/Labs/f21cn.sh

Installation

linux03[157](3.2)> source f21cn.sh
linux03[158](3.2)> install_ghc_pkgs 
Installing GHC packages 'QuickCheck' and 'HaskellForMaths' ...
~ ~/Workspace
~/f21cn/HaskellForMaths-0.1.9 ~/f21cn ~/Workspace
Configuring HaskellForMaths-0.1.9...
Preprocessing library HaskellForMaths-0.1.9...
Building HaskellForMaths-0.1.9...
[ 1 of 28] Compiling Math.Algebra.Group.StringRewriting
...
Registering HaskellForMaths-0.1.9...
Installing library in
/u1/staff/hwloidl/.cabal/lib/HaskellForMaths-0.1.9/ghc-6.12.3
Registering HaskellForMaths-0.1.9...
~/f21cn ~/Workspace
~/f21cn/QuickCheck-2.4.1.1 ~/f21cn ~/Workspace
Configuring QuickCheck-2.4.1.1...
Preprocessing library QuickCheck-2.4.1.1...
Building QuickCheck-2.4.1.1...
[ 1 of 13] Compiling Test.QuickCheck.Exception
...
Registering QuickCheck-2.4.1.1...
Installing library in
/u1/staff/hwloidl/.cabal/lib/QuickCheck-2.4.1.1/ghc-6.12.3
Registering QuickCheck-2.4.1.1...
~/f21cn ~/Workspace
You should now find 'QuickCheck' and 'HaskellForMaths' in the list below:
    QuickCheck-2.4.1.1
    HaskellForMaths-0.1.9
~/Workspace
The exercises are in file caesar.hs: -rw-rw-r-- 1 hwloidl staff 8752 Sep 22 20:49 caesar.hs

Exercises: Caesar cipher

linux03[159](3.2)> ghci -package HaskellForMaths -package QuickCheck caesar.hs
GHCi, version 6.12.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
...
[1 of 1] Compiling Caesar           ( caesar.hs, interpreted )
Ok, modules loaded: Caesar.

Exercises 2: Modular arithmetic


*Caesar> putStrLn (showtab 5)
    0 1 2 3 4
 0: 0 0 0 0 0
 1: 0 1 2 3 4
 2: 0 2 4 1 3
 3: 0 3 1 4 2
 4: 0 4 3 2 1
 
*Caesar> let x = (3 :: F5)
*Caesar> let z = x^2 + 2*x + 1
*Caesar> let zz = (x+1)^2
*Caesar> x
3
*Caesar> z
1
*Caesar> zz
1

Exercises: Euler's Theorem


*Caesar> quickCheck (\ m n -> m<2 || n<2 || not (gcd m n == 1) || m^(euler n) `mod` n == 1)
+++ OK, passed 100 tests.

Exercises: RSA


*Caesar> let p = primes!!17
*Caesar> let q = primes!!19
*Caesar> let n = p*q
*Caesar> p
61
*Caesar> q
71
*Caesar> n
4331
*Caesar> let phi = (p-1)*(q-1)
*Caesar> factors phi
[2,3,5,7]
*Caesar> let e = 11
*Caesar> gcd e phi
1
*Caesar> let d = mod_inv phi e
*Caesar> d
2291
*Caesar> e*d `mod` phi
1
*Caesar> let enc m = m^e `mod` n
*Caesar> let dec c = c^d `mod` n
*Caesar> let m = 314
*Caesar> let c = enc m
*Caesar> c
1168
*Caesar> dec c
314

*Caesar> quickCheck (\ m -> dec (enc (abs m)) == (abs m))
+++ OK, passed 100 tests.

File-system Encryption

The lab sheet on file-system encryption is available here. Follow the instructions on the lab sheet to do the exercises.

Use the partition manager of your laptop to set up 2 partitions on your USB stick: you might need admin privileges to do this step. Under Linux, you can use the fdisk command, and give the device name as argument.

For Task 2 you need to add the user, running TrueCrypt, to a list of privileged users, the so called sudoers list. As root add a file sudoers_local into the directory /etc/sudoers.d and put a line like this into this file

hwloidl  ALL=/tmp/usr/bin/truecrypt

(replace hwloidl by your username, and adjust the path if you installed truecrypt somewhere else). Make sure to set this file to read-only, i.e.

chmod 0440 sudoers_local

Now, you should be able to mount the encrypted volume that you have created in the previous step.

Exercises F21CN: Computer Network Security