Cryptographic scenarios

File: cryptography/scenarios.txt (or .pdf)

Work alone or with one partner.

Goals

• Think through the typical uses of the cryptographic primitives we have studied so far.
• Think through some of the ways that even in the presence of great math, our cryptographic protocols can be vulnerable.

Rubric

Assumptions

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

• The symmetric encryption algorithm AES. Use the function AES to denote this: AES(K, M) is the message M encrypted using the key K. To denote decryption of the ciphertext C, use AES_D(K, C). Assume everyone has agreed on a suitable block cipher mode (say, CBC).

  Don't forget that before Alice and Bob can use this algorithm, they have to agree on a key K, which is not automatically provided to them.

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

• The cryptographic hash function SHA-256. Represent the hash of a message M by H(M).

• Public/secret key pairs (P, S) for everybody. Denote Alice's key pair as (P_A, S_A), Bob's as (P_B, S_B), etc.

  Use the encryption/decryption function E to denote 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 = E(P_A, M). Then Alice can compute E(S_A, C) = E(S_A, E(P_A, M)) = M to retrieve Bob's message.

  Keep in mind that public key encryption is used in practice exclusively for short messages (e.g., to encrypt a hash function digest).

  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, as we have started to see in our initial investigations of certificates.

Simple communication 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, symmetric encryption, public-key encryption, 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 (PITM) attack.

1. Alice wants to send Bob a long message, and she doesn't want Eve to be able to read it. Assume for this scenario that PITM is impossible.

2. Alice wants to send Bob a long message. She doesn't want Mal to be able to modify the message without Bob detecting the change.

3. Alice wants to send Bob a long message (in this case, it's a signed contract between AliceCom and BobCom), 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. Assume for this scenario that PITM is impossible.

Questions about breaking security

4. Consider scenario #3 above. Suppose Bob sues Alice for breach of contract and presents as evidence: the digitally signed contract (C || Sig) and Alice's public key P_A. Suppose Alice says in court "C is not the contract I sent to Bob". (This is known as repudiation in cryptographic vocabulary.) Alice will now need to explain to the court what she believes happened that enabled Bob to end up with an erroneous contract. List at least three things Alice could claim happened. For each of Alice's claims, state briefly how plausible you would find the claim if you were the judge. (Assume that you, the judge, studied cryptography in college.)

5. For this scenario, suppose the assumption that everybody has everybody else's correct public keys is no longer true. Instead, suppose we now have a certificate authority CA, and that everybody has the correct P_CA (i.e. the certificate authority's key). Suppose further that Bob sent his public key P_B to CA, and that CA then delivered to Bob this certificate:

   Cert_B = "bob.com" || P_B || Sig_CA

   In terms of P_CA, S_CA, H, E, etc., of what would Sig_CA consist? That is, show the formula CA would use to compute Sig_CA.

6. Bob now has the certificate Cert_B from the previous question. During a communication, Bob sends Alice Cert_B. Is that enough for Alice to believe she's talking to Bob? (Hint: no.) What could Alice and Bob do to convince Alice that Bob has the S_B that goes with the P_B in Cert_B?

7. Finally, list at least two ways this certificate-based trust system could be subverted, allowing Mal to convince Alice that Mal is Bob.