Question 1 (total of 6 marks) Critique the following statement: We achieve security by obscurity: by keeping our algorithms secret we obtain the best guarantee of security. Your answer should cover roughly half a page of A4 paper. (6 marks) (ps: You are strongly encouraged to answer this question using a word processing / typesetting program, e.g., LaTex, Word. Please avoid submitting it handwritten.)

Question 3 (total of 6 marks) Choose one of the modes of operation for block ciphers discussed in class. a. Describe in detail how the mode of operation you have chosen works, highlighting features and weaknesses (if any). (2 marks) b. Describe and reference a real-world use of the mode of operation you have chosen, stating and justifying any advantages or disadvantages of this mode of operation in this context. (4 marks) Your answer to part b of Question 3 should not exceed half a page of A4 paper.

Question 2 (total of 8 marks) Answer the following. a. If & is the DES block cipher, let 2DES denote double encryption with DES with keys Ki and K₂, i.e., 2DESK(P) = DESK, (DESK, (P)) Research and describe, in your own words, how a meet-in-the-middle attack against such cipher might work. (5 marks) (Your description should include what the attacker's goal is, its capabilities, details of the attack and its overall complexity.) b. Write down how encryption works in 3DES with two keys, and give two reasons why this is better than DES. (3 marks)

Task 1. Answer the following questions based on the RFC of Diffie-Hellman key agreement https://www.ietf.org/rfc/rfc2631.txt. Reference the relevant sections in your answer but use your own words. 1. How the cryptographic keying material derived from the shared secret number is typically used? 2. How the shared secret ZZ is defined? 3. Where the primality test is used? How the the robust primality test is defined? 4. Why the group parameter validation process is needed? 5. What is ephemeral-static mode and how is it different from static-static mode?

Task 2. Suppose you have the following algorithm: 1. As an input algorithm is given five (5) unsorted integer arrays of length n. 2. Each array is sorted using bubble sort. 3. Every element of 2nd and 4th array is output on the screen of a user. 4. Number 9 is added to 7th element of 1st, 3rd and 5th arrays. Find how many steps it would take to execute this algorithm (Hint: it should look like equation). Prove that time complexity of this algorithm is O(n²).

Task 4. Using Miller-Rabin prove that 149 is a prime number for witnesses a + 3 and b +4, where a is the 3rd digit of your student code, b is the 4th digit of your student code.

Task 6. Alice invented her own protocol to share message with Bob. She decided to use encryption algorithm that has following property: Enc(ka, Enc(k₁, m)) = Enc(kb, Enc(ka, m)). Protocol works as: 1. Alice calculates ca = Enc(ka, m) where m - message, ka - key generated by Alice. She sends ca to Bob. 2. Bob calculates c = Enc(kb, ca), where k- key generated by Bob. He sends c to Alice. 3. Using the property of encryption algorithm, Alice calculates c = Dec(ka, c). She sends co to Bob. 4. Bob calculates m = Dec(kb, Cb). Assume that adversary Eve has full control over a public channel that Alice and Bob use to communicate. However, Eve cannot break cryptographic problems on which encryption algorithm relies.

Question 2 2a. The ephemeral Diffie-Hellman Key Exchange (DHKE) protocol allows two parties to agree on keying material in the presence of an adversary. The protocol assumes the two parties have already agreed on two primes p.q such that q divides p-1, and a value g> 1 such that g = 1 mod p. From this starting point, describe the remainder of the protocol. 2b. Assuming that the adversary is passive (Le., acts only as an cavesdropper), identify and define the mathematical problem underlying the security of this protocol. How does it relate to the Discrete Logarithm Problem (DLP) in the given setting? 2c. Discuss the security weaknesses of ephemeral DHKE in the situation where the adversary is an active party. 2d. Explain how you might modify the ephemeral DHKE protocol to avoid the weaknesses identified in your answer to item 2c.

IY 3660 Assessed Coursework 2 Question 1 Explain what hybrid encryption is and discuss why it is a commonly used approach in cryptog- raphy.

Question 1 Explain what hybrid encryption is and discuss why it is a commonly used approach in cryptography.

Question 2 2a. The ephemeral Diffie-Hellman Key Exchange (DHKE) protocol allows two parties to agree on keying material in the presence of an adversary. The protocol assumes the two parties have already agreed on two primes p, q such that q divides p - 1, and a value g> 1 such that gº = 1 mod p. From this starting point, describe the remainder of the protocol. [2 marks] 2b. Assuming that the adversary is passive (i.e., acts only as an eavesdropper), identify and define the mathematical problem underlying the security of this protocol. How does it relate to the Discrete Logarithm Problem (DLP) in the given setting? [4 marks] 2c. Discuss the security weaknesses of ephemeral DHKE in the situation where the adversary is an active party. 2d. Explain how you might modify the ephemeral DHKE protocol to avoid the weaknesses identified in your answer to item 2c.

Question 3 3a. Describe, using a diagram, the IND-CCA security game for public-key encryption. (Your diagram should include clearly the entities in the game, their interaction, and the winning condition.) 3b. Identify a public-key encryption scheme that satisfies IND-CCA security. For the scheme you have identified, name the mathematical assumption(s) required for the security to hold.

Question 4: What is the motivation for public-key encryption? Give an overview of Data Encryption Standard (DES), Advanced Encryption System (AES), and Rivest Shamir-Adelman algorithms.

(a) Show that (1, 1) ⊕(1, 1) = (5,6). Write out your work. (b) Show that (5, 1) ⊕(5, 1) = (5, 6). Write out your work. (c) Show that (1, 1) ⊕ (3,0) = (5, 1). Write out your work. (d) Show that (1, 1) ⊕(5, 6) = (3,0). Write out your work. (e) Show that (1,6) ⊕(5, 1) = (3,0). Write out your work.

(a) On an elliptic curve, what is the negative of a point A? (b) What is zero on an elliptic curve, and why is it important from a group theory perspective? In answering both questions, consider the case where x and y vary over the real numbers.

(a) An Authenticated Encryption (AE) scheme consists of a triple of algorithms,(KGen, Enc, Dec). Describe the function of each of these algorithms and explain what is meant by the correctness of an AE scheme.[4 marks] (b) Security for AE schemes is defined in terms of the combination of two security notions: indistinguishability under chosen plain text attacks (IND-CPA security), and integrity of ciphertexts (INT-CTXT security). Give informal descriptions of these two notions, using diagrams to illustrate your answer if you wish. For both notions, state what it means for an AE scheme to be[8 marks]secure. (c) AE schemes can be built using generic composition of symmetric encryption schemes and MAC schemes. There are three principal methods for doing so, known as EtM,MtE and E&M. Briefly describe each of these three methods, and comment on their AE security when instantiated using an IND-CPA secure encryption scheme and a strongly unforgeable MAC scheme. In each case, justify your answer.[12 marks] (d) In applications, we are often interested in simultaneously providing confidentiality and integrity for some data but only integrity for other, associated data. An Authenticated Encryption with Associated Data (AEAD) scheme meets this goal. Define the syntax of an AEAD scheme and show how to extend the generic EtM construction of an AE scheme to obtain an AEAD scheme. Use a diagram to illustrate the second part of your answer.[6 marks] (e) Nonce-based AEAD is a further extension of the AEAD paradigm. Explain what is meant by nonce-based AEAD and why it is a good primitive to offer to software developers.[4 marks]

(a) Give a formal definition of a block cipher. Your answer should make reference to the block size n and the key size k.. (b) Explain why block ciphers are usually used in modes of operation. (c) Describe the Electronic Code Book (ECB) mode of operation, using a diagram to illustrate your answer if you wish.[2 marks] (d) Explain what the main security limitation of ECB mode is. Illustrate your answer with reference to a specific example.[4 marks] (i) Draw a diagram to illustrate the encryption algorithm of this mode. (ii) Write down equations, similar to those above for encryption, that describe thedecryption operation for CBC mode.[2 marks] (f) The XML encryption scheme operates on byte-oriented data and uses the following padding method for CBC mode: at least 1 byte of padding is always appended to the raw message M, and at most one complete block of padding is appended; if s bytes of padding are needed for some s > 1, then appends - 1 random bytes to M followed by the byte encoding of integer s. So, for example, if s = 1, then the padding appended to the message M is just 0x01, while if s = 2, then a random byte followed by 0x02 is appended, and so on. (i) Explain in detail, using pseudo-code, how a typical implementation would re-move the padding from a plain text to recover M for this padding scheme. Your pseudo-code should work for general block sizes, and you should use a variable name block size in your pseudo-code to reflect this. Your pseudo-code should also generate an error message "padding error" if the padding is in-valid in some way. (Hint: your pseudo-code should check that the number of padding bytes does not exceed the maximum possible value that is implied by there being at most one complete block of padding.)[4 marks] (ii) A simplified version of XML permits bytes of any value to occur in messages M except for 0x00. After CBC mode decryption and padding removal, a simplified XML implementation checks whether the resulting message M contains byte value 0x00. If a byte with this value is found in any position of M, then the implementation returns an error string "parsing error", otherwise normal XML processing continues (and no error is returned).Now suppose you have a target block of cipher text C that is known to correspond to a full message block P* (that is, P* is a plain text block entirely from M, not containing any padding). Suppose you also know C+₁, the cipher textblock preceding C".-15 (iii) By modifying delta in other positions, or otherwise, show how to recover the value of the last byte of plain text (the padding byte) in the cipher text IV*, C* that you obtained in the previous part of the question. (Hint: consider modifying IV* by all possible XOR offsets in each position and requesting decryptions. One offset will produce 0x00 in the plaintext in position j. Does this cause a parsing error or not?) (iv) By further modifying the ciphertext IV*,C", or otherwise, sketch how you would recover the complete plaintext block P. (Hint: consider modifying IV*so that the padding byte now contains 0x01, and then doing a similar analysis to that in the previous part.)

(a) What security service is a Message Authentication Code (MAC) intended to provide? (b) A MAC scheme consists of a pair of algorithms (Tag, Vrf). Describe the function of each of these algorithms and explain what is meant by the correctness of a MACscheme.[4 marks] (c) The standard notion of security for a MAC scheme is existential unforgeability under chosen message attack, or EUF-CMA security for short. Give a description of this security notion. You may use a diagram to illustrate your answer.[6 marks] ==(d) Suppose (Tag, Vrf) is an EUF-CMA-secure MAC scheme. Consider the MAC scheme (Tag', Vrf') in which Tag (m) = Tag (m)||m, where || denotes concate-nation of strings, mo denotes the first bit of m, and in which Vrf' is defined in the obvious way. (i) Provide a brief argument to show that (Tag', Vrf') is also EUF-CMA-secure. (ii) What can you conclude about the confidentiality that is provided by an EUF-CMA-secure MAC scheme for its input messages m?[1 marks] (iii) Consider combining this MAC scheme with an IND-CPA-secure symmetric encryption scheme in an "Encrypt & MAC" construction to obtain an Authenticated Encryption (AE) scheme. Describe the ciphertexts in this scheme. What can you say about the security offered by this construction? What can you conclude about the generic security of the "Encrypt & MAC"approach to building AE?[3 marks] (e) Consider the following MAC scheme, based on an n-bit hash function H: let the key K also have n bits; define Tag (m) := +K; Vrf' is defined in the obviousway. (i) Show that this MAC algorithm is vulnerable to a key recovery attack. State the resources that your attack consumes, in terms of calls to the oracles in the EUF-CMA security definition.[3 marks] (ii) In general, how does a key recovery attack on a MAC scheme relate to its EUF-CMA security? (f) Recall the Merkle-Damgård construction of an n-bit hash function from a compression function h : {0,1}* × {0,1}" → {0,1}", a padding scheme pad(-) such that the bit-length of m' = pad(m) is a multiple of k, and an n-bit value IV: Compute m' = pad(m). • Break m' up into blocks m,...,m, each of bit-length k. Set ho = IV and compute h; | = h(m², h¡) for i = 0, … ..‚† — 1. Output h₁. (i) Draw a diagram to illustrate the hashing operation for this construction. [3 marks] (ii) Suppose that the padding scheme pad(-) adds a length field and additional padding bits to its input messages, so that pad(m) = m len(m)||padding. Show that the hash function is vulnerable to length extension attacks. That is, show that if H (m) is known for some (possibly unknown) bit-string m, then H(m||1en(m)||padding||s) can be computed, for any chosen bit-string 8. (iii) Now consider the following MAC scheme, based on such a hash function H:let the key K have k bits and define Tag, (m) H(Km); algorithm Vrfis defined in the obvious way. Show that this MAC scheme is vulnerable to a forgery attack, by exploiting the length extension weakness of H. What resources does your attack consume, in terms of calls to the oracles in the EUF-CMA security definition?[4 marks]

(a) The ephemeral Diffie-Hellman Key Exchange (DHKE) protocol allows two parties to agree on keying material in the presence of an adversary. The protocol assumes the two parties already agreed on two primes p, q such that q divides p - 1 and a value >1 such that gº = 1 med p.0 From this starting point, describe the remainder of the protocol, recalling that theephemeral version of the protocol involves the exchange of fresh Diffie-Hellmanvalues.[6 marks] (b) Assuming that the adversary is passive (i.e. acts only as an eavesdropper), identify the computational problem underlying the security of this protocol. How does it relate to the Discrete Logarithm Problem (DLP) in the given setting? [4 marks] (c) How large should p and q be so that the ephemeral DHKE protocol in your answer to Question 4(a) is secure against an adversary willing to expend an effort of 280 basic operations? What if the adversary is willing to expend an effort of 2128 basic operations? Justify your answers with reference to algorithms for solving the DLP in the given setting.[6 marks] (d) Discuss the security weaknesses of ephemeral DHKE in the situation where the adversary is an active party. (e) Explain how you might modify the ephemeral DHKE protocol to avoid the weaknesses identified in your answer to Question 4(d).[4 marks] (f) The ElGamal Public key encryption (PKE) scheme is derived from the Diffie-Hellman key exchange algorithm. Describe the EIGamal algorithm, and the relationship be-tween DHKE and the EI Gamal PKE.[4 marks] (g) Public key encryption can also be used to establish keying material in the presence of an adversary. (i) Describe a simple protocol for achieving this. (ii) Compare and contrast the approaches based on PKE and ephemeral DHKE in terms of security and efficiency.

(a) What is the main difference between a block cipher and a stream cipher? (b) Give a formal definition of a block cipher. Your answer should make reference to the block size n and the key size k. (c) In the context of a block cipher, explain what is meant by the following terms: (i) known plain text attack; (ii) chosen plain text attack; known cipher text attack. (d) To what extent are the three different attack models above realistic? Illustrate your answer with an example for each model.[6 marks] (e) You are given the task of selecting a block cipher to be used in an app that will run on smart phones. The block cipher will be used to encrypt users' passwords as they are sent from the phone to a remote server. Which block cipher would you choose for this purpose, and why?[4 marks] (f) Explain why modes of operation are usually needed when using block ciphers. (g) Define Counter (CTR) mode encryption. (h) Explain what the principal security requirement for using CTR mode is. Describe two different methods by which this requirement can be met, commenting briefly on any issues that may arise with each method.[5 marks] (i) CTR mode is vulnerable to "bit flipping" attacks. Explain, in general terms, what is meant by this statement, and which security property the attack violates (beyond confidentiality).[2 marks]

(a) An Authenticated Encryption (AE) scheme consists of a triple of algorithms,(KGen, Enc, Dec). Describe the function of each of these algorithms and explain what is meant by the correctness of an AE scheme.[4 marks] (b) Security for AE schemes is defined in terms of the combination of two security notions: indistinguish ability under chosen plain text attacks (IND-CPA security), and integrity of cipher texts (INT-CTXT security). Give informal descriptions of these two notions, using diagrams to illustrate your answer if you wish. For both notions, state what it means for an AE scheme to be[8 marks]secure. (c) AE schemes can be built using generic composition of symmetric encryption schemes and MAC schemes. There are three principal methods for doing so, known as EtM,MtE and E&M. Briefly describe each of these three methods, and comment on their AE security when instantiated using an IND-CPA secure encryption scheme and a strongly unforgeable MAC scheme. In each case, justify your answer.[12 marks] (d) In applications, we are often interested in simultaneously providing confidentiality and integrity for some data but only integrity for other, associated data. An Authenticated Encryption with Associated Data (AEAD) scheme meets this goal. Define the syntax of an AEAD scheme and show how to extend the generic EtM construction of an AE scheme to obtain an AEAD scheme. Use a diagram to illustrate the second part of your answer.[6 marks] (e) Nonce-based AEAD is a further extension of the AEAD paradigm. Explain what is meant by nonce-based AEAD and why it is a good primitive to offer to software developers.[4 marks]

Congratulations! You have just been appointed as the new head of cryptographic engineering at softoo.com, an online retailer specialising in soft toys. Since its foundation in Surrey, five years ago, the company has grown to have an annual revenue in the billions and more than 100 million regular customers. The company is very proud of its green credentials, specialising in reducing and recycling toy packaging. You set about conducting an internal review of the company's cryptographic infrastructure. You find that the company authenticates its customers to the website using a standard username/password approach, with MD5 hashes of the passwords being stored alongside usernames in a back-end database. The entire softoo.com site is served over http instead of https because your predecessor was concerned about the costs of supporting encryption. After recovering from the shock of realising that your predecessor was likely to have very limited knowledge of cryptographic security best practices, you decide to write a briefing note for the Chief Information Security Officer (CISO) of softoo.com. This note will describe the problems you've found, along with their likely security impacts and possible consequences for the business. It will also recommend remediations for these problems, including rationale for these recommendations. Your note will include timelines for implementing the remediations and any costs that you anticipate. Yourtask in this question is to produce the first draft of this note. Keep in mind thatthe CISO is smart, but cryptographically rusty, so your note will need to provide an appropriate level of detail for any solutions you propose.