T ¨UB˙ITAK B˙ILGEM UEKAE Gebze, 41470 Kocaeli Turkey

Abstract

How Biased Are Linear Biases

Abstract

In this paper we re-visit the Matsui's linear cryptanalysis. The linear attack on the full round DES was the first attack that has been verified experimentally. Matsui extended one-round linear approximations to a linear mask of plaintext-ciphertext pairs by means of his piling-up lemma. The assumption of the lemma, the independence of the random variables in the round approximations, is hopefully fulfilled for the full round DES. So the experiment was successful. However, there exist some ciphers whose linear approximations may have completely different biases than those calculated by the piling-up lemma. We work out a case study where the biases of the linear approximations cannot be calculated through the lemma. We derive the theoretical infrastructures which lead us to compute the overall bias. We verify the theoretical results by performing some experiments on a toy cipher. For the verification, we mount a linear attack on the cipher and construct two linear approximations having the same plaintext-ciphertext masks. We show that the biases of the approximations are different from what the piling-up lemma asserts.

 

Keywords

• —block cipher
• linear cryptanalysis
• nonlinearity
• DES
• linear hull
• linear approximation

References

1. A.A. Selc¸uk. On Bias Estimation in Linear Cryptanalysis. In Proc. Indocrypt 2000, LNCS 1977, pp. 52–66, Springer, 2000.
2. A. Biryukov, C. D. Canni`ere, and M. Quisquarter. On Multiple Linear Approximations.In M. Franklin (Ed.): Crypto 2004, LNCS 3152, pp. 1–22, Springer, 2004.
3. B. Collard, C. D. Canni`ere, and M. Quisquarter. Experiments on the Multiple Linear Cryptanalysis of Reduced Round Serpent.In K. Nyberg (Ed.): FSE 2008, LNCS 5086, pp. 382–397, Springer, 2008.
4. B. S. Kaliski Jr., and M. J. B. Robshaw. Linear Cryptanalysis Us- ing Multiple Approximations.In Y. G. Desmedt (Ed.): Crypto’94, LNCS 839, pp. 26–39, Springer-Verlag Berlin Heidelberg, 1994.
5. B. S. Kaliski Jr., and M. J. B. Robshaw. Linear Cryptanalysis Using Multiple Approximations and FEAL.In B. Preneel (Ed.): FSE’94, LNCS 1008, pp. 249–264, Springer, 1995.
6. F. Chabaud, S. Vaudenay. Links Between Differential and Linear Cryptanalysis.In A. D. Santis (Ed.): Eurocrypt’94, LNCS 950, pp. 356–365, Springer, 1995.
7. G. Leander. On Linear Hulls,Statistical Saturation Attacks, PRESENT and Cryptanalysis of PUFFIN.In K. G. Peterson (Ed.): Eurocrypt 2011, LNCS 6632, pp. 303–322, Springer, 2011.
8. J. Nakahara Jr., P. Sepehrdad, B. Zhang, and M. Wang. Lin- ear (Hull) and Algebraic Cryptanalysis of the Block Cipher PRESENT.In J. A. Garay, A. Miyaji, and A. Otsuka (Eds.): CANS 2009, LNCS 5888, pp. 58–75, Springer-Verlag Berlin Heidelberg, 2009.

9. K. Nyberg. Linear Approximation of Block Ciphers. In A. D. Santis (Ed.): Eurocrypt’94, LNCS 950, pp. 439–444, Springer, 1995.
10. M. Hermelin, J. Y. Cho, and K. Nyberg. Multidimensional Extension of Matsui’s Algorithm 2.In O. Dunkelman (Ed.): FSE 2009, LNCS 5665, pp. 209–227, Springer, 2009.
11. M. Hermelin, J. Y. Cho, and K. Nyberg. Multidimensional Linear Cryptanalysis of Reduced Round Serpent.In Y. Mu, W. Susilo, and J. Seberry (Eds.): ACISP 2008, LNCS 5107, pp. 203- 215, Springer-Verlag Berlin Heidelberg, 2008.
12. M. Matsui. Linear Cryptanalysis Method of DES Cipher. In Proc. EUROCRYPT’93, LNCS 765, pp. 386–397, Springer, 1994.
13. M. Matsui. The First Experimental Cryptanalysis of the Data Encryption Standard.In Proc. CRPTO’94, LNCS 839, pp. 1–11, Springer, 1994.
14. S. Murphy. The Effectiveness of the Linear Hull Effect. Techni- cal Report, RHULMA-2009-19 (2009).
15. S. Murphy. The Independence of Linear Approximations in Symmetric Cryptanalysis.In IEEE Transactions on Information Theory,Vol. 22, N0. 12, December 2006.
16. W. Meier and O. Staffelbach. Nonlinearity Criteria for Cryp- tographic Functions.In Proc. EUROCRYPT’89, LNCS 434, pp. 548–562, Springer, 1989.
17. V. Rijmen, Cryptanalysis and Design of Iterated Block Ciphers, Doctoral Dissertation, K.U. Leuven, 1997.