logo

SCIENCE CHINA Information Sciences, Volume 63 , Issue 1 : 112104(2020) https://doi.org/10.1007/s11432-018-9758-4

New insights on linear cryptanalysis

More info
  • ReceivedSep 17, 2018
  • AcceptedJan 14, 2019
  • PublishedDec 25, 2019

Abstract

Linear cryptanalysis is one of the most important cryptanalytic tools against block ciphers, thus modern block ciphers are always deliberately devised to avoid good long linear characteristics so as to resist linear cryptanalysis and its extensions. Differential-linear cryptanalysis, a powerful extension of linear cryptanalysis, has drawn much attention due to its applicability even in certain case that there is no good long linear characteristic of block ciphers. To further refine differential-linear cryptanalysis, we investigate the correlation distribution of differential-linear hull over random permutation and derive a concrete and concise correlation distribution accordingly. Theoretically, this could make differential-linear cryptanalysis more reasonable and precise. Moreover, the newly-proposed correlation distribution could lead to an interesting potential for improving the effectiveness of differential-linear cryptanalysis.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61672347, 61772129, 61472250, 61402288). The authors are grateful to the reviewers for their valuable suggestions and comments.


References

[1] Matsui M. Linear cryptanalysis method for DES cipher. In: Advances in Cryptology -- EUROCRYPT 1993. Berlin: Springer, 1994. 386--397. Google Scholar

[2] Kaliski B S, Robshaw M J B. Linear cryptanalysis using multiple aprroximations. In: Advances in Cryptology -- CRYPTO 1994. Berlin: Springer, 1994. 26--39. Google Scholar

[3] Biryukov A, De Cannière C, Quisquater M. On multiple linear approximations. In: Advances in Cryptology -- CRYPTO 2004. Berlin: Springer, 2004. 1--22. Google Scholar

[4] Baignères T, Junod P, Vaudenay S. How far can we go beyond linear cryptanalysis? In: Advances in Cryptology -- ASIACRYPT 2004. Berlin: Springer, 2004. 432--450. Google Scholar

[5] Hermelin M, Cho J Y, Nyberg K. Multidimensional linear cryptanalysis of reduced round Serpent. In: Proceedings of Australasian Conference on Information Security and Privacy -- ACISP 2008. Berlin: Springer, 2008. 203--215. Google Scholar

[6] Hermelin M, Cho J Y, Nyberg K. Statistical tests for key recovery using multidimensional extension of Matsui's algorithm 1. In: Advances in Cryptology -- EUROCRYPT 2009 - poster session, 2009.. Google Scholar

[7] Cho J Y, Hermelin M, Nyberg K. A new technique for multidimensional linear cryptanalysis with applications on reduced round Serpent. In: Proceedings of International Conference on Information Security and Cryptology -- ICISC 2008. Berlin: Springer, 2009. 383--398. Google Scholar

[8] Hermelin M, Cho J Y, Nyberg K. Multidimensional extension of Matsui's algorithm 2. In: Fast Software Encryption -- FSE 2009. Berlin: Springer, 2009. 209--227. Google Scholar

[9] Harpes C, Kramer G, Massey J. A generalization of linear cryptanalysis and the applicability of Matsui's piling-up lemma. In: Advances in Cryptology -- EUROCRYPT 1995. Berlin: Springer, 1995. 24--38. Google Scholar

[10] Knudsen L, Robshaw M. Non-linear approximations in linear cryptanalysis. In: Advances in Cryptology -- EUROCRYPT 1996. Berlin: Springer, 1996. 224--236. Google Scholar

[11] Courtois N T. Feistel schemes and bi-linear cryptanalysis. In: Advances in Cryptology -- CRYPTO 2004. Berlin: Springer, 2004. 23--40. Google Scholar

[12] Langford S K, Hellman M E. Differential-linear cryptanalysis. In: Advances in Cryptology -- CRYPTO 1994. Berlin: Springer, 1994. 17--25. Google Scholar

[13] Biham E, Dunkelman O, Keller N. Enhancing differential-linear cryptanalysis. In: Advances in Cryptology -- ASIACRYPT 2002. Berlin: Springer, 2002. 254--266. Google Scholar

[14] Liu Z Q, Gu D W, Zhang J, et al. Differential-multiple linear cryptanalysis. In: Proceedings of International Conference on Information Security and Cryptology -- INSCRYPT 2009. Berlin: Springer, 2010. 35--49. Google Scholar

[15] Lu J Q. A methodology for differential-linear cryptanalysis and its applications - (Extended Abstract). In: Fast Software Encryption -- FSE 2012. Berlin: Springer, 2012. 69--89. Google Scholar

[16] Lu J Q. A methodology for differential-linear cryptanalysis and its applications. Designs Codes and Cryptography, 2015, 77: 11--48 DOI: 10.1007/978-3-642-34047-5_5. Google Scholar

[17] Blondeau C, Leander G, Nyberg K. Differential-linear cryptanalysis revisited. In: Fast Software Encryption -- FSE 2014. Berlin: Springer, 2015. 411--430. Google Scholar

