3CollisionFindingAlgorithms

This repository implements the algorithms proposed in "Improved Generic Algorithms for 3-Collisions" of A.Joux e S.Lucks. It is the final workshop for the course "IN450" (algorithms for cryptography) of the University of Roma Tre in the academic year 2019/2020. We now give a short description of these algorithms, but we highly recommend referring to the original article (publicly available at link https://eprint.iacr.org/2009/305.pdf) for a full explanation.

Introduction

Let f be a hash function with an output set of cardinality N; our goal is to find a three-collision for f (i.e. three different a, b, and c such that f(a) = f(b) = f(c)). It is well known that finding an r-collision for a random map over a finite set of cardinality N requires more than N^(r−1)/r map evaluations, but, besides this lower bound on the evaluations needed, a prime goal is to find algorithms that do it in a memory-efficient way. Here, we both implement the folklore and the new proposed algorithm (respectively in the executable file naive_alg and new_alg).

The Folklore algorithm

The folklore algorithm is divided into two steps:

1. In the first step, we generate a number Na of random string x₁, ... x_Na, compute the hash values f(x₁), ... f(x_Na), and store them in the memory like in the following table.

Vectors' names	Vectors' elements
Image	f(x1)	f(x2)	f(x3)	...................	f(xNa)
Preimag1	x1	x2	x3	...................	xNa
Preimag2	NULL	NULL	NULL	...................	NULL

2. In the second step, we generate Nb random hash evaluations without storing them. At every cycle we have a random string y and its hash f(y); if for some i in {1, ..., Na} the hash f(y) is equal to f(x_i), y != x_i, and Preimage2[i] == NULL, we set Preimage2[i] = y. When we found two different y₁ and y₂ (both different from some x_i) such that f(x_i) = f(y₁) = f(y₂), the algorithm stops and return the 3-collision (x_i, y₁, y₂).

The New Proposed algorithm

The idea of the new proposed algorithm is to start the second step with a database that already contains 2-collisions, like in the following example:

Vectors' names	Vectors' elements
Image	f(x1,1) = f(x1,2)	f(x2,1) = f(x2,2)	f(x3,1) = f(x3,2)	...................	f(xNa,1) = f(xNa,2)
Preimag1	x1,1	x2,1	x3,1	...................	xNa,1
Preimag2	x1,2	x2,2	x3,2	...................	xNa,2

This data structure implies that the second step will find a 3-collision after the first good collision, allowing us to take a smaller Na and decrease the needed memory usage without changing the algorithm's time complexity. Furthermore, the algorithm's main problem is to compute a 2-collision table by using a space complexity of O(Na) and a time complexity of O(Nb); the algorithm reaches this goal by using the method explained in the following section.

Chain technique

Let's define a hash-chain of length Ng as a recursively apply of f over a random input x:

A hash chain of length Ng starting by x
x	→	f(x)	→	f(f(x))	→	f(f(x)))	→	...........	→	f Ng(x)

Given two hash chains with the same endpoint, we can derive a two collision:

Example of some chains which generate collisions
f201	→	02a7	→	55bc	→	a1ff	→	2095	→	d1d8
afdc	→	45ca	→	007e	→	a1ff	→	2095	→	d1d8
97e0	→	45ca	→	007e	→	a1ff	→	2095	→	d1d8
		c003	→	4da7	→	f00f	→	c6c6	→	d1d8
						bb29	→	2095	→	d1d8

For generating the 2-collisions table, the algorithm first computes the Na chain of a fixed length Ng by only storing the start and the end values and then calculates other chains until it derives Na 2-collisions.