Revisiting the wrong-key-randomization hypothesis. (English) Zbl 1455.94113

Summary: Linear cryptanalysis is considered to be one of the strongest techniques in the cryptanalyst’s arsenal. In most cases, Matsui’s Algorithm 2 is used for the key recovery part of the attack. The success rate analysis of this algorithm is based on an assumption regarding the bias of a linear approximation for a wrong key, known as the wrong-key-randomization hypothesis. This hypothesis was refined by A. Bogdanov and E. Tischhauser [Lect. Notes Comput. Sci. 8424, 19–38 (2014; Zbl 1321.94043)] to take into account the stochastic nature of the bias for a wrong key. We provide further refinements to the analysis of Matsui’s Algorithm 2 by considering sampling without replacement. This paper derives the distribution of the observed bias for wrong keys when sampling is done without replacement and shows that less data are required in this scenario. It also develops formulas for the success probability and the required data complexity when this approach is taken. The formulas predict that the success probability may reach a peak and then decrease as more pairs are considered. We provide a new explanation for this behavior and derive the conditions for encountering it. We empirically verify our results and compare them to previous work.


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


Zbl 1321.94043


Full Text: DOI Link


[1] M.A. Abdelraheem, M. Ågren, P. Beelen, G. Leander, On the Distribution of Linear Biases: Three Instructive Examples (Springer, Berlin, 2012), pp. 50-67. doi:10.1007/978-3-642-32009-5_4 · Zbl 1294.94029
[2] R. Beaulieu, D. Shors, J. Smith, S. Treatman-Clark, B. Weeks, L. Wingers, The SIMON and SPECK families of lightweight block ciphers. Cryptology ePrint Archive, Report 2013/404 (2013). https://eprint.iacr.org/2013/404 · Zbl 1382.94059
[3] A. Biryukov, C.D. Cannière, M. Quisquater, On multiple linear approximations, in M.K. Franklin, editor, Advances in Cryptology—CRYPTO 2004, 24th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings. Lecture Notes in Computer Science, vol. 3152 (Springer, 2004), pp. 1-22. doi:10.1007/978-3-540-28628-8_1
[4] Blondeau, C.; Gérard, B.; Tillich, J., Accurate estimates of the data complexity and success probability for various cryptanalyses, Des. Codes Cryptography, 59, 1-3, 3-34 (2011) · Zbl 1218.94040
[5] Blondeau, C.; Nyberg, K., Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity, Designs, Codes and Cryptography, 82, 1, 319-349 (2017) · Zbl 1402.94052
[6] A. Bogdanov, E.B. Kavun, E. Tischhauser, T. Yalçin, Large-scale high-resolution computational validation of novel complexity models in linear cryptanalysis. J. Comput. Appl. Math. 259, 592-598 (2014). doi:10.1016/j.cam.2013.10.020 · Zbl 1338.94067
[7] A. Bogdanov, V. Rijmen, Zero-correlation linear cryptanalysis of block ciphers. IACR Cryptology ePrint Archive 2011, 123 (2011). http://eprint.iacr.org/2011/123
[8] Bogdanov, A.; Rijmen, V., Linear hulls with correlation zero and linear cryptanalysis of block ciphers, Des. Codes Cryptography, 70, 3, 369-383 (2014) · Zbl 1323.94103
[9] A. Bogdanov, E. Tischhauser, On the wrong key randomisation and key equivalence hypotheses in Matsui’s algorithm 2, in S. Moriai, editor, Fast Software Encryption—20th International Workshop, FSE 2013, Singapore, March 11-13, 2013. Revised Selected Papers. Lecture Notes in Computer Science, vol. 8424 (Springer, 2013), pp. 19-38. doi:10.1007/978-3-662-43933-3_2 · Zbl 1321.94043
[10] A. Bogdanov, E. Tischhauser, P.S. Vejre, Multivariate linear cryptanalysis: the past and future of present. IACR Cryptology ePrint Archive 2016, 667 (2016). http://eprint.iacr.org/2016/667
[11] Daemen, J.; Rijmen, V., Probability distributions of correlation and differentials in block ciphers, J. Mathematical Cryptology, 1, 3, 221-242 (2007) · Zbl 1211.94028
[12] W. Feller, An Introduction to Probability Theory and Its Applications, vol. 1 (Wiley, 1967), exercise 10 · Zbl 0158.34902
[13] K. Fu, M. Wang, Y. Guo, S. Sun, L. Hu, Milp-based automatic search algorithms for differential and linear trails for speck, in International Conference on Fast Software Encryption (Springer, 2016), pp. 268-288 · Zbl 1387.94081
[14] C. Harpes, G.G. Kramer, J.L. Massey, A generalization of linear cryptanalysis and the applicability of Matsui’s piling-up lemma, in Advances in Cryptology—EUROCRYPT ’95, International Conference on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, May 21-25, 1995, Proceeding. Lecture Notes in Computer Science, vol. 921 (Springer, 1995), pp. 24-38 · Zbl 0973.94522
[15] C. Harpes, J.L. Massey, Partitioning cryptanalysis, in E. Biham, editor, Fast Software Encryption, 4th International Workshop, FSE ’97, Haifa, Israel, January 20-22, 1997, Proceedings. Lecture Notes in Computer Science, vol. 1267 (Springer, 1997), pp. 13-27. doi:10.1007/BFb0052331 · Zbl 1385.94042
[16] M. Hermelin, J.Y. Cho, K. Nyberg, Multidimensional linear cryptanalysis of reduced round serpent, in Y. Mu, W. Susilo, J. Seberry, editors, Information Security and Privacy, 13th Australasian Conference, ACISP 2008, Wollongong, Australia, July 7-9, 2008, Proceedings. Lecture Notes in Computer Science, vol. 5107 (Springer, 2008), pp. 203-215. doi:10.1007/978-3-540-70500-0_15 · Zbl 1279.94084
[17] P. Junod, S. Vaudenay, Optimal key ranking procedures in a statistical cryptanalysis, in T. Johansson, editor, Fast Software Encryption, 10th International Workshop, FSE 2003, Lund, Sweden, February 24-26, 2003, Revised Papers. Lecture Notes in Computer Science, vol. 2887 (Springer, 2003), pp. 235-246. doi:10.1007/978-3-540-39887-5_18 · Zbl 1254.94036
[18] Z. Liu, Y. Li, M. Wang, The security of SIMON-like ciphers against linear cryptanalysis. Cryptology ePrint Archive, Report 2017/576 (2017). https://eprint.iacr.org/2017/576
[19] M. Matsui, Linear cryptanalysis method for DES cipher, in T. Helleseth, editor, Advances in Cryptology—EUROCRYPT ’93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993, Proceedings. Lecture Notes in Computer Science, vol. 765 (Springer, 1993), pp. 386-397. doi:10.1007/3-540-48285-7_33 · Zbl 0951.94519
[20] W. Molenaar, Approximations to the Poisson, Binomial and Hypergeometric Distribution Functions. Ph.D. thesis, Mathematisch Centrum Amsterdam (1970) · Zbl 0199.53001
[21] K. Nyberg, Linear approximation of block ciphers, in A.D. Santis, editor, Advances in Cryptology—EUROCRYPT ’94, Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, May 9-12, 1994, Proceedings. Lecture Notes in Computer Science, vol. 950 (Springer, 1994), pp. 439-444. doi:10.1007/BFb0053460 · Zbl 0885.94023
[22] M.A. Pinsky, The normal approximation to the hypergeometric distribution. Unpublished manuscript. https://www.dartmouth.edu/ chance/teaching_aids/books_articles/probability_book/pinsky-hypergeometric.pdf
[23] Selçuk, AA, On Probability of Success in Linear and Differential Cryptanalysis, J. Cryptology, 21, 1, 131-147 (2008) · Zbl 1147.68510
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.