CSCI 462 Project 3: Hash Collision due: 4/24/2024
-
Let x1 and x2 be given messages:
- x1 = "Bob sends $10 to Oscar's account"
- x2 = "Bob sends $1000 to Oscar's account"
-
Given x1 and x2, your goal is to create two messages m1 and m2 that satisfy the following properties:
- hash(m1) == hash(m2)
- The semantic meaning of original messages x1 and x2 must be preserved in m1 and m2. That is, m1 and m2 should look like x1 and x2, respectively. You can create such messages by appending invisible characters (spaces and tabs) to the original messages.
-
Review the provided collision module. Your task is to complete the search method, which returns m1 and m2 with the properties described above.
-
Here is a sketch of the idea: During your search for a collision, in each round, you will generate (up to) two messages and store each in one of two lookup tables, H1 and H2. Whenever you create a new message, first check for a match in one of the tables to determine if a collision exists. If a match is found, you are done. If not, store the message in a table and continue your search.
-
As you make progress or have more questions, we will continue discussing this project in class and/or via Discord.
-
To get full credit, your program should not only produce correct output but also be efficient The execution time will vary for each run in the range from 0.6 seconds to 3 seconds. It is sufficient if your solution runs within 5 seconds.
- elapsed time in seconds: 1.6064980030059814
- Bob sends $10 to Oscar's account [some space here].
- Bob sends $1000 to Oscar's account [some space here].
- True
Using 50 bits, it takes between 65 seconds and 160 seconds. You may test with 50 bits. However, for grading, we will use 20 and 40 bits: