Cryptography Assignment Question

Examination - Course: Cryptography

Question 1: Qualitative Paper Analysis

Read the following website that accompanies the research on the recent breaking of SHA1:

Summarize the attack, and in particular, the impact of this work on security mechanisms that use SHA1, in your own words. (A good answer would probably take about two pages.)

Question2: Password Storage & Key Management

You are asked to implement the password storage for a webserver, where users are authenticated using password logins. You have to implement the storage without using a random number generator, and therefore cannot implement exactly the same salted storage as described in the lectures.

There are at least three alternative ways to implement the table:

  • Method A: use the same salt for each entry in the table.
  • Method B: use incremental numbers: we can use the number n as the salt for the n-th entry in the table.
  • Method C: use the number 0 as the salt for the first entry, and define the salt of each other entry as the hash of the previous entry. Thus, salt 0 for the first, hash(0) for the second, hash(hash(0)) for the third, etc.

Giventhese possibilities, answer the following questions:

  1. Compare the security of the three methods. Which of these would you prefer, and why? (A good answer would probably take at most a page.)
  2. Compare the security of Methods A, B, and C against salted storage based on a random number generator, as described in the lecture. (A good answer would probably take at most one page.)
  3. Compare the security of the previous four suggestions (methods A, B, and C and the random salt) against storing the passwords without any salt. (A good answer would probably take at most one page.)

Question 3: Protocol Design

Context: you work at an insurance company and handles a database with privacy-sensitive customer data. You are deploying a communication system within your company, where the goals are to secure communications between employees even if they are at different sites that are only connected through the internet. The company would like to use asymmetric cryptography to achieve this: every employee should have his or her own key pair. The company does not want to use TLS for authentication, because they have heard that there have been attacks on TLS.


  • Discuss at least two options for generating and distributing the key pairs. Who generates the keys? Provide benefits and drawbacks of each option. (A good answer would probably take a page)
  • Employees might forget their keys, for example, because the key storage gets corrupted. Design a system for dealing with this case. (A good answer would probably take one page)
  • Design your own mutual authentication protocol using only two messages, which uses the asymmetric cryptographic key pairs of your company's employees. It should provide mutual authentication and should establish a shared secret between the two participants. (A good answer would probably take up to two pages)
  • Assume an attacker compromises (i.e. learns) your system administrator’s long-term private key. Analyse the impact on your company. (A good answer would probably take at most one page)
  • Improve your protocol and company procedures to reduce the impact of compromise of the administrator's long-term private key. (A good answer would probably take at most one page)

In each answer, make sure you clearly explain your design choices and state all assumptions. When presenting protocols, try to use similar notation to the lecture slides.

Introduction to Cryptography — Homework #11

Explain all of your answers and if you write code to assist in answering a question, include your code with your submission. Please submit a single well-readable PDF.

  1. To see that the order of operations in DSA is important, show that the following statement does not always hold.

(αk mod p) mod q = (αk mod q) mod p

Make sure that your counterexample (i.e., your specific p,q,α,k for which the statement above is false) are allowed values for DSA. (For example, p is prime.)

  1. Exercise 11.2 from the textbook, parts 1 and 2.
  2. Let p be a prime and let α be an integer such that p does not divide α. Let h(x) ≡ αx (mod p). Explain why h(x) is not a good cryptographic hash function.
  3. Consider the following hash function. Divide the message into chunks of 160 bits (pad with 0’s if it doesn’t come out right) and then take the bitwise exclusive or of the blocks.

For each of the following properties, state whether this hash function satisfies the property and explain why (or why not).

  • Preimage resistance.
  • Second preimage resistance.
  • Collision resistance.