Thinking outside the superbox. (English) Zbl 1487.94104

Malkin, Tal (ed.) et al., Advances in cryptology – CRYPTO 2021. 41st annual international cryptology conference, CRYPTO 2021, virtual event, August 16–20, 2021. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 12827, 337-367 (2021).
Summary: Designing a block cipher or cryptographic permutation can be approached in many different ways. One such approach, popularized by AES, consists in grouping the bits along the S-box boundaries, e.g., in bytes, and in consistently processing them in these groups. This aligned approach leads to hierarchical structures like superboxes that make it possible to reason about the differential and linear propagation properties using combinatorial arguments. In contrast, an unaligned approach avoids any such grouping in the design of transformations. However, without hierarchical structure, sophisticated computer programs are required to investigate the differential and linear propagation properties of the primitive. In this paper, we formalize this notion of alignment and study four primitives that are exponents of different design strategies. We propose a way to analyze the interactions between the linear and the nonlinear layers w.r.t. the differential and linear propagation, and we use it to systematically compare the four primitives using non-trivial computer experiments. We show that alignment naturally leads to different forms of clustering, e.g., of active bits in boxes, of two-round trails in activity patterns, and of trails in differentials and linear approximations.
For the entire collection see [Zbl 1484.94002].


94A60 Cryptography
Full Text: DOI HAL


