2) Security of Cryptographic Hash Functions and Their Secure Use in Applications (see hash functions slide, and remember in-class discussions): a. What is the birthday attack against hash functions? Given an n-bit hash output, mathematically formulate the upper bound of collision probability of it. Specifically, write how the birthday paradox is formulated. You can use approximations if needed. You need to provide mathematical proof to receive credit, simple verbal descriptions receive no partial credit. b. In slides 10-14, we discussed 4 levels/types of security for the hash functions. i. What are rainbow tables in computer security? Briefly describe them and explain which types of hash functions among these types are used for rainbow tables ii. Among these four levels, one of them achieves the highest level of security against collusion attacks. Given the n-bit hash, and a similar size auxiliary input that it requires, what is the collusion probability at that level compared to the birthday attack against level other three levels? c. HMAC construction. (i) What is HMAC, write its formula. (ii) Why it is important to follow a specific padding mechanism (as opposed to the basic concatenation of the key) in HMAC construction when the MD approach discussed in the class is used?