Paper 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.

Note: Sample code for matrix arithmetic and pre-image search can be downloaded from: http://www.m-js.com/misc/fsb_test.tar.gz

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. INDOCRYPT 2007
Keywords
hash function cryptanalysisprovable securitylinearization attackFSB
Contact author(s)
m saarinen @ rhul ac uk
History
2007-09-25: last of 6 revisions
2007-08-07: received
See all versions
Short URL
https://ia.cr/2007/295
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/295,
      author = {Markku-Juhani O.  Saarinen},
      title = {Linearization Attacks Against Syndrome Based Hashes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/295},
      year = {2007},
      url = {https://eprint.iacr.org/2007/295}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.