FSBday: A parallel implementation of Wagner's generalized birthday attack

In the paper FSBday: Implementing Wagner's generalized birthday attack against the round-1 SHA-3 candidate FSB we describe the implementation of Wagner's generalized birthday attack on 8 nodes of the Coding and Cryptography Computer Cluster (CCCC) at Eindhoven University of Technology.

This website gives more information for people who want to reproduce the attack on a similar cluster and for people who want to use (parts of) our code for other Wagner-like attacks.
Disclaimer: The program is written to run only once, the source code contains some messy parts which work just for the very special case described in our paper. However, if you want to use the code for something else than verifying our results, we give more information about files that need to be changed for other instances of Wagner attacks.

Hardware requirements to reproduce the attack

Reproducing the results of our attack with our code needs:

Installing MPICH-2

Our implementation uses the MPI implementation MPICH-2. We followed this installation guide to set up MPICH-2 on our cluster machines running Ubuntu 9.04 (aka Jaunty Jackalope).
As a remark: We had problems with the setup of MPI when the hostname was mapped to 127.0.0.1 in /etc/hosts, we just removed this entry.

Downloading and running our code

To download and compile the code run
wget http://polycephaly.org/projects/fsbday/data/fsbday-20091213.tar.bz2
tar xjvf fsbday-20091213.tar.bz2
cd fsbday-20091213
make

If the data partition for the attack is not /dev/sda1, change the definition of IODEVICE in params.h accordingly before compiling, otherwise running the attack may destroy data on /dev/sda1!

This will produce a binary called fsbday, which you have to copy to each of the cluster nodes in the same directory. For this you can use the bash script mpicp.sh.

Running Phase 1

The first phase of the attack (for the description of the two phases please read the paper) is started through the bash script fsbstart.sh, before running the script you might have to change the value of the HOSTFILE (the path to the MPI host file, set to ./hosts by default) in the script. The script takes as only argument the path to a logfile, so the first phase of the attack can be started with

./fsbstart fsbday.log

The only output on stdout is the clamping constants tried and whether they lead to success, more information including the values yielding a collision can be found in the log file.

Running Phase 2

To determine the matrix positions from the clamping constants you have to run the program fsbfinal twice, once for the left and once for the right half-tree. The fsbfinal program needs as input the clamping constants used to generate the lists on level 0 and the value on level 3 that leads to success. The clamping constants are output on standard output, the value you will find in the logfile n a line looking like

0: Result: 54e28b37d58e75 781538a2cdf5639d Part: 1f8

when you grep for "Result". The first number (before the colon) is the number of the node.
Let's assume the clamping constants in the rightmost quarter-tree are you determined in phase 1 are 4, 4, 0, 0, and let's assume the value as in the line above, then you first have to convert 54e28b37d58e75 to decimal, yielding 23892985608769141, same for 781538a2cdf5639d yielding 8652884530953544605 and for the part 1f8 yielding 504.
You then run fsbfinal as follows

mpirun -l -machinefile hosts -np 8 ./fsbfinal --nlists=8 --startlevel=0 --startlist=0 --cmp=23892985608769141 --remaining=8652884530953544605 --part=504 --node=0 0 0 0 0 0 0 0 0

mpirun -l -machinefile hosts -np 8 ./fsbfinal --nlists=8 --startlevel=0 --startlist=8 --cmp=23892985608769141 --remaining=8652884530953544605 --part=504 --node=0 0 0 0 0 0 0 4 4

This will print the positions (relative positions in the according blocks and half-blocks) to stderr.

Modifying the attack

The files specific to the attack against FSB48 are entry.h, merge.h, sort.h and presort.h. The file entry.h is so specific that you will have to reimplement all functions in this file for other Wagner instances.
Furthermore the list generation in presort.h (the function gen_elements) needs to be changed (of course depending on what exactly you want to do).
Some parameters specific to our attack are set in params.h, these probably also have to change. Furthermore make sure to set the values for ALESIZE and PARTSIZE in types.h are an integer multiple of the sizes of entries on all levels, in compressed non compressed form. PARTSIZE must be an integer multiple of ALESIZE and you have to make sure that all data of one list fraction fits into NPARTS * PARTSIZE bytes.
Although merging, sorting and presorting should work if you only change the parameters in params.h and types.h, we exploit at several spots that some data fits, e.g., into a 32-bit integer or into a 64-bit integer. In particular if you scale up the parameters, there are things that may go wrong if you just use the code in merge.h, sort.h and presort.h. In any case it is necessary to understand the code in these three files to know which parts have to change.
For any questions about how to adapt the code to other problems do not hesitate to contact us.