nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Alzette: A 64-Bit ARX-box

(Feat. CRAX and TRAX)

verfasst von : Christof Beierle, Alex Biryukov, Luan Cardoso dos Santos, Johann Großschädl, Léo Perrin, Aleksei Udovenko, Vesselin Velichkov, Qingju Wang

Erschienen in: Advances in Cryptology – CRYPTO 2020

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

S-boxes are the only source of non-linearity in many symmetric primitives. While they are often defined as being functions operating on a small space, some recent designs propose the use of much larger ones (e.g., 32 bits). In this context, an S-box is then defined as a subfunction whose cryptographic properties can be estimated precisely.

We present a 64-bit ARX-based S-box called Alzette, which can be evaluated in constant time using only 12 instructions on modern CPUs. Its parallel application can also leverage vector (SIMD) instructions. One iteration of Alzette has differential and linear properties comparable to those of the AES S-box, and two are at least as secure as the AES super S-box. As the state size is much larger than the typical 4 or 8 bits, the study of the relevant cryptographic properties of Alzette is not trivial.

We further discuss how such wide S-boxes could be used to construct round functions of 64-, 128- and 256-bit (tweakable) block ciphers with good cryptographic properties that are guaranteed even in the related-tweak setting. We use these structures to design a very lightweight 64-bit block cipher (Crax) which outperforms SPECK-64/128 for short messages on micro-controllers, and a 256-bit tweakable block cipher (Trax) which can be used to obtain strong security guarantees against powerful adversaries (nonce misuse, quantum attacks).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Cryptanalysis of LEDAcrypt

Nächstes Kapitel Order-Fairness for Byzantine Consensus

Along with some conditions on the linear layer, in particular its branching number.

Under the Markov assumption which allows to treat the rounds as independent from each other.

We exploit this property to design Alzette, as explained in Sect. 2.2.

Note that those are independent of the actual round constants as the probability corresponds to the average probability over all keys when analyzing Alzette as a block cipher where independent subkeys are used instead of round constants.

The constants in Sparkle were derived from the fractional digits of e, excluding some blocks. For the excluded blocks, the actual absolute correlations are slightly higher than the theoretical bound, but all smaller than \(2^{-8}\).

Note that, in a related-tweak differential, we allow non-zero input differences not only in the plaintext, but also in the tweak value. This is because the attacker can choose the tweak, i.e., he has access to an encryption oracle for the cipher instantiated with a tweak T and a (random) key K and to an encryption oracle for a cipher instantiated with tweak \(T \oplus \varDelta \) and key K, where \(\varDelta \) can be freely chosen.

We do not consider related-cipher attacks between the obtained block cipher and the corresponding tweakable block cipher.

The source code of these Speck implementations and the complete benchmarking results are available on the CryptoLux wiki at http://www.cryptolux.org/index.php/FELICS_Block_Ciphers_Detailed_Results (“Scenario 0”).

We remark that in several modes of operations, like \(\varTheta \)CB, it is necessary to take care of domain separation. For instance, a few bits of the tweak can be reserved for this purpose. For example, the NIST lightweight AEAD candidate SKINNY-AEAD [10] simply dedicates one byte of the tweak for domain separation. Therefore, if a full 256-bit tweak needs to be exploited, a tweakable block cipher with a (slightly) larger tweak length of \(256+x\) would be beneficial.

AlTawy, R., et al.: SpoC: an authenticated cipher. NIST round 2 lightweight candidate (2019). https://csrc.nist.gov/CSRC/media/Projects/lightweight-cryptography/documents/round-2/spec-doc-rnd2/spoc-spec-round2.pdf

AlTawy, R., Gong, G., He, M., Mandal, K., Rohit, R.: SPIX: an authenticated cipher. NIST round 2 lightweight candidate (2019). https://csrc.nist.gov/CSRC/media/Projects/lightweight-cryptography/documents/round-2/spec-doc-rnd2/spix-spec-round2.pdf

