Cryptographic scenarios

File: crypto-scenarios.txt/md/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

0 - author name(s) (but do it anyway!) 14 - 2 points per numbered item below

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 name 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 (e.g., 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 from which they derive an AES 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 (we'll use "secret" and "private" interchangeably when talking about these keys). Denote Alice's key pair as (P_A, S_A), Bob's as (P_B, S_B), etc.

For encryption and decryption with the public and secret keys, use the function E. 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 in practice, public key encryption is generally used for short messages (e.g., to encrypt a hash function digest), mainly because it is much slower than symmetric encryption.

Unless otherwise instructed, you may assume that everybody has a correct copy of everybody else's public key, and that they have all kept their private keys secret. 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 scenarios below, 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 an adversary-in-the-middle (AITM) attack.

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 AITM is impossible.
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.
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 AITM is impossible.

Questions about breaking security

In the following, the symbol || represents concatenation. For example, if X and Y are 4-byte integers, then X || Y is the 8-byte quantity consisting of X followed by Y. Or "dog" || "house" is the string "doghouse". We won't worry about issues like byte-order or encoding schemes for this assignment.

Consider a scenario where Alice and Bob have been in contract negotiations and sharing documents electronically along the way. 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. Here, C contains some indication that Alice has agreed to the contract—e.g., if C is a PDF file containing an image of Alice's handwritten signature. Sig, on the other hand is a digital signature, as described at 9:23 or so of the Cryptographic Hash Functions video.

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.)
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.
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?
Finally, list at least two ways the certificate-based trust system from the previous two questions could be subverted, allowing Mal to convince Alice that Mal is Bob.