Assignment 8, due Apr 9

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: The Diffie Hellman algorithm can be used for a kind of public key cryptography as follows: Each participant i picks a private key pr_i which they do not disclose from which they compute the public key pu_i which they publish. To encrypt a message from participant i to j, user i computes k_ij=f(pr_i,pu_j). To decrypt this message, user j computes k_ij=f(pr_j,pu_i). Both users use k_ij as the key for an agreed-on symmetric-key cryptosystem.

   In the RSA system, each participant i picks a private key pr_i which they do not disclose from which they compute the public key pu_i which they publish. To encrypt a message from participant i to j, Messages encrypted with pu_i can only be decrypted with pr_i, and messages encrypted with pr_i can only be decrypted with pu_i.

   Both cryptosystems allow secure communication between users i and j, but they have some different properties. Suppose user i wishes to send user j a secret message under the RSA algorithm, with an assurance that only user i could possibly have sent the message and only user j can decrypt it.

   a) How do we do this under the RSA algorithm. (0.5 points)

   b) How do we do this using the approach to Diffie-Hellman key exchange outlined above. (0.5 points)

   c) Suppose, with both schemes, that the message being transmitted has been compressed so that, by the time it is encrypted, it is indistinguishable from a random bit pattern. What problem does this pose? (0.5 points)

   d) (0.5 points) If the public and private keys used with the Diffie Hellman and RSA systems are identical in length, n bits, which system is more secure? Why?

2. Background: You are running an election system such as RIES where the security and authenticity of the codebook used in the election is extraordinarily important. After the ballot box is published, opposition parties could compute codebooks that decrypt the ballots in a way that lets them win. So, you need to be able to prove which codebook is authentic. Before the polls close, a dishonest person getting a copy of the codebook could use it to stuff the ballot box. Each of the following mechanisms might be helpful in preventing one or the other of these threats. For each, determine which goals it supports and where it fails.

   a) Encrypt the codebook with a symmetric key cypher before the election, then divide the key into segments and give each segment to a leader of one political party. At the close of the election, the party leaders must all cooperate to decrypt the codebook. (0.5 points)

   b) Compute a secure hash function (a one-way function) of the codebook and publish the hash in the newspaper before the election. (0.5 points)

   c) Use RSA. Specifically, encrypt the codebook with the government's private key and publish the public key in the newspaper before the election. (0.5 points)

   d) Use RSA. Specifically, encrypt the codebook with the public keys provided by each political party (in alphabetical order, by party name), and then, after the polls close, let each party, in turn, decrypt the codebook with its private key.

3. Background: One vendor of thumb drives sells a thumb drive with the following characteristics: When you insert the thumb drive in the USB port of a windows computer, it appears to be a hub with two devices connected to it: Device a is a normal storage device with a normal file system on it. Device b is a read-only file system with one file, an "execute on mount" application. This application is a special USB driver for device a. It opens a dialog window on the screen, asks for a password, and then passes that password to the thumb drive, which then uses that password to as an encryption key for all data written to or read from device a. Assume that the cryptosystem used for device a is actually secure.

   a) Suppose you were a malware author intent on writing a "spearphishing" attack on a user who is known to use such devices. Describe the malware you might attempt to inject in computers they are known to use aimed at learning the passwords they use with this device. (0.5 points)

   b) Suppose you are the vendor of this drive, and you realize that you could make lots of money on the side if you could break into encrypted drives. What undocumented firmware features could you install in the thumb drive to allow you free access to the data. (0.5 points)