Linearization attacks against syndrome based hashes. (English) Zbl 1153.94426

Srinathan, K. (ed.) et al., Progress in cryptology – INDOCRYPT 2007. 8th international conference on cryptology in India, Chennai, India, December 9–13, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-77025-1/pbk). Lecture Notes in Computer Science 4859, 1-9 (2007).
Summary: 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.
For the entire collection see [Zbl 1135.94002].


94A60 Cryptography
Full Text: DOI


[1] Augot, D.; Finiasz, M.; Sendrier, N.; Dawson, E.; Vaudenay, S., A family of fast syndrome based cryptographic hash functions, Data Integration in the Life Sciences, 64-83 (2005), Heidelberg: Springer, Heidelberg · Zbl 1126.94320
[2] Bentahar, K., Page, D., Saarinen, M.-J.O., Silverman, J.H., Smart, N.: LASH. In: Proc. 2nd NIST Cryptographic Hash Workshop (2006)
[3] Contini, S.; Lenstra, A. K.; Steinfeld, R.; Vaudenay, S., VSH, an efficient and provably collision-resistant hash function, Advances in Cryptology - EUROCRYPT 2006, 165-182 (2006), Heidelberg: Springer, Heidelberg · Zbl 1140.94331 · doi:10.1007/11761679_11
[4] Coron, J.-S., Joux, A.: Cryptanalysis of a provably secure cryptographic hash function. IACR ePrint 2004 / 013 (2004), Available at http://www.iacr.org/eprint
[5] Damgård, I. B.; Brassard, G., A design principle for hash functions, Advances in Cryptology - CRYPTO ’89, 416-427 (1990), Heidelberg: Springer, Heidelberg · Zbl 0724.68029
[6] Finiasz, M., Gaborit, P., Sendrier, N.: Improved fast syndrome based cryptographic hash functions. In: ECRYPT Hash Function Workshop 2007 (2007)
[7] Merkle, R. C., A fast software one-way hash function, Journal of Cryptology, 3, 43-58 (1990) · Zbl 0705.68022 · doi:10.1007/BF00203968
[8] Saarinen, M.-J. O.; Barua, R.; Lange, T., Security of VSH in the real world, Progress in Cryptology - INDOCRYPT 2006, 95-103 (2006), Heidelberg: Springer, Heidelberg · Zbl 1175.94098 · doi:10.1007/11941378_8
[9] Rijmen, V., Barreto, P.: “Whirlpool”. Seventh hash function of ISO/IEC 10118-3:2004 (2004)
[10] Wagner, D.; Yung, M., A generalized birthday problem, Advances in Cryptology - CRYPTO 2002, 288-304 (2002), Heidelberg: Springer, Heidelberg · Zbl 1026.94541 · doi:10.1007/3-540-45708-9_19
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.