Cryptography
Budget: ₹600 – ₹1,500 INR
Birthday attack is a generic algorithm for finding collisions in hash functions.
Project Task: 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.
Requirement (IMPORTANT): Implement the generic birthday attack algorithm described in Lecture 8-1
(see also Sec. 8.3 of Boneh-Shoup’s textbook). 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.
Feel free to use the programming language of your choice. Python is recommended.
In Python, the “hashlib” library contains an implementation of SHA256.
Organization: This project allows group work. One submission per team should be made.
All the team members will received the same grade.
Organization: This project allows group work. The group sets from Programming Project 1 will be used
by default. One project report per group must be submitted by any of the group members.
All the group members will receive the same grade.
Note: If you would like to change your group membership (join/leave/form a new team),
you must notify the instructor by March 31 (Thu), 23:59pm.
Submission requirements:
• The project report must contain a short description of the task (collision search using the
birthday attack), a short description of your program, and screenshots demonstrating that
your program works according to the project task.
(The size of your report must be between 2 and 7 pages.)
• The source code, the list of inputs/outputs of the hash function (a text file with values in the hex
format), the executable(s) if any, and all other necessary files must be enclosed as a ZIP archive.
The source code must be properly commented.
• If you use Python, follow the guidelines listed below:
o Use Python 3 (any version newer than 3.0).
o Use SHA256 from “hashlib” library.
o The hash input/output list must be saved in the file “hash.txt” or “hash.csv” located in
the same folder as your code.
• If you use C or C++, your report should contain detailed instructions on how to run the code.
Also, the hash input/output list must be saved in the file “hash.txt” or “hash.csv”.
Remarks
1. Failure to provide components listed in the above submission requirements will result in
reduced grade.
2. It is students’ responsibility to demonstrate that the implementation is working.
In cases when the code cannot be run, the screenshots placed in the report and the comments
placed in the code will serve as an evidence that the code is working (and that it is authentic).
Grading system:
• The code is worth 80 points, the breakdown is as follows:
• The code is working: 70 points.
o Either the grader is able to run it, or the grader is convinced via inspecting the code and
the screenshots provided in the report.
o Collision is found: 30 points. The remaining 40 points reflect how well the birthday
attack algorithm is implemented.
• The code is properly commented: 10 points.
• The project report is worth 20 points.
• An adequate description of the task (collision search using the birthday attack)
must be provided.
Project Task: 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.
Requirement (IMPORTANT): Implement the generic birthday attack algorithm described in Lecture 8-1
(see also Sec. 8.3 of Boneh-Shoup’s textbook). 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.
Feel free to use the programming language of your choice. Python is recommended.
In Python, the “hashlib” library contains an implementation of SHA256.
Organization: This project allows group work. One submission per team should be made.
All the team members will received the same grade.
Organization: This project allows group work. The group sets from Programming Project 1 will be used
by default. One project report per group must be submitted by any of the group members.
All the group members will receive the same grade.
Note: If you would like to change your group membership (join/leave/form a new team),
you must notify the instructor by March 31 (Thu), 23:59pm.
Submission requirements:
• The project report must contain a short description of the task (collision search using the
birthday attack), a short description of your program, and screenshots demonstrating that
your program works according to the project task.
(The size of your report must be between 2 and 7 pages.)
• The source code, the list of inputs/outputs of the hash function (a text file with values in the hex
format), the executable(s) if any, and all other necessary files must be enclosed as a ZIP archive.
The source code must be properly commented.
• If you use Python, follow the guidelines listed below:
o Use Python 3 (any version newer than 3.0).
o Use SHA256 from “hashlib” library.
o The hash input/output list must be saved in the file “hash.txt” or “hash.csv” located in
the same folder as your code.
• If you use C or C++, your report should contain detailed instructions on how to run the code.
Also, the hash input/output list must be saved in the file “hash.txt” or “hash.csv”.
Remarks
1. Failure to provide components listed in the above submission requirements will result in
reduced grade.
2. It is students’ responsibility to demonstrate that the implementation is working.
In cases when the code cannot be run, the screenshots placed in the report and the comments
placed in the code will serve as an evidence that the code is working (and that it is authentic).
Grading system:
• The code is worth 80 points, the breakdown is as follows:
• The code is working: 70 points.
o Either the grader is able to run it, or the grader is convinced via inspecting the code and
the screenshots provided in the report.
o Collision is found: 30 points. The remaining 40 points reflect how well the birthday
attack algorithm is implemented.
• The code is properly commented: 10 points.
• The project report is worth 20 points.
• An adequate description of the task (collision search using the birthday attack)
must be provided.