Abstract
Several generalizations of linear cryptanalysis have been proposed in the past, as well as very similar attacks in a statistical point of view. In this paper, we define a rigorous general statistical framework which allows to interpret most of these attacks in a simple and unified way. Then, we explicitely construct optimal distinguishers, we evaluate their performance, and we prove that a block cipher immune to classical linear cryptanalysis possesses some resistance to a wide class of generalized versions, but not all. Finally, we derive tools which are necessary to set up more elaborate extensions of linear cryptanalysis, and to generalize the notions of bias, characteristic, and piling-up lemma.
Chapter PDF
Similar content being viewed by others
References
Coppersmith, D., Halevi, S., Jutla, C.: Cryptanalysis of stream ciphers with linear masking. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 515–532. Springer, Heidelberg (2002)
Cover, T., Thomas, J.: Elements of Information Theory. Wiley Series in Telecommunications. John Wiley & Sons, Chichester (1991)
Daemen, J., Govaerts, R., Vandewalle, J.: Correlation matrices. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 275–285. Springer, Heidelberg (1995)
Daemen, J., Rijmen, V.: The Design of Rijndael. Information Security and Cryptography. Springer, Heidelberg (2002)
Feller, W.: An Introduction to Probability Theory and Its Applications, 3rd edn. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, Chichester (1968)
Handschuh, H., Gilbert, H.: χ 2 cryptanalysis of the SEAL encryption algorithm. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 1–12. Springer, Heidelberg (1997)
Harpes, C., Kramer, G., Massey, J.: A generalization of linear cryptanalysis and the applicability of Matsui’s piling-up lemma. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 24–38. Springer, Heidelberg (1995)
Harpes, C., Massey, J.: Partitioning cryptanalysis. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 13–27. Springer, Heidelberg (1997)
Jakobsen, T.: Higher-order cryptanalysis of block ciphers. PhD thesis, Department of Mathematics, Technical University of Denmark (1999)
Jakobsen, T., Harpes, C.: Non-uniformity measures for generalized linear cryptanalysis and partitioning cryptanalysis. In: Pribyl, J. (ed.) Pragocrypt 1996. CTU Publishing House (1996)
Junod, P.: On the optimality of linear, differential and sequential distinguishers. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 17–32. Springer, Heidelberg (2003)
Junod, P., Vaudenay, S.: Optimal key ranking procedures in a statistical cryptanalysis. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 235–246. Springer, Heidelberg (2003)
Kaliski, B., Robshaw, M.: Linear cryptanalysis using multiple approximations. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 26–39. Springer, Heidelberg (1994)
Kelsey, J., Schneier, B., Wagner, D.: modn cryptanalysis, with applications against RC5P and M6. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 139–155. Springer, Heidelberg (1999)
Knudsen, L., Robshaw, M.: Non-linear approximations in linear cryptanalysis. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 224–236. Springer, Heidelberg (1996)
Lai, X., Massey, J., Murphy, S.: Markov ciphers and differential cryptanalysis. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 17–38. Springer, Heidelberg (1991)
Lim, C.H.: CRYPTON: A new 128-bit block cipher. In: The First AES Candidate Conference. National Institute for Standards and Technology (1998)
Lim, C.H.: A revised version of CRYPTON: CRYPTON V1.0. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 31–45. Springer, Heidelberg (1999)
Lu, Y., Vaudenay, S.: Cryptanalysis of Bluetooth Keystream Generator Two-level E0. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 483–499. Springer, Heidelberg (2004)
Lu, Y., Vaudenay, S.: Faster correlation attack on Bluetooth keystream generator E0. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 407–425. Springer, Heidelberg (2004)
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)
Matsui, M.: New structure of block ciphers with provable security against differential and linear cryptanalysis. In: Gollman, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 205–218. Springer, Heidelberg (1996)
Minier, M., Gilbert, H.: Stochastic cryptanalysis of Crypton. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 121–133. Springer, Heidelberg (2001)
Murphy, S., Piper, F., Walker, M., Wild, P.: Likelihood estimation for block cipher keys. Technical report, Information Security Group, University of London, England (1995)
National Institute of Standards and Technology, U. S. Department of Commerce. Data Encryption Standard, NIST FIPS PUB 46-2 (1993)
Parker, M.: Generalized S-Box linearity. Technical report nes/doc/uib/wp5/020/a, NESSIE Project (2003), Available on https://www.cryptonessie.org
Shimoyama, T., Kaneko, T.: Quadratic relation of S-Box and its application to the linear attack of full round DES. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 200–211. Springer, Heidelberg (1998)
Standaert, F.-X., Rouvroy, G., Piret, G., Quisquater, J.-J., Legat, J.-D.: Key-dependent approximations in cryptanalysis: an application of multiple Z4 and non-linear approximations. In: 24th Symposium on Information Theory in the Benelux (2003)
Tardy-Corfdir, A., Gilbert, H.: A known plaintext attack of 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: 3rd ACM Conference on Computer and Communications Security, pp. 139–147. ACM Press, New York (1996)
Vaudenay, S.: On the security of CS-cipher. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 260–274. Springer, Heidelberg (1999)
Vaudenay, S.: Decorrelation: a theory for block cipher security. Journal of Cryptology 16(4), 249–286 (2003)
Wagner, D.: Towards a unifying view of block cipher cryptanalysis. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 16–33. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baignères, T., Junod, P., Vaudenay, S. (2004). How Far Can We Go Beyond Linear Cryptanalysis?. In: Lee, P.J. (eds) Advances in Cryptology - ASIACRYPT 2004. ASIACRYPT 2004. Lecture Notes in Computer Science, vol 3329. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30539-2_31
Download citation
DOI: https://doi.org/10.1007/978-3-540-30539-2_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23975-8
Online ISBN: 978-3-540-30539-2
eBook Packages: Springer Book Archive