Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Speeding up Collision Search for Byte-Oriented Hash Functions
Khovratovich, Dmitry; Biryukov, Alex; Nikolic, Ivica
2009In CT-RSA
Peer reviewed
 

Files


Full Text
fast-collision-search.pdf
Publisher postprint (379.05 kB)
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Abstract :
[en] 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.
Disciplines :
Computer science
Identifiers :
UNILU:UL-CONFERENCE-2010-069
Author, co-author :
Khovratovich, Dmitry ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Biryukov, Alex ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Nikolic, Ivica ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Language :
English
Title :
Speeding up Collision Search for Byte-Oriented Hash Functions
Publication date :
2009
Event name :
Topics in Cryptology - CT-RSA
Event place :
San Francisco, United States - California
Event date :
April 20-24
Audience :
International
Main work title :
CT-RSA
Publisher :
Springer
ISBN/EAN :
978-3-642-00861-0
Pages :
164-181
Peer reviewed :
Peer reviewed
Commentary :
5473 Topics in Cryptology - CT-RSA
Available on ORBilu :
since 25 June 2014

Statistics


Number of views
135 (0 by Unilu)
Number of downloads
422 (1 by Unilu)

Scopus citations®
 
17
Scopus citations®
without self-citations
14
OpenCitations
 
19

Bibliography


Similar publications



Contact ORBilu