Paper 2009/224

Pseudo-Cryptanalysis of Luffa

Keting Jia, Yvo Desmedt, 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.

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

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Inscrypt 2010
Keywords
Luffapseudo-collisionpseudo-second-preimagepseudo-preimagegeneralized birthday attack
Contact author(s)
ktjia @ mail tsinghua edu cn
History
2010-12-02: last of 3 revisions
2009-05-30: received
See all versions
Short URL
https://ia.cr/2009/224
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/224,
      author = {Keting Jia and Yvo Desmedt and Lidong Han and Xiaoyun Wang},
      title = {Pseudo-Cryptanalysis of Luffa},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/224},
      year = {2009},
      url = {https://eprint.iacr.org/2009/224}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.