nach oben

Designs, Codes and Cryptography

Erschienen in:

17.08.2016

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

verfasst von: Céline Blondeau, Kaisa Nyberg

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1-2/2017

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Optimal software-implemented Itoh–Tsujii inversion for

Nächster Artikel Observing biases in the state: case studies with Trivium and Trivia-SC

With these parameters, the data complexity can not be equal to \(2^{123.2}\) as given in [33].

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).

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).

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).

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).

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).

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).

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).

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).

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.

Linial N., Mansour Y., Nisan N.: Constant depth circuits, fourier transform, and learnability. J. ACM 40(3), 607–620 (1993).CrossRefMATHMathSciNet

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.

Selçuk A.A.: On probability of success in linear and differential cryptanalysis. J. Cryptol. 21(1), 131–147 (2008).CrossRefMATHMathSciNet

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).

Titel: Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity
verfasst von: Céline Blondeau
Kaisa Nyberg
Publikationsdatum: 17.08.2016
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 1-2/2017
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-016-0268-6

Springer Professional

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

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 1-2/2017

Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity

MacWilliams Extension Theorem for MDS codes over a vector space alphabet

Observing biases in the state: case studies with Trivium and Trivia-SC

On some permutation binomials and trinomials over

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

Reflection ciphers

Premium Partner