Question 5

Recall hash puzzles from Lecture 10. In this question, we will see how they work in practice. This question requires programming in a language that has an implementation of SHA-256 hash function. You could use Java to program, although, you are free to use any other language with a library containing SHA-256, e.g., Python’s hashlib (which maybe easier to implement). Create an integer s containing all the digits in your student ID. For example, if my student ID is MQ12345678, then s = 12345678. Let “str” denote the string function, i.e., given any integer s, the function str(s) casts it into a string. For example, s = 12345678 becomes str(s) =“12345678”. Set the target t to:

Let H be the SHA-256 hash function. Let r be a counter starting from 0. Finally, let “||” denote string concatenation.

(a) Implement a program that tries successive values of r, i.e., r = 0, 1, 2, 3, . . ., computes H(str(s)||str(r)), compares it with t and halts whenever H(str(s)||str(r)) < t, with the output r. You need to provide the program and the output r.

(b) Let us call the program from part (a) as: PuzzleFinder(s, t). Write a program that calls PuzzleFinder with successive inputs (s + i, t), for i = 0 to 999, and records the output for each of these 1,000 runs. What is the average number of attempts before you found the target? You need to provide your program.

(c) If you drew random values between 0 and 2255 inclusive, how many attempts on average it would take before you find a value below the target? Compare this number to the answer obtained in part (b). What does it tell you about SHA-256?