Another look at success probability of linear cryptanalysis

Subhabrata Samajder; Palash Sarkar

doi:10.3934/amc.2019040

Article Contents

2019, Volume 13, Issue 4: 645-688. Doi: 10.3934/amc.2019040

This issue Previous Article Embedding cover-free families and cryptographical applications Next Article Revisiting design principles of Salsa and ChaCha

Another look at success probability of linear cryptanalysis

Subhabrata Samajder and
Palash Sarkar^,

Applied Statistics Unit, Indian Statistical Institute, 203, B.T.Road, Kolkata, 700108, India

^* Corresponding author
^* Corresponding author

Received: September 30, 2018

Revised: December 31, 2018

Published: June 2019

Abstract Full Text(HTML) Figure(3) / Table(2) Related Papers Cited by

Abstract

This work studies the success probability of key recovery attacks based on using a single linear approximation. Previous works had analysed success probability under different hypotheses on the distributions of correlations for the right and wrong key choices. This work puts forward a unifying framework of general key randomisation hypotheses. All previously used key randomisation hypotheses as also zero correlation attacks can be seen as special cases of the general framework. Derivations of expressions for the success probability are carried out under both the settings of the plaintexts being sampled with and without replacements. Compared to previous analysis, we uncover several new cases which have not been considered in the literature. For most of the cases which have been considered earlier, we provide complete expressions for the respective success probabilities. Finally, the full picture of the dependence of the success probability on the data complexity is revealed. Compared to the extant literature, our work provides a deeper and more thorough understanding of the success probability of single linear cryptanalysis.

Keywords:

Mathematics Subject Classification: 94A60, 11T71, 68P25, 62P99.

Citation:

Full Text(HTML)

Figure 1. Case $t_2\leq x_0 < t_1$

Download: Full-size image PowerPoint slide

Figure 2. Case $t_2 < t_1 < x_0$

Download: Full-size image PowerPoint slide

Figure 3. Case $x_0 < t_2 < t_1$

Download: Full-size image PowerPoint slide

Table 1. Here "type" denotes whether $p = 1/2$ or not; srswr (resp. srswor) denotes sampling with (resp. without) replacement; RKRH (resp. WKRH) is an abbreviation for right (resp. wrong) key randomisation hypothesis; std (resp. adj) denotes whether the standard (resp. adjusted) key randomisation hypothesis is considered

type	samp.	RKRH	WKRH	cond.	previous $P_{S}$	new $P_{S}$
$p \neq 1/2$	wr	std	std	-	[33]	Section 5.4, Eqn (41)
		std	adj	-	[12]	Section 5.5, Eqn (44)
		adj	std	-	-	Section 5.6, Eqn (46)
		adj	adj	-	[8]	Section 5.7, Eqn (48)
	wor	std	std	-	-	Section 5.4, Eqn (42)
		std	adj	-	[1]	Section 5.5, Eqn (44)
		adj	std	-	-	Section 5.6, Eqn (47)
		adj	adj	-	-	Section 5.7, Eqn (49)
$p = 1/2$	wr	std	adj	-	-	Section 7.1, Eqn (57)
		adj	std	-	-	Section 7.2, Eqn (60)
		adj	adj	${\mathtt{ELP}}>2^{-n}$	[7]	Section 7.3, Eqn (62)
		adj	adj	${\mathtt{ELP}} < 2^{-n}$	-	Section 7.3, Eqn (63)
	wor	std	adj	-	-	Section 7.1, Eqn (58)
		adj	std	-	-	Section 7.2, Eqn (61)
		adj	adj	${\mathtt{ELP}}>2^{-n}$	[7]	Section 7.3, Eqn (64)
		adj	adj	${\mathtt{ELP}} < 2^{-n}$	-	Section 7.3, Eqn (65)

| Show Table

DownLoad: CSV

