Top

Designs, Codes and Cryptography

Published in:

13-02-2020

Generalized related-key rectangle attacks on block ciphers with linear key schedule: applications to SKINNY and GIFT

Authors: Boxin Zhao, Xiaoyang Dong, Willi Meier, Keting Jia, Gaoli Wang

Published in: Designs, Codes and Cryptography | Issue 6/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper gives a new generalized key-recovery model of related-key rectangle attacks on block ciphers with linear key schedules. The model is quite optimized and applicable to various block ciphers with linear key schedule. As a proof of work, we apply the new model to two very important block ciphers, i.e. SKINNY and GIFT, which are basic modules of many candidates of the Lightweight Cryptography (LWC) standardization project by NIST. For SKINNY, we reduce the complexity of the best previous 27-round related-tweakey rectangle attack on SKINNY-128-384 from \(2^{331}\) to \(2^{294}\). In addition, the first 28-round related-tweakey rectangle attack on SKINNY-128-384 is given, which gains one more round than before. For the candidate LWC SKINNY AEAD M1, we conduct a 24-round related-tweakey rectangle attack with a time complexity of \(2^{123}\) and a data complexity of \(2^{123}\) chosen plaintexts. For the case of GIFT-64, we give the first 24-round related-key rectangle attack with a time complexity \(2^{91.58}\), while the best previous attack on GIFT-64 only reaches 23 rounds at most.

previous article Predicting truncated multiple recursive generators with unknown parameters

next article New MDS self-dual codes over finite fields of odd characteristic

Note that the authors of GIFT [7] do not give any security claim in the related-key setting, but as shown by Liu et al. [49] and Chen et al. [20], it is still theoretically meaningful to understand its security margin in this setting.

Abdelkhalek A., Sasaki Y., Todo T., Tolba M., Youssef A.M.: MILP modeling for (large) s-boxes to optimize probability of differential characteristics. IACR Trans. Symmetric Cryptol. 2017(4), 99–129 (2017).

Ankele R., Banik S., Chakraborti A., List E., Mendel F., Sim S.M., Wang G.: Related-key impossible-differential attack on reduced-round skinny. In: Proceedings of Applied Cryptography and Network Security—15th International Conference, ACNS 2017, Kanazawa, Japan, July 10–12, 2017, pp. 208–228 (2017).

Avanzi R.: The QARMA block cipher family. almost MDS matrices over rings with zero divisors, nearly symmetric even-mansour constructions with non-involutory central rounds, and search heuristics for low-latency s-boxes. IACR Trans. Symmetric Cryptol. 2017(1), 4–44 (2017).

Banik S., Bogdanov A., Isobe T., Shibutani K., Hiwatari H., Akishita T., Regazzoni F.: Midori: a block cipher for low energy. In: Proceedings of Advances in Cryptology—ASIACRYPT 2015—21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29–December 3, 2015, Part II, pp. 411–436 (2015).

Banik S., Bogdanov A., Peyrin T., Sasaki Y., Sim S.M., Tischhauser E., Todo Y.: SUNDAE-GIFT. Submission to Round 1 of the NIST Lightweight Cryptography Standardization process (2019).

Banik S., Chakraborti A., Iwata T., Minematsu K., Nandi M., Peyrin T., Sasaki Y., Sim S.M., Todo Y.: GIFT-COFB. Submission to Round 1 of the NIST Lightweight Cryptography Standardization process (2019).

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: Proceedings of Cryptographic Hardware and Embedded Systems—CHES 2017—19th International Conference, Taipei, Taiwan, September 25–28, 2017, pp. 321–345 (2017).

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).MATH

Beierle C., Jean J., Kölbl S., Leander G., Moradi A., Peyrin T., Sasaki Y., Sasdrich P., Sim S.M.: SKINNY-AEAD and SKINNY-Hash v1.0. Submission to Round 1 of the NIST Lightweight Cryptography Standardization process (2019).

10.

Beierle C., Jean J., Kölbl S., Leander G., Moradi A., Peyrin T., Sasaki Y., Sasdrich P., Sim S.M.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Proceedings of Advances in Cryptology—CRYPTO 2016—36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14–18, 2016, Part II, pp. 123–153 (2016).

11.

Beierle C., Leander G., Moradi A., Rasoolzadeh S.: CRAFT: lightweight tweakable block cipher with efficient protection against DFA attacks. IACR Trans. Symmetric Cryptol. 2019(1), 5–45 (2019).

12.

Biham E., Dunkelman O., Keller N.: A related-key rectangle attack on the full KASUMI. In: Proceedings of Advances in Cryptology - ASIACRYPT 2005, 11th International Conference on the Theory and Application of Cryptology and Information Security, Chennai, India, December 4–8, pp. 443–461 (2005).

