×

The phantom of differential characteristics. (English) Zbl 1458.94263

Summary: For differential cryptanalysis under the single-key model, the key schedules hardly need to be exploited in constructing the characteristics, which is based on the hypothesis of stochastic equivalence. In this paper, we study a profound effect of the key schedules on the validity of the differential characteristics. Noticing the sensitivity in the probability of the characteristics to specific keys, we label the keys where a characteristic has nonzero probability by effective keys. We propose the concept of singular characteristics which are characteristics with no effective keys, and exploit an algorithm to sieve them out by studying the key schedule. We show by a differential characteristic of PRINCE whose expected differential probability is much larger than that of a random permutation, i.e., \(2^{-35}\) vs. \(2^{-64}\). Yet, it is indeed singular which could be mis-used to mount a differential attack. Singular characteristics are found for 3-round AES and 3-round Midori-128 as well. Furthermore, taking the possible mismatches of the effective keys in a number of differential characteristics into consideration, we present singular clusters which indicates an empty intersection of the corresponding effective keys, and this is evidenced by showing two differential characteristics of the 2-round AES. We also show that characteristics are tightly linked to the key schedule, as shown in the paper, a valid characteristic in the AES-128 can be singular for the AES-192. Our results indicate a gap over the perspectives of the designers and the attackers, which warns the latter to validate the theoretically-built distinguishers. Therefore, a closer look into the characteristics is inevitable before any attack is claimed.

MSC:

94A60 Cryptography

Software:

Midori; PRINCE; KLEIN; SIMON
Full Text: DOI

References:

