Assignment 7, due Mar 23

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated (usually a Friday), and unless there is what insurance companies call "an act of God" - something outside your control; the only exceptions to this rule will be by advance arrangement.

1. Background: Suppose Alice is an innocent computer user, and Bob is a corrupt policie official. Carol is a judge. Bob arrests Alice and confiscates her computer. He now needs to prove to Carol that Alice's hard drive contained illegal files in encrypted form.

   Bob asserts that Alice has been using a one-time pad to encrypt her files by exclusive-oring the files with material from the pad. Bob asserts that his cryptanalysts have broken her code and found the key.

   a) How can Bob's cryptanalysts create a page of the one-time pad that will decrypt some random file from Alice's disk in order to produce the required incriminating evidence. (Hint: They dan do this with any of Alice's files, so long as it is big enough.) (0.5 points)

   b) Carol went to law school because she was no good at math. What should Alice do to defend herself after Bob "decrypts" Alice's file using the key provided by his cryptanalysts? (0.5 points)

2. Background: The C-standard library function random is not known to be cryptographically secure (so far as I know), but it might be practical to replace it with a cryptographically secure pseudorandom number generator. Look up the man page for random and, using that information, answer the following questions.

   a) There are several ways to set the seed (initial state) of the random number generator. Explain why, for cryptographic applications, the srandom function should never be used. (0.5 points)

   b) How big a state array would you consider to be the minimum size for cryptographic applications? (0.5 points)

   c) Some versions of Unix/Linux (not the CS departmental server) have a special interface to random called srandomdev. This uses /dev/random (see man 4 random) as a source for the random number seed. Explain the comment from the srandomdev man page that "Note that this particular seeding procedure can generate states which are impossible to reproduce by calling srandom()..." (Quotation from an Internet copy of the man page will not answer this question -- you must infer what srandomdev does.) (0.5 points)

   d) What information is missing from the man page for random that you would need to know in order to use it to its full cryptographic potential. (0.5 points)

3. Background: Consider the problem of guaranteeing that some file remains unchanged as of some date by publishing a secure hash of that file in a newspaper of record.

   a) Why not just post the secure hash value to the web. (0.5 points)

   b) The web wayback machine, at www.archive.org, offers a service that is potentially as effective as publication in a newspaper of record. Pick some web site that is old (for example, homepage.cs.uiowa.edu, and examine how frequently it is archived by the wayback machine. From this, draw conclsions about the likelihood that newspaper publication will remain valuable. (0.5 points)

   c) What is the advantage of publishing your secure hash code in a want ad in the New York Times instead of in the Daily Iowan? Hint: It's not a matter of prestige, and it actually gives some newspapers another advantage over the web wayback machine! (0.5 points)

4. A Problem: How long should your password be in order to have a near absolute assurance that dictionary-based attacks on your password system would be unlikely to succede ever, no matter what breakthroughs are made in computer technology. If your password is an English word or phrase, does this make any difference? (Note that the entropy of English test is under 4 bits per character.) (0.5 points)