Cryptology ePrint Archive: Report 2010/589

Higher-order differential properties of Keccak and Luffa

Christina Boura and Anne Canteaut and Christophe De Cannière

Abstract: In this paper, we identify higher-order differential and zero-sum properties in the full Keccak-f permutation, in the Luffa v1 hash function, and in components of the Luffa v2 algorithm. These structural properties rely on a new bound on the degree of iterated permutations with a nonlinear layer composed of parallel applications of smaller balanced Sboxes. These techniques yield zero-sum partitions of size $2^{1590}$ for the full Keccak-f permutation and several observations on the Luffa hash family. We first show that Luffa v1 applied to one-block messages is a function of 255 variables with degree at most 251. This observation leads to the construction of a higher-order differential distinguisher for the full Luffa v1 hash function, similar to the one presented by Watanabe et al. on a reduced version. We show that similar techniques can be used to find all-zero higher-order differentials in the Luffa v2 compression function, but the additional blank round destroys this property in the hash function.

Category / Keywords: secret-key cryptography / Hash functions, degree, higher-order differentials, zero-sums, SHA-3

Date: received 19 Nov 2010, last revised 24 Nov 2010

Contact author: Anne Canteaut at inria fr

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: Correction on the typo in the ANF of the Sbox in Luffa v2 (first line of Page 9)

Version: 20101124:095907 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]