13.

Biham E., Dunkelman O., Keller N.: New results on boomerang and rectangle attacks. In: Fast Software Encryption, 9th International Workshop, FSE 2002, Leuven, Belgium, February 4–6, 2002, Revised Papers, pp. 1–16 (2002).

14.

Biham E., Dunkelman O., Keller N.: Related-key boomerang and rectangle attacks. In: Proceedings of Advances in Cryptology—EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22–26, 2005, pp. 507–525 (2005).

15.

Biham E., Dunkelman O., Keller N.: The rectangle attack—rectangling the serpent. In: Proceedings of Advances in Cryptology—EUROCRYPT 2001, International Conference on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, May 6–10, 2001, pp. 340–357 (2001).

16.

Biham E., Shamir A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes A., Vanstone S.A. (eds.) Advances in Cryptology—CRYPTO 90, vol. 537, pp. 2–21. Lecture Notes in Computer ScienceSpringer, New York (1991).CrossRef

17.

Biryukov A., Khovratovich D.: Related-key cryptanalysis of the full AES-192 and AES-256. In: Proceedings of Advances in Cryptology—ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6–10, 2009, pp. 1–18 (2009).

18.

Bogdanov A., Knudsen L.R., Leander G., Paar C., Poschmann A., Robshaw M.J.B., Seurin Y., Vikkelsoe C.: PRESENT: an ultra-lightweight block cipher. In: Proceedings of Cryptographic Hardware and Embedded Systems—CHES 2007, 9th International Workshop, Vienna, Austria, September 10–13, 2007, pp. 450–466 (2007).

19.

Canteaut A., Duval S., Leurent G., Naya-Plasencia M., Perrin L., Pornin T., Schrottenloher A.: Saturnin v1: a suite of lightweight symmetric algorithms for post-quantum security. Submission to Round 1 of the NIST Lightweight Cryptography Standardization process (2019).

20.

Chen L., Wang G., Zhang G.: MILP-based related-key rectangle attack and its application to GIFT, Khudra, MIBS. Accepted by The Computer Journal.

21.

Chen H., Zong R., Dong X.: Improved Differential Attacks on GIFT-64. To appear in ICICS 2019.

22.

Cid C., Huang T., Peyrin T., Sasaki Y., Song L.: Boomerang connectivity table: a new cryptanalysis tool. In: Proceedings of Advances in Cryptology—EUROCRYPT 2018—37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29–May 3, 2018, Part II, pp. 683–714 (2018).

23.

Daemen J., Rijmen V.: The Design of Rijndael: AES—The Advanced Encryption Standard. Information Security and CryptographySpringer, New York (2002).CrossRef

24.

Dunkelman O., Keller N., Shamir A.: A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3g telephony. In: Proceedings of Advances in Cryptology—CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15–19, 2010, pp. 393–410 (2010).

25.

Guo J., Peyrin T., Poschmann A., Robshaw M.J.B.: The LED block cipher. In: Proceedings of Cryptographic Hardware and Embedded Systems—CHES 2011—13th International Workshop, Nara, Japan, September 28–October 1, 2011, pp. 326–341 (2011).

26.

Iwata T., Khairallah M., Minematsu K., Peyrin T., Sasaki Y., Sim S.M., Sun L.: Thank Goodness It’s Friday (TGIF). Submission to Round 1 of the NIST Lightweight Cryptography Standardization process (2019).

27.

Iwata T., Khairallah M., Minematsu K., Peyrin T.: Remus v1. Submission to Round 1 of the NIST Lightweight Cryptography Standardization Process (2019).

28.

Iwata T., Khairallah M., Minematsu K., Peyrin T.: Romulus v1. Submission to Round 1 of the NIST Lightweight Cryptography Standardization Process (2019).

29.

Jean J., Nikolić I., Peyrin T., Seurin Y.: Submission to Caesar: Deoxys v1.41, (October 2016).

30.

Jean J., Nikolic I., Peyrin T.: Tweaks and keys for block ciphers: the TWEAKEY framework. In: Proceedings of Advances in Cryptology—ASIACRYPT 2014—20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, ROC, December 7–11, 2014, Part II, pp. 274–288 (2014).

31.

Kelsey J., Kohno T., Schneier B.: Amplified boomerang attacks against reduced-round MARS and serpent. In: Proceedings of Fast Software Encryption, 7th International Workshop, FSE 2000, New York, NY, USA, April 10–12, 2000, pp. 75–93 (2000).

32.

Krovetz T., Rogaway P.: The software performance of authenticated-encryption modes. In: Fast Software Encryption—18th International Workshop, FSE 2011, Lyngby, Denmark, February 13–16, 2011, Revised Selected Papers, pp. 306–327 (2011).

