COS 109: Problem Set 8     (Last one!!)

Mon Nov 13 09:39:32 EST 2023

Due midnight Wednesday November 15

Problem set answers need not be long, merely clear enough that we can understand what you have done, though for computational problems, show enough of your work that we can see where your answer came from. Please type your answers if at all possible. Thanks.

Don't forget that if the data you start with is approximate, the results cannot be precise.

1. Bits, Bytes, Binary

(a) The image below comes from a short-lived Wendy's advertisement. List all the positive integer pairs of x and y for which xy is 256.

(b) Assuming that the options are simple alternatives like "do you want cheese or not?", what's the most likely number of options that a customer is offered?

(c) A home wi-fi router acts as a NAT. It usually uses the IPv4 address range to internally, assigning a unique IP address in this range to each device in the home. In principle, how many devices could this range support? Express it as a power of 2.

(d) Old versions of Excel supported a maximum of 65,536 rows; columns were labeled A, B, ..., Z, AA, AB, ..., through IV. Give a plausible explanation of why the last column has the label IV.

2. What's Your Password?

One major problem with secret-key cryptographic systems (which we will cover in class soon) is the proliferation of keys if various information is to be shared among different independent combinations of people.

For this problem, a "key" is just "a password" that is potentially shared with other people.

(a) Suppose that Alice, Bob and Carol have a relationship in which

How many different passwords do they need in total? List the passwords by the people who will share them.

(b) Suppose that David joins the group, and relationships are even more complicated: they need passwords for each individual and each possible combination of private conversations among subgroups (e.g., Alice, Carol and David want to be able to talk among themselves while excluding Bob) as well as excluding outsiders from all combinations. How many different secret passwords are now needed? List the passwords by the people who will share them.

(c) As the group grows, more and more passwords will be needed. Give a general formula or way to express how the number of passwords varies as a function of N, the number of people in the group. If you don't see a formula, then give the numbers you have computed, for 1 through 6 people.

(Hint: figure out how many passwords are needed for one person, for two people, and so on up to five people, combine that with what you did above, and look for a pattern.)

3. Password Cracking

It's possible to crack passwords by a brute-force attack that just tries all possible passwords in some set.

(a) AOL used to generate initial passwords by joining two five-letter words with a colon ":", such as "cheap:skate" or "tiger:tunes". Suppose that AOL's list has 10,000 5-letter words, and that all words are entirely in lower case. How many passwords does this scheme provide?

(b) One way to make AOL's original scheme more secure is to allow upper case as well as lower case anywhere in the words, and treat upper-case and lower-case letters as distinct (so that "Tiger:tunes" is not the same as "tiger:tunes"or "tigEr:TuNeS"). By what factor does this scheme increase the number of different passwords?

(c) How does the difficulty in cracking such passwords grow in proportion to the number of words in AOL's dictionary?


Please use this Google doc for your answers.

Submit your problem set in PDF format by uploading a file called pset8.pdf to Gradescope. You can submit as many times as you like; we will only look at the last one.