×

Block cipher invariants as eigenvectors of correlation matrices. (English) Zbl 1457.94099

Summary: A new approach to invariant subspaces and nonlinear invariants is developed. This results in both theoretical insights and practical attacks on block ciphers. It is shown that, with minor modifications to some of the round constants, Midori-64 has a nonlinear invariant with \(2^{96} + 2^{64}\) corresponding weak keys. Furthermore, this invariant corresponds to a linear hull with maximal correlation. By combining the new invariant with integral cryptanalysis, a practical key-recovery attack on ten rounds of unmodified Midori-64 is obtained. The attack works for \(2^{96}\) weak keys and irrespective of the choice of round constants. The data complexity is \(1.25 \cdot 2^{21}\) chosen plaintexts, and the computational cost is dominated by \(2^{56}\) block cipher calls. The validity of the attack is verified by means of experiments.

MSC:

94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing

Software:

PRINCE; SKINNY; Midori
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] M.A. Abdelraheem, M. Ågren, P. Beelen, G. Leander, On the distribution of linear biases: three instructive examples, in R. Safavi-Naini, R. Canetti, editors, CRYPTO 2012. LNCS, vol. 7417 (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, August 19-23, 2012), pp. 50-67 · Zbl 1294.94029
[2] Ankele, R.; Dobraunig, C.; Guo, J.; Lambooij, E.; Leander, G.; Todo, Y., Zero-correlation attacks on tweakable block ciphers with linear tweakey expansion, IACR Trans. Symmetric Cryptol, 2019, 1, 192-235 (2019)
[3] S. Banik, A. Bogdanov, T. Isobe, K. Shibutani, H. Hiwatari, T. Akishita, F. Regazzoni, Midori: A block cipher for low energy, in T. Iwata, J.H. Cheon, editors, ASIACRYPT 2015, Part II. LNCS, vol. 9453 (Springer, Heidelberg, Germany, Auckland, New Zealand, Nov 30-Dec 3, 2015), pp. 411-436. 10.1007/978-3-662-48800-3_17 · Zbl 1382.94057
[4] C. Beierle, A. Canteaut, G. Leander, Y. Rotella, Proving resistance against invariant attacks: How to choose the round constants, in J. Katz, H. Shacham, editors, CRYPTO 2017, Part II. LNCS, vol. 10402 (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, Aug 20-24, 2017), pp. 647-678 · Zbl 1410.94045
[5] C. Beierle, J. Jean, S. Kölbl, G. Leander, A. Moradi, T. Peyrin, Y. Sasaki, P. Sasdrich, S.M. Sim, The SKINNY family of block ciphers and its low-latency variant MANTIS, in M. Robshaw, J. Katz, editor, CRYPTO 2016, Part II. LNCS, vol. 9815 (Springer, Heidelberg, Germany, Santa Barbara, CA, USA, Aug 14-18, 2016), pp. 123-153. 10.1007/978-3-662-53008-5_5 · Zbl 1372.94412
[6] T. Beyne, Block cipher invariants as eigenvectors of correlation matrices, in ASIACRYPT 2018, Part I. LNCS (Springer, Heidelberg, Germany, Dec 2018), pp. 3-31. 10.1007/978-3-030-03326-2_1 · Zbl 1446.94102
[7] T. Beyne, Block cipher invariants as eigenvectors of correlation matrices (full version). Cryptology ePrint Archive, Report 2018/763 (2018). https://eprint.iacr.org/2018/763 · Zbl 1446.94102
[8] A. Biryukov, L. Perrin, State of the art in lightweight symmetric cryptography. Cryptology ePrint Archive, Report 2017/511 (2017). http://eprint.iacr.org/2017/511
[9] J. Borghoff, A. Canteaut, T. Güneysu, E.B. Kavun, M. Knežević, L.R. Knudsen, G. Leander, V. Nikov, C. Paar, C. Rechberger, P. Rombouts, S.S. Thomsen, T. Yalçin, PRINCE: a low-latency block cipher for pervasive computing applications-extended abstract, in X. Wang, K. Sako, editor, ASIACRYPT 2012. LNCS, vol. 7658 (Springer, Heidelberg, Germany, Beijing, China, Dec 2-6, 2012), pp. 208-225. 10.1007/978-3-642-34961-4_14 · Zbl 1292.94035
[10] T. Ceccherini-Silberstein, F. Scarabotti, F. Tolli, in Harmonic Analysis on Finite Groups (Cambridge University Press, Cambridge, 2008) · Zbl 1149.43001
[11] J. Daemen, R. Govaerts, J. Vandewalle, Correlation matrices, in B. Preneel, editor, FSE’94. LNCS, vol. 1008 (Springer, Heidelberg, Germany, Leuven, Belgium, Dec 14-16, 1995), pp. 275-285 · Zbl 0939.94516
[12] J. Daemen, V. Rijmen, The wide trail design strategy, in B. Honary, editor, 8th IMA International Conference on Cryptography and Coding, Dec 17-19, 2001. LNCS, vol. 2260 (Springer, Heidelberg, Germany, Cirencester, UK), pp. 222-238 · Zbl 0998.94541
[13] P. Diaconis, in Group Representations in Probability and Statistics, Lecture Notes-Monograph Series. vol. 11 (Institute of Mathematical Statistics, Hayward, CA, 1988). 10.1214/lnms/1215467418 · Zbl 0695.60012
[14] C. Dobraunig, M. Eichlseder, D. Kales, F. Mendel, Practical key-recovery attack on MANTIS5. IACR Trans. Symm. Cryptol. 2016(2), 248-260 (2016). 10.13154/tosc.v2016.i2.248-260, http://tosc.iacr.org/index.php/ToSC/article/view/573
[15] B. Dravie, J. Parriaux, P. Guillot, G. Millérioux, Matrix representations of vectorial Boolean functions and eigenanalysis. Cryptogr. Commun. Discrete Struct. Boolean Funct. Seq. 8(4), 555-577 (2016). 10.1007/s12095-015-0160-7, https://hal.archives-ouvertes.fr/hal-01259921 · Zbl 1372.94424
[16] M. Eichlseder, D. Kales, Clustering related-tweak characteristics: application to MANTIS-6. IACR Trans. Symm. Cryptol.2018(2), 111-132 (2018). 10.13154/tosc.v2018.i2.111-132
[17] W. Feller, in An Introduction to Probability Theory and Its Applicatons. vol. 2 (Wiley, New York, 1971)
[18] J. Guo, J. Jean, I. Nikolic, K. Qiao, Y. Sasaki, S.M. Sim, Invariant subspace attack against Midori64 and the resistance criteria for S-box designs. IACR Trans. Symm. Cryptol.2016(1), 33-56 (2016). 10.13154/tosc.v2016.i1.33-56, http://tosc.iacr.org/index.php/ToSC/article/view/534
[19] L.R. Knudsen, D. Wagner, Integral cryptanalysis, in J. Daemen, V. Rijmen, editors, FSE 2002, Feb 4-6, 2002. LNCS, vol. 2365 (Springer, Heidelberg, Germany, Leuven, Belgium), pp. 112-127 · Zbl 1045.94527
[20] G. Leander, M.A. Abdelraheem, H. AlKhzaimi, E. Zenner, A cryptanalysis of PRINTcipher: the invariant subspace attack, in P. Rogaway, editor, CRYPTO 2011, Aug 14-18, 2011. LNCS, vol. 6841 (Springer, Heidelberg, Germany, Santa Barbara, CA, USA), pp. 206-221 · Zbl 1287.94080
[21] Lin, L.; Wu, W., Meet-in-the-middle attacks on reduced-round Midori64, IACR Trans. Symm. Cryptol, 2017, 1, 215-239 (2017)
[22] A. Luykx, B. Mennink, K.G. Paterson, Analyzing multi-key security degradation, in T. Takagi, T. Peyrin, editors, ASIACRYPT 2017, Part II, Dec 3-7, 2017. LNCS, vol. 10625 (Springer, Heidelberg, Germany, Hong Kong, China), pp. 575-605 · Zbl 1417.94071
[23] M. Matsui, Linear cryptanalysis method for DES cipher, in T. Helleseth, editor, EUROCRYPT’93, May 23-27, 1994. LNCS, vol. 765 (Springer, Heidelberg, Germany, Lofthus, Norway), pp. 386-397 · Zbl 0951.94519
[24] K. Nyberg, Linear approximation of block ciphers (rump session), in A.D. Santis, editor, EUROCRYPT’94, May 9-12, 1995. LNCS, vol. 950 (Springer, Heidelberg, Germany, Perugia, Italy), pp. 439-444 · Zbl 0885.94023
[25] Y. Todo, G. Leander, Y. Sasaki, Nonlinear invariant attack-practical attack on full SCREAM, iSCREAM, and Midori64, in J.H. Cheon, T. Takagi, editors, ASIACRYPT 2016, Part II, Dec 4-8, 2016. LNCS, vol. 10032 (Springer, Heidelberg, Germany, Hanoi, Vietnam), pp. 3-33. 10.1007/978-3-662-53890-6_1 · Zbl 1380.94126
[26] C. Zhan, W. Xiaoyun, Impossible differential cryptanalysis of Midori. Cryptology ePrint Archive, Report 2016/535 (2016). http://eprint.iacr.org/2016/535
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.