Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 1-2/2017

17-08-2016

Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity

Authors: Céline Blondeau, Kaisa Nyberg

Published in: Designs, Codes and Cryptography | Issue 1-2/2017

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The power of a statistical attack is inversely proportional to the number of plaintexts needed to recover information on the encryption key. By analyzing the distribution of the random variables involved in the attack, cryptographers aim to provide a good estimate of the data complexity of the attack. In this paper, we analyze the hypotheses made in simple, multiple, and multidimensional linear attacks that use either non-zero or zero correlations, and provide more accurate estimates of the data complexity of these attacks. This is achieved by taking, for the first time, into consideration the key variance of the statistic for both the right and wrong keys. For the family of linear attacks considered in this paper, we differentiate between the attacks which are performed in the known-plaintext and those in the distinct-known-plaintext model.
previous article Optimal software-implemented Itoh–Tsujii inversion for
next article Observing biases in the state: case studies with Trivium and Trivia-SC
Footnotes
1
With these parameters, the data complexity can not be equal to \(2^{123.2}\) as given in [33].
 
Literature
1.
Abdelraheem M.A., Ågren M., Beelen P., Leander G.: On the distribution of linear biases: three instructive examples. In: Safavi-Naini R., Canetti R. (eds.) Proceedings of Advances in Cryptology—CRYPTO 2012—32nd Annual Cryptology Conference, Santa Barbara, CA, 19–23 Aug, 2012. Lecture Notes in Computer Science, vol. 7417, pp. 50–67. Springer, New York (2012).
2.
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.E. (eds.) SAC 2000. Lecture Notes in Computer Science, vol. 2012. Springer, New York (2001).
3.
Baignères T., Junod P., Vaudenay S.: How far can we go beyond linear cryptanalysis? In: Advances in Cryptology—ASIACRYPT 2004. Lecture Notes in Computer Science, vol. 3329, pp. 432–450. Springer, New York (2004).
4.
Biham E., Shamir A.: Differential cryptanalysis of DES-like cryptosystems. In: Alfred M., Vanstone S.A. (eds.) CRYPTO. Lecture Notes in Computer Science, vol. 537, pp. 2–21. Springer, New York (1990).
5.
Biryukov A., De Cannière C., Quisquater M.: On multiple linear approximations. In: Franklin M.K. (ed.) Advances in Cryptology—CRYPTO, 2004, 24th Annual International Cryptology Conference, Santa Barbara, CA, August 15–19, 2004. Lecture Notes in Computer Science, vol. 3152, pp. 1–22. Springer (2004).
6.
Blondeau C., Nyberg K.: Links between truncated differential and multidimensional linear properties of block ciphers and underlying attack complexities. In: Oswald E., Nguyen P.Q. (eds.) EUROCRYPT 2014. Lecture Notes in Computer Science, vol. 8441. Springer, New York (2014).
7.
Bogdanov A., Tischhauser E.: On the wrong key randomisation and key equivalence hypotheses in Matsui’s Algorithm 2. In: Shiho M. (ed.) Fast Software Encryption—20th International Workshop, FSE 2013, Singapore, 11–13 Mar, 2013. Revised Selected Papers. Lecture Notes in Computer Science, vol. 8424, pp. 19–38. Springer, New York (2013).
8.
Bogdanov A., Wang M.: Zero correlation linear cryptanalysis with reduced data complexity. In: Canteaut A. (ed.) FSE. Lecture Notes in Computer Science, vol. 7549, pp. 29–48. Springer, New York (2012).
9.
Bogdanov A., Knudsen L.R., Leander G., Paar C., Poschmann A., Robshaw M.J., Seurin Y., Vikkelsoe C.: PRESENT: an ultra-lightweight block cipher. In: Paillier P., Verbauwhede I. (eds.) CHES. Lecture Notes in Computer Science, vol. 4727, pp. 450–466. Springer, New York (2007).
10.
Bogdanov A., Leander G., Nyberg K., Wang M.: Integral and multidimensional linear distinguishers with correlation zero. In: Wang X., Sako K. (eds.) ASIACRYPT. Lecture Notes in Computer Science, vol. 7658, pp.244–261. Springer, New York (2012).
11.
Bogdanov A., Boura C., Rijmen V., Wang M., Wen L., Zhao J.: Key difference invariant bias in block ciphers. In: Sako K., Sarkar P. (eds.) ASIACRYPT 2013. Lecture Notes in Computer Science, vol. 8269, pp. 357–376. Springer, New York (2013).
12.
Bogdanov A., Geng H., Wang M., Wen L., Collard B.: Zero-correlation linear cryptanalysis with FFT and improved attacks on ISO standards camellia and CLEFIA. In: SAC’13. Lecture Notes in Computer Science. Springer, New York (2014).
13.
Boura C., Naya-Plasencia M., Suder V.: Scrutinizing and improving impossible differential attacks: applications to CLEFIA, Camellia, LBlock and Simon. In: Sarkar P., Iwata T., (eds.) ASIACRYPT 2014. Lecture Notes in Computer Science, vol. 8873, pp.179–199. Springer, New York (2014).
14.
Canteaut A., Carlet C., Charpin P., Fontaine C.: On cryptographic properties of the cosets of r(1, m). IEEE Trans. 47(4), 1494–1513 (2001).MATHMathSciNet
15.
Daemen J., Rijmen V.: Probability distributions of correlation and differentials in block ciphers. IACR Cryptology ePrint Archive Report 2005/212 (2006).
16.
Daemen J., Rijmen V.: Probability distributions of correlation and differentials in block ciphers. J. Math. Cryptol. 1(3), 221–242 (2007).CrossRefMATHMathSciNet
17.
Daemen J., Govaerts R., Vandewalle J.: Correlation matrices. In: Fast Software Encryption—FSE 1994. Lecture Notes in Computer Science, vol. 1008, pp.275–285. Springer, New York (1995).
18.
Hermelin M., Cho J.Y., Nyberg K.: Multidimensional extension of Matsui’s Algorithm 2. In: FSE. Lecture Notes in Computer Science, vol. 5665, pp. 209–227. Springer, New York (2009).
19.
Huang J., Vaudenay S., Lai X., Nyberg K.: Capacity and data complexity in multidimensional linear attack. In: Gennaro R., Robshaw M. (eds.) Advances in Cryptology—CRYPTO 2015—35th Annual Cryptology Conference, Santa Barbara, CA, 16–20 Aug, 2015, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9215, pp. 141–160. Springer, New York (2015).
20.
Knudsen L.R.: Truncated and higher order differentials. In: Preneel B. (ed.) Proceedings of Fast Software Encryption: Second International Workshop. Leuven, Belgium, 14–16 Dec, 1994. Lecture Notes in Computer Science, vol. 1008, pp.196–211. Springer, New York (1994).
21.
Leander G.: Small scale variants of the block cipher PRESENT. IACR Cryptology ePrint Archive 2010, 143 (2010).
22.
Leander G.: On linear hulls, statistical saturation attacks, PRESENT and a cryptanalysis of PUFFIN. In Paterson K.G. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 6632, pp. 303–322. Springer, New York (2011).
23.
24.
Matsui M.: Linear cryptanalysis method for DES cipher. In: Helleseth T. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 765, pp. 386–397. Springer, New York (1993).
25.
McLaughlin J., Clark J.A.: Filtered nonlinear cryptanalysis of reduced-round serpent, and the wrong-key randomization hypothesis. In: Proceedings of Cryptography and Coding—14th IMA International Conference, IMACC 2013, Oxford, 17–19 Dec, 2013. Lecture Notes in Computer Science, vol. 8308, pp.120–140. Springer, New York (2013).
26.
Murphy S.: The effectiveness of the linear hull effect. Technical Report, Royal Holloway College London (2009).
27.
Nyberg K.:. Linear approximation of block ciphers. In: Advances in Cryptology—EUROCRYPT’94. Lecture Notes in Computer Science, vol. 950, pp. 439–444. Springer, New York (1995).
28.
Röck A., Nyberg K.: Generalization of Matsui’s Algorithm 1 to linear hull for key-alternating block ciphers. Des. Codes Cryptogr. 66(1–3), 175–193 (2013).CrossRefMATHMathSciNet
29.
30.
Shirai T., Shibutani K., Akishita T., Moriai S., Iwata T.: The 128-bit block cipher CLEFIA (extended abstract). In: Biryukov A. (ed.) FSE. Lecture Notes in Computer Science, vol. 4593, pp. 181–195. Springer, New York (2007).
31.
Soleimany H., Nyberg K.: Zero-correlation linear cryptanalysis of reduced-round LBlock. Des. Codes Cryptogr. 73(2), 683–698 (2014).CrossRefMATHMathSciNet
32.
Weisstein E.: Binomial distribution. Wolfram MathWorld (2016).
33.
Wen L., Wang M., Bogdanov A., Chen H.: General application of FFT in cryptanalysis and improved attack on CAST-256. In: Willi M., Debdeep M. (eds.) INDOCRYPT. Lecture Notes in Computer Science, vol. 8885, pp. 161–176. Springer, New York (2014).
34.
Wen L., Wang M., Zhao J.: Related-key impossible differential attack on reduced-round LBlock. J. Comput. Sci. Technol. 29(1), 165–176 (2014).CrossRef
35.
Wu, W., Zhang, L.: LBlock: a lightweight block cipher. In: Javier L., Gene T. (eds.) ACNS. Lecture Notes in Computer Science, vol. 6715, pp. 327–344 (2011).
Metadata
Title
Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity
Authors
Céline Blondeau
Kaisa Nyberg
Publication date
17-08-2016
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 1-2/2017
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-016-0268-6

Other articles of this Issue 1-2/2017

Designs, Codes and Cryptography 1-2/2017 Go to the issue

OriginalPaper

Revisiting (nested) Roos bias in RC4 key scheduling algorithm

OriginalPaper

Idempotent and p-potent quadratic functions: distribution of nonlinearity and co-dimension

OriginalPaper

Improving algebraic attacks on stream ciphers based on linear feedback shift register over

OriginalPaper

Optimal software-implemented Itoh–Tsujii inversion for

OriginalPaper

Security proof of the canonical form of self-synchronizing stream ciphers

OriginalPaper

Almost cover-free codes and designs

Premium Partner

    Image Credits