Key: B Bookwork; a Similar to Exercise Or Test Question; S Seen in Lecture; U Unseen

CIS326 2004SOLUTIONS

Key: B bookwork; A similar to exercise or test question; S seen in lecture; U unseen

Note that B questions are generally intelligent application or extraction of information rather than direct repetition of the studyguide.

SECTION A

Question 1

To prevent burglary of a physical item we could lock it away where no-one can get near it, but locking up a computer does not necessarily mean that no-one can access it. If a physical item is stolen, then we would detect the theft by seeing that the item is missing, however digital information can be stolen by copying so that the original information is still present. We might not detect that there has been a theft. If a physical item is stolen, then one reaction is to replace the item, but if data is stolen by copying, then the original owner will also still have it. Police might catch a burglar “red-handed” but people committing theft of digital information might be no-where near the scene of the crime.

( 2 marks for each traditional method plus reason why it is not appropriate) [B]

Question 2

a ) i. Authentication : proving that you are who you say you are. [ ½ B]

ii. Access Control : determining which users have permission to enter (different parts of) the system are granting only those users access (when authenticated) [ ½ B]

b)i. The attacker tries passwords with a particular relevance to the user such as names, birthdays etc [ ½ B]

ii.The attacker tries all the words in a dictionary [ ½ B]

iii. The attacker tries every possible password in turn until the correct password is found [1 B]

c)It would be best to try an intelligent search if you were trying to find the password of a particular person and you know that person. For example if a company employee is trying to discover the password of another employee. [1 U]

You could use a dictionary search if you were trying to find the password of any user of the system rather than a particular user. It is likely that at least some of the system users will have used dictionary words as their password. [1 U]

You could use an exhaustive search if a dictionary search failed. This would be the most appropriate type of search in the case that passwords were forced not to be dictionary words eg. If the passwords were a list of digits then an exhaustive search would be used. [1 U]

Question 3

a) There are 26*26*26*10*10*10 = 17576000 possible passwords [2 A]

b) On average you would have to try ½ the passwords = 17576000 / 2 = 8788000 [1 A]

This would take 8788000 / 10000 = 8788 minutes = 8788 / 60 = 14.6

Answer is 15 hours [2 A]

c) Now it takes 15*10 = 150 hours or 14.6 * 10 = 146 hours (accept either) [1 U]

Question 4

a) In a symmetric cryptosystem, the decryption key can be easily deduced from the encryption key so anyone who knows the encryption key can decrypt the ciphertext [1 B]

b)The message is split up into blocks before encryption. The blocksize is the number of binary bits in each block. [1 B]

The keyspace is the set of all possible keys which can be used with the cryptosystem [1 B]

c)If the blocksize is too small, an attacker can perform statistical tests to recover the message [1 B]

d)Rijndael is more flexible because it has different key lengths ; Rijndael requires less memory so is suitable for implementation in hardware as well as software. [1 B for any sensible advantage]

Rijndael is new so not as well studied and tested as Triple DES. [1 B for any sensible disadvantage]

Question 5

a)We need to know that some tasks such as factorisation cannot be performed efficiently since the security of certain cryptographic protocols lies in the fact that the task cannot be performed. We need to know that other tasks such as exponentiation can be performed efficiently since otherwise certain cryptographic protocols would be too slow to be practical. [2 U]

b)When cryptographically protecting a password file it is best to use an inefficient one way function. [1 B]

c)The numbers are ½ as big, so the time takes (1/2)2 = ¼ as long = 2s [3 A]

Question 6

a)Given prime p, generator g and integer y find integer x such that y = gx mod p [2 B]

b)Key generation in El Gamel:

Bob generates a large random prime number p [½ B]
He determines a number g which is a generator for p [½ B]
He picks a random number a with 1 < a < p-1 [½ B]
He computes y = ga mod p [½ B]
The public key are the values of p, g and y [1 B]
Bob’s private key is the value of a [1 B]

Question 7

a) Bob takes the following steps to recover the message

Bob receives the values of k’ and c [ ½ A]
Bob decrypts k’ [ ½ A] using his private key [ ½ A] and public key cryptosystem to obtain k [½ A]
Bob decrypts the ciphertext c [ ½ A] using the session key k [ ½ A] and the symmetric cryptosystem to obtain m [ ½ A] + [ ½ A] for doing steps in correct order.

