UPDATES IN RED

Homework 2, Due Feb 5, 11am

  1. This problem is focused on explaining why it is important to target security against chosen-plaintext and chosen-ciphertext attacks.

    1. Give an example scenario justifying the need for security under chosen-plaintext attacks in this scenario.
    2. Give an example scenario justifying the need for security under chosen-ciphertext attacks in this scenario.

  2. Suppose Bob receives a message signed using a digital signature scheme with Alice's secret signing key. Does this prove that Alice saw the message in question and chose to sign it?

  3. Suppose you have a processor that can perform a single DES encryption or decryption operation in 2-26 seconds. Suppose you also have a large number of plaintext-ciphertext pairs for DES under a single, unknown key. How many hours would it take, on average, to find that DES key, using an exhaustive search approach and a single processor? How many hours would it take, on average, to find that DES key, using an exhaustive search approach and a collection of 214 processors?

  4. Using an existing cryptography library, decrypt the following ciphertext (in hex)
    53 9B 33 3B 39 70 6D 14 90 28 CF E1 D9 D4 A4 07
    with the following 256-bit key (also in hex)
    80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01
    using AES.

    Turn in both your answer to this question, and your source code.

  5. Let P1,P2 be a message that is two blocks long, and let P1' be a message that is one block long. Let C0,C1,C2 be the encryption of P1,P2 using CBC mode with a random IV and a random key, and let C0',C1' be the encryption of P1' using CBC mode with a random IV and the same key. Suppose an attacker knows P1,P2 and suppose the attacker intercepted and thus know C0,C1,C2 and C0',C1'. Further suppose that, by random chance, C1'=C2. Show that the attacker can compute P1'.

  6. Suppose you, as an attacker, observe the following 32-byte ciphertext C (in hex)
    46 64 DC 06 97 BB FE 69 33 07 15 07 9B A6 C2 3D 2B 84 DE 4F 90 8D 7D 34 AA CE 96 8B 64 F3 DF 75
    and the following 32-byte ciphertext C' (also in hex)
    51 7E CC 05 C3 BD EA 3B 33 57 0E 1B D8 97 D5 30 7B D0 91 6B 8D 82 6B 35 B7 8B BB 8D 74 E2 C7 3B.
    Suppose you know these ciphertexts were generated using CTR mode with the same nonce. The nonce is implicit, so it is not included in the ciphertext. You also know that the plaintext P corresponding to C is 43 72 79 70 74 6F 67 72 61 70 68 79 20 43 72 79 70 74 6F 67 72 61 70 68 79 20 43 72 79 70 74 6F. What information, if any, can you infer about the plaintext P' corresponding to C'?

  7. UPDATED: Consider SHA-512-n, a hash function that first runs SHA-512 and then outputs only the first n bits of the result. Write a program that uses a birthday attack to find and output a collision on SHA-512-n, where n is a multiple of 8 between 8 and 48. Your program may use an existing cryptography library. Try to make your program as efficient as possible. Time how long your program takes when n is 8, 16, 24, 32, 40, and 48, averaged over five runs for each n, and produce a graph with those timings (n on horizontal axis, time on vertical). How long would you expect your program to take for SHA-512-256? For SHA-512-384? For SHA-512 itself?

    Turn in your answers to these question and your source code. Also turn in a list of which messages collided, and the resulting hash values (in hex); i.e., you'd have 5 pairs of inputs and two 5 hash values for n=8 (which are equivalent in the first 8 bits), 5 pairs of inputs and two 5 hash values for n=16 (which are equivalent in the first 16 bits), and so on. Do your timings on a machine in the undergraduate lab. Tell us which machine you used (with "echo $HOSTNAME" since some hostnames, like attu, actually correspond to multiple machines) and the load (with "uptime") prior to your experiments.

  8. Using an existing cryptography library, compute the MAC of the message
    4D 41 43 73 20 61 72 65 20 76 65 72 79 20 75 73 65 66 75 6C 20 69 6E 20 63 72 79 70 74 6F 67 72 61 70 68 79 21
    using HMAC with SHA-256 and the key
    0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b.

    Turn in both your answer to this question, and your source code.

  9. Suppose A and B are both one block long, and suppose the sender MACs A, B, and (A||B) with CBC-MAC. Here || denotes string concatenation. An attacker who intercepts the MAC tags for these messages can now forge the MAC for the message (B || (M(B) xor M(A) xor B)), which the sender never sent. The forged tag for this message is equal to M(A||B), the tag for (A||B). Justify mathematically why this is true.

  10. Extra credit. Watch a movie that is somehow related to computer security, broadly defined. Tell us: what movie you watched and how it is related to computer security. Then discuss your reactions to the movie from an informed perspective of computer security. Your discussion might touch on (but is not limited to) the following questions: Does the movie accurately represent real computer security issues? Were the threats and issues raised in the movie realistic? What would you have done differently if you authored the movie?

    Please use the forum if you wish to brainstorm with others regarding possible movies.

For the crypto implementation problems, you might consider using OpenSSL (from C) or the latest cryptography packages in Java. If you're using OpenSSL on a Linux machine, you'll need to link with the OpenSSL library, e.g., "gcc -o your_code your_code.c -lcrypto".