University of Virginia, Department of Computer Science
CS588: Cryptography, Spring 2005

Problem Set 1 Out: 20 January 2005
Due: 3 February 2005
(beginning of class)

Collaboration Policy

You may discuss these problems with anyone you want. You should not take any written artifacts out of those discussions, however. You must write up your answers independently, and understand completely everything you turn in. Working together means discussing the questions and criticing possible solutions; it does not permit splitting up questions in a group.

You may consult any outside resources you wish including books, papers, web sites and people; the only resources you may not use without explicit permission are materials from previous offerings of this couse. If you use resources other than the class materials, indicate what you used along with your answer.

Problem set answers may be hand-written, but only if your hand writting is neat enough for us to read it. For full credit, answers must be clear, elegant and concise.

1. Security Principles

a. (5) Use two examples from the Feynman story, Safecracker Meets Safecracker to illustrate the tradeoff between security and convenience.

b. (5) What (if anything) should the army have done differently?

c. (5) Describe a realistic scenario in which a protocol that is insecure under the Dolev-Yao threat model could be securely used?

2. Critters in the Middle

There is a problem with this question. It is removed from PS1.
Suppose Alice and Bob know each other's public keys, and want to agree on a shared symmetric encryption key. Slimey Sally suggests they use the following four-step key agreement protocol (based very loosely on the Needham-Schroeder shared key protocol):

1. A → B: EKUB(A, NA)
2. B → A: EKUA(NB, B, kB)
3. A → B: EKUB(A, kA)
At this point, both A and B can compute K ≡ kA XOR kB.
4. B → A: EK(NB)
Notation
NA — Alice's nonce
NB — Bob's nonce
KUA — Alice's public key
KUB — Bob's public key
kA — partial symmetric key (generated randomly by A)
kB — partial symmetric key (generated randomly by B)
K — K ≡ kA XOR kB (the final shared symmetric key)
After receiving the message from B in step 4, A decrypts the message received and checks that the value matches NB. If it doesn't, B worries that the protocol was compromised and does not trust K. Otherwise, B assumes K is a valid, secret key shared with A.

a. (10) Suppose Sally is an active attacker (with the characteristics of Malice in the Dolev-Yao threat model). Explain clearly how Sally can trick Bob into estalishing a key Bob thinks is shared with Alice, but is actually shared with Sally.

b. (10) Suggest a change to step 4 in the protocol (and no other steps) that prevents the attack in part a. Argue convincingly that the modified protocol is secure against an active attacker.

3. Bad Beats

Alice and Bob are playing an apparently friendly (but high-stakes) game of Texas-Hold-Em poker. In this game, each player is initially dealt two cards face down (called the "hole cards") from a 52-card deck (4 suits, 13 ranks in each suit). Then after a round of betting, three community cards are dealt face up (this is called the "flop"). After another round of betting a fourth (the "turn") community card is dealt, followed by another round of betting and a final (the "river") community card. At the end of the hand, each player makes the best possible five-card hand using their hole cards and the community cards (it is not required that a player use any of their hole cards; for example, both players could make the same best possible hand using the 5 community cards, and then the pot would be split).

For purposes of this question, we only consider two kinds of hands:

A full house beats a flush.

a. (5) After both players hole cards are dealt but no other cards, Alice has the Ace of Hearts and 6 of Hearts. What is the probability Alice will make a flush on the flop (the next 3 cards revealed)?

b. (5) What is the probability Alice will make a flush by the end of the hand?

c. (5) Suppose the flop is KH 7C 7H and the turn is 3H. After the turn, Bob goes all in (bets all his chips) and Alice calls. Bob reveals at KD 3S (giving him 2 pair which would lose to Alice's flush). What is the probability Bob wins the hand (by making a full house) on the final card?

d. (10) During the course of many days of uninterrupted poker play, Alice and Bob get into the same situation 10 times where Alice has a flush after 4 cards and Bob has 2 pairs needing to make a full house. How many times should Alice expect her flush to be out-drawn?

4. Entropy

a. (5) (Based on Exercise 7.3 in the text.) Prove the entropy of source SP corresponding to a plaintext message is the same as the entropy of the source SC corresponding to the ciphertext resulting from a simple (monoalphabetic) substitution cipher.

b. (10) How much information can be transmitted with perfect secrecy using symbols from the English alphabet (26 letters) with a transposition cipher with block size 8 and a permutation choosen randomly from all possible permutations?

5. Two-Time Pads

Begining in the 1940s, the Soviet Union communicated with KGB agents using a cryptosystem that involved first encoding the message using a codebook, and then encrypting the result using a one-time pad. This should have been perfectly secure, except they made mistakes in constructing the one-time pad key and reused segments of the key. The VENONA project of the Signal Intelligence Service (later the NSA) successfully decoded many of these messages.

a. (10) Prove that a two-time pad is not a perfect cipher (that is, it is not information-theoretically secure). Assume the key K is perfectly random. The key is used to encrypt two messages M1 and M2, giving the attacker C1 = M1 XOR K and C2 = M2 XOR K.

b. (20) Ben Bitdiddle has foolishly used the same one-time pad to encrypt two messages. You have intercepted these two ciphertexts:

Knowing Ben's fondness for obscure quotations, you suspect both the message are quotations in English. It would be safe to assume that the message was encoded using 7-bit ASCII (A = 65 = 1000001, Z = 90 = 1011010, a = 97, z = 122, space = 32).

You may find this program (which we used to create the encodings) helpful: http://www.cs.virginia.edu/cs588/ps/ps1/Pad.java.

What is the message corresponding to C1? (Explain your approach to decrypting the message and include any code you wrote in your answer. Even if you are not able to break the message, you will receive partial credit for describing a reasonable approach.)

6. Padding Cakes

Maury Bond, Secret Agent 000, wants to give the directions to the super ray gun to his colleagues Sly McCraken, Cript O'Hacker and Trey Tor. The message M is n-bits long. He suspects one of them may be a double agent, so he divides the message as follows: a. (5) How can Sly, Cript and Trey determine M?

b. (10) Is the scheme secure? Argue convincingly that either (1) it is secure - no two people can determine any bit of M with probability greater than 1/2; or (2) is it insecure - two peoople can conspire to determine a bit of M with probability greater than 1/2.

c. (10) Sly, Cript and Trey gather in Borneo to combine their messages and track down the super ray gun. Sly reveals K_1, Cript reveals K_2, and Trey reveals a n-bit random sequence. They combine the keys to determine M, but a meaningless bit sequence results. Sly and Cript leave the island befuddled, while Trey uses K_1, K_2 and C (which he kept to himself) to construct M and locate the super ray gun for himself. What could be done to prevent this?

7. Feedback

Your answers to these questions are optional and will not effect your grade in any way, but may help the course staff improve future problem sets.

a. How long did you spend on this problem set?
b. Did any problem seem unfairly hard?
c. Did any problem seem like too much tedious work?

CS 655 University of Virginia
Department of Computer Science
CS 588: Cryptology - Principles and Applications
 cs588–staff@cs.virginia.edu