Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free New method to describe the differential distribution table for large S-boxes in MILP and its application

  • Author(s): Ling-Chen Li 1, 2 ; Wen-Ling Wu 1 ; Lei Zhang 1 ; Ya-Fei Zheng 1
    • View affiliations
  • Source: Volume 13, Issue 5, September 2019, p. 479 – 485
    DOI:  10.1049/iet-ifs.2018.5284 , Print ISSN 1751-8709, Online ISSN 1751-8717
© The Institution of Engineering and Technology
Received 09/06/2018, Accepted 23/01/2019, Revised 05/12/2018, Published 23/01/2019

Based on the method of the H-representation of the convex hull, the linear inequalities of all possible differential patterns of 4-bit S-boxes in the mix integer linear programming (MILP) model can be generated easily by the SAGE software. Whereas this method cannot be apply to 8-bit S-boxes. In this study, the authors propose a new method to obtain the inequalities for large S-boxes with the coefficients belonging to integer. The relationship between the coefficients of the inequalities and the corresponding excluded impossible differential patterns is obtained. As a result, the number of inequalities can be lower than 4000 for the AES S-box. Then, the new method for finding the best probability of the differential characteristics of 4–15 rounds SM4 in the single-key setting is presented. Especially, the authors found that the 15-round SM4 exists four differential characteristics with 12 active S-boxes. The exact lower bound of the number of differentially active S-boxes of the 16-round SM4 is 15. The authors also found eight differential characteristics of the 19-round SM4 with the probability .

Inspec keywords: concave programming; probability; cryptography; linear programming; integer programming

Other keywords: convex hull; SAGE software; linear inequalities; H-representation; MILP; differential patterns; differential distribution table; AES S-box; mix integer linear programming model; differentially active S-boxes

Subjects: Cryptography; Data security; Other topics in statistics; Other topics in statistics; Optimisation techniques; Cryptography theory; Optimisation techniques

References

    1. 1)
      • 14. Xiang, Z., Zhang, W., Bao, Z., et al: ‘Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers’. Proc. Int. Conf. ASIACRYPT, Hanoi, Vietnam, December 2016, pp. 648–678.
    2. 2)
      • 19. Abdelkhalek, A., Sasaki, Y., Todo, Y., et al: ‘MILP modeling for (large) S-boxes to optimize probability of differential characteristics’, IACR Trans. Symmetric Cryptol., 2017, 2017, (4), pp. 99–129.
    3. 3)
      • 7. Mouha, N., Preneel, B.: ‘Towards finding optimal differential characteristics for ARX: application to Salsa20’, Cryptology ePrint Archive, May 2013.
    4. 4)
      • 4. Bahrak, B., Aref, M.R.: ‘Impossible differential attack on seven-round AES-128’, IET Inf. Sec., 2008, 2, (2), pp. 28–32.
    5. 5)
      • 16. 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’. Proc. Int. Conf. ASIACRYPT, Kaoshiung, Taiwan, ROC, December 2014, pp. 158–178.
    6. 6)
      • 9. Sun, S., Gerault, D., Lafourcade, P., et al: ‘Analysis of AES, SKINNY, and others with constraint programming’, Cryptology ePrint Archive, February 2017.
    7. 7)
      • 5. Matsui, M.: ‘On correlation between the order of S-boxes and the strength of DES’. Proc. Int. Conf. EUROCRYPT, Italy, May 1994, pp. 366–375.
    8. 8)
      • 2. Wagner, D: ‘The boomerang attack’. Proc. Int. Conf. FSE, Rome, Italy, March 1999, pp. 156–170.
    9. 9)
      • 17. ‘SAGE’, http://www.sagemath.org/index.html.
    10. 10)
      • 24. Zhang, J., Wu, W., Zheng, Y.: ‘Security of SM4 against (related-key) differential cryptanalysis’. Proc. Int. Conf. ISPEC, Zhangjiajie, China, November 2016, pp. 65–78.
    11. 11)
      • 25. Su, B.Z., Wu, W.L., Zhang, W.T.: ‘Security of the SMS4 block cipher against differential cryptanalysis’. J. Comput. Sci. Technol., 2011, 26, (1), pp. 130–138.
    12. 12)
      • 21. Li, L., Wu, W., Zhang, L.: ‘Improved automatic search tool for Bit-oriented block ciphers and its applications’. Proc. Int. Conf. ICICS, Beijing, China, December 2017, pp. 502–508.
    13. 13)
      • 20. ‘Logic friday’, http://sontrak.com/.
    14. 14)
      • 1. Biham, E., Shamir, A.: ‘Differential cryptanalysis of DES-like cryptosystems’. J. Cryptol., 1991, 4, (1), pp. 3–72.
    15. 15)
      • 18. Sasaki, Y., Todo, Y.: ‘New algorithm for modeling S-box in MILP based differential and division trail search’. Proc. Int. Conf. SecITC, Bucharest, Romania, June 2017, pp. 150–165.
    16. 16)
      • 11. ‘CryptoMiniSat5’, https://www.msoos.org/cryptominisat5.
    17. 17)
      • 22. ‘COCAL’, https://cocalc.com/.
    18. 18)
      • 3. Knudsen, L.R: ‘Truncated and higher order differentials’. Proc. Int. Conf. FSE, Leuven, Belgium, December 1994, pp. 196–211.
    19. 19)
      • 13. Sasaki, Y., Todo, Y.: ‘New impossible differential search tool from design and cryptanalysis aspects’. Proc. Int. Conf. EUROCRYPT, Paris, France, April 2017, pp. 185–215.
    20. 20)
      • 12. ‘Choco’, http://www.choco-solver.org/.
    21. 21)
      • 23. Diffie, W., Ledin, G.: ‘SMS4 encryption algorithm for wireless networks’, IACR Cryptology ePrint Archive, July 2008.
    22. 22)
      • 8. Gĺęrault, D., Lafourcade, P., Minier, M., et al: ‘Revisiting AES related-key differential attacks with constraint programming’, Cryptology ePrint Archive, February 2017.
    23. 23)
      • 10. ‘Gurobi Optimizer 7.5.2’, http://www.gurobi.com.
    24. 24)
      • 15. Cid, C., Huang, T., Peyrin, T., et al: ‘A security analysis of deoxys and its internal tweakable block ciphers’, IACR Trans. Symmetric Cryptol., 2017, 17, (3), pp. 73–107.
    25. 25)
      • 6. Mouha, N., Wang, Q., Gu, D., et al: ‘Differential and linear cryptanalysis using mixed-integer linear programming’. Proc. Int. Conf. Inscrypt, Beijing China, November 2011, pp. 57–76.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2018.5284
Loading

Related content

content/journals/10.1049/iet-ifs.2018.5284
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address