Skip to main content
SpringerLink
Log in

Exploiting Non-full Key Additions: Full-Fledged Automatic Demirci-Selçuk Meet-in-the-Middle Cryptanalysis of SKINNY

  • Conference paper
  • First Online:
Advances in Cryptology – EUROCRYPT 2023 (EUROCRYPT 2023)

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

Abstract

The Demirci-Selçuk meet-in-the-middle (DS-MITM) attack is a sophisticated variant of differential attacks. Due to its sophistication, it is hard to efficiently find the best DS-MITM attacks on most ciphers except for AES. Moreover, the current automatic tools only capture the most basic version of DS-MITM attacks, and the critical techniques developed for enhancing the attacks (e.g., differential enumeration and key-dependent-sieve) still rely on manual work. In this paper, we develop a full-fledged automatic framework integrating all known techniques (differential enumeration, key-dependent-sieve, and key bridging, etc.) for the DS-MITM attack that can produce key-recovery attacks directly rather than only search for distinguishers. Moreover, we develop a new technique that is able to exploit partial key additions to generate more linear relations beneficial to the attacks. We apply the framework to the SKINNY family of block ciphers and significantly improved results are obtained. In particular, all known DS-MITM attacks on the respective versions of SKINNY are improved by at least 2 rounds, and the data, memory, or time complexities of some attacks are reduced even compared to previous best attacks penetrating less rounds.

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 11439
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
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

References

  1. Ankele, R., Dobraunig, C., Guo, J., Lambooij, E., Leander, G., Todo, Y.: Zero-correlation attacks on tweakable block ciphers with linear tweakey expansion. IACR Trans. Symmetric Cryptol. 2019(1), 192–235 (2019). https://doi.org/10.13154/tosc.v2019.i1.192-235

  2. Bao, Z., Guo, J., Shi, D., Tu, Y.: Superposition meet-in-the-middle attacks: updates on fundamental security of AES-like hashing. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology - CRYPTO 2022–42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, 15–18 August 2022, Proceedings, Part I. LNCS, vol. 13507, pp. 64–93. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15802-5_3

  3. 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, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_5

    Chapter  Google Scholar 

  4. Chen, Q., Shi, D., Sun, S., Hu, L.: Automatic Demirci-Selçuk meet-in-the-middle attack on SKINNY with key-bridging. In: Zhou, J., Luo, X., Shen, Q., Xu, Z. (eds.) ICICS 2019. LNCS, vol. 11999, pp. 233–247. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-41579-2_14

    Chapter  Google Scholar 

  5. Daemen, J., Rijmen, V.: The Design of Rijndael - The Advanced Encryption Standard (AES), Second Edition. Information Security and Cryptography. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-662-60769-5

  6. Demirci, H., Selçuk, A.A.: A meet-in-the-middle attack on 8-round AES. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 116–126. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-71039-4_7

    Chapter  Google Scholar 

  7. Demirci, H., Taşkın, İ, Çoban, M., Baysal, A.: Improved meet-in-the-middle attacks on AES. In: Roy, B., Sendrier, N. (eds.) INDOCRYPT 2009. LNCS, vol. 5922, pp. 144–156. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10628-6_10

    Chapter  MATH  Google Scholar 

  8. Derbez, P., Fouque, P.-A.: Exhausting Demirci-Selçuk meet-in-the-middle attacks against reduced-round AES. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 541–560. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43933-3_28

    Chapter  Google Scholar 

  9. Derbez, P., Fouque, P.-A.: Automatic search of meet-in-the-middle and impossible differential attacks. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 157–184. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_6

    Chapter  MATH  Google Scholar 

  10. Derbez, P., Fouque, P.-A., Jean, J.: Improved key recovery attacks on reduced-round , in the single-key setting. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 371–387. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_23

    Chapter  MATH  Google Scholar 

  11. Dong, X., Hua, J., Sun, S., Li, Z., Wang, X., Hu, L.: Meet-in-the-middle attacks revisited: key-recovery, collision, and preimage attacks. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 278–308. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_10

    Chapter  Google Scholar 

  12. Dunkelman, O., Huang, S., Lambooij, E., Perle, S.: Biased differential distinguisher - cryptanalysis of reduced-round SKINNY. Inf. Comput. 281, 104796 (2021). https://doi.org/10.1016/j.ic.2021.104796

    Article  MathSciNet  MATH  Google Scholar 

  13. Dunkelman, O., Keller, N., Shamir, A.: Improved single-key attacks on 8-round AES-192 and AES-256. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 158–176. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_10

    Chapter  Google Scholar 

  14. Hadipour, H., Eichlseder, M.: Autoguess: a tool for finding guess-and-determine attacks and key bridges. In: Ateniese, G., Venturi, D. (eds.) Applied Cryptography and Network Security - 20th International Conference, ACNS 2022, Rome, Italy, 20–23 June 2022, Proceedings. LNCS, vol. 13269, pp. 230–250. Springer (2022). https://doi.org/10.1007/978-3-031-09234-3_12

  15. Hadipour, H., Sadeghi, S., Eichlseder, M.: Finding the impossible: automated search for full impossible differential, zero-correlation, and integral attacks. IACR Cryptology ePrint Archive, p. 1147 (2022). https://eprint.iacr.org/2022/1147

  16. Li, L., Jia, K., Wang, X.: Improved single-key attacks on 9-round AES-192/256. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 127–146. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46706-0_7

    Chapter  Google Scholar 

  17. Li, R., Jin, C.: Meet-in-the-middle attacks on 10-round AES-256. Des. Codes Crypt. 80(3), 459–471 (2015). https://doi.org/10.1007/s10623-015-0113-3

    Article  MathSciNet  MATH  Google Scholar 

  18. Li, R., Jin, C.: Meet-in-the-middle attacks on round-reduced tweakable block cipher Deoxys-BC. IET Inf. Secur. 13(1), 70–75 (2019). https://doi.org/10.1049/iet-ifs.2018.5091

    Article  Google Scholar 

  19. Lin, L., Wu, W., Wang, Y., Zhang, L.: General model of the single-key meet-in-the-middle distinguisher on the word-oriented block cipher. In: Lee, H.-S., Han, D.-G. (eds.) ICISC 2013. LNCS, vol. 8565, pp. 203–223. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-12160-4_13

    Chapter  Google Scholar 

  20. Shi, D., Sun, S., Derbez, P., Todo, Y., Sun, B., Hu, L.: Programming the Demirci-Selçuk meet-in-the-middle attack with constraints. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11273, pp. 3–34. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_1

    Chapter  Google Scholar 

  21. Shi, D., Sun, S., Song, L., Hu, L., Yang, Q.: Exploiting non-full key additions: full-fledged automatic Demirci-Selcuk meet-in-the-middle cryptanalysis of skinny. IACR Cryptology ePrint Archive, p. 255 (2023). https://eprint.iacr.org/2023/255

  22. Tolba, M., Abdelkhalek, A., Youssef, A.M.: Impossible differential cryptanalysis of reduced-round SKINNY. In: Joye, M., Nitaj, A. (eds.) AFRICACRYPT 2017. LNCS, vol. 10239, pp. 117–134. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57339-7_7

    Chapter  Google Scholar 

  23. Yang, D., Qi, W., Chen, H.: Impossible differential attacks on the SKINNY family of block ciphers. IET Inf. Secur. 11(6), 377–385 (2017). https://doi.org/10.1049/iet-ifs.2016.0488

    Article  Google Scholar 

