Zero-correlation attacks: statistical models independent of the number of approximations. (English) Zbl 1411.94089

Summary: Multiple and multidimensional zero-correlation linear cryptanalysis have been two of the most powerful cryptanalytic techniques for block ciphers, and it has been shown that the differentiating factor of these two statistical models is whether distinct plaintexts are assumed or not. Nevertheless, questions remain regarding how these analyses can be universalized without any limitations and can be used to accurately estimate the data complexity and the success probability.
More concretely, the current models for multiple zero-correlation (MPZC) and multidimensional zero-correlation (MDZC) cryptanalysis are not valid in the setting with a limited number of approximations and the accuracy of the estimation for data complexity can not be guaranteed. Besides, in a lot of cases, using too many approximations may cause an exhaustive search when we want to launch key-recovery attacks. In order to generalize the original models using the normal approximation of the \(\chi^2\)-distribution, we provide a more accurate approach to estimate the data complexity and the success probability for MPZC and MDZC cryptanalysis without such approximation. Since these new models directly rely on the \(\chi^{2}\)-distribution, we call them the \(\chi ^{2}\) MPZC and MDZC models. An interesting thing is that the chi-square-multiple zero-correlation (\(\chi^{2}\)-MPZC) model still works even though we only have a single zero-correlation linear approximation. This fact puts an end to the situation that the basic zero-correlation linear cryptanalysis requires the full codebook under the known-plaintext attack setting.
As an illustration, we apply the \(\chi^{2}\)-MPZC model to analyze TEA and XTEA. These new attacks cover more rounds than the previous MPZC attacks. Moreover, we reconsider the multidimensional zero-correlation (MDZC) attack on 14-round CLEFIA-192 by utilizing less zero-correlation linear approximations. In addition, some other ciphers which already have MDZC analytical results are reevaluated and the data complexities under the new model are all less than or equal to those under the original model. Some experiments are conducted in order to verify the validity of the new models, and the experimental results convince us that the new models provide more precise estimates of the data complexity and the success probability.


94A60 Cryptography


Full Text: DOI