Table 2. Summary of the different cases and sub-cases showing the dependence of the success probability on the data complexity for $ p\neq 1/2 $. Here $ n $ is the block size, $ \epsilon = p-1/2 $, $ \mathfrak{s}_0^2 = ({\mathtt{ELP}}-4\epsilon^2)/4 $, $ \mathfrak{s}_1^2 = 2^{-n-2} $ and $\gamma ={{\mathit{\Phi} }^{-1}}\left( 1-\frac{{{2}^{m-a-1\;\;\;}}}{{{2}^{m}}-1\;\;\;\;} \right)$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	T. Ashur, T. Beyne and V. Rijmen, Revisiting the wrong-key-randomization hypothesis, IACR Cryptology ePrint Archive, 2016 (2016), 990, Available at http://eprint.iacr.org/2016/990.
[2]	T. Baignères, P. Junod and S. Vaudenay, How far can we go beyond linear cryptanalysis?, In Pil Joong Lee, editor, Advances in Cryptology - ASIACRYPT 2004, 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004, Proceedings, volume 3329 of Lecture Notes in Computer Science, 432–450. Springer, 2004. ISBN: 3-540-23975-8. doi: 10.1007/978-3-540-30539-2_31.
[3]	T. Baignères, P. Sepehrdad and S. Vaudenay, Distinguishing distributions using chernoff information, In Swee-Huay Heng and Kaoru Kurosawa, editors, Provable Security - 4th International Conference, ProvSec 2010, Malacca, Malaysia, October 13-15, 2010. Proceedings, volume 6402 of Lecture Notes in Computer Science, pages 144–165. Springer, 2010. ISBN: 978-3-642-16279-4. doi: 10.1007/978-3-642-16280-0_10.
[4]	A. Biryukov, C. De Cannière and M. Quisquater, On multiple linear approximations, Advances in cryptology–CRYPTO 2004, Lecture Notes in Comput. Sci., Springer, Berlin, 3152 (2004), 1–22. doi: 10.1007/978-3-540-28628-8_1.
[5]	C. Blondeau, B. Gérard and K. Nyberg, Multiple differential cryptanalysis using LLR and $\chi^{2}$ statistics, Security and Cryptography for Networks, 343–360, Lecture Notes in Comput. Sci., 7485, Springer, Heidelberg, 2012. doi: 10.1007/978-3-642-32928-9_19.
[6]	C. Blondeau and M. Minier, Analysis of impossible, integral and zero-correlation attacks on type-ii generalized feistel networks using the matrix method, Fast Software Encryption - 22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers, Lecture Notes in Computer Science, Springer, 9054 (2015), 92–113. doi: 10.1007/978-3-662-48116-5_5.
[7]	C. Blondeau and K. Nyberg, Improved parameter estimates for correlation and capacity deviates in linear cryptanalysis, IACR Transactions Symmetric Cryptology, 2016 (2016), 162–191. https://www.doi.org/10.13154/tosc.v2016.i2.162-191.
[8]	C. Blondeau and K. Nyberg, Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity, Design Codes Cryptography, 82 (2017), 319-349. doi: 10.1007/s10623-016-0268-6.
[9]	A. Bogdanov, H. Geng, M. Wang, L. Wen and B. Collard, Zero-correlation linear cryptanalysis with fft and improved attacks on iso standards camellia and CLEFIA, In Tanja Lange, Kristin E. Lauter, and Petr Lisonek, editors, Selected Areas in Cryptography - SAC 2013 - 20th International Conference, Burnaby, BC, Canada, August 14-16, 2013, Revised Selected Papers, volume 8282 of Lecture Notes in Computer Science, Springer, (2014), 306–323. https://www.doi.org/10.1007/978-3-662-43414-7_16, ISBN: 978-3-662-43413-0.
[10]	A. Bogdanov, G. Leander, K. Nyberg and M. Wang, Integral and multidimensional linear distinguishers with correlation zero, In Xiaoyun Wang and Kazue Sako, editors, Advances in Cryptology - ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012. Proceedings, volume 7658 of Lecture Notes in Computer Science, pages 244–261. Springer, 2012. ISBN: 978-3-642-34960-7. doi: 10.1007/978-3-642-34961-4_16.
[11]	A. Bogdanov and V. Rijmen, Linear hulls with correlation zero and linear cryptanalysis of block ciphers, Design Codes Cryptography, 70 (2014), 369-383. doi: 10.1007/s10623-012-9697-z.
[12]	A. Bogdanov and E. Tischhauser, On the wrong key randomisation and key equivalence hypotheses in matsui's algorithm 2, In Shiho Moriai, editor, Fast Software Encryption - 20th International Workshop, FSE 2013, Singapore, March 11-13, 2013. Revised Selected Papers, volume 8424 of Lecture Notes in Computer Science, pages 19–38. Springer, 2014. ISBN: 978-3-662-43932-6. doi: 10.1007/978-3-662-43933-3_2.
[13]	A. Bogdanov and M. Wang, Zero correlation linear cryptanalysis with reduced data complexity, In Anne Canteaut, editor, Fast Software Encryption - 19th International Workshop, FSE 2012, Washington, DC, USA, March 19-21, 2012. Revised Selected Papers, volume 7549 of Lecture Notes in Computer Science, pages 29–48. Springer, 2012. ISBN: 978-3-642-34046-8. doi: 10.1007/978-3-642-34047-5_3.
[14]	J. Daemen and V. Rijmen, Probability distributions of correlation and differentials in block ciphers, IACR Cryptology ePrint Archive, 2005: 212, 2005. Available at http://eprint.iacr.org/2005/212.
[15]	J. Daemen and V. Rijmen, Probability distributions of correlation and differentials in block ciphers, Journal of Mathematical Cryptology, 1 (2007), 221-242. doi: 10.1515/JMC.2007.011.
[16]	W. Feller, An Introduction to Probability Theory and Its Applications, Volume 1, John Wiley & Sons, Inc., New York, N.Y., 1950.
[17]	B. Gérard and J.-P. Tillich, On linear cryptanalysis with many linear approximations, In Matthew G. Parker, editor, Cryptography and Coding, 12th IMA International Conference, Cryptography and Coding 2009, Cirencester, UK, December 15-17, 2009. Proceedings, volume 5921 of Lecture Notes in Computer Science, 112–132. Springer, 2009. doi: 10.1007/978-3-642-10868-6_8.
[18]	C. Harpes, G. G. Kramer and J. L. Massey, A generalization of linear cryptanalysis and the applicability of matsui's piling-up lemma, In Louis C. Guillou and Jean-Jacques Quisquater, editors, Advances in Cryptology - EUROCRYPT '95, International Conference on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, May 21-25, 1995, Proceeding, volume 921 of Lecture Notes in Computer Science, 24–38. Springer, 1995. https://www.doi.org/10.1007/3-540-49264-X_3.
[19]	M. Hermelin, J. Y. Cho and K. Nyberg, Multidimensional extension of matsui's algorithm 2, In Fast Software Encryption, 16th International Workshop, FSE 2009, Leuven, Belgium, February 22-25, 2009, Revised Selected Papers, volume 5665 of Lecture Notes in Computer Science, 209–227. Springer, 2009. doi: 10.1007/978-3-642-03317-9_13.
[20]	J. Huang, S. Vaudenay, X. Lai and K. Nyberg, Capacity and data complexity in multidimensional linear attack, In Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I, volume 9215 of Lecture Notes in Computer Science, 141–160, Springer, 2015. doi: 10.1007/978-3-662-47989-6_7.
[21]	B. S. Kaliski Jr. and M. J. B. Robshaw, Linear cryptanalysis using multiple approximations, In Yvo Desmedt, editor, Advances in Cryptology - CRYPTO '94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, volume 839 of Lecture Notes in Computer Science, 26–39, Springer, 1994. doi: 10.1007/3-540-48658-5_4.
[22]	P. Junod, On the complexity of matsui's attack, In Serge Vaudenay and Amr M. Youssef, editors, Selected Areas in Cryptography, 8th Annual International Workshop, SAC 2001 Toronto, Ontario, Canada, August 16-17, 2001, Revised Papers, volume 2259 of Lecture Notes in Computer Science, 199–211, Springer, 2001. doi: 10.1007/3-540-45537-X_16.
[23]	P. Junod, On the optimality of linear, differential, and sequential distinguishers, In Eli Biham, editor, Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003, Proceedings, volume 2656 of Lecture Notes in Computer Science, 17–32, Springer, 2003. doi: 10.1007/3-540-39200-9_2.
[24]	P. Junod and S. Vaudenay, Optimal key ranking procedures in a statistical cryptanalysis, In Thomas Johansson, editor, Fast Software Encryption, 10th International Workshop, FSE 2003, Lund, Sweden, February 24-26, 2003, Revised Papers, volume 2887 of Lecture Notes in Computer Science, 235–246, Springer, 2003. doi: 10.1007/978-3-540-39887-5_18.
[25]	S. N. Lahiri and A. Chatterjee, A Berry-Esseen theorem for hypergeometric probabilities under minimal conditions, Proceedings of the American Mathematical Society, 135 (2007), 1535-1545. doi: 10.1090/S0002-9939-07-08676-5.
[26]	M. Matsui, Linear cryptanalysis method for des cipher, In Tor Helleseth, editor, Advances in Cryptology - EUROCRYPT '93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993, Proceedings, volume 765 of Lecture Notes in Computer Science, 386–397, Springer, 1994. https://www.doi.org/10.1007/3-540-48285-7_33.
[27]	M. Matsui, The first experimental cryptanalysis of the data encryption standard, In Yvo Desmedt, editor, Advances in Cryptology - CRYPTO '94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, volume 839 of Lecture Notes in Computer Science, 1–11, Springer, 1994. https://www.doi.org/10.1007/3-540-48658-5_1.
[28]	S. Murphy, The independence of linear approximations in symmetric cryptanalysis, IEEE Transactions on Information Theory, 52 (2006), 5510-5518. doi: 10.1109/TIT.2006.885528.
[29]	S. Samajder and P. Sarkar, Another look at normal approximations in cryptanalysis, Journal Mathematical Cryptology, 10 (2016), 69-99. doi: 10.1515/jmc-2016-0006.
[30]	S. Samajder and P. Sarkar, A new test statistic for key recovery attacks using multiple linear approximations, In Raphael C.-W. Phan and Moti Yung, editors, Paradigms in Cryptology - Mycrypt 2016. Malicious and Exploratory Cryptology - Second International Conference, Mycrypt 2016, Kuala Lumpur, Malaysia, December 1-2, 2016, Revised Selected Papers, volume 10311 of Lecture Notes in Computer Science, 277–293, Springer, 2017, https://www.doi.org/10.1007/978-3-319-61273-7_14.
[31]	S. Samajder and P. Sarkar, Rigorous upper bounds on data complexities of block cipher cryptanalysis, Journal of Mathematical Cryptology, 11 (2017), 147-175. doi: 10.1515/jmc-2016-0026.
[32]	S. Samajder and P. Sarkar, Success Probability of Multiple/Multidimensional Linear Cryptanalysis Under General Key Randomisation Hypotheses, Cryptography and Communications, 10 (2018), 835-879. doi: 10.1007/s12095-017-0257-2.
[33]	A. A. Selçuk, On probability of success in linear and differential cryptanalysis, Journal of Cryptology, 21 (2008), 131-147. doi: 10.1007/s00145-007-9013-7.
[34]	H. Soleimany and K. Nyberg, Zero-correlation linear cryptanalysis of reduced-round lblock, Design Codes Cryptography, 73 (2014), 683-698. doi: 10.1007/s10623-014-9976-y.
[35]	L. Sun, H. Chen and M. Wang, Zero-correlation attacks: Statistical models independent of the number of approximations, Designs, Codes and Cryptography, 86 (2018), 1923-1945. doi: 10.1007/s10623-017-0430-9.
[36]	E. W. Tischhauser, Mathematical Aspects of Symmetric-Key Cryptography, PhD thesis, Katholieke Universiteit Leuven, 2012.
[37]	A. M. Walker, A note on the asymptotic distribution of sample quantiles, Journal of the Royal Statistical Society. Series B (Methodological), 30 (1968), 570-575. doi: 10.1111/j.2517-6161.1968.tb00757.x.