MILPbased automatic differential search for LEA and HIGHT block ciphers
 Author(s): Elnaz Bagherzadeh^{ 1} and Zahra Ahmadian^{ 1}


View affiliations

Affiliations:
1:
Department of Electrical Engineering , Shahid Beheshti University , Tehran , Iran

Affiliations:
1:
Department of Electrical Engineering , Shahid Beheshti University , Tehran , Iran
 Source:
Volume 14, Issue 5,
September
2020,
p.
595 – 603
DOI: 10.1049/ietifs.2018.5539 , Print ISSN 17518709, Online ISSN 17518717
The authors use the mixedinteger 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 rround 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 13round differentials whose probabilities are better than the best previous 12 and 13round differentials for a factor of about 2^{6} and 2^{7}, respectively. In the case of HIGHT block cipher, they found new 12 and 13round differentials, though with the same bestreported probabilities.
Inspec keywords: probability; linear programming; mixing; polynomials; integer programming; cryptography; differentiation
Other keywords: newly developed model; linear inequalities; differential property; 13round differentials; mixedinteger linear programming technique; HIGHT ARX ciphers; linear constraints; HIGHT block cipher; LEA block cipher; automatic search; differential probability; MILPbased automatic differential search; strong differential effect; MILP model; searching process; differential characteristics
Subjects: Cryptography; Optimisation techniques; Other topics in statistics; Combinatorial mathematics; Combinatorial mathematics; Optimisation techniques; Other topics in statistics; Data security
References


1)

31. Winnen, L.: Sage Sbox MILP toolkit.


2)

36. Wen, L., Wang, M., Bogdanov, A., et al: ‘Multidimensional zerocorrelation attacks on lightweight block cipher HIGHT: improved cryptanalysis of an ISO standard’, Inf. Process. Lett., 2014, 114, (6), pp. 322–330.


3)

23. Sun, S., Hu, L., Song, L., et al: ‘Automatic security evaluation of block ciphers with SbP structures against relatedkey differential attacks’. Int. Conf. on Information Security and Cryptology, Guangzhou, People's Republic of China, November 2013, pp. 39–51.


4)

17. Fu, K., Wang, M., Guo, Y., et al: ‘MILPbased automatic search algorithms for differential and linear trails for speck’. Int. Conf. on Fast Software Encryption, Bochum, Germany, March 2016, pp. 268–288.


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. 379–394.


6)

19. Mouha, N., Wang, Q., Gu, D., et al: ‘Differential and linear cryptanalysis using mixedinteger linear programming’. Int. Conf. on Information Security and Cryptology, Beijing, People's Republic of China, November 2011, pp. 57–76.


7)

14. Mouha, N., Preneel, B.: ‘Towards finding optimal differential characteristics for ARX: Application to Salsa20’, Cryptology ePrint Archive, Report 2013/328, 2013.


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. 336–350.


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. 648–678.


10)

7. Bernstein, D.J.: ‘ChaCha, a variant of Salsa20’. Workshop Record of SASC, Lausanne, Switzerland, January 2008, Vol. 8, pp. 3–5.


11)

5. Aumasson, J.P., Bernstein, D.J.: ‘SipHash: a fast shortinput PRF’. Int. Conf. on Cryptology in India, Kolkata, India, December 2012, pp. 489–508.


12)

20. Wu, S., Wang, M.: ‘Security evaluation against differential cryptanalysis for block cipher structures’. IACR Cryptology ePrint Archive, 2011, p. 551.


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)

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. 1641–1652.


15)

21. Sun, S., Hu, L., Wang, P., et al: ‘Automatic security evaluation and (relatedkey) differential characteristic search: application to SIMON, PRESENT, LBlock, DES (L) and other bitoriented block ciphers’. Int. Conf. on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 2014, pp. 158–178.


16)

34. Dwivedi, A.D., Srivastava, G.: ‘Differential Cryptanalysis in ARX Ciphers, Applications to LEA’. Cryptology ePrint Archive, Report 2018/898..


17)

24. Sasaki, Y., Todo, Y.: ‘Tight bounds of differentially and linearly active Sboxes and division property of Lilliput’, IEEE Trans. Comput., 2018, 67, (5), pp. 717–732.


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. 161–185.


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. 306–324.


20)

12. Matsui, M.: ‘On correlation between the order of Sboxes and the strength of DES’. Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, May 1994, pp. 366–375.


21)

1. Aumasson, J.P., Henzen, L., Meier, W., et al: ‘SHA3 proposal blake’, Submission to NIST, 2008.


22)

6. Mouha, N., Mennink, B., Van Herrewege, A., et al: ‘Chaskey: an efficient MAC algorithm for 32bit microcontrollers’. Int. Workshop on Selected Areas in Cryptography, Montreal, QC, Canada, August 2014, pp. 306–323.


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. 76–86.


24)

22. Sun, S., Hu, L., Wang, M., et al: ‘Towards finding the best characteristics of some bitoriented block ciphers and automatic enumeration of (relatedkey) differential and linear characteristics with predefined properties’. Cryptology ePrint Archive, Report, 2014, 747, p. 2014.


25)

10. Rivest, R.L.: ‘The RC5 encryption algorithm’. Int. Workshop on Fast Software Encryption, Leuven, Belgium, December 1994, pp. 86–96.


26)

33. Sun, L., Wang, W., Wang, M.: ‘Automatic search of bitbased division property for ARX ciphers and wordbased division property’. Int. Conf. on the Theory and Application of Cryptology and Information Security, Hong Kong, People's Republic of China, December 2017, pp. 128–157.


27)

27. Wu, S., Wu, H., Huang, T., et al: ‘Leakedstateforgery attack against the authenticated encryption algorithm ALE’. Int. Conf. on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 2013, pp. 377–404.


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. 117–137.


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)

8. Wu, H.: ‘The stream cipher HC128’ in Robshaw, M., Billet, O. (Eds.): ‘New stream cipher designs’ (Springer, Berlin, Heidelberg, 2008), pp. 39–47.


31)

13. Biryukov, A., Nikolić, I.: ‘Search for relatedkey differential characteristics in DESlike ciphers’. Int. Workshop on Fast Software Encryption, Lyngby, Denmark, February 2011, pp. 18–34.


32)

18. Cui, T., Jia, K., Fu, K., et al: ‘New automatic search tool for impossible differentials and zerocorrelation linear approximations’. IACR Cryptology ePrint Archive, 2016, 2016, p. 689.


33)

11. Hong, D., Sung, J., Hong, S., et al: ‘HIGHT: a new block cipher suitable for lowresource device’. Int. Workshop on Cryptographic Hardware and Embedded Systems, Yokohama, Japan, October 2006, pp. 46–59.


34)

3. Bernstein, D.J.: ‘The Salsa20 family of stream ciphers’, in ‘New stream cipher designs’ (Springer, Berlin, Heidelberg, 2008), pp. 84–97.


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. 17–38.


36)

9. Hong, D., Lee, J.K., Kim, D.C., et al: ‘LEA: A 128bit block cipher for fast encryption on common processors’. Int. Workshop on Information Security Applications, Jeju Island, Republic of Korea, August 2013, pp. 3–27.


37)

26. Gleixner, A., Eifler, L., Gally, T., et al: ‘The SCIP optimization suite 5.0’, 2017.


38)

4. Beaulieu, R., TreatmanClark, 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. 1–6.


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. 404–426.


1)