[1] Biham E., Biryukov A., Shamir A.: Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. In: Stem J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 12-23. Springer, Berlin (1999). · Zbl 0927.94013
[2] Biham, E; Shamir, A, Differential cryptanalysis of DES-like cryptosystems, J. Cryptol., 4, 3-72, (1991) · Zbl 0729.68017
[3] Blondeau C., Nyberg K.: On distinct known plaintext attacks. http://users.ics.aalto.fi/ blondeau/PDF/WCC_2015.pdf.
[4] Blondeau, C; Nyberg, K, Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity, Des. Codes Cryptogr., 82, 319-349, (2017) · Zbl 1402.94052
[5] Bogdanov A., Geng H., Wang M., Wen L., Collard B.: Zero-correlation linear cryptanalysis with FFT and improved attacks on ISO standards Camellia and CLEFIA. In: Lange T., Lauter K., Lisoněk P. (eds.) SAC 2013. LNCS, vol. 8282, pp. 306-323. Springer, Heidelberg (2014). · Zbl 1323.94102
[6] Bogdanov A., Leander G., Nyberg K., Wang M.: Integral and multidimensional linear distinguishers with correlation zero. In: Wang X., Sako K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 244-261. Springer, Heidelberg (2012). · Zbl 1292.94031
[7] Bogdanov, A; Rijmen, V, Linear hulls with correlation zero and linear cryptanalysis of block ciphers, Des. Codes Cryptogr., 70, 369-383, (2014) · Zbl 1323.94103
[8] Bogdanov A., Wang M.: Zero correlation linear cryptanalysis with reduced data complexity. In: Canteaut A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 29-48. Springer, Heidelberg (2012). · Zbl 1282.94035
[9] Bogdanov A., Boura C., Rijmen V., Wang M., Wen L., Zhao J.: Key difference invariant bias in block ciphers. In: Salo K., Sarkar P. (eds.) ASIACRYPT 2013. LNCS, vol. 8269, pp. 357-376. Springer, Heidelberg (2013). · Zbl 1327.94034
[10] Chen J., Wang M., Preneel B.: Impossible differential cryptanalysis of the lightweight block ciphers TEA, XTEA and HIGHT. In: Progress in Cryptology—AFRICACRYPT 2012, pp. 117-137. Springer, Heidelberg (2012). · Zbl 1304.94039
[11] Hong S., Hong D., Ko Y., Chang D., Lee W., Lee S.: Differential cryptanalysis of TEA and XTEA. In: Lim J., Lee D. (eds.) ICISC 2003. LNCS, vol. 2971, pp. 402-417. Springer, Berlin (2004). · Zbl 1092.94507
[12] Huang J., Vaudenay S., Lai X., Nyberg K.: Capacity and data complexity in multidimensional linear attack. In: Advances in Cryptology—CRYPTO 2015, pp. 141-160. Springer, Berlin (2015). · Zbl 1369.94540
[13] Isobe T., Shibutani K.: Security analysis of the lightweight block ciphers XTEA, LED and Piccolo. In: Susilo W., Mu Y., Seberry J. (eds.) IACISP 2012. LNCS, vol. 7372, pp. 71-86. Springer, Heidelberg (2012). · Zbl 1291.94103
[14] Kelsey J., Schneier B., Wagner D.: Key-schedule cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES. In: Kobitz N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 237-251. Springer, Heidelberg (1996). · Zbl 1329.94066
[15] Knudsen L.: DEAL—A 128-Bit Block Cipher. NIST AES Proposal (1998).
[16] Matsui M.: Linear cryptanalysis method for DES cipher. In: Helleseth T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386-397. Springer, Berlin (1994). · Zbl 0951.94519
[17] Moon D., Hwang K., Lee W., Lee S., Lim J.: Impossible differential cryptanalysis of reduced round XTEA and TEA. In: Daemon J., Rijmen V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 49-60. Springer, Berlin (2002). · Zbl 1045.94529
[18] Needham R.M., Wheeler D.J.: TEA, a tiny encryption algorithm. In: Preneel B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 363-366 (1995). · Zbl 0939.94550
[19] Needham R.M., Wheeler D.J.: TEA Extensions. Report. Cambridge University, Cambridge (1997).
[20] Phan, RCW, Mini advanced encryption standard (mini-AES): a testbed for cryptanalysis students, Cryptologia, 26, 283-306, (2002)
[21] Sasaki Y., Wang L., Sakai Y., Sakiyama K., Ohta K.: Three-subset meet-in-the-middle attack on reduced XTEA. In: Mitrokotsa A., Vaudenay S. (eds.) AFRICACRYPT 2012. LNCS, vol. 7374, pp. 138-154. Springer, Heidelberg (2012). · Zbl 1304.94083
[22] Sekar G., Mouha N., Velichkov V., Preneel B.: Meet-in-the-middle attacks on reduced-round XTEA. In: Kiayias A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 250-267. Springer, Heidelberg (2011). · Zbl 1284.94109
[23] Soleimany, H; Nyberg, K, Zero-correlation linear cryptanalysis of reduced-round lblock, Des. Codes Cryptogr., 73, 683-698, (2014) · Zbl 1310.94169
[24] Wang Y., Wu W.: Improved multidimensional zero-correlation linear cryptanalysis and applications to LBlock and TWINE. In: Susilo W., Mu Y. (eds.) ACISP 2014. LNCS, vol. 8544, pp. 1-16. Springer, Cham (2014). · Zbl 1318.94085
[25] Wen L., Wang M., Bogdanov A.: Multidimensional zero-correlation linear cryptanalysis of E2. In: Pointcheval D., Vergnaud D. (eds.) AFRICACRYPT 2014. LNCS, vol. 8649, pp. 147-164. Springer, Cham (2014). · Zbl 1288.94085
[26] Wen L., Wang M., Bogdanov A., Chen H.: General application of FFT in cryptanalysis and improved attack on CAST-256. In: Meier W., Mukhopadhyay D. (eds.) INDOCRYPT 2014. LNCS, vol. 8885, pp. 161-176. Springer, Cham (2014). · Zbl 1337.94079
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.