[1] Banik S., Bogdanov A., Isobe T., Shibutani K., Hiwatari H., Akishita T., Regazzoni F.: Midori: a block cipher for low energy. In: Advances in Cryptology—ASIACRYPT 2015, pp. 411-436. Springer (2015). · Zbl 1382.94057
[2] Biham E., Shamir A.: Differential cryptanalysis of DES-like cryptosystems. In: Advances in Cryptology—CRYPTO ’90, 10th Annual International Cryptology Conference, Santa Barbara, California, USA, 11-15 August 1990. Proceedings, pp. 2-21 (1990). · Zbl 0787.94014
[3] Biham E., Shamir A.: Differential cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer. In: Advances in Cryptology—CRYPTO ’91, 11th Annual International Cryptology Conference, Santa Barbara, California, USA, 11-15 August 1991. Proceedings, pp. 156-171 (1991).
[4] Biham E., Biryukov A., Shamir A.: Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials. In: Advances in Cryptology—EUROCRYPT ’99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, 2-6 May 1999. Proceeding, pp. 12-23 (1999). · Zbl 0927.94013
[5] Biham E., Dunkelman O., Keller N.: New results on boomerang and rectangle attacks. In: Fast Software Encryption, 9th International Workshop, FSE 2002, Leuven, Belgium, 4-6 February 2002. Revised Papers, pp. 1-16 (2002). · Zbl 1045.94512
[6] Biryukov A., Khovratovich D.: Related-key cryptanalysis of the full AES-192 and AES-256. In: Advances in Cryptology—ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, 6-10 December 2009. Proceedings, pp. 1-18 (2009). · Zbl 1267.94041
[7] Blondeau C., Gérard B.: Multiple differential cryptanalysis: theory and practice. In: Fast Software Encryption—18th International Workshop, FSE 2011, Lyngby, Denmark, 13-16 February 2011. Revised Selected Papers, pp. 35-54 (2011). · Zbl 1282.94034
[8] Borghoff J., Canteaut A., Güneysu T., Kavun E.B., Knezevic M., Knudsen L.R., Leander G., Nikov V., Paar C., Rechberger C., Rombouts P., Thomsen S.S., Yalçin T.: PRINCE—a low-latency block cipher for pervasive computing applications—extended abstract. In: Advances in Cryptology—ASIACRYPT 2012—18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, 2-6 December 2012. Proceedings, pp. 208-225 (2012). · Zbl 1292.94035
[9] Canteaut A., Fuhr T., Gilbert H., Naya-Plasencia M., Reinhard J.: Multiple differential cryptanalysis of round-reduced PRINCE. In: Fast Software Encryption—21st International Workshop, FSE 2014, London, UK, 3-5 March 2014. Revised Selected Papers, pp. 591-610 (2014). · Zbl 1382.94079
[10] Canteaut, A.; Lambooij, E.; Neves, S.; Rasoolzadeh, S.; Sasaki, Y.; Stevens, M., Refined probability of differential characteristics including dependency between multiple rounds, IACR Trans. Symmetric Cryptol., 2017, 2, 203-227 (2017)
[11] Daemen J., Rijmen V.: AES and the wide trail design strategy. In: EUROCRYPT 2002, pp. 108-109 (2002). · Zbl 1055.94514
[12] Daemen, J.; Rijmen, V., The Design of Rijndael: AES-The Advanced Encryption Standard (2002), Berlin: Springer, Berlin · Zbl 1065.94005
[13] Daemen, J.; Rijmen, V., Plateau characteristics, IET Inf. Secur., 1, 1, 11-17 (2007) · doi:10.1049/iet-ifs:20060099
[14] Derbez P., Fouque P., Jean J.: Improved key recovery attacks on reduced-round AES in the single-key setting. In: Advances in Cryptology—EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, 26-30 May 2013. Proceedings, pp. 371-387 (2013). · Zbl 1306.94044
[15] Gauravaram P., Knudsen L.R., Matusiewicz K., Mendel F., Rechberger C., Schläffer M., Thomsen S.S.: Grøstl-a SHA-3 candidate. In: Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2009).
[16] Hall C., Kelsey J., Rijmen V., Schneier B., Wagner D.: Cryptanalysis of SPEED. In: Selected Areas in Cryptography ’98, SAC’98, Kingston, Ontario, Canada, 17-18 August 1998. Proceedings, pp. 319-338 (1998). · Zbl 0929.94011
[17] Karpman P., Peyrin T., Stevens M.: Practical free-start collision attacks on 76-step SHA-1. In: Advances in Cryptology—CRYPTO 2015—35th Annual Cryptology Conference, Santa Barbara, CA, USA, 16-20 August 2015. Proceedings, Part I, pp. 623-642 (2015). · Zbl 1375.94137
[18] Khovratovich D., Nikolic I., Pieprzyk J., Sokolowski P., Steinfeld R.: Rotational cryptanalysis of ARX revisited. In: Fast Software Encryption—22nd International Workshop, FSE 2015, Istanbul, Turkey, 8-11 March 2015. Revised Selected Papers, pp. 519-536 (2015). · Zbl 1382.94128
[19] Knudsen L.R.: Iterative characteristics of DES and s \({^2}\)-DES. In: Advances in Cryptology—CRYPTO ’92, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, 16-20 August 1992. Proceedings, pp. 497-511 (1992). · Zbl 0809.94018
[20] Knudsen L.R.: Truncated and higher order differentials. In: Fast Software Encryption: Second International Workshop, Leuven, Belgium, 14-16 December 1994. Proceedings, pp. 196-211 (1994). · Zbl 0939.94556
[21] Kölbl S., Leander G., Tiessen T.: Observations on the SIMON block cipher family. In: Advances in Cryptology—CRYPTO 2015—35th Annual Cryptology Conference, Santa Barbara, CA, USA, 16-20 August 2015. Proceedings, Part I, pp. 161-185. Springer (2015). · Zbl 1369.94546
[22] Lai, X., Higher order derivatives and differential cryptanalysis, Commun. Cryptogr., 276, 227-233 (1994) · Zbl 0840.94017 · doi:10.1007/978-1-4615-2694-0_23
[23] Lai X., Massey J.L., Murphy S.: Markov ciphers and differential cryptanalysis. In: Advances in Cryptology—EUROCRYPT ’91, Workshop on the Theory and Application of Cryptographic Techniques, Brighton, UK, 8-11 April 1991, Proceedings, pp. 17-38 (1991). · Zbl 0777.94013
[24] Lallemand V., Naya-Plasencia M.: Cryptanalysis of KLEIN. In: Fast Software Encryption—21st International Workshop, FSE 2014, London, UK, 3-5 March 2014. Revised Selected Papers, pp. 451-470 (2014). · Zbl 1382.94132
[25] Leander G., Abdelraheem M., AlKhzaimi H., Zenner E.: A cryptanalysis of PRINTcipher: the invariant subspace attack. In: Advances in Cryptology—CRYPTO 2011—31st Annual Cryptology Conference, Santa Barbara, CA, USA, 14-18 August 2011. Proceedings, pp. 206-221. Springer (2011). · Zbl 1287.94080
[26] Leurent G.: Analysis of differential attacks in ARX constructions. In: Advances in Cryptology—ASIACRYPT 2012—18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, 2-6 December 2012. Proceedings, pp. 226-243 (2012). · Zbl 1292.94098
[27] Mendel F., Rechberger C., Schläffer M., Thomsen S.S.: The rebound attack: cryptanalysis of reduced whirlpool and Grøstl. In: Fast Software Encryption, 16th International Workshop, FSE 2009, Leuven, Belgium, 22-25 February 2009. Revised Selected Papers, pp. 260-276 (2009). · Zbl 1291.94130
[28] National Bureau of Standards: Data Encryption Standard. US Department of Commerce, FIPS Publication 46 (1977).
[29] Stevens M., Bursztein E., Karpman P., Albertini A., Markov Y.: The first collision for full SHA-1. In: Advances in Cryptology—CRYPTO 2017—37th Annual International Cryptology Conference, Santa Barbara, CA, USA, 20-24 August 2017. Proceedings, Part I, pp. 570-596 (2017). · Zbl 1407.94153
[30] Sun B., Liu Z., Rijmen V., Li R., Cheng L., Wang Q., AlKhzaimi H., Li C.: Links among impossible differential, integral and zero correlation linear cryptanalysis. In: Advances in Cryptology—CRYPTO 2015—35th Annual Cryptology Conference, Santa Barbara, CA, USA, 16-20 August 2015. Proceedings, Part I, pp. 95-115 (2015). · Zbl 1347.94059
[31] Sun B., Liu M., Guo J., Rijmen V., Li R.: Provable security evaluation of structures against impossible differential and zero correlation linear cryptanalysis. In: Advances in Cryptology—EUROCRYPT 2016—35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, 8-12 May 2016. Proceedings, Part I, pp. 196-213 (2016). · Zbl 1347.94058
[32] Sun, S.; Gerault, D.; Lafourcade, P.; Yang, Q.; Todo, Y.; Qiao, K.; Hu, L., Analysis of AES, skinny, and others with constraint programming, IACR Trans. Symmetric Cryptol., 2017, 1, 281-306 (2017)
[33] Sun, L.; Wang, W.; Wang, M., More accurate differential properties of LED64 and Midori64, IACR Trans. Symmetric Cryptol., 2018, 3, 93-123 (2018)
[34] Tolba M., Abdelkhalek A., Youssef A.M.: Truncated and multiple differential cryptanalysis of reduced round Midori128. In: Information Security—19th International Conference, ISC 2016, Honolulu, HI, USA, 3-6 September 2016. Proceedings, pp. 3-17 (2016). · Zbl 1397.94104
[35] Wagner D.: The boomerang attack. In: Fast Software Encryption, 6th International Workshop, FSE ’99, Rome, Italy, 24-26 March 1999. Proceedings, pp. 156-170 (1999). · Zbl 0942.94022
[36] Wang X., Yu H.: How to break MD5 and other hash functions. In: Advances in Cryptology—EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, 22-26 May 2005. Proceedings, pp. 19-35 (2005). · Zbl 1137.94359
[37] Wang X., Yin Y.L., Yu H.: Finding collisions in the full SHA-1. In: Advances in Cryptology—CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, 14-18 August 2005. Proceedings, pp. 17-36 (2005). · Zbl 1145.94454
[38] Wang G., Keller N., Dunkelman O.: The delicate issues of addition with respect to XOR differences. In: Selected Areas in Cryptography, 14th International Workshop, SAC 2007, Ottawa, Canada, 16-17 August 2007. Revised Selected Papers, pp. 212-231 (2007). · Zbl 1154.94438
[39] Wang M., Sun Y., Tischhauser E., Preneel B.: A model for structure attacks, with applications to PRESENT and Serpent. In: Fast Software Encryption—19th International Workshop, FSE 2012, Washington, DC, USA, 19-21 March 2012. Revised Selected Papers, pp. 49-68 (2012). · Zbl 1312.94098
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.