Cryptanalysis of a Hash Function Based on Quasi-cyclic Codes

Pierre-Alain Fouque (1, 2, 3) , Gaëtan Leurent (3)

1 LIENS - Laboratoire d'informatique de l'école normale supérieure
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
3 ENS-PSL - École normale supérieure - Paris

At the ECRYPT Hash Workshop 2007, Finiasz, Gaborit, and Sendrier proposed an improved version of a previous provably secure syndrome-based hash function. The main innovation of the new design is the use of a quasi-cyclic code in order to have a shorter description and to lower the memory usage. In this paper, we look at the security implications of using a quasi-cyclic code. We show that this very rich structure can be used to build a highly efficient attack: with most parameters, our collision attack is faster than the compression function!

Domaines: Cryptographie et sécurité [cs.CR]

Pierre-Alain Fouque, Gaëtan Leurent. Cryptanalysis of a Hash Function Based on Quasi-cyclic Codes. Topics in Cryptology - CT-RSA 2008, The Cryptographers' Track at the RSA Conference 2008, 2008, San Francisco, United States. pp.19-35, ⟨10.1007/978-3-540-79263-5_2⟩. ⟨inria-00556689⟩