SEAT NUMBER: ......... ROOM:.......... This question paper must FAMILY NAME .......................... be returned. Candidates are not permitted to OTHER NAMES .......................... remove any part of it from the examination STUDENT NUMBER ....................... room. MID-YEAR EXAMINATIONS 2012 Unit: COMP343 - Cryptography and Information Security Date: Monday 18 June 13.20 to 16.30 Time Allowed: 3 hours plus ten minutes reading time Total Number of Questions: 16 (Total Marks: 100) Instructions: Answer ALL questions. This examination consists of two sections A and B. Section A is worth 35 marks and Section B is worth 65 marks. Both sections include two different types of questions. Core questions assess your knowledge and basic comprehension of the material covered in the unit. Advanced questions (preceded by *) assess higher problem solving skills as well as analysis and synthesis skills. Core and Advanced questions amount respectively to 74 and 26 marks. Note that for the same amount of marks, a Core question should be easier and take significantly less time than an Advanced question. The answers to each of Sections A and B must be written in a separate answer book. Write your name and student number on the cover of each answer book. Also write the section (A or B) on the cover of each answer book. Write your name and student number at the top of this page. You may do rough working on this question paper, but all answers MUST be submitted as described above. Hand in this question paper at the end of the examination. Materials permitted: No dictionaries, no calculators, no notes permitted.SECTION A (5 QUESTIONS, 35 MARKS) Question 1. [5 marks] Consider the Caesar Cipher that cyclically shifts all letters by a key k. Say, for k = 2, ‘A’ is encrypted as ‘C’, ‘B’ is encrypted as ‘D’, . . . , ‘Z’ is encrypted as ‘B’. a. (3 marks) Given an encrypted message ‘KDVKLQJ’ encrypted with an unknown key k, explain how to use the chosen cipher text attack. For example, assume that you know that ‘LGHD’ is an encryption of ‘IDEA’, then decrypt the original message. * b. (2 marks) What property of natural languages makes Caesar Cipher very weak? Write no more than 2-3 lines. Question 2. [6 marks] Let h : f0; 1g∗ ! f0; 1gn be hash function. a. (1 mark) In no more than 2-3 lines, explain what finding a 2nd preimage means. b. (1 mark) In no more than 2-3 lines, explain what finding a collision means. c. (2 marks) What is the complexity of a generic collision finding algorithm that is based on the birthday paradox? d. (2 marks) Name two different hash functions that are used in practice. Question 3. [6 marks] Assume that f : f0; 1gn ! f0; 1gn is a preimage resistant hash function. Consider the compression function h : f0; 1g2n ! f0; 1gn that: • takes x 2 f0; 1g2n and writes it as x = x1kx2 with x1; x2 2 f0; 1gn; • outputs h(x) = f(x2) ⊕ f(x1) ⊕ x1 ⊕ x2, where ⊕ denotes the bitwise XOR. For example, if n = 4 and x = (1; 0; 0; 1; 1; 1; 0; 0) we have x1 = (1; 0; 0; 1), x2 = (1; 1; 0; 0); hence x1 ⊕ x2 = (0; 1; 0; 1). In no more than 5 lines, explain how one can construct a collision. Page 1Question 4. [7 marks] Alice relies on RSA to perform different kinds of information security operations. Alice’s public key is (N; e). She keeps secret the primes p and q such that N = pq and the private exponent d. a. (2 marks) What is the trapdoor in the RSA cryptosystem? In other words, explain how Alice can decrypt a message C sent to her whereas everybody else can’t. b. (2 marks) Explain how Alice can sign a message M and how other people can check it comes from her. * c. (3 marks) Assume that Alice collects secret votes from several users. For this, each user chooses: • a random odd positive integer V < N=2 (e.g. 1; 3; 5; 7; : : : ) to vote for \Yes"; • a random even positive integer V < N=2 (e.g. 2; 4; 6; 8; : : : ) to vote for \No"; and encrypts V with RSA as V e mod N. Explain how the attacker, Eve, can apply a man-in-the-middle attack, to intercept the sent encryptions and modify them before passing then further to Alice in a way to significantly increase the proportion of \No" votes. Note, that Eve is not able to factor the modulus N or find the secret exponent d, so her attack must be based on a different (and computationally much simpler) approach. Hint: Explore the fact that V is requested to satisfy 1 ≤ V < N=2 instead of being chosen from the full range 1 ≤ V < N. Question 5. [11 marks] Consider an implementation of ElGamal cryptosystem modulo a large prime number p and with generator g. In this context, Alice’s private and public keys are denoted respectively by n1 and g1 = gn1. Bob’s private and public keys are respectively denoted by n2 and g2 = gn2. a. (1 mark) Resolve the acronym DLP and explain what it means. b. (1 mark) Cite two attacks against the DLP. c. (2 marks) For the same level of security, is it possible to use significantly shorter keys with ElGamal than with RSA? Provide arguments. d. (2 marks) Recall the key agreement protocol between Alice and Bob. Outline why it is secure. e. (5 marks in total) Assume that there is a third person, Charlie, whose private and public keys are respectively n3 and g3 = gn3. In order to share a common value they proceed as follows. Page 2In a first round, Alice takes g2 and g3 then computes and publishes g1;2 = g2 n1 and g1;3 = g n1 3 . Similarly, Bob takes g1 and g3 then computes and publishes g2;1 = g1 n2 and g2;3 = g3 n2. Finally, Charlie takes g1 and g2 then computes and publishes g3;1 = g1 n3 and g3;2 = g2 n3. In a second round, Alice selects g2;3 (or g3;2) and takes it to the power n1. Similarly, Bob selects g1;3 (or g3;1) and takes it to the power n2. Finally, Charlie selects g1;2 (or g2;1) and takes it to the power n3. i. (1 mark) What is the common value computed by all the parties? * ii. (2 marks) Modify the protocol in order to reduce the number of values that need to be computed/published. * iii. (2 marks) Generalising this approach, how many rounds and how many exponentiations would be necessary for n persons to share a common secret? Page 3SECTION B (11 QUESTIONS, 65 MARKS) Question 6. [5 marks] You are Chief Information Security Officer for a company which employs a number of contract managers who need to exchange contract files with both suppliers and customers in a secure manner, preserving both the confidentiality and authenticity of the documents involved. A request for proposals has produced a short list of two products which meet the functional requirements, and you are now expected to recommend one. • Product A has options for both symmetric-key and public-key encryption and authentication (signing), under control of the user. • Product B has no options - it just signs all documents using public-key cryptography and encrypts them for transfer using a session key. Which product do you recommend for purchase, and why? Question 7. [10 marks] Alice and Bob are both users on a Unix system, and Alice wants to share some files in a work documents directory with Bob. Alice executes the following series of commands: [alice@research home]$ ls -ld alice drwxr-x--- 3 alice alice 4096 Apr 29 10:43 alice [alice@research home]$ cd [alice@research alice]$ ls -ld work-docs/ drwxrwx--- 2 alice alice 4096 Apr 29 10:43 work-docs/ [alice@research alice]$ cd work-docs/ [alice@research work-docs]$ ls -l total 8 -rw-rw-r-- 1 alice alice 49 Apr 29 10:40 file1.txt -rw-rw-r-- 1 alice alice 22 Apr 29 10:43 file2.txt [alice@research work-docs]$ chmod 644 file2.txt [alice@research work-docs]$ umask 0002 [alice@research work-docs]$ vi file3.txt [alice@research work-docs]$ (In the final command, she uses the vi editor to create a third document.) Page 4Bob subsequently executes the following commands: [bob@research bob]$ id uid=1004(bob) gid=1004(bob) groups=1004(bob),1003(alice) [bob@research bob]$ cd ~alice/work-docs a. (1 mark) Will the cd ~alice/work-docs command issued by Bob succeed? b. (3 marks) Can Bob edit the file file1.txt? If not, can he overwrite it, and why? c. (3 marks) Can Bob edit the file file2.txt? If not, can he overwrite it, and why? d. (3 marks) Can Bob edit the file file3.txt? If not, can he overwrite it, and why? Question 8. [5 marks] A UNIX system user connects, as he has done many times before, to a system using OpenSSH. As he does so, he receives an error message: Warning: the RSA host key for ’nile.comp343corp.com’ has changed. Do you want to continue connecting (yes/no) ? a. (2 marks) Should the user continue and connect to the system? If not, why not? b. (3 marks) Suppose that the user is actually an administrator, who presses \y" and connects, confident that the system is secure and has not been compromised in any way. Suggest an explanation for why this might occur. *Question 9. [7 marks] The Internet Domain Name Server (DNS) provides a protocol which allows hosts to send requests containing host names and get back replies containing the corresponding Internet Protocol (IP) addresses, which are then used to connect to the desired host. Until recently, versions of the Berkeley Internet Naming Daemon - the domain name server most commonly used on the Internet - used a very simple protocol to match replies to the corresponding requests. It used a Linear Congruential Generator (LCG) pseudo-random number generator to generate a 32-bit nonce which was inserted into a lookup request, and expected the server to send back a reply using the same nonce value. Describe an attack which an adversary could use to poison a caching name server by injecting invalid data into it | for example, by inserting the address of a phishing website in place of the correct address for an online banking website. Assume that the adversary has the following abilities: Page 5• Send queries to the name server and get back replies • Get the name server to send queries to the attacker, and send back replies to it • Send unsolicited replies to the name server at any time Question 10. [6 marks] You are consulting to a bank, for whom you have installed and configured a biometric access control system using iris readers. Give two examples of possible attacks which you might expect against such a system. *Question 11. [5 marks] Alice and Bob set up communication using a Key Distribution Center, Trent, using the following primitive protocol: a. A ! T : B b. T ! A : KB c. A ! B : fKSgKB d. B ! A : fAgKS a. (1 mark) Has Alice authenticated Bob? b. (1 mark) Has Bob authenticated Alice? c. (3 marks) Where is the weakest point in this system, and how could it be attacked? Question 12. [6 marks] The OpenVPN open-source virtual private network uses a Public Key Infrastructure to authenticate client computers to the firewall, and vice-versa. The setup instructions and scripts, installed on the firewall, walk the user through the creation of a self-signed root certificate, and then the signing of certificate requests for the client computers. Is this a good scheme? What would you change about it? Page 6*Question 13. [5 marks] You have been given the job of designing a secure tape backup system for a bank, to use AES- 256 symmetric encryption. Realising that much of the data to be written to tape will contain repeating sequences of bits, you reject ECB mode as inappropriate and settle on CBC mode. Each tape block is 1024 bits in size, so will contain eight 128-bit blocks of ciphertext. * a. (3 marks) Suggest a scheme for generating an initialization vector for each tape block. * b. (2 marks) What will be the effect on each of the ciphertext blocks in a tape block if there is a 1-bit read error in the first ciphertext block? Question 14. [5 marks] Windows NT domains authenticated users by passing a keyed hash of a known constant value, with the user’s password as the key, across the network. a. (2 marks) List two types of attack which will allow recovery of the user password. b. (3 marks) Suggest a simple modification which would effectively eliminate one of those attacks. Question 15. [7 marks] Alice wishes to send Bob a confidential message, but they have not previously exchanged public keys. So, in order to send the message, they use the following protocol, using RSA public key cryptography: 1. A ! B : fMgKA 2. B ! A : ffMgKAgKB 3. A ! B : fMgKB (Step 3 is possible because of the commutative property of RSA, i.e. ffMgKAgKB == ffMgKBgKA). a. (5 marks) Show how Mallory can conduct a man-in-the-middle attack against this protocol. b. (2 marks) What is the basic feature, missing from this protocol, that makes the attack possible? Page 7Question 16. [4 marks] Alice uses the GNU Privacy Guard system. On her keyring, she has four keys apart from her own. She accepts them all as valid, and has assessed Bob and Carol as marginal introducers, while she has no knowledge of Dave’s competence as an introducer. She has just received the public key of Eric, who she knows nothing about. However, Eric’s key is signed by all of Bob, Carol and Dave (see Figure 1). Should she trust Eric? Explain why. Figure 1: Trust Relationships Among PGP Keys Page 8