Use the birthday attack to generate a collision in a reduced version of SHA-1 (just a 40-bit hash). To find the hash value of a string s, you can execute the following Python code:

import hashlib

hashval=hashlib.shal(s.encode('utf-8')).hexdigest()

We will use the high-order 40 bits (ten hex digits) as the 'hash value', so as to make this problem do-able.

Problem 1: Basic birthday attack on a 40-bit hash Finding collision of any two messages

Write a function birthday () that returns a truple (s; t; n); where s and t are different ASCII strings whose SHA-1 hashes have the same high-order 40 bits (same 10 initial hex digits). The last component n of the return value is the number of calls to SHA-1. Again, you can generate random ASCII strings by converting random integers to hex. By the theory of these birthday attacks, you will need to compute somewhat more than 1 million =square root of 240 =220 hashes to find this collision with probability greater than 1/2. The simplest way to do it is to repeatedly generate random strings s and enter the pair SHA-1(s):s in a Python dictionary structure. When you find a hash value that's already in the dictionary, you're done. Include two different colliding pairs of strings in your writeup. In addition, specify the time needed to find the collided pairs.

Problem 2: Finding First preimages

Implement a program using python to find the first preimage of a hash function output. Finding first preimage is defined as "Given H, the attacker tries to find m where it has the hash value H. if H has an output of the first 10 initial hex digits of the SHA-1 hashes, write a program to find the preimage of ABCDEF0123. Specify the time needed to find the preimage M, and compare this time with the previous times in problems 1.

Problem 3: Finding Second preimages

Here you will start by computing the hash value H of your name M, and then search for a random ASCII string M2 that has the same hash value as your name M1. you still need to use the same 10 initial hex digits of the SHA-1 hash. In addition, specify the time needed to find the second pair. Compare this time with the previous time in problem 1 and 2.ss