[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

abstractXOR: A global constraint dedicated to differential cryptanalysis

  • Conference paper
  • First Online:
Principles and Practice of Constraint Programming (CP 2020)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 12333))

Abstract

Constraint Programming models have been recently proposed to solve cryptanalysis problems for symmetric block ciphers such as AES. These models are more efficient than dedicated approaches but their design is difficult: straightforward models do not scale well and it is necessary to add advanced constraints derived from cryptographic properties. We introduce a global constraint which simplifies the modelling step and improves efficiency. We study its complexity, introduce propagators and experimentally evaluate them on two cryptanalysis problems (single-key and related-key) for two block ciphers (AES and Midori).

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
£29.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
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 103.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 129.99
Price includes VAT (United Kingdom)
  • 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. Abdelkhalek, A., Sasaki, Y., Todo, Y., Tolba, M., Youssef, A.: MILP modeling for (large) s-boxes to optimize probability of differential characteristics. IACR Trans. Symmetric Cryptol. 2017(4), 99–129 (2017)

    Google Scholar 

  2. Banik, S., et al.: Midori: a block cipher for low energy. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 411–436. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48800-3_17

    Chapter  Google Scholar 

  3. Beierle, C., et al.: The SKINNY family of block ciphers and its low-latency ariant 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. Biere, A.: Yet another local search solver and lingeling and friends entering the sat competition 2014, pp. 39–40, January 2014

    Google Scholar 

  5. Biham, E.: New types of cryptoanalytic attacks using related keys (extended abstract). In: EUROCRYPT, LNCS, vol. 765, pp. 398–409. Springer (1993)

    Google Scholar 

  6. Biham, E., Shamir, A.: Differential cryptanalysis of feal and N-Hash. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 1–16. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-46416-6_1

    Chapter  Google Scholar 

  7. Biryukov, A., Nikolić, I.: Automatic search for related-key differential characteristics in byte-oriented block ciphers: application to AES, Camellia, Khazad and others. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 322–344. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_17

    Chapter  MATH  Google Scholar 

  8. Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting systematic search by weighting constraints. In: Proceedings of the 16th Eureopean Conference on Artificial Intelligence, ECAI 2004, pp. 146–150. IOS Press (2004)

    Google Scholar 

  9. Cid, C., Huang, T., Peyrin, T., Sasaki, Yu., Song, L.: Boomerang connectivity table: a new cryptanalysis tool. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 683–714. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_22

    Chapter  Google Scholar 

  10. FIPS 197: Advanced Encryption Standard. Federal Information Processing Standards Publication 197 (2001). u.S. Department of Commerce/N.I.S.T

    Google Scholar 

  11. Fouque, P.-A., Jean, J., Peyrin, T.: Structural evaluation of AES and chosen-key distinguisher of 9-round AES-128. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 183–203. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_11

    Chapter  Google Scholar 

  12. Gérault, D.: Security Analysis of Contactless Communication Protocols. Ph.D. thesis, Université Clermont Auvergne (2018)

    Google Scholar 

  13. Gérault, D., Lafourcade, P.: Related-key cryptanalysis of Mmidori. In: Dunkelman, O., Sanadhya, S.K. (eds.) INDOCRYPT 2016. LNCS, vol. 10095, pp. 287–304. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49890-4_16

    Chapter  Google Scholar 

  14. Gerault, D., Lafourcade, P., Minier, M., Solnon, C.: Computing AES related-key differential characteristics with constraint programming. Artif. Intell. 278, 103183 (2020)

    Article  MathSciNet  Google Scholar 

  15. Gerault, D., Minier, M., Solnon, C.: Constraint programming models for chosen key differential cryptanalysis. In: Rueher, M. (ed.) CP 2016. LNCS, vol. 9892, pp. 584–601. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44953-1_37

    Chapter  Google Scholar 

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

    Chapter  Google Scholar 

  17. Kölbl, S., Leander, G., Tiessen, T.: Observations on the SIMON block cipher family. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 161–185. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_8

    Chapter  Google Scholar 

  18. Lafitte, F.: Cryptosat: a tool for sat-based cryptanalysis. IET Inf. Secur. 12(6), 463–474 (2018)

    Article  Google Scholar 

  19. Le clément de saint Marcq, V., Schaus, P., Solnon, C., Lecoutre, C.: Sparse-sets for domain implementation. In: CP Workshop on Techniques for Implementing Constraint Programming Systems (TRICS) (2013). https://hal.archives-ouvertes.fr/hal-01339250

  20. Minier, M., Solnon, C., Reboul, J.: Solving a symmetric key cryptographic problem with constraint programming. In: Workshop on Constraint Modelling and Reformulation (ModRef), pp. 1–13 (2014)

    Google Scholar 

  21. Mouha, N., Preneel, B.: A proof that the ARX cipher salsa20 is secure against differential cryptanalysis. IACR Cryptology ePrint Archive 2013, p. 328 (2013)

    Google Scholar 

  22. Prud’homme, C., Fages, J.G., Lorca, X.: Choco Documentation. TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S. (2016). http://www.choco-solver.org

  23. Soos, M., Nohl, K., Castelluccia, C.: Extending SAT solvers to cryptographic problems. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol. 5584, pp. 244–257. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02777-2_24

    Chapter  Google Scholar 

  24. Sun, L., Wang, W., Wang, M.: More accurate differential properties of led64 and midori64. IACR Trans. Symmetric Cryptol. 2018(3), 93–123 (2018)

    Google Scholar 

  25. Sun, S., et al.: Analysis of AES, SKINNY, and others with constraint programming. In: 24th International Conference on Fast Software Encryption (2017)

    Google Scholar 

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

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

    Chapter  Google Scholar 

  28. Zhou, N.-F., Kjellerstrand, H., Fruhman, J.: Constraint Solving and Planning with Picat. SIS. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-25883-6

    Book  Google Scholar 

Download references

Acknowledgement

This work has been funded by ANR DeCrypt (ANR-18-CE39-0007). We thank Charles Prud’homme for answering our numerous questions on Choco.

Author information

Authors and Affiliations

  1. CITI, INRIA, INSA Lyon, 69621, Villeurbanne, France

    Loïc Rouquette & Christine Solnon

  2. LIRIS, UMR5201 CNRS, 69621, Villeurbanne, France

    Loïc Rouquette

Authors
  1. Loïc Rouquette
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Christine Solnon
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Christine Solnon .

Editor information

Editors and Affiliations

  1. Insight Centre for Data Analytics, School for Computer Science and Information Technology, University College Cork, Cork, Ireland

    Helmut Simonis

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Rouquette, L., Solnon, C. (2020). abstractXOR: A global constraint dedicated to differential cryptanalysis. In: Simonis, H. (eds) Principles and Practice of Constraint Programming. CP 2020. Lecture Notes in Computer Science(), vol 12333. Springer, Cham. https://doi.org/10.1007/978-3-030-58475-7_33

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-58475-7_33

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-58474-0

  • Online ISBN: 978-3-030-58475-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation