On linear hulls and trails. (English) Zbl 1394.94927

Dunkelman, Orr (ed.) et al., Progress in cryptology – INDOCRYPT 2016. 17th international conference on cryptology in India, Kolkata, India, December 11–14, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-49889-8/pbk; 978-3-319-49890-4/ebook). Lecture Notes in Computer Science 10095, 269-286 (2016).
Summary: This paper improves the understanding of linear cryptanalysis by highlighting some previously overlooked aspects. It shows that linear hulls are sometimes formed already in a single round, and that overlooking such hulls may lead to a wrong estimation of the linear correlation, and thus of the data complexity. It shows how correlation matrices can be used to avoid this, and provides a tutorial on how to use them properly. By separating the input and output masks from the key mask it refines the formulas for computing the expected correlation and the expected linear potential. Finally, it shows that when the correlation of a hull is not properly estimated (e.g., by using the correlation of a single trail as the correlation of the hull), the success probability of Matsui’s algorithm 1 drops, sometimes drastically. It also shows that when the trails composing the hull are properly accounted for, more than a single key bit can be recovered using algorithm 1. All the ideas presented in this paper are followed by examples comparing previous methods to the corrected ones, and verified experimentally with reduced-round versions of Simon32/64.
For the entire collection see [Zbl 1349.94007].


94A60 Cryptography


Full Text: DOI Link


[1] Aoki, K., Ichikawa, T., Kanda, M., Matsui, M., Moriai, S., Nakajima, J., Tokita, T.: Camellia: a 128-bit block cipher suitable for multiple platforms – design and analysis. In: Stinson, D.R., Tavares, S. (eds.) SAC 2000. LNCS, vol. 2012, pp. 39–56. Springer, Heidelberg (2001). doi: 10.1007/3-540-44983-3_4 · Zbl 1037.94540
[2] Ashur, T., Rijmen, V.: On linear hulls and trails in simon. IACR Cryptology ePrint Archive 2016, 88 (2016). http://eprint.iacr.org/2016/088 · Zbl 1394.94927
[3] Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK families of lightweight block ciphers. Cryptology ePrint Archive, Report 2013/404 (2013). http://eprint.iacr.org/ · Zbl 1382.94059
[4] Biham, E.: On Matsui’s linear cryptanalysis. In: Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 341–355. Springer, Heidelberg (1995). doi: 10.1007/BFb0053449 · Zbl 0879.94025
[5] Biryukov, A., Cannière, C., Quisquater, M.: On multiple linear approximations. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 1–22. Springer, Heidelberg (2004). doi: 10.1007/978-3-540-28628-8_1 · Zbl 1104.94018
[6] Chabaud, F., Vaudenay, S.: Links between differential and linear cryptanalysis. In: Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 356–365. Springer, Heidelberg (1995). doi: 10.1007/BFb0053450 · Zbl 0879.94023
[7] Daemen, J., Govaerts, R., Vandewalle, J.: Correlation matrices. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 275–285. Springer, Heidelberg (1995). doi: 10.1007/3-540-60590-8_21 · Zbl 0939.94516
[8] Hermelin, M., Cho, J.Y., Nyberg, K.: Multidimensional linear cryptanalysis of reduced round serpent. In: Mu, Y., Susilo, W., Seberry, J. (eds.) ACISP 2008. LNCS, vol. 5107, pp. 203–215. Springer, Heidelberg (2008). doi: 10.1007/978-3-540-70500-0_15 · Zbl 1279.94084
[9] Kaliski, B.S., Robshaw, M.J.B.: Linear cryptanalysis using multiple approximations. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 26–39. Springer, Heidelberg (1994). doi: 10.1007/3-540-48658-5_4 · Zbl 0939.94534
[10] Keliher, L., Meijer, H., Tavares, S.: New method for upper bounding the maximum average linear hull probability for SPNs. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 420–436. Springer, Heidelberg (2001). doi: 10.1007/3-540-44987-6_26 · Zbl 1015.94546
[11] Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994). doi: 10.1007/3-540-48285-7_33 · Zbl 0951.94519
[12] Murphy, S.: The effectiveness of the linear hull effect. J. Math. Cryptol. 6(2), 137–147 (2012). http://dx.doi.org/10.1515/jmc-2011-0025 · Zbl 1279.94105
[13] Nyberg, K.: Linear approximation of block ciphers. In: Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 439–444. Springer, Heidelberg (1995). doi: 10.1007/BFb0053460 · Zbl 0885.94023
[14] Röck, A., Nyberg, K.: Generalization of Matsui’s algorithm 1 to linear hull for key-alternating block ciphers. Des. Codes Cryptograph. 66(1–3), 175–193 (2013). http://dx.doi.org/10.1007/s10623-012-9679-1 · Zbl 1263.94025
[15] Shi, D., Hu, L., Sun, S., Song, L.: Linear (hull) cryptanalysis of round-reduced versions of KATAN. Cryptology ePrint Archive, Report 2015/964 (2015). http://eprint.iacr.org/
[16] Shi, D., Hu, L., Sun, S., Song, L., Qiao, K., Ma, X.: Improved linear (hull) cryptanalysis of round-reduced versions of SIMON. Cryptology ePrint Archive, Report 2014/973 (2014). http://eprint.iacr.org/
[17] Sun, S., Hu, L., Wang, M., Wang, P., Qiao, K., Ma, X., Shi, D., Song, L., Fu, K.: Towards finding the best characteristics of some bit-oriented block ciphers and automatic enumeration of (related-key) differential and linear characteristics with predefined properties. Cryptology ePrint Archive, Report 2014/747 (2014). http://eprint.iacr.org/
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.