AlTawy, R., Rohit, R., He, M., Mandal, K., Yang, G., Gong, G.: sLiSCP: Simeck-based permutations for lightweight sponge cryptographic primitives. In: Adams, C., Camenisch, J. (eds.) SAC 2017. LNCS, vol. 10719, pp. 129–150. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-72565-9_7CrossRef

Altawy, R., Rohit, R., He, M., Mandal, K., Yang, G., Gong, G.: SLISCP-light: towards hardware optimized sponge-specific cryptographic permutations. ACM Trans. Embed. Comput. Syst. 17(4), 81:1–81:26 (2018)CrossRef

Barreto, P., Nikov, V., Nikova, S., Rijmen, V., Tischhauser, E.: Whirlwind: a new cryptographic hash function. Des. Codes Cryptogr. 56(2), 141–162 (2010). https://doi.org/10.1007/s10623-010-9391-yMathSciNetCrossRefMATH

Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK families of lightweight block ciphers. IACR Cryptology ePrint Archive 2013, 404 (2013). http://eprint.iacr.org/2013/404

Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK block ciphers on AVR 8-bit microcontrollers. Cryptology ePrint Archive, Report 2014/947 (2014). http://eprint.iacr.org/2014/947

Beierle, C., et al.: SCHWAEMM and ESCH: lightweight authenticated encryption and hashing using the Sparkle permutation family. NIST round 2 lightweight candidate (2019). https://csrc.nist.gov/CSRC/media/Projects/lightweight-cryptography/documents/round-2/spec-doc-rnd2/sparkle-spec-round2.pdf

Beierle, C., et al.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. Part II. LNCS, vol. 9815, pp. 123–153. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_5CrossRef

10.

Beierle, C., et al.: SKINNY-AEAD and SKINNY-Hash. NIST round 2 lightweight candidate (2019). https://csrc.nist.gov/CSRC/media/Projects/lightweight-cryptography/documents/round-2/spec-doc-rnd2/SKINNY-spec-round2.pdf

11.

Bernstein, D.J., et al.: Gimli: a cross-platform permutation. In: Fischer, W., Homma, N. (eds.) CHES 2017. LNCS, vol. 10529, pp. 299–320. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66787-4_15CrossRef

12.

Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_1CrossRef

13.

Biryukov, A., De Cannière, C., Braeken, A., Preneel, B.: A toolbox for cryptanalysis: linear and affine equivalence algorithms. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 33–50. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_3CrossRef

14.

Biryukov, A., Velichkov, V., Corre, Y.L.: Automatic search for the best trails in ARX: application to block cipher speck. In: Peyrin [34], pp. 289–310

15.

Canteaut, A., et al.: Saturnin: a suite of lightweight symmetric algorithms for post-quantum security. NIST round 2 lightweight candidate (2019). https://csrc.nist.gov/CSRC/media/Projects/lightweight-cryptography/documents/round-2/spec-doc-rnd2/saturnin-spec-round2.pdf

16.

Cheon, J.H., Takagi, T. (eds.): ASIACRYPT 2016. Part I. LNCS, vol. 10031. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6CrossRefMATH

17.

Dinu, D.: Efficient and secure implementations of lightweight symmetric cryptographic primitives. Ph.D. thesis, University of Luxembourg (2017). https://orbilu.uni.lu/handle/10993/33803

18.

Dinu, D., Corre, Y.L., Khovratovich, D., Perrin, L., Großschädl, J., Biryukov, A.: Triathlon of lightweight block ciphers for the Internet of things. J. Cryptogr. Eng. 9(3), 283–302 (2018). https://doi.org/10.1007/s13389-018-0193-x CrossRef

19.

Dinu, D., Perrin, L., Udovenko, A., Velichkov, V., Großschädl, J., Biryukov, A.: Design strategies for ARX with provable bounds: Sparx and LAX. In: Cheon and Takagi [16], pp. 484–513

20.

Fu, K., Wang, M., Guo, Y., Sun, S., Hu, L.: MILP-based automatic search algorithms for differential and linear trails for speck. In: Peyrin [34], pp. 268–288

21.

Gueron, S., Johnson, S., Walker, J.: SHA-512/256. Cryptology ePrint Archive, Report 2010/548 (2010). http://eprint.iacr.org/2010/548

