CS 341: Cryptography

Exam

Due 11:59PM Friday, March 4. Write up your answers in .txt, .doc(x), or .pdf form, and put this document in a folder called "exam" along with any relevant code or data, and hand in the exam folder via the Courses hand-in system.

This is an open-book, open-Internet, open-library takehome exam. You may not consult with any person other than me (Jeff Ondich, to be precise) about this exam.

  1. (6 points) Suppose we need a block of bytes to be a multiple of 8 bytes long before processing. To achieve this goal, we pad our message M with a pad of between zero and seven null bytes in order to make len(M||pad) mod 8 == 0 (where || means concatenation). Describe simply and in detail an example that shows why this padding scheme is a bad idea.

  2. (10 points) The other day, Rich Graves seemed quite fond of salt. If you haven't already done so, read Password Security: A Case History, Morris and Thompson, Communications of the ACM, 1979.

    1. What is salt?
    2. When and where is it generated?
    3. Where is salt stored?
    4. When, if at all, is salt transmitted over the network? If it is transmitted over the network, is it encrypted?
    5. Describe as clearly and simply as you can an attack that salt is intended to thwart. What affect on this attack does a two-byte salt have? How about eight bytes?

  3. (8 points) In RSA, we start the whole game by choosing large prime numbers p and q. Then, from p, q, n = p*q, and some small prime number e, we compute d and we're off to the races. But when we use Rabin-Miller, there's a small chance that we'll end up with a p or q that isn't actually prime. Rabin-Miller is great, and as Schneier and his friends point out in the book, the likelihood of your dying while reading this sentence is way higher than the likelihood of getting a composite p or q out of properly implemented Rabin-Miller.

    But just for a few minutes, let's pretend that instead of getting nailed by a meteor, we actually did get a composite value for p. What effect would this have on the functioning of RSA? More specifically:

    • Would you be guaranteed to be able to find d?
    • If a suitable d exists, would decryption work?
    • For each of the above questions, either show an example where the answer is no, or provide a proof that the answer is yes. (Of course, for counter-examples, you should feel free to use small numbers.)

  4. (10 points) Alice is Bob's stockbroker. Since Bob makes lots of moves with his portfolio, they have worked out an electronic system by which Bob will request transactions. At lunch one day, they agree on a system of 10-byte messages like this: "+00250 IBM" (which means "buy 250 shares of IBM") or "-01500APPL" (which means "sell 1500 shares of Apple"). At that lunch, they also generate a 10-byte random key K to be used as a one-time pad. That is, when Bob wants to send Alice one of his 10-byte messages M, he will send M XOR K.

    Of course, Bob and Alice don't take the "one-time" part of "one-time pad" seriously, and they use the same K every time. And there's the usual eavesdropper, Eve, able to watch, intercept, and replace messages as they go by, if she feels like it.

    1. Can Eve determine which messages are buys and which are sells? If so, how? If not, why not?
    2. Suppose Bob only sends one message to Alice while Eve is in control of the line. If Eve knows somehow that the message is a buy order, can she change it to a sell?
    3. Same situation (just the one message gets sent), but now Eve doesn't know whether the order is a buy or a sell. Can she change it to the opposite order?
    4. Suppose Bob sends lots of orders. What can Eve do, if anything, to figure out the value of K, or a portion of it? Are there portions of K that might be easier than others to determine? (Suppose, for example, that Eve knows Bob is especially interested in technology companies.)

  5. (10 points) The group that presented on WEP last week mentioned the RC4 stream cipher. This exercise concerns RC4.

    1. Suppose I have a long-term key "Moose" (i.e. the five bytes with values 77, 111, 111, 115, 101) and a nonce "Mr" (77, 114), and I do the typical thing and obtain my RC4 key by concatenating them as MrMoose, or (77, 114, 77, 111, 111, 115, 101). Given this key, compute the RC4 ciphertext for the plaintext "ping-pong balls".
    2. As discussed in the "Biased Outputs of the RC4" section of the RC4 wikipedia page, Shamir and Mantin discovered a non-random output pattern for RC4. Write some code to enable you collect data to show this particular non-randomness in practice.
    3. Describe how this lack of randomness be turned into a practical attack on RC4-encrypted data.