PGP uses public key cryptography to exchange a symmetric session key. It uses symmetric cryptography to encrypt the message because it is more efficient than public key cryptography. [2 U]

Question 8

a)A key escrow protocol can be used to recover a secret key in an emergency if the key holder is not available because for example he/she has died or has been sacked from the company [1 B]

b)A different key part is given to n different people. Any t of the n people have to work together to recover the original key [1 B]

c)Assume that K is a binary string of length n bits. The first two key parts X and Y are random binary strings also of length n bits. The third key part Z is generated by XORing K, X and Y

So that Z = K  X  Y [2 B]

d) K = X  Y = 10011101  11011000 = 01000101 [1 A]

e) An “n of n” protocol might not be practical since it relies on all of the key holders working together. If one of these key holders is not available (for example they might have died in the same accident as killed the original key holder) then the original key cannot be recovered. [1 U]

SECTION B

Question 1

a)i. Subjects: Mrs A, Dr B, Dr C, Dr D, Prof H [1 mark for each complete list,

Objects: salary.doc, timetable.doc, marks.doc ½ mark for incomplete list A]

Operations: read, write

ii. The three lecturers could be put into a group since they all have the same permissions [1 A]

iii. [4 A]

salary.doc / timetable.doc / marks.doc
Mrs A / {r} / {w,r} / {}
Lecturers / {} / {r} / {w,r}
Prof H / {w,r} / {r} / {r}

b)When the security levels are strictly hierarchical [1 B]]

c) West [2 A]e) [2 A]

d)Graphs can be used to represent security levels by labelling each vertice with a security label and drawing an edge from one vertex to another if the first is at a higher level than the second. Or the vertices can represent subjects and objects and an edge, or an indirect path, from a subject to an object (or another subject) shows that the subject has access to the object [4 B]

e)i. There are nine security levels [1 A]

ii. [4 A] (West and East essentially the same with different labels)

iii. (C,{i}) and (U,{i})[2 A one mark for each]

iv.This graph is not a lattice[1 S] because nothing is dominated by both (U,{n}) and (U,{i}) [1S]

Question 2

a)The basis of the protocol is the discrete log problem. Alice and Bob agree on a large prime number p and a generator g mod p. Then Alice chooses a secret random key a and Bob chooses a secret random key b. Alice computes x = ga mod p and sends the value of x to Bob. Meanwhile, Bob computes y = gb mod p and sends the value of y to Alice. Alice then computes k = ya mod p and Bob computes k = xb mod p. The two values of k are equal because k = xb = (ga)b = (gb)a = ya = k mod p. If someone intercepts the values of x or y, they cannot recover the value of k unless they can solve a DLP. [4 B]

b)West

Alice computes x = 25 mod 19 = 13 ; Bob computes y = 28 mod 19 = 9;

Alice sends 13 to Bob and Bob sends 9 to Alice.

Alice computes k = 95 mod 19 = 16; Bob computes k = 138 mod 19 = 16. [4 A]

c)Although Charles cannot find the value of k by intercepting x and y, he could perform a man-in-the middle attack by intercepting these values and then sending other values to Alice and Bob.

First of all Charles computes z = gc mod p. Alice thinks she is sending the value of x to Bob and Bob thinks that he is sending the value of y to Alice but Charles intercepts these messages and instead sends the value of z to both Alice and Bob in place of x and y. Now Alice computes

k1 = za mod p and Charles computes k1 = xc mod p. Also Bob computes k2 = zb mod p and Charles computes k2 = yc mod p. Alice and Bob think that they are sharing a common key and communicating with each other. In fact Alice is sending messages to Charles using key k1 and Bob is sending messages to Charles using key k2. Charles can decrypt a message from Alice using key k1 and then alter it, encrypt it again using key k2 and then send it to Bob who will decrypt it thinking that the message has come from Alice. [upto 5 S for description]

Alice computes x = 25 mod 19 = 13 ; Bob computes y = 28 mod 19 = 9;

Alice sends 13 to Bob and Bob sends 9 to Alice.

Charles computes z = 23 mod 19 = 8 and intercepts x = 13 and y = 9;

Charles sends Alice the value 8 and Bob the value 8

Alice computes k1 = 85 mod 19 = 12

Bob computes k2 = 88 mod 19 = 7

Charles computes k1 = 133 mod 19 = 12 and k2 = 93 mod 19 = 7 [upto 5 S for example]

d)The Needham-Schroeder Protocol is a way of exchanging a session key without using public key cryptography but instead using a server [1 B]

