Homework 4

Problem 1

Consider a face recognition system deployed at a casino. The goal is to detect known cheaters. Photos of these known cheaters are stored in a database that is shared between casinos. Suppose that 0.05% of all people who walk into a casino are cheaters. Suppose the system has a false positive rate of 0.8% (innocent people flagged as cheaters) and a false negative rate of 40% (cheaters not flagged as cheaters).

What is the probability that a person flagged by the face recognition system as a cheater is, in fact, innocent? Please show your work.

Problem 2

We created the following cryptogram using the RSA primitive. The public parameters are N = 33, e = 7. (In the slides we used a lower case 'n'.) To encrypt, 'A' is first encoded as a 1, 'B' as a 2, 'C' as a 3, and so on. Decrypt this cryptogram.

15 13 6 13 1 6 14 1 12 12 31 21 20 29 6 14 1 11 1 29 12 14 ?

Show how you compute the private exponent d by hand using Euclid's algorithm.

For the first three characters in the ciphertext, show how you decrypt them by hand.

Problem 3

For this problem, consider the Diffie-Hellman key exchange with N = 37, g = 17. Alice has private key x = 5 and public key X = 19; Bob has private key y = 23 and public key Y = 18. Alice sends X to Bob. Bob sends Y to Alice.

(a) Compute K = Y^x mod N by hand, showing your work.

(b) Compute K' = X^y mod N by hand, showing your work.

(c) Explain why DH provides a key agreement protocol -- why Alice and Bob end up deriving the same shared key (K = K').

(d) Explain why the above protocol provides a secure key agreement protocol when the parameters are very large. No proofs are necessary. Rather, describe the assumptions that are necessary in order to ensure that an attacker who only knows X and Y cannot efficiently compute K and K'.

(Although not part of the problem, recall that we will often hash the resulting values K and K' before actually obtaining the key that we will use with symmetric encryption.)

Extra Credit

Overview: For this extra credit problem, let's take a look at a real protocol: WinZip's new AE-2 encryption scheme. Here's the URL: http://www.winzip.com/aes_info.htm.

As a bit of background, WinZip is a nice company, and they do really care about the security of their product. But, as we've learned (and will continue to learn) in the context of lots of other protocols (e.g., early version of SSL, etc), security is hard to "get right."

There are numerous reasons why we consider WinZip in this homework. For example, the WinZip AE-2 design is relatively simple, and we've already covered all the material necessary to understand AE-2. Still, we can learn a lot by studying the advantages and disadvantages of AE-2.

NOTE: There are already security reviews of WinZip's AE-2 scheme online. Please do not read these before conducting your evaluations. As with much of this class, the goal is to practice thinking about security issues in the context of real systems. Looking at others' results first will spoil the insights you might gain from doing these evaluations -- and spoil the fun!

The Task: You are to pretend that you are a consultant, hired by WinZip, to evaluate the security of their new AE-2 encryption scheme. (For this assignment, you don't need to consider their AE-1 version, just the AE-2 version. The AE-2 version does not include a CRC in the Zip archive.)

Write-up structure:

• You should begin your writeup with a brief summary of how the system (WinZip with AE-2 encryption) works.

• Then describe the security goals, adversaries, and weaknesses of the system. Unlike the security evaluations on the blog, you are to find real weaknesses under the adversarial conditions that you specify. I.e., you should describe in precise detail how an adversary could actually violate the relevant security goals.

  For your writeup, please discuss each security goal / adversary / weakness together. I.e., don't start by presenting all your goals, then all your weaknesses. Rather, bundle together the corresponding goals, adversaries, and weaknesses.

For full credit, you should:

• Find three or more security problems (weaknesses). As noted above, you should describe how an attacker could exploit these weaknesses.

• One security problem must revolve around the use of self-extracting executables.

• One security problem must work under the following scenario. Alice sends an encrypted archive to Bob. The archive contains a single text file. Mallory (the attacker) modifies the archive in transit. When Bob decrypts/extracts the archive, the resulting text file looks like garbage. Then for some reason assume that Mallory can look at this resulting "garbage-looking" text file. (Maybe this involves some social engineering on Mallory's part. After all, the file looks like garbage, so Bob may just discard it in an insecure way, or even email it to his company's support office for debugging purposes.) In any case, show how Mallory can actually learn the entire contents of the original text file if he can obtain a copy of the garbage-looking extracted file.

Suggestions: The WinZip page above links to other pages describing the Zip file format, etc. To find three security issues, you really shouldn't need to dig through all these other references. Of course, you're welcome to read these other references if you'd like. Just remember that the Zip file format was designed a long time ago, and now there are many different compression modes, ranging from NONE to DEFLATE to AE-2 (even though AE-2 isn't a compression mode but an encryption mode). Also, if you don't have a copy of WinZip on your machine, I could email you a self-extracting (and possibly self-decrypting) executable. If you run this executable (and possibly enter a password), you should recover the file that I wanted to send you.