Cryptology ePrint Archive: Report 2009/224

Pseudo-Cryptanalysis of Luffa

Keting Jia and Yvo Desmedt and Lidong Han and Xiaoyun Wang

Abstract: In this paper, we present the pseudo-collision, pseudo-second-preimage and pseudo-preimage attacks on the SHA-3 candidate algorithm Luffa. The pseudo-collisions and pseudo-second-preimages can be found easily by computing the inverse of the message injection function at the beginning of Luffa. We explain in details the pseudo-preimage attacks. For Luffa-224/256, given the hash value, only 2 iteration computations are needed to get a pseudo-preimage. For Luffa-384, finding a pseudo-preimage needs about $2^{64}$ iteration computations with $2^{67}$ bytes memory by the extended generalized birthday attack. For Luffa-512, the complexity is $2^{128}$ iteration computations with $2^{132}$ bytes memory.

It is noted that, we can find the pseudo-collision pairs and the pseudo-second images only changing a few different bits of initial values. That is directly converted to the forgery attack on NMAC in related key cases.

Category / Keywords: Luffa, pseudo-collision, pseudo-second-preimage, pseudo-preimage, generalized birthday attack

Publication Info: Inscrypt 2010

Date: received 19 May 2009, last revised 1 Dec 2010

Contact author: ktjia at mail tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Note: Improving the pseudo-preimage attack on Luffa-384/512

Version: 20101202:022732 (All versions of this report)

Short URL: ia.cr/2009/224

Discussion forum: Show discussion | Start new discussion