Download references

Acknowledgments

We thank anonymous reviewers for their valuable comments. This research is supported by the National Key R &D Program of China (Grants No. 2022YFB2701900, 2018YFA0704704), the National Natural Science Foundation of China (Grants No. 62172410, 62022036, 62132008, 62032014, 62202460), the Youth Innovation Promotion Association of Chinese Academy of Sciences, and the Fundamental Research Funds for the Central Universities.

Author information

Authors and Affiliations

  1. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China

    Danping Shi, Lei Hu & Qianqian Yang

  2. School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

    Danping Shi, Lei Hu & Qianqian Yang

  3. School of Cryptology, University of Chinese Academy of Sciences, Beijing, China

    Siwei Sun

  4. Jinan University, Guangzhou, China

    Ling Song

Authors
  1. Danping Shi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Siwei Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ling Song
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Lei Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Qianqian Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Siwei Sun .

Editor information

Editors and Affiliations

  1. Bar-Ilan University, Ramat Gan, Israel

    Carmit Hazay

  2. Simula UiB, Bergen, Norway

    Martijn Stam

Rights and permissions

Reprints and permissions

Copyright information

© 2023 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Shi, D., Sun, S., Song, L., Hu, L., Yang, Q. (2023). Exploiting Non-full Key Additions: Full-Fledged Automatic Demirci-Selçuk Meet-in-the-Middle Cryptanalysis of SKINNY. In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14007. Springer, Cham. https://doi.org/10.1007/978-3-031-30634-1_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-30634-1_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-30633-4

  • Online ISBN: 978-3-031-30634-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation