Your browser does not support JavaScript!

access icon free MILP-based automatic differential search for LEA and HIGHT block ciphers

The authors use the mixed-integer linear programming (MILP) technique for the automatic search for differential characteristics of LEA and HIGHT ciphers. They show that the MILP model of the differential property of modular addition with one constant input can be represented with a much lesser number of linear inequalities compared to the general case. Benefiting from this model for HIGHT block cipher, they can achieve a reduction of 112r out of 480r in the total number of linear constraints for the MILP model of r-round of HIGHT. This saving accelerates the searching process of HIGHT about twice as fast. They enjoy the MILP model to investigate the differential effect of these ciphers and provide a more accurate estimation for the differential probability. Their observations show that despite HIGHT, LEA exhibits a strong differential effect. The results gained by this method improve/extend the previous results as follows. For LEA block cipher, they found more efficient 12- and 13-round differentials whose probabilities are better than the best previous 12- and 13-round differentials for a factor of about 26 and 27, respectively. In the case of HIGHT block cipher, they found new 12- and 13-round differentials, though with the same best-reported probabilities.


    1. 1)
      • 31. Winnen, L.: Sage S-box MILP toolkit.
    2. 2)
      • 36. Wen, L., Wang, M., Bogdanov, A., et al: ‘Multidimensional zero-correlation attacks on lightweight block cipher HIGHT: improved cryptanalysis of an ISO standard’, Inf. Process. Lett., 2014, 114, (6), pp. 322330.
    3. 3)
      • 23. Sun, S., Hu, L., Song, L., et al: ‘Automatic security evaluation of block ciphers with S-bP structures against related-key differential attacks’. Int. Conf. on Information Security and Cryptology, Guangzhou, People's Republic of China, November 2013, pp. 3951.
    4. 4)
      • 17. Fu, K., Wang, M., Guo, Y., et al: ‘MILP-based automatic search algorithms for differential and linear trails for speck’. Int. Conf. on Fast Software Encryption, Bochum, Germany, March 2016, pp. 268288.
    5. 5)
      • 30. Song, L., Huang, Z., Yang, Q.: ‘Automatic differential analysis of ARX block ciphers with application to SPECK and LEA’. Australasian Conf. on Information Security and Privacy, Melbourne, VIC, Australia, July 2016, pp. 379394.
    6. 6)
      • 19. Mouha, N., Wang, Q., Gu, D., et al: ‘Differential and linear cryptanalysis using mixed-integer linear programming’. Int. Conf. on Information Security and Cryptology, Beijing, People's Republic of China, November 2011, pp. 5776.
    7. 7)
      • 14. Mouha, N., Preneel, B.: ‘Towards finding optimal differential characteristics for ARX: Application to Salsa20’, Cryptology ePrint Archive, Report 2013/328, 2013.
    8. 8)
      • 28. Lipmaa, H., Moriai, S.: ‘Efficient algorithms for computing differential properties of addition’. Int. Workshop on Fast Software Encryption, Yokohama, Japan, April 2001, pp. 336350.
    9. 9)
      • 25. Xiang, Z., Zhang, W., Bao, Z., et al: ‘Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers’. Int. Conf. on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 2016, pp. 648678.
    10. 10)
      • 7. Bernstein, D.J.: ‘ChaCha, a variant of Salsa20’. Workshop Record of SASC, Lausanne, Switzerland, January 2008, Vol. 8, pp. 35.
    11. 11)
      • 5. Aumasson, J.P., Bernstein, D.J.: ‘SipHash: a fast short-input PRF’. Int. Conf. on Cryptology in India, Kolkata, India, December 2012, pp. 489508.
    12. 12)
      • 20. Wu, S., Wang, M.: ‘Security evaluation against differential cryptanalysis for block cipher structures’. IACR Cryptology ePrint Archive, 2011, p. 551.
    13. 13)
      • 39. Azimi, S.A., Ahmadi, S., Ahmadian, Z., et al: ‘Improved impossible differential and biclique cryptanalysis of HIGHT’, Int. J. Commun. Syst., 2018, 31, (1), p. e3382.
    14. 14)
      • 38. Ahmadi, S., Ahmadian, Z., Mohajeri, J., et al: ‘Low data complexity biclique cryptanalysis of block ciphers with application to piccolo and HIGHT’, IEEE Trans. Inf. Forensics Secur., 2014, 9, (10), pp. 16411652.
    15. 15)
      • 21. Sun, S., Hu, L., Wang, P., et al: ‘Automatic security evaluation and (related-key) differential characteristic search: application to SIMON, PRESENT, LBlock, DES (L) and other bit-oriented block ciphers’. Int. Conf. on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 2014, pp. 158178.
    16. 16)
      • 34. Dwivedi, A.D., Srivastava, G.: ‘Differential Cryptanalysis in ARX Ciphers, Applications to LEA’. Cryptology ePrint Archive, Report 2018/898..
    17. 17)
      • 24. Sasaki, Y., Todo, Y.: ‘Tight bounds of differentially and linearly active S-boxes and division property of Lilliput’, IEEE Trans. Comput., 2018, 67, (5), pp. 717732.
    18. 18)
      • 16. Kölbl, S., Leander, G., Tiessen, T.: ‘Observations on the SIMON block cipher family’. Annual Cryptology Conf., Santa Barbara, CA, USA., August 2015, pp. 161185.
    19. 19)
      • 15. Aumasson, J.P., Jovanovic, P., Neves, S.: ‘Analysis of NORX: investigating differential and rotational properties’. Int. Conf. on Cryptology and Information Security in Latin America, Florianópolis, Brazil, September 2014, pp. 306324.
    20. 20)
      • 12. Matsui, M.: ‘On correlation between the order of S-boxes and the strength of DES’. Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, May 1994, pp. 366375.
    21. 21)
      • 1. Aumasson, J.P., Henzen, L., Meier, W., et al: ‘SHA-3 proposal blake’, Submission to NIST, 2008.
    22. 22)
      • 6. Mouha, N., Mennink, B., Van Herrewege, A., et al: ‘Chaskey: an efficient MAC algorithm for 32-bit microcontrollers’. Int. Workshop on Selected Areas in Cryptography, Montreal, QC, Canada, August 2014, pp. 306323.
    23. 23)
      • 35. Zhang, P., Sun, B., Li, C.: ‘Saturation attack on the block cipher HIGHT’. Int. Conf. on Cryptology and Network Security, Kanazawa, Japan, December 2009, pp. 7686.
    24. 24)
      • 22. Sun, S., Hu, L., Wang, M., 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, Report, 2014, 747, p. 2014.
    25. 25)
      • 10. Rivest, R.L.: ‘The RC5 encryption algorithm’. Int. Workshop on Fast Software Encryption, Leuven, Belgium, December 1994, pp. 8696.
    26. 26)
      • 33. Sun, L., Wang, W., Wang, M.: ‘Automatic search of bit-based division property for ARX ciphers and word-based division property’. Int. Conf. on the Theory and Application of Cryptology and Information Security, Hong Kong, People's Republic of China, December 2017, pp. 128157.
    27. 27)
      • 27. Wu, S., Wu, H., Huang, T., et al: ‘Leaked-state-forgery attack against the authenticated encryption algorithm ALE’. Int. Conf. on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 2013, pp. 377404.
    28. 28)
      • 37. Chen, J., Wang, M., Preneel, B.: ‘Impossible differential cryptanalysis of the lightweight block ciphers TEA, XTEA and HIGHT’. Int. Conf. on Cryptology in Africa, Ifrance, Morocco, July 2012, pp. 117137.
    29. 29)
      • 2. Ferguson, N., Lucks, S., Schneier, B., et al: ‘The skein hash function family’. Submission to NIST (round 3), 2010, 7, (7.5), p. 3.
    30. 30)
      • 8. Wu, H.: ‘The stream cipher HC-128’ in Robshaw, M., Billet, O. (Eds.): ‘New stream cipher designs’ (Springer, Berlin, Heidelberg, 2008), pp. 3947.
    31. 31)
      • 13. Biryukov, A., Nikolić, I.: ‘Search for related-key differential characteristics in DES-like ciphers’. Int. Workshop on Fast Software Encryption, Lyngby, Denmark, February 2011, pp. 1834.
    32. 32)
      • 18. Cui, T., Jia, K., Fu, K., et al: ‘New automatic search tool for impossible differentials and zero-correlation linear approximations’. IACR Cryptology ePrint Archive, 2016, 2016, p. 689.
    33. 33)
      • 11. Hong, D., Sung, J., Hong, S., et al: ‘HIGHT: a new block cipher suitable for low-resource device’. Int. Workshop on Cryptographic Hardware and Embedded Systems, Yokohama, Japan, October 2006, pp. 4659.
    34. 34)
      • 3. Bernstein, D.J.: ‘The Salsa20 family of stream ciphers’, in ‘New stream cipher designs’ (Springer, Berlin, Heidelberg, 2008), pp. 8497.
    35. 35)
      • 32. Lai, X., Massey, J.L., Murphy, S.: ‘Markov ciphers and differential cryptanalysis’. Workshop on the Theory and Application of Cryptographic Techniques, Brighton, UK., April 1991, pp. 1738.
    36. 36)
      • 9. Hong, D., Lee, J.K., Kim, D.C., et al: ‘LEA: A 128-bit block cipher for fast encryption on common processors’. Int. Workshop on Information Security Applications, Jeju Island, Republic of Korea, August 2013, pp. 327.
    37. 37)
      • 26. Gleixner, A., Eifler, L., Gally, T., et al: ‘The SCIP optimization suite 5.0’, 2017.
    38. 38)
      • 4. Beaulieu, R., Treatman-Clark, S., Shors, D., et al: ‘The SIMON and SPECK lightweight block ciphers’. 2015 52nd ACM/EDAC/IEEE Design Automation Conf. (DAC), San Francisco, CA, USA., June 2015, pp. 16.
    39. 39)
      • 29. Yin, J., Ma, C., Lyu, L., et al: ‘Improved cryptanalysis of an ISO standard lightweight block cipher with refined MILP modelling’. Int. Conf. on Information Security and Cryptology, Xi'an, China, November 2017, pp. 404426.

Related content

This is a required field
Please enter a valid email address