Difference between revisions of "FSB"
From The ECRYPT Hash Function Website
(→Collision Attacks) |
|||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 7: | Line 7: | ||
* Specification: | * Specification: | ||
--> | --> | ||
| + | |||
| + | <bibtex> | ||
| + | @inproceedings{mycryptAugotFS05, | ||
| + | author = {Daniel Augot and Matthieu Finiasz and Nicolas Sendrier}, | ||
| + | title = {A Family of Fast Syndrome Based Cryptographic Hash Functions}, | ||
| + | booktitle = {Mycrypt}, | ||
| + | year = {2005}, | ||
| + | pages = {64-83}, | ||
| + | url = {http://dx.doi.org/10.1007/11554868_6}, | ||
| + | editor = {Ed Dawson and Serge Vaudenay}, | ||
| + | publisher = {Springer}, | ||
| + | series = {LNCS}, | ||
| + | volume = {3715}, | ||
| + | isbn = {3-540-28938-0}, | ||
| + | abstract = {Recently, some collisions have been exposed for a variety of cryptographic hash functions [20,21] including some of the most widely used today. Many other hash functions using similar constructions can however still be considered secure. Nevertheless, this has drawn attention on the need for new hash function designs. In this article is presented a family of secure hash functions, whose security is directly related to the syndrome decoding problem from the theory of error-correcting codes. Taking into account the analysis by Coron and Joux [4] based on Wagner’s generalized birthday algorithm [19] we study the asymptotical security of our functions. We demonstrate that this attack is always exponential in terms of the length of the hash value. We also study the work-factor of this attack, along with other attacks from coding theory, for non asymptotic range, i.e. for practical values. Accordingly, we propose a few sets of parameters giving a good security and either a faster hashing or a shorter description for the function.}, | ||
| + | } | ||
| + | </bibtex> | ||
| + | |||
| + | <bibtex> | ||
| + | @MISC{ecryptFiniaszGS07, | ||
| + | author = {Matthieu Finiasz and Philippe Gaborit and Nicolas Sendrier}, | ||
| + | title = {Improved fast syndrome based cryptographic hash function}, | ||
| + | howpublished = {ECRYPT Hash Workshop, Barcelona, Spain, May 24-25}, | ||
| + | year = {2007}, | ||
| + | abstract = {At Mycrypt 2005, Augot, Finiasz and Sendrier presented a provably collision resistant family of hash functions [1]. We propose here to improve this construction in two ways: we add a final compression transform so as to achieve a security level equal to half the output length and we use a random quasi-cyclic matrix instead of a generic random matrix in order to get a shorter description for the hash function. Having a shorter description helps in multiple aspects: first the matrix can fit in the cache of a standard CPU, thus greatly improving the overall speed of the construction, second it allows new applications, for example in memory constrained environments.}, | ||
| + | url = {http://events.iaik.tugraz.at/HashWorkshop07/papers/Finiasz_ImprovedFastSyndromeBasedCryptographicHashFunction.pdf}, | ||
| + | } | ||
| + | </bibtex> | ||
== Cryptanalysis == | == Cryptanalysis == | ||
| Line 21: | Line 49: | ||
=== Collision Attacks === | === Collision Attacks === | ||
| + | |||
| + | <bibtex> | ||
| + | @inproceedings{ctrsaFouqueL08, | ||
| + | author = {Pierre-Alain Fouque and Ga{\"e}tan Leurent}, | ||
| + | title = {Cryptanalysis of a Hash Function Based on Quasi-cyclic Codes}, | ||
| + | booktitle = {CT-RSA}, | ||
| + | year = {2008}, | ||
| + | pages = {19-35}, | ||
| + | url = {http://dx.doi.org/10.1007/978-3-540-79263-5_2}, | ||
| + | abstract = {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! }, | ||
| + | editor = {Tal Malkin}, | ||
| + | publisher = {Springer}, | ||
| + | series = {LNCS}, | ||
| + | volume = {4964}, | ||
| + | isbn = {978-3-540-79262-8}, | ||
| + | } | ||
| + | </bibtex> | ||
| + | |||
| + | <bibtex> | ||
| + | @inproceedings{indocryptSaarinen07, | ||
| + | author = {Markku-Juhani Olavi Saarinen}, | ||
| + | title = {Linearization Attacks Against Syndrome Based Hashes}, | ||
| + | booktitle = {INDOCRYPT}, | ||
| + | year = {2007}, | ||
| + | pages = {1-9}, | ||
| + | url = {http://dx.doi.org/10.1007/978-3-540-77026-8_1}, | ||
| + | editor = {K. Srinathan and C. Pandu Rangan and Moti Yung}, | ||
| + | publisher = {Springer}, | ||
| + | series = {LNCS}, | ||
| + | volume = {4859}, | ||
| + | isbn = {978-3-540-77025-1}, | ||
| + | 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.}, | ||
| + | } | ||
| + | </bibtex> | ||
---- | ---- | ||
Latest revision as of 11:59, 10 November 2008
Contents
1 Specification
Daniel Augot, Matthieu Finiasz, Nicolas Sendrier - A Family of Fast Syndrome Based Cryptographic Hash Functions
- Mycrypt 3715:64-83,2005
- http://dx.doi.org/10.1007/11554868_6
BibtexAuthor : Daniel Augot, Matthieu Finiasz, Nicolas Sendrier
Title : A Family of Fast Syndrome Based Cryptographic Hash Functions
In : Mycrypt -
Address :
Date : 2005
Matthieu Finiasz, Philippe Gaborit, Nicolas Sendrier - Improved fast syndrome based cryptographic hash function
- ,2007
- http://events.iaik.tugraz.at/HashWorkshop07/papers/Finiasz_ImprovedFastSyndromeBasedCryptographicHashFunction.pdf
BibtexAuthor : Matthieu Finiasz, Philippe Gaborit, Nicolas Sendrier
Title : Improved fast syndrome based cryptographic hash function
In : -
Address :
Date : 2007
2 Cryptanalysis
2.1 Best Known Results
2.2 Generic Attacks
2.3 Collision Attacks
Pierre-Alain Fouque, Ga\"etan Leurent - Cryptanalysis of a Hash Function Based on Quasi-cyclic Codes
- CT-RSA 4964:19-35,2008
- http://dx.doi.org/10.1007/978-3-540-79263-5_2
BibtexAuthor : Pierre-Alain Fouque, Ga\"etan Leurent
Title : Cryptanalysis of a Hash Function Based on Quasi-cyclic Codes
In : CT-RSA -
Address :
Date : 2008
Markku-Juhani Olavi Saarinen - Linearization Attacks Against Syndrome Based Hashes
- INDOCRYPT 4859:1-9,2007
- http://dx.doi.org/10.1007/978-3-540-77026-8_1
BibtexAuthor : Markku-Juhani Olavi Saarinen
Title : Linearization Attacks Against Syndrome Based Hashes
In : INDOCRYPT -
Address :
Date : 2007
