1 Extending Hash Functions

Happy threw together a hash function h : 32-bits → 16-bits, which he implemented by a C function hash32(). Adapting Method 2 from slide 31 of Lecture 15, Happy defined a new hash function H:64-bits → 16-bits and implemented it by a C function hash64(). Since he didn’t know how to find colliding pairs for h, he thought that H would also be collision-free.

Clever Clem was able to find lots of colliding pairs for H. He didn’t want to tell Happy how he did it, but he presented Happy with a file H-collisions of colliding pairs for H, each line of which consists of two 64-bit whitespace-separated hex numbers.

2 Assignment

Your job is to write a program breakHash.c that applies the ideas presented on slide 32 of Lecture 15 to find corresponding colliding pairs for h. Your program should take the name of a file containing pairs of collisions for H as a command line argument. It should read each line, determine whether case 1 or case 2 applies, and find the corresponding colliding pair for h. It should then write a line to standard output consisting of 5 numbers: the original colliding pair for H, the case number that pertains (1 or 2), and the colliding pair for h described by that case. Colliding pairs should be written in hex with the 0x-prefix (as in the input file). The case number should be written as a single digit. In case 2, if both m₁≠m₁′ and m₂≠m₂′, then print the first colliding pair for h.

Do not attempt to reverse-engineer hash32() (although this is possible to do with a little thought and cleverness). Rather, the goal of this problem is for you to apply the cited method from Lecture 15 for finding colliding pairs for hash32() given colliding pairs for hash64(). For this reason, I am only releasing the object code for hash32() and hash64(). Your program can call these functions, but I’m purposely not giving you the source code.

You will find the three files that you need for this assignment in Zoo directory /c/cs467/ assignments/hw8/:

In order to call hash32() and hash64() from your own program, breakHash.c, you will need to do three things:

1. Put hw8.h and libhw8.a into your working directory along with your code.
2. #include the header file hw8.h in your code.
3. Link your compiled code to the library libhw8.a.

You can compile and link with the single command line:

The switch -L. says to search for the library in your working directory. The switch -lhw8 says to link to the library hw8, which resides in the file libhw8.a.

The folder osx contains a version of libhw8.a that you can use if you choose to develop your code on a Mac. However, you should compile and test your code on the Zoo before submitting.

When your code is working, run it on H-collisions with standard output redirected to a file H-collisions.out.

3 Submission

All work should be submitted as usual via Canvas. The code, data files, and output file should be put in a .zip or tar.gz compressed archive file and submitted. All files necessary to compile and run your code should be included in the archive, including those that were furnished in the assignment directory and not modified. The idea is that the grader should be able to unpack your archive on the Zoo and compile and link your code to produce the executable file breakHash. Then the output produced by running your executable on the file H-collisions should match your submitted file H-collisions.out.

Please do not submit generated .o, executable files, or hidden files that your IDE might generate. The grader will recompile your code from your source files.