Cryptology ePrint Archive: Report 2007/295
Linearization Attacks Against Syndrome Based Hashes
Markku-Juhani O. Saarinen
Abstract: In MyCrypt 2005, Augot, Finiasz, and Sendrier proposed FSB, a family of cryptographic hash functions. The security claim of the FSB hashes is based on a coding theory problem with hard average-case complexity. In the ECRYPT 2007 Hash Function Workshop, new versions with essentially the same compression function but radically different security parameters and an additional final transformation were presented. We show that hardness of average-case complexity of the underlying problem is irrelevant in collision search by presenting a linearization method that can be used to produce collisions in a matter of seconds on a desktop PC for the variant of FSB with claimed $2^128$ security.
Category / Keywords: secret-key cryptography / hash function cryptanalysis, provable security, linearization attack, FSB
Publication Info: INDOCRYPT 2007
Date: received 31 Jul 2007, last revised 25 Sep 2007
Contact author: m saarinen at rhul ac uk
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Note: Sample code for matrix arithmetic and pre-image search can be downloaded from: http://www.m-js.com/misc/fsb_test.tar.gz
Version: 20070925:074841 (All versions of this report)
Short URL: ia.cr/2007/295
[ Cryptology ePrint archive ]