×

Higher-order differential properties of Keccak and Luffa. (English) Zbl 1307.94040

Joux, Antoine (ed.), Fast software encryption. 18th international workshop, FSE 2011, Lyngby, Denmark, February 13–16, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-21701-2/pbk). Lecture Notes in Computer Science 6733, 252-269 (2011).
Summary: 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 a number of balanced Sboxes. These techniques yield zero-sum partitions of size \(2^{1575}\) 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 D. Watanabe et al. on a reduced version [FSE 2010, Lect. Notes Comput. Sci. 6147, 270–285 (2010; Zbl 1279.94125)]. 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.
For the entire collection see [Zbl 1217.68011].

MSC:

94A60 Cryptography

Citations:

Zbl 1279.94125

Software:

Keccak
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aumasson, J.-P., Meier, W.: Zero-sum distinguishers for reduced Keccak -f and for the core functions of Luffa and Hamsi. Presented at the Rump Session of Cryptographic Hardware and Embedded Systems - CHES 2009 (2009)
[2] Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Keccak sponge function family main document. Submission to NIST, Round 2 (2009)
[3] Boura, C., Canteaut, A.: Zero-Sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 1–17. Springer, Heidelberg (2011) · Zbl 1290.94048 · doi:10.1007/978-3-642-19574-7_1
[4] De Cannière, C., Sato, H., Watanabe, D.: The reasons for the change of Luffa. Supplied with the Second Round Package
[5] De Cannière, C., Sato, H., Watanabe, D.: Hash Function Luffa: Specification. Submission to NIST, Round 1 (2008)
[6] De Cannière, C., Sato, H., Watanabe, D.: Hash Function Luffa: Specification. Submission to NIST, Round 2 (2009)
[7] Canteaut, A., Videau, M.: Degree of composition of highly nonlinear functions and applications to higher order differential cryptanalysis. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 518–533. Springer, Heidelberg (2002) · Zbl 1056.94512 · doi:10.1007/3-540-46035-7_34
[8] Duan, M., Lai, X.: Improved zero-sum distinguisher for full round Keccak -f permutation. IACR ePrint Report 2011/023 (January 2011), http://eprint.iacr.org/2011/023
[9] Khovratovich, D., Naya-Plasencia, M., Röck, A., Schläffer, M.: Cryptanalysis of Luffa v2 components. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 388–409. Springer, Heidelberg (2011) · Zbl 1293.94083 · doi:10.1007/978-3-642-19574-7_26
[10] Knudsen, L.R.: Truncated and higher order differentials. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 196–211. Springer, Heidelberg (1995) · Zbl 0939.94556 · doi:10.1007/3-540-60590-8_16
[11] Knudsen, L.R., Rijmen, V.: Known-key distinguishers for some block ciphers. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 315–324. Springer, Heidelberg (2007) · Zbl 1153.94403 · doi:10.1007/978-3-540-76900-2_19
[12] Lai, X.: Higher order derivatives and differential cryptanalysis. In: Proc. Symposium on Communication, Coding and Cryptography, in Honor of J. L. Massey on the Occasion of His 60’th Birthday. Kluwer Academic Publishers, Dordrecht (1994)
[13] Watanabe, D., Hatano, Y., Yamada, T., Kaneko, T.: Higher Order Differential Attack on Step-Reduced Variants of Luffa v1. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol. 6147, pp. 270–285. Springer, Heidelberg (2010) · Zbl 1279.94125 · doi:10.1007/978-3-642-13858-4_15
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.