[18] Blondeau C, Leander G, Nyberg K. Differential-linear cryptanalysis revisited. Journal of Cryptology, 2017, 30: 859--888 DOI: 10.1007/978-3-662-46706-0_21. Google Scholar

[19] Leurent G. Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning. In: Advances in Cryptology -- EUROCRYPT 2016. Berlin: Springer, 2016. 344--371. Google Scholar

[20] Biham E, Carmeli Y. An improvement of linear cryptanalysis with addition operations with applications to FEAL-8X. In: Selected Areas in Cryptography -- SAC 2014. Berlin: Springer, 2014. 59--76. Google Scholar

[21] Bogdanov A, Rijmen V. Linear hulls with correlation zero and linear cryptanalysis of block ciphers. Des Codes Cryptogr, 2014, 70: 369-383 CrossRef Google Scholar

[22] Bogdanov A, Leander G, Nyberg K, et al. Integral and multidimensional linear distinguishers with correlation zero. In: Advances in Cryptology -- ASIACRYPT 2012. Berlin: Springer, 2012. 244--261. Google Scholar

[23] Bogdanov A, Wang M Q. Zero correlation linear cryptanalysis with reduced data complexity. In: Fast Software Encryption -- FSE 2012. Berlin: Springer, 2012. 29--48. Google Scholar

[24] Wang Y F, Wu W L. Improved multidimensional zero-correlation linear cryptanalysis and applications to LBlock and TWINE. In: Proceedings of Australasian Conference on Information Security and Privacy -- ACISP 2014. Berlin: Springer, 2014. 1--16. Google Scholar

[25] Wen L, Wang M, Bogdanov A. Multidimensional zero-correlation attacks on lightweight block cipher HIGHT: Improved cryptanalysis of an ISO standard. Inf Processing Lett, 2014, 114: 322-330 CrossRef Google Scholar

[26] Chen S, Yi W. Multidimensional zero-correlation linear cryptanalysis of the block cipher KASUMI. CrossRef Google Scholar

[27] Tolba M, Abdelkhalek A, Youssef A M. Multidimensional zero-correlation linear cryptanalysis of reduced round SPARX-128. In: Selected Areas in Cryptography -- SAC 2017. Berlin: Springer, 2017. 423--441. Google Scholar

[28] Chabaud F, Vaudenay S. Links between differential and linear cryptanalysis. In: Advances in Cryptology -- EUROCRYPT 1994. Berlin: Springer, 1995. 356--365. Google Scholar

[29] Leander G. On linear hulls, statistical saturation attacks, PRESENT and a cryptanalysis of PUFFIN. In: Advances in Cryptology -- EUROCRYPT 2011. Berlin: Springer, 2011. 303--322. Google Scholar

[30] Blondeau C, Nyberg K. New links between differential and linear cryptanalysis. In: Advances in Cryptology -- EUROCRYPT 2013. Berlin: Springer, 2013. 388--404. Google Scholar

[31] Blondeau C, Bogdanov A, Wang M Q. On the (in)equivalence of impossible differential and zero-correlation distinguishers for Feistel- and Skipjack-type ciphers. In: Applied Cryptography and Network Security -- ACNS 2014. Berlin: Springer, 2014. 271--288. Google Scholar

[32] Blondeau C, Nyberg K. Links between truncated differential and multidimensional linear properties of block ciphers and underlying attack complexities. In: Advances in Cryptology -- EUROCRYPT 2014. Berlin: Springer, 2014. 165--182. Google Scholar

[33] Sun B, Liu Z Q, Rijmen V, et al. Links among impossible differential, integral and zero-correlation linear cryptanalysis. In: Advances in Cryptology -- CRYPTO 2015. Berlin: Springer, 2015. 95--115. Google Scholar

[34] 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, 2017, 82: 319-349 CrossRef Google Scholar

[35] Blondeau C, Nyberg K. Improved parameter estimates for correlation and capacity deviates in linear cryptanalysis. IACR Transactions on Symmetric Cryptology, 2017, 2016: 162--191 doi: 10.13154/tosc.v2016.i2.162-191. Google Scholar

[36] Daemen J, Rijmen V. Probability distributions of correlation and differentials in block ciphers. Journal of Mathematical Cryptology, 2007, 1: 221--242. Google Scholar

[37] Beaulieu R, Shors D, Smith J, et al. The SIMON and SPECK families of lightweight block ciphers. IACR Cryptology ePrint Archive, 2013, 2013: 404 DOI: 10.1145/2744769.2747946. Google Scholar

[38] Biryukov A, Roy A, Velichkov V. Differential analysis of block ciphers SIMON and SPECK. In: Fast Software Encryption -- FSE 2014. Berlin: Springer, 2015. 546--570. Google Scholar

[39] Wang Q J, Liu Z Q, Varı cı K, et al. Cryptanalysis of reduced-round SIMON32 and SIMON48. In: Progress in Cryptology -- INDOCRYPT 2014. Berlin: Springer, 2014. 143--160. Google Scholar

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号