Speeding up Collision Search for Byte-Oriented Hash Functions

Dmitry Khovratovich, Alex Biryukov, Ivica Nikolic

Abstract

We describe a new tool for the search of collisions for hash functions. The tool is applicable when an attack is based on a differential trail, whose probability determines the complexity of the attack. Using the linear algebra methods we show how to organize the search so that many (in some cases — all) trail conditions are always satisfied thus significantly reducing the number of trials and the overall complexity.
BibTeX
@inproceedings{khovratovich2009speeding,
  author = {Dmitry Khovratovich and Alex Biryukov and Ivica Nikolic},
  title = {{Speeding up Collision Search for Byte-Oriented Hash Functions}},
  booktitle = {CT-RSA},
  year = {2009},
  doi = {10.1007/978-3-642-00862-7\_11},
}
Figure