IACR News item: 01 January 2013
Gaëtan Leurent
ePrint Reportfor a hash function. If we consider only hash computations, it is
easy to compute a lower-bound for the complexity of near-collision
algorithms, and to build a matching algorithm. However, this
algorithm needs a lot of memory, and makes than 2^{n/2} memory
accesses. Recently, several algorithms have been proposed without
this memory requirement; they require more hash evaluations, but the
attack is actually more practical. They can be divided in two main
categories: some are based on truncation, and some are based on
covering codes.
In this paper, we give a new insight to the generic complexity of a
near-collision attack. First, we consider time-memory trade-offs for
truncation-based algorithms. For a practical implementation, it seems
reasonable to assume that some memory is available and we show that
taking advantage of this memory can significantly reduce the
complexity. Second, we show a new method combining truncation and
covering codes. The new algorithm is always at least as good as the
previous works, and often gives a significant improvement. We
illustrate our results by giving a 10-near collision for MD5: our
algorithm has a complexity of 2^45.4 using 1TB of memory while the
best previous
Additional news items may be found on the IACR news page.