Cryptography -- 2
Budget: ₹600 – ₹1,500 INR
Write a program that runs the birthday attack against a hash function defined next.
This hash function is called “BadHash40” – it is constructed using SHA256 as a subroutine.
Specifically, BadHash40(x) := SHA256(x)[1..40], i.e., it takes the first 40 bits of the output of SHA256. The construction of BadHash40 is illustrated in the following figure:
Your task is to find two (arbitrary) inputs to the function BadHash40 which result in the same output, i.e., to search for a collision in BadHash40. Your program must compute such the two inputs and the corresponding output for BadHash40; use the hex format when reporting all these values.
Your program must write the list of random messages mi and their corresponding hash values ti into a text file (use the hex format for these values). This file will have to be included into your submission package.
Tip: The size of messages mi can be set to 256 bits.
This hash function is called “BadHash40” – it is constructed using SHA256 as a subroutine.
Specifically, BadHash40(x) := SHA256(x)[1..40], i.e., it takes the first 40 bits of the output of SHA256. The construction of BadHash40 is illustrated in the following figure:
Your task is to find two (arbitrary) inputs to the function BadHash40 which result in the same output, i.e., to search for a collision in BadHash40. Your program must compute such the two inputs and the corresponding output for BadHash40; use the hex format when reporting all these values.
Your program must write the list of random messages mi and their corresponding hash values ti into a text file (use the hex format for these values). This file will have to be included into your submission package.
Tip: The size of messages mi can be set to 256 bits.