Abstract
In this paper we explore the recovery of key information from a block cipher when using unbiased linear approximations of a certain form. In particular we develop a theoretical framework for their treatment and we confirm their behaviour with experiments on reduced-round variants of DES. As an application we show a novel form of linear cryptanalysis using multiple linear approximations which can be used to extract key information when all pre-existing techniques would fail.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Biryukov, A., De Cannière, C., Quisquater, M.: On Multiple Linear Approximations. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 1–22. Springer, Heidelberg (2004)
Cho, J.Y.: Linear Cryptanalysis of Reduced-Round PRESENT. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 302–317. Springer, Heidelberg (2010)
Collard, B., Standaert, F.-X., Quisquater, J.-J.: Improving the Time Complexity of Matsui’s Linear Cryptanalysis. In: Nam, K.-H., Rhee, G. (eds.) ICISC 2007. LNCS, vol. 4817, pp. 77–88. Springer, Heidelberg (2007)
Collard, B., Standaert, F.-X., Quisquater, J.-J.: Experiments on the Multiple Linear Cryptanalysis of Reduced-Round Serpent. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 382–397. Springer, Heidelberg (2008)
Daemen, J.: Cipher and Hash Function Design. Ph.D. Thesis (March 1995)
Hermelin, M., Cho, J.Y., Nyberg, K.: Multidimensional Linear Cryptanalysis of Reduced Round Serpent. In: Mu, Y., Susilo, W., Seberry, J. (eds.) ACISP 2008. LNCS, vol. 5107, pp. 203–215. Springer, Heidelberg (2008)
Hermelin, M., Cho, J.Y., Nyberg, K.: A New Technique for Multidimensional Linear Cryptanalysis with Applications on Reduced Round Serpent. In: Yung, M., Liu, P., Lin, D. (eds.) ICISC 2008. LNCS, vol. 5461, pp. 383–398. Springer, Heidelberg (2009)
Hermelin, M., Cho, J.Y., Nyberg, K.: Multidimensional Extension of Matsuis Algorithm 2. In: Goos, G., Hartmanis, J., van Leeuwen, J. (eds.) Fast Software Encryption. LNCS, vol. 5665, pp. 209–227. Springer, Heidelberg (2009)
Junod, P.: On the complexity of Matsui’s attack. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, pp. 199–211. Springer, Heidelberg (2001)
Kaliski, B.S., Robshaw, M.J.B.: Linear Cryptanalysis Using Multiple Approximations. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 26–39. Springer, Heidelberg (1994)
Kaliski, B.S., Robshaw, M.J.B.: Linear Cryptanalysis and FEAL. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 249–264. Springer, Heidelberg (1995)
Matsui, M.: Linear Cryptanalysis Method for DES Cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
Matsui, M.: The first experimental cryptanalysis of the Data Encryption Standard. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 1–11. Springer, Heidelberg (1994)
Murphy, S.: The Independence of Linear Approximations in Symmetric Cryptanalysis. IEEE Transactions on Information Theory 52, 5510–5518 (2006)
National Institute of Standards and Technology. FIPS 46-3: Data Encryption Standard (November 1998), http://csrc.nist.gov
Selçuk, A.: On Probability of Success in Linear and Differential Cryptanalysis. Journal of Cryptology 21(1), 131–147 (2008)
Silvey, S.D.: Statistical Inference. Chapman and Hall, Boca Raton (1975)
Tardy-Corfdir, A., Gilbert, H.: A Known Plaintext Attack on FEAL-4 and FEAL-6. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 172–182. Springer, Heidelberg (1992)
Vaudenay, S.: An Experiment on DES Statistical Cryptanalysis. In: Proceedings of the Third ACM Conference on Computer Security, pp. 386–397 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Etrog, J., Robshaw, M.J.B. (2010). On Unbiased Linear Approximations. In: Steinfeld, R., Hawkes, P. (eds) Information Security and Privacy. ACISP 2010. Lecture Notes in Computer Science, vol 6168. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14081-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-14081-5_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14080-8
Online ISBN: 978-3-642-14081-5
eBook Packages: Computer ScienceComputer Science (R0)