nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Improved Cryptanalysis of an ISO Standard Lightweight Block Cipher with Refined MILP Modelling

verfasst von : Jun Yin, Chuyan Ma, Lijun Lyu, Jian Song, Guang Zeng, Chuangui Ma, Fushan Wei

Erschienen in: Information Security and Cryptology

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Differential and linear cryptanalysis are two of the most effective attacks on block ciphers. Searching for (near) optimal differential or linear trails is not only useful for the security evaluation of block ciphers against these attacks, but also indispensable to the cryptanalysts who want to attack a cipher with these techniques. In recent years, searching for trails automatically with Mixed-Integer Linear Programming (MILP) gets a lot of attention. At first, Mouha et al. translated the problem of counting the minimum number of differentially active S-boxes into an MILP problem for word-oriented block ciphers. Subsequently, in Asiacrypt 2014, Sun et al. extended Mouha et al.’s method, and presented a technique which can find actual differential or linear characteristics of a block cipher in both the single-key and related-key models. In this paper, we refine the constraints of the 2-XOR operation in order to reduce the overall number of variables and constraints. Experimental results show that MILP models with the refined constraints can be solved more efficiently. We apply our method to HIGHT (an ISO standard), and we find differential (covering 11 rounds) or linear trails (covering 10 rounds) with higher probability or correlation. Moreover, we find so far the longest differential and linear distinguishers of HIGHT.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel BotTokenizer: Exploring Network Tokens of HTTP-Based Botnet Using Malicious Network Traces

Nächstes Kapitel Meet in the Middle Attack on Type-1 Feistel Construction

In [5], the 10-round linear approximation with \(\varepsilon ^{2}=2^{-54}\), \(\varepsilon \) is called bias. Correspondingly, converted into the 10-round linear approximation with correlation \(2^{-26}\).

The Figs. 1, 2 and 3 are generated by TikZ for Cryptographers, please refer to http://www.iacr.org/authors/tikz/.

The constraints appear in the slide that Sasaki et al. were reported in Eurocrypt 2017, please refer to https://eurocrypt2017.di.ens.fr/slides/A09-new-impossible-differential.pdf

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 CrossRef

Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., Vikkelsoe, C.: PRESENT: an ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74735-2_31 CrossRef

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 CrossRef

Zhang, W., Bao, Z., Lin, D., Rijmen, V., Yang, B., Verbauwhede, I.: Rectangle: a bit-slice lightweight block cipher suitable for multiple platforms. Sci. Chin. Inf. Sci. 58(12), 1–15 (2015). https://doi.org/10.1007/s11432-015-5459-7

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 CrossRef

Wheeler, D.J., Needham, R.M.: TEA, a tiny encryption algorithm. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 363–366. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60590-8_29 CrossRef

Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The simon and speck families of lightweight block ciphers. Cryptology ePrint Archive, Report 2013/404 (2013). http://eprint.iacr.org/2013/404

Dinu, D., Perrin, L., Udovenko, A., Velichkov, V., Großschädl, J., Biryukov, A.: Design strategies for ARX with provable bounds: Sparx and LAX. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 484–513. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_18 CrossRef

Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_1 CrossRef

10.

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

11.

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

12.

Chen, J., Miyaji, A., Su, C., Teh, J.S.: Accurate estimation of the full differential distribution for general feistel structures. In: Lin, D., Wang, X.F., Yung, M. (eds.) Inscrypt 2015. LNCS, vol. 9589, pp. 108–124. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-38898-4_7

13.

Chen, J., Miyaji, A., Su, C., Teh, J.: Improved differential characteristic searching methods. In: IEEE 2nd International Conference on Cyber Security and Cloud Computing, CSCloud 2015, New York, NY, USA, 3–5 November 2015, pp. 500–508 (2015). https://doi.org/10.1109/CSCloud.2015.42

14.

Biryukov, A., Velichkov, V.: Automatic search for differential trails in ARX ciphers. In: Benaloh, J. (ed.) CT-RSA 2014. LNCS, vol. 8366, pp. 227–250. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-04852-9_12 CrossRef

15.

Mouha, N., Preneel, B.: Towards finding optimal differential characteristics for arx: Application to salsa20. Cryptology ePrint Archive, Report 2013/328 (2013). http://eprint.iacr.org/2013/328

16.

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

17.

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

18.