Alice and the server have an established symmetric key KAS and Bob and the server have an established symmetric key KBS. If Alice wants to send Bob a message she needs to obtain a session key KAB as follows:

Alice sends the names of Alice and Bob to the server – this is essentially a request for the server to generate session key KAB
The server sends, all encrypted using KAS, Alice:

the name of Bob
KAB
The name of Alice and KAB all encrypted using Bobs key KB

Alice decrypts the items sent in step 2 using KAS then she has the value of the session key KAB. Alice sends Bob the name of Alice and KAB encrypted with KBS sent to her in step 2c) above.
Bob decrypts the name of Alice and the session key using KBS. Now both Alice and Bob know the value of the session key KAB and can communicate directly with each other.

[7B marks for the description. They can use a symbolic protocol but only award full marks if this is suitably explained]

Question 3

a)RSA Key Generation

Bob generates two large primes p and q
He computes n = p*q and r = (p-1)*(q-1)
He chooses a key e at random such that e is less than r and co-prime with r
He finds d, the inverse of e mod r
He carefully discards the values of p, q and r
He keeps the key d private and publishes his public key (n and e)

RSA Encryption

If Alice wants to send Bob a message, she looks up Bob’s public key (n,e). Then she breaks the message up into blocks of the correct size and them for each block m she computes ciphertext c = me mod n. Alice sends Bob the value of c

RSA Decryption

Bob receives the ciphertext block c from Alice. He computes m = cd mod n where d is his private key. This works because

cd = (me)d = me*d = m1 mod r = m mod n

The security of the RSA cryptosystem is based on the difficulty of the factorisation problem.

RSA is secure because only Bob knows his private key d. Although anyone can know the values of n and e, it is not possible to factorise n (if p and q are large enough) and so it is not possible to find r and therefore not possible to find d. [12 B]

b) n=77 so p=7 and q=11. Therefore r = (7-1)(11-1) = 6*10 = 60

d=43 is the private key if e*d = 1 mod r

43*7 = 301=1 mod 60

Therefore 43 is the inverse of e=7 mod r = 60 and so the private key is 43 [5U]

c) m=13, c=137 mod 77 = 62

the ciphertext has value 62 [3 A]

d) c = 17, m = 1743 mod 77 = 73[6 A]

Y / U / N
1 / 17 / 43
17 / 58 / 21
62 / 53 / 10
62 / 37 / 5
61 / 60 / 2
61 / 58 / 1
73

Question 4

It should be easy to compute the hash function – so that the hash function is efficient
The input x can be of arbitrary length – so that any message can be hashed
Given a value y, it should be hard to find an x such that h(x) = y – to prevent someone who knows h(x) from substituting a different input data
It should be hard to find different inputs x1 and x2 such that h(x1) = h(x2) – to prevent someone sending message x1 and then claiming to have sent x2.

[6 B – one mark for each property + ½ for each reason]

SHA – the input is broken into blocks of length 512 bits and each block is then split into 16 words of length 32-bits. Call these words w(0), w(1),…,w(15). These words are expanded into 80 words using a formula. Five 32 bit words h(0),h(1),…,h(4) are given initial values. Then for each 512 bit block SHA operates on the 80 words w(0),….w(79) and h(0).,…h(4) to generate new values of h(i). This continues until all of the 512 bit blocks have been processed. The final values of h(0),..h(4) are concatenated to form the value of the hash. [4 B]

Statistical and experimental test show that SHA has all of the required properties but there is no proof that if does have properties 3 and 4. [1 B]

Alice creates a message m
She uses SHA to compute a hash of the message SHA(m)
Alice encrypts the hash using her private key to get a signature s s = PKencrypt(A priv)(SHA(m))
Alice sends Bob m and s
Bob receives m and s
Bob decrypts the ciphertext s using Alice’s public key to get s’ = PKdecrypt(A pub)(s)
Bob computes the hash of the message SHA(m)
If SHA(m) = s’ then the digital signature and message are verified. The message has not been altered and Alice cannot deny having sent it. [8 B]

Charles can substitute his public key in place of Alices. Then Charles uses his private key to encrypt and sign the message. Bob looks up what he thinks is Alice’s public key (but in fact is Charles) which works in authenticating the message. Therefore Charles accepts the message as coming from Alice. [6 U]

f) They could use a certification agency to verify that the keys they are using are the ones the think they are. [1 U]