Improved security analysis of Fugue-256

Praveen Gauravaram, Nasour Bagheri, Lars Ramkilde Knudsen, Wei Lei

    Research output: Book/ReportReportResearchpeer-review

    1 Downloads (Pure)


    Fugue is a cryptographic hash function designed by Halevi, Hall and Jutla and was one of the fourteen hash algorithms of the second round of NIST’s SHA3 hash competition. We consider Fugue-256, the 256-bit instance of Fugue. Fugue-256 updates a state of 960 bits with a round transformation R parametrized by a 32-bit message word. Twice in every state update, this transform invokes an AES like round function called SMIX. Fugue-256 relies on a final transformation G to output digests that look random. G has 18 rounds where each round invokes SMIX twice and finally the 960-bit output of the G transform is mapped with a transform to a 256-bit digest. In this paper, we present some improved as well as new analytical results of Fugue-256 (with lengthpadding). First we improve Aumasson and Phans’ integral distinguisher on the 5.5 rounds of the G transform to 16.5 rounds, thus showing weak diffusion in the G transform. Next we improve the designers’ meet-in-the-middle preimage attack on Fugue-256 from 2480 time and memory to 2416. Next we study the security of Fugue-256 against free-start distinguishers and free-start collisions. In this direction, we use an improved variant of the differential characteristic of the G transform shown by the designers to present an efficient distinguisher for the (G)(.) transform showing another weak diffusion property of G. We then extend this distinguisher to some interesting practical free-start distinguishers and free-start collisions for the length padded Fugue-256 in 233 complexity. Finally, we show that free-start collision attacks on the length-padded Fugue-256 can be found in just O(1)
    Original languageEnglish
    Publication statusPublished - 2011


    • Hash function analysis
    • SHA-3 hash competition
    • Fugue-256


    Dive into the research topics of 'Improved security analysis of Fugue-256'. Together they form a unique fingerprint.

    Cite this