Fu, K., Wang, M., Guo, Y., Sun, S., Hu, L.: MILP-based automatic search algorithms for differential and linear trails for speck. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 268–288. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-52993-5_14 CrossRef

19.

Sun, S., Gerault, D., Lafourcade, P., Yang, Q., Todo, Y., Qiao, K., Hu, L.: Analysis of aes, skinny, and others with constraint programming. IACR Trans. Symmetric Cryptol. 2017(1), 281–306 (2017). https://doi.org/10.13154/tosc.v2017.i1.281-306

20.

International Organization for Standardization. ISO/IEC 18033-3: 2010. Information technology Security techniques Encryption algorithms Part 3: Block ciphers (2010)

21.

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 CrossRef

22.

Wagner, D.: The boomerang attack. In: Knudsen, L. (ed.) FSE 1999. LNCS, vol. 1636, pp. 156–170. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48519-8_12 CrossRef

23.

Biryukov, A., Wagner, D.: Slide attacks. In: Knudsen, L. (ed.) FSE 1999. LNCS, vol. 1636, pp. 245–259. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48519-8_18 CrossRef

24.

Biham, E.: New types of cryptanalytic attacks using related keys. J. Cryptology 7(4), 229–246 (1994). https://doi.org/10.1007/BF00203965

25.

Lu, J.: Cryptanalysis of reduced versions of the hight block cipher from CHES 2006. In: Nam, K.-H., Rhee, G. (eds.) ICISC 2007. LNCS, vol. 4817, pp. 11–26. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-76788-6_2 CrossRef

26.

Özen, O., Varıcı, K., Tezcan, C., Kocair, Ç.: Lightweight block ciphers revisited: cryptanalysis of reduced round PRESENT and HIGHT. In: Boyd, C., González Nieto, J. (eds.) ACISP 2009. LNCS, vol. 5594, pp. 90–107. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02620-1_7 CrossRef

27.

Chen, J., Wang, M., Preneel, B.: Impossible differential cryptanalysis of the lightweight block ciphers TEA, XTEA and HIGHT. In: Mitrokotsa, A., Vaudenay, S. (eds.) AFRICACRYPT 2012. LNCS, vol. 7374, pp. 117–137. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31410-0_8 CrossRef

28.

Cui, T., Jia, K., Fu, K., Chen, S., Wang, M.: New automatic search tool for impossible differentials and zero-correlation linear approximations. Cryptology ePrint Archive, Report 2016/689 (2016). http://eprint.iacr.org/2016/689

29.

Koo, B., Hong, D., Kwon, D.: Related-key attack on the full HIGHT. In: Rhee, K.-H., Nyang, D.H. (eds.) ICISC 2010. LNCS, vol. 6829, pp. 49–67. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24209-0_4 CrossRef

30.

Igarashi, Y., Sueyoshi, R., Kaneko, T., Fuchida, T.: Meet-in-the-middle attack with splice-and-cut technique on the 19-round variant of block cipher HIGHT. In: Kim, K.J. (ed.) Information Science and Applications. LNEE, vol. 339, pp. 423–429. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46578-3_50 CrossRef

31.

Gurobi Optimazation, Gurobi optimizer reference manual. http://www.gurobi.com

32.

CPLEX, Ibm software group: User-Manual CPLEX 12, https://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/

33.

Computational Algebra Group, School of Mathematics and Statistics, University of Sydney: Magma Computational Algebra System, http://magma.maths.usyd.edu.au

34.

Sun, S., Hu, L., Wang, M., Wang, P., Qiao, K., Ma, X., Shi, D., Song, L.: Automatic enumeration of (related-key) differential and linear characteristics with predefined properties and its applications. IACR Cryptology ePrint Archive 2014, 747 (2014). http://eprint.iacr.org/2014/747

35.

Wallén, J.: Linear approximations of addition modulo 2ⁿ. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 261–273. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39887-5_20 CrossRef

Titel: Improved Cryptanalysis of an ISO Standard Lightweight Block Cipher with Refined MILP Modelling
verfasst von: Jun Yin
Chuyan Ma
Lijun Lyu
Jian Song
Guang Zeng
Chuangui Ma
Fushan Wei
Verlag: Springer International Publishing
Buch: Information Security and Cryptology
Print ISBN: 978-3-319-75159-7

Electronic ISBN: 978-3-319-75160-3

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-75160-3_24

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner