FSBday : Implementing Wagner's generalized birthday attack against the SHA-3 round-1 candidate FSB

D.J. Bernstein, T. Lange, R.F. Niederhagen, C.P. Peters, P. Schwabe

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 Citations (Scopus)
15 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationProgress in Cryptology - INDOCRYPT 2009 (Proceedings 10th International Conference on Cryptology in India, New Delhi, India, December 13-16, 2009)
EditorsB. Roy, N. Sendrier
Place of PublicationBerlin
ISBN (Print)978-3-642-10627-9
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'FSBday : Implementing Wagner's generalized birthday attack against the SHA-3 round-1 candidate FSB'. Together they form a unique fingerprint.

Cite this