CS 231: Computer Security

Cryptographic scenarios

Folder: cryptography
File: cryptography/scenarios.txt or cryptography/scenarios.pdf

Please work with one or two partners for this assignment. See this survey to let me know whether you want me to assign you a partner.

What you have to work with

Suppose Alice, Bob, Eve, Mal, and all their friends and enemies have access to the following.

• A symmetric encryption algorithm (e.g. AES). Use the function S to represent this, so SK(M) is the message M encrypted using the key K. If you need to represent decryption, use a -1 superscript to indicate inverse. For example, SK-1(SK(M)) = M. (Note that before Alice and Bob can use this algorithm, they have to agree on a key K, which is not automatically provided to them.)

  This notation conflicts with the use of S below to represent a secret key. This was the result of shifting to the E notation I started using for public-key cryptography this time without thinking through how that affected all the other pieces of this assignment. So next time, let's say AES(K, M) instead of S_K(M)

• A Diffie-Hellman key exchange procedure. If you want to use this, just say "Alice and Bob use Diffie-Hellman to agree on a shared secret key K" or something like that.
• A cryptographic hash function H (e.g. SHA-256). Represent the hash of a message M by H(M).

• Public/secret key pairs (P, S) for everybody.

  We will use the encryption/decryption function E and subscripted P's and S's to indicate various operations involving the public and secret keys. For example, if M is a small enough message to be in the domain of E, then Bob can send an encryption of M to Alice by sending her the ciphertext C:

  C = E(PA, M)
  where PA is Alice's public key. Then Alice can compute:
  E(SA, C) = E(SA, E(PA, M)) = M
  to retrieve M, where SA is Alice's secret key.

  Keep in mind that public key encryption is used in practice exclusively for short messages (e.g. hash function digests).

  You may assume that everybody has a correct copy of everybody else's public key, and that they have all kept their private keys private. This assumption is a big one—exchanging public keys safely is a hard problem (solved, more or less, by the complicated system of certificates that we use now, which will be the subject of a future assignment).

The Scenarios

For each of the following scenarios, describe as concisely as you can how you would use the tools listed above to achieve the goals described in the scenario. Then, briefly explain why your plan achieves those goals.

Make your plans as simple as possible given the goals of the scenario. You might be able to come up with a single plan that handles all the scenarios, but that's not what I'm after. I want you to understand the properties of Diffie Hellman, RSA, cryptographic hashes, digital signatures, etc. By responding to each scenario with the simplest plan using the available tools, you'll demonstrate that understanding.

We'll use Eve to refer to any eavesdropper, and Mal to refer to any person attempting a person-in-the-middle attack.

1. Alice wants to send Bob a long message, and she doesn't want Eve to be able to read it. (I say "Eve" here because I want you to assume for this scenario that person-in-the-middle is impossible, and give an answer that is as simple as possible under that assumption.)
2. Alice wants to send Bob a long message. She doesn't want Mal to be able to intercept, read, and modify the message without Bob detecting the change. Next time, change "intercept, read, and modify" to "modify". For this one, I don't care if Mal can read the message. I just want Bob to be able to detect modification. So to be absolutely clear, I should remove the word "read" from this description. And the word "intercept" is pretty much redundant with "modify", so let's remove it, too.
3. Alice wants to send Bob a long message, she doesn't want Eve to be able to read it, and she wants Bob to have confidence that it was Alice who sent the message. (Again, don't worry about Mal and person-in-the-middle here.)
4. Alice wants to send Bob a long message (in this case, it's a contract between AliceCom and BobCom). She doesn't want Eve to be able to read it. She wants Bob to have confidence that it was Alice who sent the message. She doesn't want Bob to be able to change the document and claim successfully in court that the changed version was the real version. And finally, Bob doesn't want Alice to be able to say in court that she never sent the contract in the first place. This one needs to be rewritten. It's good to introduce repudiation concerns here, but do we care about Mal? And if not, then how is this one different from #3?