Cryptology ePrint Archive: Report 2009/292

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

Daniel J. Bernstein and Tanja Lange and Ruben Niederhagen and Christiane Peters and Peter Schwabe

Abstract: This paper applies generalized birthday attacks to the FSB compression function, and shows how to adapt the attacks so that they run in far less memory. In particular, this paper presents details of a parallel implementation attacking FSB48 , a scaled-down version of FSB proposed by the FSB submitters. The implementation runs on a cluster of 8 PCs, each with only 8GB of RAM and 700GB of disk. This situation is very interesting for estimating the security of systems against distributed attacks using contributed off-the-shelf PCs.

Category / Keywords: implementation / SHA-3, Birthday, FSB -- Wagner, not much Memory

Date: received 17 Jun 2009, last revised 27 Sep 2011

Contact author: tanja at hyperelliptic org

Available formats: PDF | BibTeX Citation

Version: 20110927:133044 (All versions of this report)

Discussion forum: Show discussion | Start new discussion