CSC 580: Cryptography and Security in Computing

A printable PDF is available.

Homework 8 – Due Tuesday, April 3

  1. Draw and label a picture that illustrates the Merkle-Damgard hash function construction. Make sure you clearly label the input to the hash function and the output (the hash value).

  2. Since a MAC is conceptually like adding a key to a hash function, let's try taking the key away from a MAC and seeing if it makes a good hash function. In particular, consider the Data Authentication Algorithm (sometimes called CBC-MAC) using DES, which is described in Section 12.6, where the input consists of an integer number of 64-bit blocks: D1,...,DN. We then "take away" the key by setting it to zero, and computing
    O1 = DES(0, D1)
    O2 = DES(0, D2 XOR O1)
       ...
    ON = DES(0, DN XOR ON-1)

    The hash output is ON. Is this preimage resistant? (Justify your answer, giving an attack algorithm if appropriate.)

  3. For the hash function in the previous problem, can you find collisions efficiently (given D1,D2,...,DN can you find a different input that gives the same hash value)? (Justify your answer, giving an attack algorithm if appropriate.)