[1] Banik, S., Pandey, S.K., Peyrin, T., Sasaki, Y., Sim, S.M., Todo, Y.: GIFT: a small present - towards reaching the limit of lightweight encryption. In: CHES (2017) · Zbl 1450.94026
[2] Beaulieu, R.; Shors, D.; Smith, J.; Treatman-Clark, S.; Weeks, B.; Wingers, L., The SIMON and SPECK families of lightweight block ciphers, IACR Cryptol. ePrint Arch., 2013, 404 (2013) · Zbl 1382.94059
[3] Bernstein, DJ; Robshaw, M.; Billet, O., The Salsa20 family of stream ciphers, New Stream Cipher Designs, 84-97 (2008), Heidelberg: Springer, Heidelberg
[4] Bernstein, D.J.: Cache-timing attacks on AES. Technical report (2005)
[5] Bertoni, G., Daemen, J., Hoffert, S., Peeters, M., Van Assche, G., Van Keer, R.: Extended Keccak code package. https://github.com/XKCP/XKCP · Zbl 1306.94028
[6] Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: The Keccak reference (Jan 2011) · Zbl 1306.94028
[7] Beyne, T., Chen, Y.L., Dobraunig, C., Mennink, B.: Dumbo, jumbo, and delirium: Parallel authenticated encryption for the lightweight circus. IACR Trans. Symmetric Cryptol. 2020(S1), 5-30 (2020). doi:10.13154/tosc.v2020.iS1.5-30
[8] Biham, E.; Shamir, A.; Menezes, AJ; Vanstone, SA, Differential cryptanalysis of DES-like cryptosystems, Advances in Cryptology-CRYPT0’ 90, 2-21 (1991), Heidelberg: Springer, Heidelberg · Zbl 0787.94014
[9] Bogdanov, A.; Knezevic, M.; Leander, G.; Toz, D.; Varici, K.; Verbauwhede, I., SPONGENT: the design space of lightweight cryptographic hashing, IACR Cryptol. ePrint Arch., 2011, 697 (2011) · Zbl 1365.94406
[10] Bogdanov, A.; Paillier, P.; Verbauwhede, I., PRESENT: an ultra-lightweight block cipher, Cryptographic Hardware and Embedded Systems - CHES 2007, 450-466 (2007), Heidelberg: Springer, Heidelberg · Zbl 1142.94334
[11] Boyar, J.; Peralta, R.; Festa, P., A new combinational logic minimization technique with applications to cryptology, Experimental Algorithms, 178-189 (2010), Heidelberg: Springer, Heidelberg
[12] Canteaut, A., et al.: Saturnin: a suite of lightweight symmetric algorithms for post-quantum security. IACR ToSC (S1) (2020)
[13] Canteaut, A., et al.: Saturnin implementations. https://project.inria.fr/saturnin/files/2019/05/saturnin.zip
[14] Daemen, J.: Cipher and hash function design, strategies based on linear and differential cryptanalysis, PhD Thesis. K.U. Leuven (1995)
[15] Daemen, J., Hoffert, S., Peeters, M., Van Assche, G., Van Keer, R.: Xoodyak, a lightweight cryptographic scheme. IACR ToSC (S1) (2020)
[16] Daemen, J.; Hoffert, S.; Van Assche, G.; Van Keer, R., The design of Xoodoo and Xoofff, IACR Trans. Symmetric Cryptol., 2018, 4, 1-38 (2018)
[17] Daemen, J., Hoffert, S., Van Assche, G., Van Keer, R.: XooTools (2018). https://github.com/KeccakTeam/Xoodoo/tree/master/XooTools
[18] Daemen, J., Peeters, M., Van Assche, G., Bertoni, G.: On alignment in Keccak. Note (2011) · Zbl 1306.94028
[19] Daemen, J.; Rijmen, V.; De Prisco, R.; Yung, M., Understanding two-round differentials in AES, Security and Cryptography for Networks, 78-94 (2006), Heidelberg: Springer, Heidelberg · Zbl 1152.94413
[20] Daemen, J.; Rijmen, V.; Honary, B., The wide trail design strategy, Cryptography and Coding, 222-238 (2001), Heidelberg: Springer, Heidelberg · Zbl 0998.94541
[21] Daemen, J.; Rijmen, V., Plateau characteristics, IET Inf. Secur., 1, 1, 11-17 (2007)
[22] Daemen, J., Rijmen, V.: The Design of Rijndael - The Advanced Encryption Standard (AES), 2nd edn. Information Security and Cryptography. Springer, Berlin (2020). doi:10.1007/978-3-662-60769-5 · Zbl 1437.94001
[23] Huffman, W.C., Pless, V.: Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge (2003) · Zbl 1099.94030
[24] Knudsen, LR; Preneel, B., Truncated and higher order differentials, Fast Software Encryption, 196-211 (1995), Heidelberg: Springer, Heidelberg · Zbl 0939.94556
[25] Kranz, T.; Leander, G.; Stoffelen, K.; Wiemer, F., Shorter linear straight-line programs for MDS matrices, IACR Trans. Symmetric Cryptol., 2017, 4, 188-211 (2017)
[26] Künzer, M., Tentler, W.: Zassenhaus-algorithmus. https://mo.mathematik.uni-stuttgart.de/inhalt/beispiel/beispiel1105/
[27] Leander, G.; Poschmann, A.; Carlet, C.; Sunar, B., On the classification of 4 bit S-boxes, Arithmetic of Finite Fields, 159-176 (2007), Heidelberg: Springer, Heidelberg · Zbl 1184.94239
[28] Li, C.; Wang, Q., Design of lightweight linear diffusion layers from near-MDS matrices, IACR Trans. Symmetric Cryptol., 2017, 1, 129-155 (2017)
[29] Matsui, M.; Helleseth, T., Linear cryptanalysis method for DES cipher, Advances in Cryptology — EUROCRYPT ’93, 386-397 (1994), Heidelberg: Springer, Heidelberg · Zbl 0951.94519
[30] McGeer, P.C., Sanghavi, J.V., Brayton, R.K., Sangiovanni-Vincentelli, A.L.: ESPRESSO-SIGNATURE: a new exact minimizer for logic functions. IEEE Trans. Very Large Scale Integr. Syst. 1(4), 432-440 (1993)
[31] Mella, S., Daemen, J., Van Assche, G.: New techniques for trail bounds and application to differential trails in Keccak. IACR ToSC (1) (2017)
[32] NIST: Federal information processing standard 197, advanced encryption standard (AES) (Nov 2001)
[33] NIST: Federal information processing standard 202, SHA-3 standard: Permutation-based hash and extendable-output functions (Aug 2015)
[34] Nyberg, K.; Helleseth, T., Differentially uniform mappings for cryptography, Advances in Cryptology — EUROCRYPT ’93, 55-64 (1994), Heidelberg: Springer, Heidelberg · Zbl 0951.94510
[35] Park, S.; Sung, SH; Chee, S.; Yoon, E-J; Lim, J.; Zheng, Y., On the security of Rijndael-like structures against differential and linear cryptanalysis, Advances in Cryptology — ASIACRYPT 2002, 176-191 (2002), Heidelberg: Springer, Heidelberg · Zbl 1065.68530
[36] Schwabe, P.; Stoffelen, K.; Avanzi, R.; Heys, H., All the AES you need on cortex-M3 and M4, Selected Areas in Cryptography - SAC 2016, 180-194 (2017), Cham: Springer, Cham · Zbl 1412.94209
[37] Shamsabad, MRM; Dehnavi, SM, Dynamic MDS diffusion layers with efficient software implementation, Int. J. Appl. Cryptogr., 4, 1, 36-44 (2020) · Zbl 1504.94172
[38] Stoffelen, K.: AES implementations. https://github.com/Ko-/aes-armcortexm · Zbl 1387.94100
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.