Assignment 4: Due Wednesday, March 27

  1. Textbook, page 148, Exercise 4.7, parts a and b.

    Hint: Make sure you understand Construction 4.7 and why each part of the construction is needed. Each one protects against a particular weakness that the MACs in this problem are vulnerable to.

  2. An “error-detecting code” is a fixed-length code computed from a message, similar to how a MAC tag is computed from a message, and is designed to detect random errors in transmission. One of the most popular error-detecting codes is called a “Cyclic Redundancy Check,” with one important version abbreviated CRC32 since it produces a 32-bit error-detecting code. For this question, the actual CRC32 algorithm is irrelevant, but you need to know that for any messages m1 and m2, CRC32(m1 ⊕ m2) = CRC32(m1) ⊕ CRC32(m2) (mathematically, this means that CRC32 is “a homomorphism with respect to exclusive-or”).

    The original designers of security for 802.11 wireless ethernet (WiFi) created WEP (Wired Equivalent Privacy) with the goal of providing cryptographic protections. They knew that CRC32 wasn’t strong enough to protect against malicious adversaries, so they created a MAC by exclusive-or’ing the output of CRC32 with a value computed with a pseudo-random function F : {0, 1}n × {0, 1}* → {0, 1}32 with a random input. In particular, they created a canonical MAC in which the MAC function is computed using key k and message m as follows:

    • Select random 32-bit random r
    • Compute t := Fk(r) ⊕ CRC32(m)
    • Return the pair ⟨r, t⟩ as the tag

    Prove that this is not a secure MAC. This should follow from the fact that CRC32 is a homomorphism, and not from the length of the tag. (If the tag being so short bothers you, pretend that it is 256 bits long instead of 32 bits.)

  3. Textbook, page 149, Exercise 4.12

    Hint: This is a modified version of the proof to Theorem 4.8. Even though it is similar to the proof in the book, you need to write out the entire proof — don’t just talk about what changes, but rather give a full, self-contained proof.

  4. Textbook, page 191, Exercise 5.10

    Note: This is unfortunately a common way that people attempt to create a MAC, and it is totally insecure when used with a hash function built using the Merkle-Damgard construction, like MD5, SHA1, or SHA2. How common is it to mistakenly do this? If you look back at your textbook from CSC 581, you’ll see that the authors of that book actually used this insecure construction for a MAC in Section 1.3.4 (page 36). Ouch.

  5. Consider a fixed-length hash function (Gen, h) that takes inputs of length 2n and produces an output with length n that is fully-secure (collision-resistant, second-preimage resistant, and preimage resistant). Now consider a user that wants to use this hash function for inputs that are twice as long (4n bits). He decides that since the outputs of the hash function look random, and exclusive-or with random values produces a random value, he can just hash the two halves of the input separately and exclusive-or the results together. More specifically, he creates a hash function (Gen, g) that computes function g for a 4n-bit input value x by first chopping it into two 2n-bit pieces x1 and x2 (so x = x1 ∥ x2), and then gs(x1 ∥ x2) = hs(x1) ⊕ hs(x2).

    Is (Gen, g) collision resistant? Is it second-preimage resistant? Justify your answer (your justification needs to be clear, precise, and unambiguous, but you don’t need to write full mathematical proofs).