22.

Gurobi Optimization, LLC: Gurobi optimizer reference manual (2018). http://www.gurobi.com

23.

Knudsen, L.: Deal - a 128-bit block cipher. NIST AES Proposal (1998)

24.

Kranz, T., Leander, G., Wiemer, F.: Linear cryptanalysis: key schedules and tweakable block ciphers. IACR Trans. Symmetric Cryptol. 2017(1), 474–505 (2017)

25.

Krovetz, T., Rogaway, P.: The software performance of authenticated-encryption modes. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 306–327. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21702-9_18CrossRefMATH

26.

Leander, G., Abdelraheem, M.A., AlKhzaimi, H., Zenner, E.: A cryptanalysis of PRINTcipher: the invariant subspace attack. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 206–221. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_12CrossRef

27.

Liu, Y., Wang, Q., Rijmen, V.: Automatic search of linear trails in ARX with applications to SPECK and Chaskey. In: Manulis, M., Sadeghi, A.-R., Schneider, S. (eds.) ACNS 2016. LNCS, vol. 9696, pp. 485–499. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39555-5_26CrossRef

28.

Liu, Z.: Automatic tools for differential and linear cryptanalysis of ARX ciphers. Ph.D. thesis, University of Chinese Academy of Science (2017). (in Chinese)

29.

Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48285-7_33CrossRef

30.

Matsui, M.: On correlation between the order of S-boxes and the strength of DES. In: Santis, A.D. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 366–375. Springer, Heidelberg (1995). https://doi.org/10.1007/BFb0053451CrossRef

31.

Niels, F., et al.: The Skein hash function family. Submission to the NIST SHA-3 competition (round 3) (2010)

32.

Niemetz, A., Preiner, M., Biere, A.: Boolector 2.0 system description. J. Satisf. Boolean Model. Comput. 9, 53–58 (2014 (published 2015)). https://github.com/boolector/boolector

33.

Patarin, J., Goubin, L., Courtois, N.: Improved algorithms for isomorphisms of polynomials. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 184–200. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054126CrossRef

34.

Peyrin, T. (ed.): FSE 2016. LNCS, vol. 9783. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-52993-5CrossRefMATH

35.

Peyrin, T., Seurin, Y.: Counter-in-tweak: authenticated encryption modes for tweakable block ciphers. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. Part I. LNCS, vol. 9814, pp. 33–63. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_2CrossRefMATH

36.

Sun, L., Wang, W., Wang, M.: Automatic search of bit-based division property for ARX ciphers and word-based division property. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. Part I. LNCS, vol. 10624, pp. 128–157. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_5CrossRef

37.

Todo, Y.: Structural evaluation by generalized integral property. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. Part I. LNCS, vol. 9056, pp. 287–314. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_12CrossRef

38.

Todo, Y., Leander, G., Sasaki, Y.: Nonlinear invariant attack - practical attack on full SCREAM, iSCREAM, and Midori64. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. Part II. LNCS, vol. 10032, pp. 3–33. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_1CrossRef

39.

Todo, Y., Morii, M.: Bit-based division property and application to Simon family. In: Peyrin [34], pp. 357–377

40.

Varrette, S., Bouvry, P., Cartiaux, H., Georgatos, F.: Management of an academic HPC cluster: the UL experience. In: Proceedings of the 2014 International Conference on High Performance Computing & Simulation (HPCS 2014), pp. 959–967. IEEE, Bologna, July 2014

41.

Xiang, Z., Zhang, W., Bao, Z., Lin, D.: Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers. In: Cheon and Takagi [16], pp. 648–678

Titel: Alzette: A 64-Bit ARX-box
verfasst von: Christof Beierle
Alex Biryukov
Luan Cardoso dos Santos
Johann Großschädl
Léo Perrin
Aleksei Udovenko
Vesselin Velichkov
Qingju Wang
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2020
Print ISBN: 978-3-030-56876-4

Electronic ISBN: 978-3-030-56877-1

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-56877-1_15

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner