Generalized related-key rectangle attacks on block ciphers with linear key schedule: applications to SKINNY and GIFT. (English) Zbl 1448.94236
Summary: 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.
MSC:
| 94A60 | Cryptography |
Software:
Remus; SIMON; SPECK; tweakey; Midori; Romulus; Saturnin; CRAFT; GIFT; SIMECK; QARMA; LED; SKINNY; PRESENTReferences:
| [1] | Abdelkhalek, A.; Sasaki, Y.; Todo, T.; Tolba, M.; Youssef, AM, MILP modeling for (large) s-boxes to optimize probability of differential characteristics, IACR Trans. Symmetric Cryptol., 2017, 4, 99-129 (2017) |
| [2] | 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). · Zbl 1521.94024 |
| [3] | 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) |
| [4] | 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). · Zbl 1382.94057 |
| [5] | 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). |
| [6] | 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). |
| [7] | 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). · Zbl 1450.94026 |
| [8] | 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) |
| [9] | 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). · Zbl 1372.94412 |
| [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). · Zbl 1154.94375 |
| [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). · Zbl 1045.94512 |
| [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). · Zbl 1137.94338 |
| [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). · Zbl 0981.94017 |
| [16] | Biham, E.; Shamir, A.; Menezes, A.; Vanstone, SA, Differential cryptanalysis of DES-like cryptosystems, Advances in Cryptology—CRYPTO 90, 2-21 (1991), New York: Springer, New York · Zbl 0787.94014 |
| [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). · Zbl 1267.94041 |
| [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). · Zbl 1142.94334 |
| [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). · Zbl 1428.94065 |
| [23] | Daemen, J.; Rijmen, V., The Design of Rijndael: AES—The Advanced Encryption Standard (2002), New York: Springer, New York · Zbl 1065.94005 |
| [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). · Zbl 1283.94064 |
| [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). · Zbl 1291.94092 |
| [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). · Zbl 1317.94113 |
| [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). · Zbl 0994.68635 |
| [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). · Zbl 1307.94119 |
| [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). · Zbl 1439.94046 |
| [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). · Zbl 1281.94044 |
| [36] | Murphy, S., The return of the cryptographic boomerang, IEEE Trans. Inf. Theory, 57, 4, 2517-2521 (2011) · Zbl 1366.94520 · doi:10.1109/TIT.2011.2111091 |
| [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). · Zbl 1394.94941 |
| [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). · Zbl 1398.94157 |
| [41] | Selçuk, AA, On probability of success in linear and differential cryptanalysis, J. Cryptol., 21, 1, 131-147 (2008) · Zbl 1147.68510 · doi:10.1007/s00145-007-9013-7 |
| [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). · Zbl 1446.94157 |
| [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). · Zbl 1408.94969 |
| [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). · Zbl 0942.94022 |
| [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). · Zbl 1509.94147 |
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.
