SI 540: Fall 1999

HW 10

due December 6

Last modified 12/1/99 --PR
Class home page

You can do this assignment in pairs, but not in groups larger than two.


15.3, 16.2-16.3, 17.1-17.3

Reading on load balancing from HotWired.

Text exericses

Let me review the textbook's notation here for your use in answering the following questions. Label any operation performed by the sender as an "encryption" operation, with a capital E, whether that operation is a signature (using a private key) or an actual encryption (using a public key or a shared key). Any operation performed by the receiver we'll call a decryption operation, with a capital D, whether that operation is verifying a signature or actually decrypting a message. The subscrip will indicate whose key is used and, for public key systems, whether it is the public or the private part of the key pair that is used. For example EASK(M) is encryption of the message M using Alice's secret key: this creates a signature on the messaage M.

  1. (1 point) Suppose that Alice sends the message M and the signature EASK(M) to Bob. What does Bob do to verify that the signature is valid?
  2. (1 point) Suppose that Alice wants to send a message M to Bob so that it is both confidential and non-repudiable. What should she send to Bob and what should Bob do with what he receives?
  3. (2 points) Suppose you are going to design and market a "fingerprint recognizer" to authenticate users over a network. A hardware device would scan the user's finger (or thumb) and send a bitstring representation to another user, where it would be compared to a fingerprint already on file. An obvious problem you have is to avoid an imposter intercepting the transmission, saving it, and resending it at a later time when that person is no longer present. Devise a protocol for authentication based on fingerprints that is not susceptible to this problem.

Lab Exercises

C. Simon Says (4 points)

"Simon says" is a children's game played in the United States. A leader stands at the front and speaks commands like:

  1. Simon says stand up
  2. Simon says sit down
  3. Simon says put your right hand on top of your head
  4. Take your hand off your head

Everyone in the audience is supposed to follow the leader's commands, but only if it is prefaced by "Simon says". Anyone who fails to follow commands 1-3 loses the game. Anyone who does follow command 4 loses the game.

Our version is a little different, so pay attention. The userID "Simon" initially has Simon privileges. You should follow any instruction that is signed by Simon's key. An instruction will tell you one or more of the following:

First, download the zipped file and unzip it in a directory accessible to you from your UNIX prompt. You should have the following files:


You should initially trust that the key in simonkey.txt is associated with the initial userID "Simon". Here's some further information about the key:

To be really safe, you should check this against the "key fingerprint" I wrote on the whiteboard in class. That way, you can be sure that one of your classmates has not broken into the web server and changed this document to make her own key appear to be Simon's. One semester someone impersonating Simon made all the students write that they disliked the professor of SI540 and you certainly wouldn't want to say something like that by mistake. (Actually, I forgot to put this information up on the whiteboard in class, so you'll have to take risk that the fingerprint listed in this file is correct.)

You will need to add the Simon key to your ring and certify that the key really belongs to the user "Simon".  To initiate this command, type:

login% pgp -ka simonkey.txt

If prompted, you should tell PGP not to treat Simon as an "ultimately trusted introducer", which is a status reserved for your private key. You should, however, indicate that you always trust Simon to introduce other people's keys to you   (this is analogous to saying that you trust Simon as a CA).

By the way, the relevant portion of the PGP documentation for understanding the relationship between certification, trust, validity, and introducers is titled "How Does PGP Keep Track of Which Keys are Valid?". In brief

  1. Certifying a key means signing it with your private key. If you sign it, you are vouching that the key belongs to the person/identifier it is bound to.
  2. An introducer is someone who certifies a key-id binding.
  3. A *trusted* introducer is someone who you trust to certify key-id bindings (i.e., you think they always verify that the key belongs to the id before certifying).
  4. The *ultimately trusted* introducer is you (or, more accurately, your key).
  5. A key-id binding is valid if it is certified by a trusted introducer or by the ultimately trusted introducer.
  6. A signature is "good" if the decrypted signature matches the accompanying plaintext. A signature may be good, but you may still not trust the message if you're not sure who the signing key belonged to.

You will need to add keys from the keyring file, keys.txt. The file is signed with Simon's key, so first decrypt it:

login% pgp keys.txt

You may be prompted to add the keys to a keyring. If not, you'll need to separately add them to a keyring:

login% pgp -ka keys.txt [keyring]

Simon's Instructions

Next, take a look at the 9 instruction files. Based on what's in them, and whether you think they're valid according to Simon's instructions, decide what text to include in the homework you turn in. For each of the 9 instruction files, say why you ignored it or followed its instruction.

Explanation exercise (2)

Explain the idea of public-key encryption to someone else, making sure to explain what's public about it.