MILP Modeling of Division Property Propagation for Block Ciphers with Complex Linear Layers
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [22]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    As an automatic search tool, mixed integer linear programming (MILP) is widely used to search for differential, linear, integral, and other cryptographic properties of block ciphers. In this study, a new technique of constructing MILP models based on a dynamic selection strategy is proposed, which uses different constraint inequalities to describe the propagation of cryptographic properties under different conditions. Specifically, according to the different Hamming weights of the input division property, this study adopts different methods to construct MILP models of the division property propagation with linear layers. Finally, this technique is applied to search for integral distinguishers of uBlock and Saturnin algorithms. The experimental results show that the proposed technique can obtain an 8-round integral distinguisher with 32 more balance bits than the previous optimal integral distinguisher for the uBlock128 algorithm. In addition, this study gets 9- and 10-round integral distinguishers for uBlock128 and uBlock256 algorithms which are one round longer than the previous optimal integral distinguishers. For the Saturnin256 algorithm, the study finds a 9-round integral distinguisher which is one round longer than the previous optimal integral distinguisher.

    Reference
    [1] Knudsen L, Wagner D. Integral cryptanalysis. In:Proc. of the 9th Int'l Workshop on Fast Software Encryption. Leuven:Springer, 2002. 112-127.
    [2] Todo Y. Structural evaluation by generalized integral property. In:Proc. of the 34th Annual Int'l Conf. on the Theory and Applications of Cryptographic Techniques. Sofia:Springer, 2015. 287-314.
    [3] Todo Y. Integral cryptanalysis on full MISTY1. In:Proc. of the 35th Annual Cryptology Conf. Santa Barbara:Springer, 2015. 413-432.
    [4] Sun B, Hai X, Zhang WY, Cheng L, Yang ZC. New observation on division property. Science China Information Sciences, 2017, 60(9):098102.[doi:10.1007/s11432-015-0376-x]
    [5] Todo Y, Morii M. Bit-based division property and application to SIMON family. In:Proc. of the 23rd Int'l Conf. on Fast Software Encryption. Bochum:Springer, 2016. 357-377.
    [6] Mouha N, Wang QJ, Gu DW, Preneel B. Differential and linear cryptanalysis using mixed-integer linear programming. In:Proc. of the 7th Int'l Conf. on Information Security and Cryptology. Beijing:Springer, 2012. 57-76.
    [7] Sun SW, Hu L, Wang P, Qiao KX, Ma XS, 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:Proc. of the 20th Int'l Conf. on the Theory and Application of Cryptology and Information Security. Springer, 2014. 158-178.
    [8] Xiang ZJ, Zhang WT, Bao ZZ, Lin DD. Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers. In:Proc. of the 22nd Int'l Conf. on the Theory and Application of Cryptology and Information Security. Hanoi:Springer, 2016. 648-678.
    [9] Sun L, Wang W, Wang MQ. MILP-aided bit-based division property for primitives with non-bit-permutation linear layers. IET Information Security, 2020, 14(1):12-20.[doi:10.1049/iet-ifs.2018.5283]
    [10] Zhang WY, Rijmen V. Division cryptanalysis of block ciphers with a binary diffusion layer. IET Information Security, 2019, 13(2):87-95.[doi:10.1049/iet-ifs.2018.5151]
    [11] ElSheikh M, Youssef AM. On MILP-based automatic search for bit-based division property for ciphers with (large) linear layers. In:Proc. of the 26th Australasian Conf. on Information Security and Privacy. Cham:Springer, 2021. 111-131.
    [12] Hong CL, Zhang SS, Chen SW, Lin D, Xiang ZJ. More accurate division property propagations based on optimized implementations of linear layers. In:Proc. of the 17th Int'l Conf. on Information Security and Cryptology. Cham:Springer, 2021. 212-232.
    [13] Hu K, Wang QJ, Wang MQ. Finding bit-based division property for ciphers with complex linear layers. IACR Transactions on Symmetric Cryptology, 2020, 2020(1):396-424.[doi:10.13154/tosc.v2020.i1.396-424]
    [14] 吴文玲, 张蕾, 郑雅菲, 李灵琛. 分组密码uBlock. 密码学报. 2019, 6(6):690-703.
    Wu WL, Zhang L, Zheng YF, Li LC. The block cipher uBlock. Journal of Cryptologic Research, 2019, 6(6):690-703 (in Chinese with English abstract).
    [15] Tian WQ, Hu B. Integral cryptanalysis on two block ciphers Pyjamask and uBlock. IET Information Security, 2020, 14(5):572-579.[doi:10.1049/iet-ifs.2019.0624]
    [16] Canteaut A, Duval S, Leurent G, Naya-Plasencia M, Perrin L, Pornin T, Schrottenloher A. Saturnin:A suite of lightweight symmetric algorithms for post-quantum security. IACR Transactions on Symmetric Cryptology, 2020, 2020(S1):160-207.[doi:10.13154/tosc.v2020.iS1.160-207]
    [17] Gurobi Optimization, LLC. Gurobi optimizer reference manual. 2022. https://www.gurobi.com
    [18] Paar C. Optimized arithmetic for Reed-Solomon encoders. In:Proc. of the 1997 IEEE Int'l Symp. on Information Theory. Ulm:IEEE, 1997. 250.
    [19] Boyar J, Matthews P, Peralta R. Logic minimization techniques with applications to cryptology. Journal of Cryptology, 2013, 26(2):280-312.[doi:10.1007/s00145-012-9124-7]
    [20] Xiang ZJ, Zeng XY, Lin D, Bao ZZ, Zhang SS. Optimizing implementations of linear layers. IACR Transactions on Symmetric Cryptology, 2020, 2020(2):120-145.[doi:10.13154/tosc.v2020.i2.120-145]
    [21] Abdelkhalek A, Sasaki Y, Todo Y, Tolba M, Youssef AM. MILP modeling for (large) s-boxes to optimize probability of differential characteristics. IACR Transactions on Symmetric Cryptology, 2017, 2017(4):99-129.[doi:10.13154/tosc.v2017.i4.99-129]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

黄明,张莎莎,洪春雷,曾乐,向泽军.分组密码复杂线性层可分性传播的MILP刻画方法.软件学报,2024,35(4):1980-1992

Copy
Share
Article Metrics
  • Abstract:566
  • PDF: 1829
  • HTML: 859
  • Cited by: 0
History
  • Received:August 26,2022
  • Revised:October 15,2022
  • Online: July 28,2023
  • Published: April 06,2024
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063