Homework 3: Audit and Authentication

Hard deadline: Friday, March 27, 11:59 pm.
Soft deadline: Wednesday, March 25, 11:59 pm

Know thyself. —Inscription at the Temple of Delphi

Updated 3/20/15: added string arguments to hash function calls in Problem 1. You may solve Problem 1 either with or without those arguments; just be clear about which version you are using.

Problem 1

The lecture notes on audit discuss how a tamperproof log can be constructed using iterated hashing. In that construction, a machine M records a message m in its log as follows:

M:

1. ek = H("encrypt", ak) // hash authentication key to derive encryption key for this entry
2. c = Enc(m; ek) // encrypt the message in this entry
3. erase ek // forget the encryption key
4. t = MAC(c; ak) // create a tag for the new link
5. entry = c, t // the log entry contains the encrypted message and the tag
6. record entry in log
7. ak = H("iterate", ak) // iterated hash of authentication key to derive new authentication key for the next entry

Answer the following questions about the protocol:

1. Suppose that log messages were not encrypted. That is, each log entry (line 5) would be the plaintext m followed by tag t=MAC(m;ak). What new attacks would be possible against the protocol?
2. Suppose that log messages were not authenticated. That is, each log entry (line 5) would be only the ciphertext c with no tag. What new attacks would be possible against the protocol?
3. Suppose that the hash iteration in line 7 were omitted. That is, the authentication key ak stays the same for every entry. What new attacks would be possible against the protocol?

What to submit: a file named tamperproof.pdf with your answers to the above questions.

Evaluation: We will grade your answer based on its correctness and clarity.

Problem 2

based on [Schneider, chapter 5, problem 5.3]

You have been asked to determine the feasibility of conducting a brute-force attack on a password. Your goal is to produce a dictionary for use in an offline guessing attack. You don't know in advance the passwords that you will need to crack, so you must build a full dictionary.

1. How much time would it take to create a dictionary to crack passwords under both of the following assumptions?
   • Passwords are chosen from this supposed list of leaked MySpace passwords [source: www.skullsecurity.org].
   • The stored form of password pwd is H(salt, pwd), where H is SHA-512 and the salt is four bytes. (That's how OS X Lion stores passwords.)
2. How much time would it take to create a dictionary to crack passwords under both of the following assumptions?
   • Passwords are chosen uniformly at random from the space of all 8 character or less passwords over the alphabet containing lower-case letters and digits (i.e., a–z and 0–9).
   • The stored form of password pwd is H(pwd), where H is SHA-512. No salt is used.
3. Under what circumstances would you recommend the password regime in part (1)? Under what circumstances would you recommend the password regime in part (2)?

To answer the questions above, you will need to do some programming and experimentation to measure how much time it takes to hash and store passwords to a dictionary file. We expect you to report how you went about this experimentation, including the kind of processor, machine, OS, etc.

Your answers for problems 1 and 2 should be broken into three parts:

1. A formula for calculating the amount of time.
2. Your measurements.
3. A final time estimate constructed from the previous two parts,

What to submit: a file named bruteforce.pdf with your answers to the above questions. You should also submit any relevant source code (and tell us under what filename to find it).

Evaluation: We will grade your answer based on its correctness and clarity. Flawed experimental designs may be penalized.

Problem 3

Many websites will indicate to users whether a new password they have chosen is strong or weak. See, for example, www.passwordmeter.com. Your task is to program your own password classifier that, given a password, classifies it as either strong or weak. (More nuanced classification—e.g., very strong, strong, weak, very weak—is possible, but we're just considering a binary classification here.)

You may use any heuristics that you want to build your classifier, including those we've covered in class as well as any you might discover by doing independent research. You may not, however, reuse any code or libraries. All the implementation must be your own. Any particular algorithms that you've identified by independent research must be attributed to their proper inventor in comments in your source code.

Specification:

• Your program's main method must be located in the default package and in a class named PasswordClassifier.
• We will compile your program from the command-line as follows:

  javac PasswordClassifier.java

  Your program is welcome to read in any auxiliary data from files that you supply along with it.

• We will execute your program by invoking it from the command-line as follows:

  java PasswordClassifier infile outfile

  where infile is a command-line argument specifying the name of an input file containing a list of passwords, and outfile is the name of an output file that your program should produce.
• Given an input file formatted like this:

  123456
  2984borawQ!
  iloveyou
  

  Your program should produce an output file formatted like this:

  123456, weak
  2984borawQ!, strong
  iloveyou, weak
  

We will evaluate your classifier by running it against n large test sets—T1,T2,...Tn—of passwords, which we have previously classified ourselves. Everyone's classifier will be evaluated against the same test sets. We will compare the classification you produce against the classification we expect. In our test sets, passwords will be generated in accordance with the material we studied on estimating and calculating the entropy of passwords: strong passwords will be generated in high-entropy ways, whereas weak passwords will be generated in low-entropy ways.

What to submit: a file named PasswordClassifier.java, along with any other supporting files it might need. Also submit a file named ClassifierDesign.pdf, describing the design of your classifier (i.e., how it ascertains whether a password is strong or weak).

Evaluation: We will grade your answer based on how well it performs on our test set, and on the quality of your design. Also, this problem is a competition. Whoever turns in the best solution will receive a bonus of a full letter grade on this homework.

Problem 4

based on [Schneider, chapter 5, problem 5.16]

Tokens can be used to generate one-time passwords for authentication. One way to do this is to use hash chains. For this method, a token stores a unique secret s and a current index i. (We assume the token protects the confidentiality and integrity of those values in some way, which is left unspecified here.) It generates the following sequence of N one-time passwords using its secret and a hash function H as follows:

OTP(i) = H^N-i(s),

Alice can be authenticated by a system S using token T with the following protocol:

1. T → S: Alice requests authentication
2. S → T: prev_i
3. T:
   • i = max(i, prev_i) + 1
   • if i > N then halt (cannot generate anymore passwords!)
     else
     • otp = H^N-i+1(s)
     • T → S: Alice, i, otp
4. S: if prev_i < i ∧ H^i-prev_i(otp) = prev_otp then
   • prev_i = i
   • prev_otp = otp
   • Alice is authenticated

Answer the following questions about the protocol:

1. Suppose the token instead generated one-time passwords as follows:

   OTP(i) = H(i, s).

   Rewrite the protocol above to use that construction of one-time passwords. How does your new protocol compare to the original? Your comparison should mention one or two strengths and one or two weaknesses of the new protocol.
2. Suppose the token instead used a clock to generate one-time passwords, as follows:

   OTP(i) = H(time, s).

   (You do not need to rewrite the protocol for this part of the question.) What are the comparative strengths and weaknesses of using time vs. indices? When might you prefer to use the hash-chain method for generating one-time passwords vs. the clock-based method, and vice versa? (No essays please—a well-written paragraph will suffice.)

What to submit: a file named tokens.pdf with your answers to the above questions.

Evaluation: We will grade your answer based on its correctness and clarity.

Submission

Include your name and NetID as a header in every file For type-set solutions, use 10 point or larger type, start your solution to each problem on a separate page, and restrict your solution to at most one page for every problem.

Bundle all the files you need to submit into a single .zip file named hw3.zip. Submit that file to CMS.

Submissions that do not adhere to the requirements stipulated here will lose points.