Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Speeding up Collision Search for Byte-Oriented Hash Functions
verfasst von : Dmitry Khovratovich, Alex Biryukov, Ivica Nikolic
Erschienen in: Topics in Cryptology – CT-RSA 2009
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.
The method is illustrated with the collision and second preimage attacks on the compression functions based on Rijndael. We show that slow diffusion in the Rijndael (and AES) key schedule allows to run an attack on a version with a 13-round compression function, and the S-boxes do not prevent the attack. We finally propose how to modify the key schedule to resist the attack and provide lower bounds on the complexity of the generic differential attacks for our modification.