CS 257 - Problem Set 4

Assigned:Monday October 12
Deadline:Thursday October 29, 11:59pm

Reading

Mark Stamp, “Information Security: Principles and Practice”, Chapters 5 and 7.

Available at Yale as a licensed online book.

Deliverable

Create a pdf file yournetid.cs257hw4.pdf with your answers to the following questions. DO NOT include your name or netid in the file. You should use gradescope to submit your assigments.

Problem 1: (10 points) [Chapter 5, problem 1, page 153]

As discussed in this chapter, a cryptographic hash function must satisfy all of the following properties:
  1. Suppose that a hash function fails to provide compression but provides all of the other required properties. Give an application where a cryptographic hash function should be used, but where this hash function would fail to be useful.
  2. Repeat part a, but assume that all properties hold except for efficiency.
  3. Repeat part a, but assume that all properties hold except for oneway.
  4. Repeat part a, but assume that all properties hold except for the collision resistance properties.

Problem 2: (10 points) [Chapter 5, problem 8, page 155]

Consider a CRC that uses the divisor 10011. Find two collisions with 10101011, that is, find two other data values that produce the same CRC checksum as 10101011.

Problem 3: (10 points) [Chapter 5, problem 17, page 156]

Recall the online bid method discussed in Section 5.8.1.
  1. What property or properties of a secure hash function h does this scheme rely on to prevent cheating?
  2. Suppose that Charlie is certain that Alice and Bob will both submit bids between $10,000 and $20,000. Describe a forward search attack that Charlie can use to determine Alice's bid and Bob's bid from their respective hash values.
  3. Is the attack in part b a practical security concern?
  4. How can the bidding procedure be modified to prevent a forward search such as that in part b?

Problem 4: (10 points) [Chapter 5, problem 33, page 161]

Consider a "2 out of 3" secret sharing scheme.
  1. Suppose that Alice's share of the secret is (4,10/3), Bob's share is (6,2), and Charlie's share is (5,8/3). What is the secret S? What is the equation of the line?
  2. Suppose that the arithmetic is taken modulo 13, that is, the equation of the line is of the form ax + by = c (mod 13). If Alice's share is (2,2), Bob's share is (4,9), and Charlie's share is (6,3), what is the secret S? What is the equation of the line, mod 13?

Problem 5: (10 points) [Chapter 5, problem 37, page 122]

Suppose that you have a text file and you plan to distribute it to several different people. Describe a simple non-digital watermarking method that you could use to place a distinct invisible watermark in each copy of the file. Note that in this context, "invisible" does not imply that the watermark is literally invisible—instead, it means that the watermark is not obvious to the reader.

Problem 6: (10 points) [Chapter 7, problem 5, page 255]

Suppose that on a particular system, all passwords are 10 characters, there are 64 choices for each character, and the system has a password file containing 512 hashed passwords. Furthermore, Trudy has a dictionary of 220 common passwords. Provide pseudo-code for an efficient attack on the password file in the following cases.
  1. The password hashes are not salted.
  2. The password hashes are salted.

Problem 7: (10 points) [Chapter 7, problem 10, page 256]

Suppose all passwords on a given system are 8 characters and that each character can be any one of 64 different values. The passwords are hashed (with a salt) and stored in a password file. Now suppose Trudy has a password cracking program that can test 64 passwords per second. Trudy also has a dictionary of 230 common passwords and the probability that any given password is in her dictionary is 1/4. The password file on this system contains 256 password hashes.
  1. How many different passwords are possible?
  2. How long, on average, will it take Trudy to crack the administrator's password?
  3. What is the probability that at least one of the 256 passwords in the password file is in the dictionary?
  4. What is the expected work for Trudy to recover any one of the passwords in the password file?

Problem 8: (10 points) [Chapter 7, problem 20, page 259]

Suppose that you have n accounts, each of which requires a password. Trudy has a dictionary and the probability that a password appears in Trudy's dictionary is p.
  1. If you use the same password for all n accounts, what is the probability that your password appears in Trudy's dictionary?
  2. If you use distinct passwords for each of your n accounts, what is the probability that at least one of your passwords appears in Trudy's dictionary? Show that if n = 1, your answer agrees with your answer to part a.
  3. Which is more secure, choosing the same password for all accounts, or choosing different passwords for each account? Why? See also Problem 21.

Problem 9: (10 points) [Chapter 7, problem 27, page 260]

Suppose DNA matching could be done in real time.
  1. Describe a biometric for secure entry into a restricted facility based on this technique.
  2. Discuss one security concern and one privacy concern with your proposed system in part a.

Problem 10: (10 points) [Chapter 7, problem 37, page 263]

Suppose that a particular iris scan systems generates 64-bit iris codes instead of the standard 2048-bit iris codes mentioned in this chapter. During the enrollment phase, the following iris codes (in hex) are determined. 
User     Iris code
Alice    BE439AD598EF5147
Bob      9C8B7A1425369584
Charlie  885522336699CCBB
During the recognition phase, the following iris codes are obtained. 
User Iris code
U    C975A2132E89CEAF
V    DB9A8675342FEC15
W    A6039AD5F8CFD965
X    1DCA7A54273497CC
Y    AF8B6C7D5E3F0F9A
Use the iris codes above to answer the following questions.
  1. Use the formula in equation (7.1) to compute the following distances:

    d(Alice, Bob), d(Alice, Charlie), d(Bob, Charlie).

  2. Assuming that the same statistics apply to these iris codes as the iris codes discussed in Section 7.4.2.3, which of the users, U,V,W,X,Y, is most likely Alice? Bob? Charlie? None of the above?