SpringerLink
Log in

New Automatic Search Tool for Searching for Impossible Differentials Using Undisturbed Bits

  • Conference paper
  • First Online:
Information Security and Cryptology (Inscrypt 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13837))

Included in the following conference series:

  • 804 Accesses

Abstract

Impossible differential cryptanalysis is a powerful tool for analyzing the security of symmetric-key primitives. At first, the attacker must finds some impossible differentials as long as possible. There are many tools to automatically search for the longest impossible differentials. In all of these search tools, the input and output differences are fixed before searching, which leads to some limitations. The first limitation is that the number of impossible differentials that can be found is very small. The second limitation is that the existing tools are ineffective in searching for truncated impossible differentials. For some symmetric-key primitives, these tools can only find short round truncated impossible differentials, and for others they can’t even find truncated impossible differentials. As we all know, the number of impossible differentials is also very important because it can improve the data complexity and time complexity of impossible differential cryptanalysis in some cases. In addition, using truncated impossible differentials can usually get better results when impossible differentials are of the same length. In this paper, we propose a new automatic search tool that can overcome the above two limitations. The tool can not only find a large number of impossible differentials in a short time, but also can get truncated impossible differentials of bit-level primitives. It uses undisturbed differential bits, that is, the differential bits with probability 1 in differential propagation, and is based on mixed-integer linear programming (MILP) and meet-in-the-middle technology. We applied the tool to ASCON, SIMON, LBlock and LEA. For each of the four primitives, we found many new impossible differentials. For SIMON and LBlock, we found some related-key impossible differentials longer than the best-known results.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 67.40
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 85.59
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Abdelkhalek, A., Sasaki, Y., Todo, Y., Tolba, M., Youssef, A.M.: MILP modeling for (large) s-boxes to optimize probability of differential characteristics. IACR Trans. Symmetric Cryptol. 2017(4), 99–129 (2017)

    Google Scholar 

  2. Alkhzaimi, H., Lauridsen, M.: Cryptanalysis of the simon family of block ciphers. IACR Cryptology ePrint Archive (2013)

    Google Scholar 

  3. Baksi, A.: New insights on differential and linear bounds using mixed integer linear programming. In: Maimut, D., Oprina, A.-G., Sauveron, D. (eds.) SecITC 2020. LNCS, vol. 12596, pp. 41–54. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-69255-1_4

    Chapter  Google Scholar 

  4. Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK lightweight block ciphers. In: 2015 52nd ACM/EDAC/IEEE Design Automation Conference (DAC), pp. 1–6. IEEE (2015)

    Google Scholar 

  5. Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Permutation-based encryption, authentication and authenticated encryption. In: Directions in Authenticated Ciphers, pp. 159–170 (2012)

    Google Scholar 

  6. Biham, E., Biryukov, A., Shamir, A.: Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 12–23. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_2

    Chapter  Google Scholar 

  7. Bogdanov, A., Leander, G., Nyberg, K., Wang, M.: Integral and multidimensional linear distinguishers with correlation zero. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 244–261. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_16

    Chapter  Google Scholar 

  8. Bogdanov, A., Wang, M.: Zero correlation linear cryptanalysis with reduced data complexity. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 29–48. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34047-5_3

    Chapter  Google Scholar 

  9. 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. LNCS, vol. 8873, pp. 179–199. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45611-8_10

    Chapter  Google Scholar 

  10. Tingting, C.U.I., Shiyao, C.H.E.N., Kai, F.U., Meiqin, W.A.N.G., Keting, J.I.A.: New automatic tool for finding impossible differentials and zero-correlation linear approximations. Inf. Sci. 64(129103), 1–129103 (2021)

    Google Scholar 

  11. Dobraunig, C., Eichlseder, M., Mendel, F., Schläffer, M.: Ascon v1. 2. Submission to the CAESAR Competition (2016)

    Google Scholar 

  12. Hong, D., Lee, J., Kim, D., Kwon, D., Ryu, K.H., Lee, D.: LEA: a 128-bit block cipher for fast encryption on common processors. In: Workshop on Information Security Applications, pp. 3–27 (2013)

    Google Scholar 

  13. Hong, D., et al.: HIGHT: a new block cipher suitable for low-resource device. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 46–59. Springer, Heidelberg (2006). https://doi.org/10.1007/11894063_4

    Chapter  Google Scholar 

  14. Kim, J., Hong, S., Sung, J., Lee, S., Lim, J., Sung, S.: Impossible differential cryptanalysis for block cipher structures. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 82–96. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-24582-7_6

    Chapter  Google Scholar 

  15. Knudsen, L.: Deal-a 128-bit block cipher. Complexity 258(2), 216 (1998)

    Google Scholar 

  16. Kondo, K., Sasaki, Yu., Todo, Y., Iwata, T.: Analyzing key schedule of Simon: iterative key differences and application to related-key impossible differentials. In: Obana, S., Chida, K. (eds.) IWSEC 2017. LNCS, vol. 10418, pp. 141–158. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-64200-0_9

    Chapter  MATH  Google Scholar 

  17. Luo, Y., Wu, Z., Lai, X., Gong, G.: Unified impossible differential cryptanalysis on block cipher structures. Report, Cryptology ePrint Archive, Report 2009/627 (2009)

    Google Scholar 

  18. Sasaki, Yu., Todo, Y.: New impossible differential search tool from design and cryptanalysis aspects. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 185–215. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_7

    Chapter  Google Scholar 

  19. Sun, S., Hu, L., Wang, P., Qiao, K., Ma, X., Song, L.: Automatic security evaluation and (related-key) differential characteristic search: application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 158–178. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45611-8_9

    Chapter  Google Scholar 

  20. Tezcan, C.: Improbable differential attacks on present using undisturbed bits. J. Comput. Appl. Math. 259, 503–511 (2014)

    Article  MATH  Google Scholar 

  21. Tezcan, C.: Truncated, impossible, and improbable differential analysis of ASCON. In: Camp, O., Furnell, S., Mori, P. (eds.) Proceedings of the 2nd International Conference on Information Systems Security and Privacy, ICISSP 2016, Rome, Italy, 19–21 February 2016, pp. 325–332. SciTePress (2016)

    Google Scholar 

  22. Wang, Q., Liu, Z., Varıcı, K., Sasaki, Yu., Rijmen, V., Todo, Y.: Cryptanalysis of reduced-round SIMON32 and SIMON48. In: Meier, W., Mukhopadhyay, D. (eds.) INDOCRYPT 2014. LNCS, vol. 8885, pp. 143–160. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13039-2_9

    Chapter  Google Scholar 

  23. Wang, X., Baofeng, W., Hou, L., Lin, D.: Searching for related-key impossible differentials for SIMON. J. Cryptol. Res. 8(5), 881–893 (2021)

    Google Scholar 

  24. Wu, S., Wang, M.: Automatic search of truncated impossible differentials for word-oriented block ciphers. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 283–302. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34931-7_17

    Chapter  Google Scholar 

  25. Wu, W., Zhang, L.: LBlock: a lightweight block cipher. In: Lopez, J., Tsudik, G. (eds.) ACNS 2011. LNCS, vol. 6715, pp. 327–344. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21554-4_19

    Chapter  Google Scholar 

Download references

Acknowledgements

The authors would like to thank the anonymous reviewers for their helpful comments and suggestions. This work was supported by the National Natural Science Foundation of China (Grant No. 61379138).

Author information

Authors and Affiliations

  1. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Bei**g, China

    Weiwei Cao, Wentao Zhang & Chunning Zhou

  2. School of Cyber Security, University of Chinese Academy of Sciences, Bei**g, China

    Weiwei Cao, Wentao Zhang & Chunning Zhou

Authors
  1. Weiwei Cao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wentao Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Chunning Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wentao Zhang .

Editor information

Editors and Affiliations

  1. Institute of Information Engineering, CAS, Bei**g, China

    Yi Deng

  2. Columbia University, New York, NY, USA

    Moti Yung

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Cao, W., Zhang, W., Zhou, C. (2023). New Automatic Search Tool for Searching for Impossible Differentials Using Undisturbed Bits. In: Deng, Y., Yung, M. (eds) Information Security and Cryptology. Inscrypt 2022. Lecture Notes in Computer Science, vol 13837. Springer, Cham. https://doi.org/10.1007/978-3-031-26553-2_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-26553-2_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-26552-5

  • Online ISBN: 978-3-031-26553-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation