Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

A Methodology for Differential-Linear Cryptanalysis and Its Applications

(Extended Abstract)

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 7549))

Included in the following conference series:

Abstract

In 1994 Langford and Hellman introduced a combination of differential and linear cryptanalysis under two default independence assumptions, known as differential-linear cryptanalysis, which is based on the use of a differential-linear distinguisher constructed by concatenating a linear approximation with a (truncated) differential with probability 1. In 2002, by using an additional assumption, Biham, Dunkelman and Keller gave an enhanced version that can be applicable to the case when a differential with a probability of smaller than 1 is used to construct a differential-linear distinguisher. In this paper, we present a new methodology for differential-linear cryptanalysis under the original two assumptions implicitly used by Langford and Hellman, without using the additional assumption of Biham et al. The new methodology is more reasonable and more general than Biham et al.’s methodology, and apart from this advantage it can lead to some better differential-linear cryptanalytic results than Biham et al.’s and Langford and Hellman’s methodologies. As examples, we apply it to attack 10 rounds of the CTC2 block cipher with a 255-bit block size and key, 13 rounds of the DES block cipher, and 12 rounds of the Serpent block cipher. The new methodology can be used to cryptanalyse other block ciphers, and block cipher designers should pay attention to this new methodology when designing a block cipher.

An earlier version of this work appeared in 2010 as part of Cryptology ePrint Archive Report 2010/025 [28], which was done when the author was with Eindhoven University of Technology (The Netherlands) under the support of the Dutch Sentinels project PINPASJC (No. TIF.6687).

Similar content being viewed by others

Keywords

References

  1. Biham, E., Anderson, R., Knudsen, L.R.: Serpent: A New Block Cipher Proposal. In: Vaudenay, S. (ed.) FSE 1998. LNCS, vol. 1372, pp. 222–238. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  2. Anderson, R., Biham, E., Knudsen, L.R.: Serpent: a proposal for the Advanced Encryption Standard (1998)

    Google Scholar 

  3. Biham, E.: New types of cryptanalytic attacks using related keys. Journal of Cryptology 7(4), 229–246 (1994)

    Article MATH  Google Scholar 

  4. Biham, E., Biryukov, A.: An improvement of Davies’ attack on DES. Journal of Cryptology 10(3), 195–206 (1997)

    Article MATH  Google Scholar 

  5. Biham, E., Dunkelman, O., Keller, N.: Enhancing Differential-Linear Cryptanalysis. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 254–266. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  6. Biham, E., Dunkelman, O., Keller, N.: Differential-Linear Cryptanalysis of Serpent. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 9–21. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  7. Biham, E., Dunkelman, O., Keller, N.: New Combined Attacks on Block Ciphers. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 126–144. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  8. Biham, E., Shamir, A.: Differential Cryptanalysis of DES-like Cryptosystems. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1991)

    Google Scholar 

  9. Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. Journal of Cryptology 4(1), 3–72 (1991)

    Article MathSciNet MATH  Google Scholar 

  10. Biham, E., Shamir, A.: Differential Cryptanalysis of the Full 16-Round DES. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 487–496. Springer, Heidelberg (1993)

    Chapter  Google Scholar 

  11. Courtois, N.T.: CTC2 and fast algebraic attacks on block ciphers revisited. IACR ePrint report 2007/152 (2007)

    Google Scholar 

  12. Courtois, N.T., Pieprzyk, J.: Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 267–287. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  13. Davies, D.: Investigation of a potential weakness in the DES algorithm (1987)

    Google Scholar 

  14. Dunkelman, O.: Techniques for cryptanalysis of block ciphers. Ph.D. thesis, Technion — Israel Institute of Technology, Israel (2006)

    Google Scholar 

  15. Dunkelman, O., Keller, N.: Cryptanalysis of CTC2. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 226–239. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  16. Dunkelman, O., Indesteege, S., Keller, N.: A Differential-Linear Attack on 12-Round Serpent. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 308–321. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  17. Handschuh, H., Naccache, D.: SHACAL. In: Proceedings of the First Open NESSIE Workshop (2000)

    Google Scholar 

  18. Hawkes, P.: Differential-Linear Weak Key Classes of IDEA. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 112–126. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  19. Kelsey, J., Schneier, B., Wagner, D.: Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 237–251. Springer, Heidelberg (1996)

    Google Scholar 

  20. Kim, J.: Combined differential, linear and related-key attacks on block ciphers and MAC algorithms. Ph.D. thesis, Katholieke Universiteit Leuven, Blegium (2006)

    Google Scholar 

  21. Knudsen, L.R.: Cryptanalysis of LOKI91. In: Zheng, Y., Seberry, J. (eds.) AUSCRYPT 1992. LNCS, vol. 718, pp. 196–208. Springer, Heidelberg (1993)

    Chapter  Google Scholar 

  22. Knudsen, L.R.: Trucated and Higher Order Differentials. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 196–211. Springer, Heidelberg (1995)

    Chapter  Google Scholar 

  23. Knudsen, L.R., Mathiassen, J.E.: A Chosen-Plaintext Linear Attack on DES. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 262–272. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  24. Lai, X., Massey, J.L.: Markov Ciphers and Differential Cryptanalysis. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 17–38. Springer, Heidelberg (1991)

    Chapter  Google Scholar 

  25. Langford, S.K.: Differential-linear cryptanalysis and threshold signatures. Ph.D. thesis, Stanford University, USA (1995)

    Google Scholar 

  26. Langford, S.K., Hellman, M.E.: Differential-Linear Cryptanalysis. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 17–25. Springer, Heidelberg (1994)

    Google Scholar 

  27. Lu, J.: Cryptanalysis of block ciphers. Ph.D. thesis, University of London, UK (2008)

    Google Scholar 

  28. Lu, J.: New methodologies for differential-linear cryptanalysis and its extensions. Cryptology ePrint Archive, Report 2010/025 (2010),http://eprint.iacr.org/2010/025

  29. Matsui, M.: Linear Cryptanalysis Method for DES Cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)

    Chapter  Google Scholar 

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

    Google Scholar 

  31. Matsui, M., Yamagishi, A.: A New Method for Known Plaintext Attack of FEAL Cipher. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 81–91. Springer, Heidelberg (1993)

    Chapter  Google Scholar 

  32. National Bureau of Standards (NBS), Data Encryption Standard (DES), FIPS-46 (1977)

    Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Agency for Science, Technology and Research, Institute for Infocomm Research, 1 Fusionopolis Way, #19-01 Connexis, Singapore, 138632

    Jiqiang Lu

Authors
  1. Jiqiang Lu

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. INRIA Paris-Rocquencourt, B.P. 105, 78153, Le Chesnay, France

    Anne Canteaut

Rights and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Lu, J. (2012). A Methodology for Differential-Linear Cryptanalysis and Its Applications. In: Canteaut, A. (eds) Fast Software Encryption. FSE 2012. Lecture Notes in Computer Science, vol 7549. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34047-5_5

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp