A Novel Method for Finding Differential-Linear Distinguishers: Application to  $$\textsf{Midori64}$$ , $$\textsf{CRAFT}$$ , and  $$\textsf{Skinny64}$$ | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Novel Method for Finding Differential-Linear Distinguishers: Application to \(\textsf{Midori64}\), \(\textsf{CRAFT}\), and \(\textsf{Skinny64}\)

  • Conference paper
  • First Online:
Cryptology and Network Security (CANS 2024)

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

Included in the following conference series:

  • 53 Accesses

Abstract

In this paper, we propose a new method based on Mixed-Integer Linear Programming (MILP) to search for differential-linear (DL) distinguishers targeting word-oriented block ciphers. To be specific, we present a new structure of DL distinguishers based on the works of Biham et al. and Bar-On et al., and divide the process of finding an R-round DL distinguisher into two stages. In the first stage, we aim to prepare some special (\(R-1\))-round truncated differentials with high probabilities using MILP, which is adapted to our new DL structure. To achieve this goal, we simplify the types of previous truncated differential (TD) patterns and optimize the propagation rules of TDs. In the second stage, we concatenate the prepared TDs with the introduced concept of the differential-linear connectivity layer (DLCL), whose bias can be calculated by differential-linear connectivity tables (DLCTs) of S-boxes, to efficiently determine the optimal output linear mask for deriving an R-round DL distinguisher.

We apply the proposed method to Midori64, CRAFT, and Skinny64. As a result, the longest DL distinguishers obtained in this paper for Midori64, CRAFT, and Skinny64 are 6, 11, and 10 rounds with the estimated biases of \(2^{-14.43}\), \(2^{-16.04}\), and \(2^{-22.73}\), respectively. To the best of our knowledge, this is the first study to explore the DL distinguishers of Midori64 and CRAFT against DL cryptanalysis. In addition, we also conduct experiments to verify the validity of these distinguishers. Consequently, our estimated biases are very close to the experimental ones, which indicates that these DL distinguishers are indeed valid and also provides a strong support for the effectiveness of our method. By the way, our results cannot threaten the security of the three ciphers, but provide a better understanding on the strength against DL cryptanalysis, especially for Midori64 and CRAFT.

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 6634
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 8293
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    https://github.com/someoneDL/MILP_DL_Search.

  2. 2.

    https://sagecell.sagemath.org/.

  3. 3.

    https://www.gurobi.com/.

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). https://doi.org/10.13154/TOSC.V2017.I4.99-129

  2. Banik, S., Bogdanov, A., Isobe, T., Shibutani, K., Hiwatari, H., Akishita, T., Regazzoni, F.: Midori: A block cipher for low energy. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 411–436. Springer (2015). https://doi.org/10.1007/978-3-662-48800-3_17

  3. Bar-On, A., Dunkelman, O., Keller, N., Weizman, A.: DLCT: A new tool for differential-linear cryptanalysis. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 313–342. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_11

  4. Beierle, C., et al.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 123–153. Springer, Cham (2016). https://doi.org/10.1007/978-3-662-53008-5_5

  5. Beierle, C., Leander, G., Moradi, A., Rasoolzadeh, S.: CRAFT: Lightweight tweakable block cipher with efficient protection against DFA attacks. IACR Trans. Symmetric Cryptol. 2019(1), 5–45 (2019). https://doi.org/10.13154/tosc.v2019.i1.5-45

  6. Bellini, E., Gérault, D., Grados, J., Makarim, R.H., Peyrin, T.: Fully automated differential-linear attacks against ARX ciphers. In: Rosulek, M. (ed.) CT-RSA 2023. LNCS, vol. 13871, pp. 252–276. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30872-7_10

  7. Biham, E., Biryukov, A., Shamir, A.: Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. J. Cryptol. 18(4), 291–311 (2005). https://doi.org/10.1007/S00145-005-0129-3

    Article  MathSciNet  Google Scholar 

  8. Biham, E., Dunkelman, O., Keller, N.: Enhancing differential-linear cryptanalysis. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 254–266. Springer, Cham (2002). https://doi.org/10.1007/3-540-36178-2_16

  9. Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4(1), 3–72 (1991). https://doi.org/10.1007/BF00630563

    Article  MathSciNet  Google Scholar 

  10. Blondeau, C., Leander, G., Nyberg, K.: Differential-linear cryptanalysis revisited. J. Cryptol. 30(3), 859–888 (2017). https://doi.org/10.1007/s00145-016-9237-5

    Article  MathSciNet  Google Scholar 

  11. Daemen, J., Rijmen, V.: The design of rijndael: AES - the advanced encryption standard. information security and cryptography, Springer, Cham (2002). https://doi.org/10.1007/978-3-662-04722-4

  12. Dey, S., Garai, H.K., Sarkar, S., Sharma, N.K.: Revamped differential-linear cryptanalysis on reduced round ChaCha. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13277, pp. 86–114. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-07082-2_4

  13. Dobraunig, C., Eichlseder, M., Mendel, F., Schläffer, M.: Cryptanalysis of ascon. In: Nyberg, K. (ed.) CT-RSA 2015. LNCS, vol. 9048, pp. 371–387. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-16715-2_20

  14. Dobraunig, C., Eichlseder, M., Mendel, F., Schläffer, M.: Ascon v1.2: Lightweight authenticated encryption and hashing. J. Cryptol. 34(3), 33 (2021). https://doi.org/10.1007/s00145-021-09398-9

  15. Guo, H., Zhang, Z., Yang, Q., Hu, L., Luo, Y.: A new method to find all the high-probability word-oriented truncated differentials: application to midori. SKINNY CRAFT. Comput. J. 66(5), 1069–1082 (2023). https://doi.org/10.1093/comjnl/bxab213

    Article  Google Scholar 

  16. Hadipour, H., Derbez, P., Eichlseder, M.: Revisiting differential-linear attacks via a boomerang perspective with application to AES, Ascon, CLEFIA, SKINNY, PRESENT, KNOT, TWINE, WARP, LBlock, Simeck, and SERPENT. IACR Cryptol. ePrint Arch., Paper 2024/255 at https://eprint.iacr.org/2024/255 (2024)

  17. Knudsen, L.R.: Truncated and higher order differentials. In: Preneel, B. (ed.) FES 1994. LNCS, vol. 1008, pp. 196–211. Springer, Cham (1994). https://doi.org/10.1007/3-540-60590-8_16

  18. Lai, X.: Higher order derivatives and differential cryptanalysis. Communications and Cryptography: Two Sides of One Tapestry, pp. 227–233 (1994)

    Google Scholar 

  19. Langford, S.K., Hellman, M.E.: Differential-linear cryptanalysis. In: Desmedt, Y. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 17–25. Springer, Cham (1994). https://doi.org/10.1007/3-540-48658-5_3

  20. Leurent, G.: Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning. In: Fischlin, M., Coron, J. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 344–371. Springer, Cham (2016). https://doi.org/10.1007/978-3-662-49890-3_14

  21. Liu, M., Lu, X., Lin, D.: Differential-linear cryptanalysis from an algebraic perspective. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 247–277. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_9

  22. Lu, J.: A methodology for differential-linear cryptanalysis and its applications. Des. Codes Cryptogr. 77(1), 11–48 (2015). https://doi.org/10.1007/s10623-014-9985-x

    Article  MathSciNet  Google Scholar 

  23. Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Cham (1993). https://doi.org/10.1007/3-540-48285-7_33

  24. Matsui, M.: On correlation between the order of s-boxes and the strength of DES. In: Santis, A.D. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 366–375. Springer, Cham (1994). https://doi.org/10.1007/BFb0053451

  25. Moghaddam, A.E., Ahmadian, Z.: New automatic search method for truncated-differential characteristics application to Midori. SKINNY CRAFT. Comput. J. 63(12), 1813–1825 (2020). https://doi.org/10.1093/comjnl/bxaa004

    Article  MathSciNet  Google Scholar 

  26. Mouha, N., Wang, Q., Gu, D., Preneel, B.: Differential and linear cryptanalysis using mixed-integer linear programming. In: Wu, C., Yung, M., Lin, D. (eds.) Inscrypt 2011. LNCS, vol. 7537, pp. 57–76. Springer, Cham (2011). https://doi.org/10.1007/978-3-642-34704-7_5

  27. Pal, D., Chandratreya, V.P., Chowdhury, D.R.: New techniques for modeling sboxes: an MILP approach. In: Deng, J., Kolesnikov, V., Schwarzmann, A.A. (eds.) CANS 2023. LNCS, vol. 14342, pp. 318–340. Springer, Cham (2023). https://doi.org/10.1007/978-981-99-7563-1_15

  28. 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 

  29. Sun, L., Gérault, D., Wang, W., Wang, M.: On the usage of deterministic (related-key) truncated differentials and multidimensional linear approximations for SPN ciphers. IACR Trans. Symmetric Cryptol. 2020(3), 262–287 (2020). https://doi.org/10.13154/tosc.v2020.i3.262-287

  30. Sun, S., Hu, L., Song, L., Xie, Y., Wang, P.: Automatic security evaluation of block ciphers with S-bP structures against related-key differential attacks. In: Lin, D., Xu, S., Yung, M. (eds.) Inscrypt 2013. LNCS, vol. 8567, pp. 39–51. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-12087-4_3

  31. Sun, S., et al.: Towards finding the best characteristics of some bit-oriented block ciphers and automatic enumeration of (related-key) differential and linear characteristics with predefined properties. Cryptology ePrint Archive, Paper 2014/747. https://eprint.iacr.org/2014/747 (2014)

  32. Todo, Y., Isobe, T., Hao, Y., Meier, W.: Cube attacks on non-blackbox polynomials based on division property. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10403, pp. 250–279. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_9

  33. US National Bureau of Standards: Data Encryption Standard (DES). Federal Information Processing Standards Publications No. 46 (1977)

    Google Scholar 

  34. Watanabe, D., Okamoto, K., Kaneko, T.: A hardware-oriented light weight pseudo-random number generator Enocoro-128v2. In: The Symposium on Cryptography and Information Security, pp. 3D1–3 (2010)

    Google Scholar 

  35. Xiang, Z., Zhang, W., Bao, Z., Lin, D.: Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 648–678. Springer, Cham (2016). https://doi.org/10.1007/978-3-662-53887-6_24

Download references

Acknowledgement

We would like to thank all the anonymous reviewers of CANS ‘24 for their valuable comments to improve the quality of this paper. This work was supported by the National Natural Science Foundation of China (No. 62272147, No. 12471492, No. 62072161, No. 62072161), the Innovation Group Project of the Natural Science Foundation of Hubei Province of China (No. 2023AFA021), the Science and Technology on Communication Security Laboratory Foundation (No. 6142103012207) and the Wuhan Science and Technology Bureau (NO. 2022010801020328).

Author information

Authors and Affiliations

  1. School of Cyber Science and Technology, Key Laboratory of Intelligent Sensing System and Security, Ministry of Education, Wuhan, China

    Mei Yan, Siwei Chen, Zejun Xiang & Shasha Zhang

  2. Faculty of Mathematics and Statistics, Hubei Key Laboratory of Applied Mathematics, Hubei University, Wuhan, China

    Xiangyong Zeng

Authors
  1. Mei Yan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Siwei Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zejun Xiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Shasha Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Xiangyong Zeng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Siwei Chen .

Editor information

Editors and Affiliations

  1. University of Edinburgh, Edinburgh, UK

    Markulf Kohlweiss

  2. King Abdullah University of Science and Technology, Thuwal, Saudi Arabia

    Roberto Di Pietro

  3. Department of Computer Science and Technology, University of Cambridge, Cambridge, UK

    Alastair Beresford

Rights and permissions

Reprints and permissions

Copyright information

© 2025 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Yan, M., Chen, S., Xiang, Z., Zhang, S., Zeng, X. (2025). A Novel Method for Finding Differential-Linear Distinguishers: Application to \(\textsf{Midori64}\), \(\textsf{CRAFT}\), and \(\textsf{Skinny64}\). In: Kohlweiss, M., Di Pietro, R., Beresford, A. (eds) Cryptology and Network Security. CANS 2024. Lecture Notes in Computer Science, vol 14906. Springer, Singapore. https://doi.org/10.1007/978-981-97-8016-7_10

Download citation

  • DOI: https://doi.org/10.1007/978-981-97-8016-7_10

  • Published:

  • Publisher Name: Springer, Singapore

  • Print ISBN: 978-981-97-8015-0

  • Online ISBN: 978-981-97-8016-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation