A way to deal with denial of service attacks and/ or brute force attacks, is to request a proof of work from the client machine. The purpose here, is to ensure that the client machine has to spend some computational resources, before your server does something. Suppose there is a server that accepts requests and processes them provided that they are accompanied by a valid proof of work. A valid proof of work is a pair (x,y) where y=H(x) and also y=H(clientIP) and (x different than client IP). Assume that the Hash function is small, in particular it has a 16-bit output and works on inputs of any size. The Hash function despite its small output has good cryptographic properties. Reply to the following questions:

a) How is it possible to exploit this protection mechanism so that multiple requests can be made and processed without performing a new proof of work for each request?

b) What kind of attack on the hash function is performed by an honest client machine?

c) What is the computational complexity of such an attack? (How many tries does the machine need to make in order to find the (x,y) pair on average?) Is such an attack computationally feasible? d) Suggest a way to improve this protocol and ensure that the exploit discovered in part a) cannot be exploited any more. On your solution you should ensure that the server does not have to keep any state for a client that wants to make a request.