validated (recheck)
Supervisions for Part II Security
University of Cambridge Computer Laboratory
Computer Science Tripos
Lent 2000
Lecturer: Ross Anderson
Supervisor: Frank Stajano
Hello everyone and thanks for choosing me for your security supervisions. I hope you'll enjoy this exciting and fascinating subject!
This year I am supervising 4 pairs of students from Queen's college. Each pair gets 3 supervisions. After a bit of trial and error I can confirm that the supervisions are held in the "Small exams hall, old TV studio", which is on the 2nd floor of the building where Photography and Illustration is. When you reach the 2nd floor landing, go through the door on your right (I hereby declare you to be an authorised person) and, past that, to the door on your left. Apologies for any confusion (I was previously confused myself, and received contradictory and partially wrong advice.)
All supervisions are on Wednesday afternoon: 16 Feb (lectures 1-4), 23 Feb (lectures 5-8), 1 Mar (lectures 9-12).
| When | Who |
|---|---|
| 1500-1600 | Siraj Khaliq and Julian Brown |
| 1600-1700 | George Danezis and Mark Shinwell |
| 1700-1800 | Patrick Wynn and Bruno Bowden |
| 1800-1900 | Justin Siu and Paul Gotch |
You will only really get your money's worth out of the supervisions if you do the assigned homework in advance. Please submit the homework by the end of Monday so that I have some time to go through it.
Someone (Mark I think) asked if I could return his homework so that he could go through my scribbles. Well, I thought I could do better. Here is a .pdf.pgp file with all your (marked up) submissions. Get it from this .bin link and rename it if your browser insists on doing CR-LF translation on it. You'll probably get even greater benefit from looking at what your peers have done than from looking at my own scribbles (which were mostly meant as reminders for points I wanted to raise at the supervision, rather than as "scores"). The file is encrypted under the keys of the participants and can't be read by others.
The file was scanned at 240 dpi b/w to keep the size down (even so, it's 22 pages and 1.2 MB). It probably looks unreadable on screen, but you can zoom in quite a bit.
Julian: you were meant to be one of the recipients, but aren't. The reason why it's not encrypted to you too is not because you didn't submit any work but because I couldn't find any key for "Julian Brown" on the keyservers. Maybe if you had sent in your stuff I could have looked it up via the key id.
This time the questions are a little bit harder, so there are fewer of them. If you want an optional challenge (hard), try L6Q3 from your notes. The three questions below are all mandatory.
The Soviet ZS-23 antiaircraft gun's radar used a lag sequence to make jamming harder (a '1' bit caused the next pulse to be delayed). The sequence was generated using a 16 bit linear feedback shift register, whose key was not just the initial state but also the feedback polynomial itself. Show that 31 bits of the sequence are enough to predict it (hint: arrange these bits in a suitable matrix). (verbatim from lecture 6 problem 4)
Pen-and-paper application: assume a setup like the one above, but with only a 4-bit shift register. Using the technique developed above, work out the initial state of the register and the position of the taps. (Reminder: "linear feedback" in practice means that the only operations you do in the feedback network that decides the next bit are XORs). The observed output is (earlier outputs leftmost): 0 1 1 0 1 1 0 1 1 ...
Describe the following modes of operation of a block cipher: electronic codebook, cipher block chaining, output feedback, cipher feedback, message authentication code and hash function.(verbatim from 1997 Paper 7 question 9)
Describe the purpose of hash functions, message authentication codes and digital signatures, sketching a possible construction for each of them. (verbatim from 1998 Paper 7 question 9)
Here they are, with my markup and extra goodies. Remove the .bin extension before decrypting, it's there just to avoid CR-LF problems.
Explain the maths of RSA. Don't prove theorems, but state what they say and note that you use them in the appropriate places.
NB: ^ denotes exponentiation, so for example 2 ^ 8 = 256
2.1.The Tatebayashi-Matsuzaki-Newmann protocol may be described as follows:
A -> S : rA ^ 3 (mod N)
B -> S : rB ^ 3 (mod N)
S -> A : rA XOR rB
Explain what is happening here, including the goal and the assumptions.
2.2.How can this protocol be attacked?
2.3.It has been suggested that the protocol can be strengthened by changing the contents of the last message to { rB }rA (rB encrypted by rA using a secret key algorithm). Does this help? Explain your answer.
(verbatim from 1995 Paper 9 question 6)
Find out about, and explain, ElGamal signature and ElGamal encryption. What's the difference between ElGamal and Diffie-Hellman? And RSA, for that matter? (Creative answers welcome, i.e. the more differences you can think of, the better -- there aren't just mathematical ones.)
© 2000 Frank Stajano
Back to Frank's home page
validated (recheck)