The hash function FSB is one of the candidates submitted to NIST’s competition to find the new standard hash function, SHA-3. The compression function of FSB is based on error correcting codes. In this paper we show how to use Wagner’s generalized birthday attack to find collisions in FSB’s compression function. In particular, we present details on our implementation attacking FSB48, a toy version of FSB which was proposed by the FSB submitters as a training case for FSB.
Our attack does not make use of any properties of the particular linear code used within FSB. FSB48 was chosen as a target where generalized birthday attacks would be one of the strongest attacks and which could be attacked in practice.
We show how to adapt this attack so that it runs on our computer cluster of only 10 PCs which provides far less memory than the usual implementation of generalized birthday attacks would require. This situation is very interesting for estimating the security of systems against distributed attacks using contributed off-the-shelf PCs.
For the SHA-3 competition this result is meaningful in that it allows to assess the security of FSB against the strongest non-structural attack; it does not provide any insight in the security of this particular choice of linear code.
|Title of host publication||Progress in Cryptology - INDOCRYPT 2009 (Proceedings 10th International Conference on Cryptology in India, New Delhi, India, December 13-16, 2009)|
|Editors||B. Roy, N. Sendrier|
|Place of Publication||Berlin|
|Publication status||Published - 2009|
|Name||Lecture Notes in Computer Science|