33.

Liu Y., Sasaki Y.: Related-key boomerang attacks on GIFT with automated trail search including bct effect. Cryptology ePrint Archive, Report 2019/669 (2019).

34.

Liu G., Ghosh M., Song L.: Security analysis of SKINNY under related-tweakey settings (long paper). IACR Trans. Symmetric Cryptol. 2017(3), 37–72 (2017).

35.

Moradi A., Poschmann A., Ling S., Paar C., Wang H.: Pushing the limits: a very compact and a threshold implementation of AES. In: Proceedings of Advances in Cryptology—EUROCRYPT 2011—30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15–19, 2011, pp. 69–88 (2011).

36.

Murphy S.: The return of the cryptographic boomerang. IEEE Trans. Inf. Theory 57(4), 2517–2521 (2011).MathSciNetCrossRef

37.

National Institute of Standards and Technology (NIST): Lightweight cryptography (LWC) standardization process. https://csrc.nist.gov/Projects/Lightweight-Cryptography/Round-1-Candidates (2019).

38.

Sadeghi S., Mohammadi T., Bagheri N.: Cryptanalysis of reduced round SKINNY block cipher. IACR Trans. Symmetric Cryptol. 2018(3), 124–162 (2018).

39.

Sasaki Y., Todo Y.: New impossible differential search tool from design and cryptanalysis aspects - revealing structural properties of several ciphers. In: Proceedings of Advances in Cryptology—EUROCRYPT 2017—36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30–May 4, 2017, Part III, pp. 185–215 (2017).

40.

Sasaki Y.: Integer linear programming for three-subset meet-in-the-middle attacks: application to GIFT. In: Proceedings of Advances in Information and Computer Security—13th International Workshop on Security, IWSEC 2018, Sendai, Japan, September 3–5, 2018, pp. 227–243 (2018).

41.

Selçuk A.A.: On probability of success in linear and differential cryptanalysis. J. Cryptol. 21(1), 131–147 (2008).MathSciNetCrossRef

42.

Shi D., Sun S., Derbez P., Todo Y., Sun B., Hu L.: Programming the demirci-selçuk meet-in-the-middle attack with constraints. In: Proceedings of Advances in Cryptology—ASIACRYPT 2018—24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Part II, pp. 3–34 (2018).

43.

Song L., Qin X., Lei H.: Boomerang connectivity table revisited. Application to SKINNY and AES. IACR Trans. Symmetric Cryptol. 2019(1), 118–141 (2019).

44.

Sun S., Gerault D., Lafourcade P., Yang Q., Todo Y., Qiao K., Lei H.: Analysis of AES, SKINNY, and others with constraint programming. IACR Trans. Symmetric Cryptol. 2017(1), 281–306 (2017).

45.

The CAESAR Committee: CAESAR: competition for authenticated encryption: security, applicability, and robustness (2014).

46.

Tolba M., Abdelkhalek A., Youssef A.M.: Impossible differential cryptanalysis of reduced-round SKINNY. In: Proceedings of Progress in Cryptology—AFRICACRYPT 2017—9th International Conference on Cryptology in Africa, Dakar, Senegal, May 24–26, 2017, pp. 117–134 (2017).

47.

Wagner D.A.: The boomerang attack. In: Proceedings of Fast Software Encryption, 6th International Workshop, FSE ’99, Rome, Italy, March 24–26, 1999, pp. 156–170 (1999).

48.

Wang H., Peyrin T.: Boomerang switch in multiple rounds. Application to AES variants and Deoxys. IACR Trans. Symmetric Cryptol. 2019(1), 142–169 (2019).

49.

Zhu B., Dong X., Yu H.: MILP-based differential attack on round-reduced GIFT. In: Proceedings of Topics in Cryptology—CT-RSA 2019—The Cryptographers’ Track at the RSA Conference 2019, San Francisco, CA, USA, March 4–8, 2019, pp. 372–390 (2019).

Title: Generalized related-key rectangle attacks on block ciphers with linear key schedule: applications to SKINNY and GIFT
Authors: Boxin Zhao
Xiaoyang Dong
Willi Meier
Keting Jia
Gaoli Wang
Publication date: 13-02-2020
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 6/2020
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-020-00730-1

Springer Professional

Generalized related-key rectangle attacks on block ciphers with linear key schedule: applications to SKINNY and GIFT

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 6/2020

Quantum attacks on some feistel block ciphers

Relative generalized Hamming weights of affine Cartesian codes

New MDS self-dual codes over finite fields of odd characteristic

Block transitive codes attaining the Tsfasman–Vladut–Zink bound

Partially APN functions with APN-like polynomial representations

Linear codes with few weights from cyclotomic classes and weakly regular bent functions

Premium Partner