CS 231: Computer Security

Cryptographic scenarios

You may work alone or with a partner.

Hand in by creating a folder named "scenarios" at the top level of your CS231 repository, and putting a .pdf or .txt file with your answers in that folder.

What you have to work with

Suppose Alice, Bob, Eve, 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.)

• Public/private key pairs for everybody. Instead of (n, e) and (n, d), use functional notation for this, with EA for public key encryption and DA for private key decryption. For example, if Bob wants to send an encrypted message to Alice, he will send her EA(M) and she will then compute DA(EA(M)) = M to read the message.

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

  In Part 1, 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). In Part 2, you will assume that you have access to the usual PKI consisting of certificates and certificate authorities.

• 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).

Part 1: 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.
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.

Part 2: can certificates thwart person-in-the-middle?

Imagine the following protocol:

1. Alice initiates Diffie Hellman with Bob, and they agree on an AES key K. All further communications are encrypted with SK.
2. Bob sends Alice his certificate (signed by a CA that Alice trusts).
3. Alice verifies the certificate.
4. Bob computes DB(K) and sends it to Alice.
5. Alice computes EB(DB(K)). If the result doesn't match K, she terminates the connection.
6. Otherwise, Alice and Bob continue to talk about whatever they want using AES with key K.

Let's pretend Mal is able to get a person-in-the-middle setup in place, so that when Alice tries to contact Bob, she actually contacts Mal. Mal may or may not choose to contact Bob--that's up to you. But of course, if Alice notices Mal failing to follow the expected protocol, she will either assume there's a problem on the network or realize that she's not talking to Bob; either way, she'll terminate the connection.

Answer the following questions.

5. What exactly does Alice do at step (c) to "verify" the certificate?
6. Suppose the protocol proceeds to step (b), at which time Mal sends Bob's actual certificate to Alice. Does the protocol make it all the way to (f) without Alice being aware she's not talking to Bob? (Hint: no.) Where does the protocol break down?
7. Suppose Mal creates a self-signed certificate connecting Mal's public key to Bob's domain. Does the protocol make it all the way to (f) without Alice being aware she's not talking to Bob? (Hint: no.) Where does the protocol break down?
8. Can Mal obtain a certificate from one of Alice's trusted CAs connecting Bob's domain to Mal's public key? If so, will this enable Mal to fool Alice into thinking she's talking to Bob?
9. Assuming Mal is unsuccessful at getting a forged certificate, can Mal involve Bob in the conversation in such a way as to fool Alice? Next time I use this problem, I would change "can Mal involve Bob..." to "can you think of any way for Mal to fool Alice into thinking she's talking to Bob when she's actually talking to Mal?" That is, the "involve Bob" idea seemed like I was pointing to something in particular, when I was just trying to get the students to discuss the question of whether Mal has a prayer here. This section of this assignment is part of my on-going effort to get the students to dig into the question of how (and to what extent) our certificate-based PKI thwarts person-in-the-middle attacks. I've tried having them analyze SSH, but the specs are complicated and wireshark is no help since most of the protocol happens after encryption begins.