高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于混合整数线性规划的八阵图不可能差分分析

杜小妮 梁丽芳 贾美纯 李锴彬

杜小妮, 梁丽芳, 贾美纯, 李锴彬. 基于混合整数线性规划的八阵图不可能差分分析[J]. 电子与信息学报, 2023, 45(12): 4391-4398. doi: 10.11999/JEIT221292
引用本文: 杜小妮, 梁丽芳, 贾美纯, 李锴彬. 基于混合整数线性规划的八阵图不可能差分分析[J]. 电子与信息学报, 2023, 45(12): 4391-4398. doi: 10.11999/JEIT221292
DU Xiaoni, LIANG Lifang, JIA Meichun, LI Kaibin. Impossible Differential Cryptanalysis of Eight-Sided Fortress Based on Mixed Integer Linear Programming[J]. Journal of Electronics & Information Technology, 2023, 45(12): 4391-4398. doi: 10.11999/JEIT221292
Citation: DU Xiaoni, LIANG Lifang, JIA Meichun, LI Kaibin. Impossible Differential Cryptanalysis of Eight-Sided Fortress Based on Mixed Integer Linear Programming[J]. Journal of Electronics & Information Technology, 2023, 45(12): 4391-4398. doi: 10.11999/JEIT221292

基于混合整数线性规划的八阵图不可能差分分析

doi: 10.11999/JEIT221292
基金项目: 国家自然科学基金(62172337),甘肃省自然科学基金重点项目(23JRRA685),甘肃省基础研究创新群体项目(23JRRA684)
详细信息
    作者简介:

    杜小妮:女,博士,教授,研究方向为应用密码学

    梁丽芳:女,硕士生,研究方向为应用密码学

    贾美纯:女,硕士生,研究方向为应用密码学

    李锴彬:男,硕士生,研究方向为分组密码

    通讯作者:

    梁丽芳 llf_1003@163.com

  • 中图分类号: TN918; TP309.7

Impossible Differential Cryptanalysis of Eight-Sided Fortress Based on Mixed Integer Linear Programming

Funds: The National Natural Science Foundation of China (62172337), The Key Project of Gansu Natural Science Foundation (23JRRA685), The Funds for Innovative Fundamental Research Group Project of Gansu Province (23JRRA684)
  • 摘要: 八阵图(ESF)是基于LBlock改进的轻量级分组密码,具有优良的软硬件实现效率。针对ESF算法的安全性,该文借助自动化搜索工具,利用不可能差分分析方法,对算法进行安全性评估。首先结合ESF的结构特性和$ S $盒的差分传播特性,建立了基于混合整数线性规划(MILP)的不可能差分搜索模型;其次利用算法 $ S $盒的差分传播特性和密钥扩展算法中轮子密钥间的相互关系,基于一条9轮不可能差分区分器,通过向前扩展2轮向后扩展4轮,实现了对ESF算法的15轮密钥恢复攻击。分析结果表明,该攻击的数据复杂度和时间复杂度分别为$ {2^{60.16}} $和 $ {2^{67.44}} $,均得到有效降低,且足够抵抗不可能差分分析。
  • 图  1  ESF 算法结构

    图  2  ESF 算法轮函数

    图  3  ESF的15轮不可能差分攻击

    表  1  ESF的S

    $ \boldsymbol{x} $
    0123456789abcdef
    $ {S_0} $38f1a65bed42709c
    $ {S_1} $fc27905a1be86d34
    $ {S_2} $86793cafd1e40b52
    $ {S_3} $0fb8c963d124a75e
    $ {S_4} $1f83c0b6254a9e7d
    $ {S_5} $f52b4a9c03e8d671
    $ {S_6} $72c5846be91fd3a0
    $ {S_7} $1df0e82b74ca9356
    下载: 导出CSV

    表  2  ESF 的S0盒差分分布表

    0123456789abcdef
    016000000000000000
    10002022200022040
    20000000002204224
    30222000204022000
    40000000004400440
    50020420020220020
    60224022400000000
    70020420022020200
    80002022200022400
    90220022002200220
    a0222000200422000
    b0220022000004004
    c0200402022020200
    d0004000440000004
    e0200402020220020
    f0220022040000004
    下载: 导出CSV

    表  3  ESF的S盒差分传播特性

    $ {S_0} $$ {S_1} $$ {S_2} $$ {S_4} $$ {S_5} $$ {S_6} $
    $ \alpha $$ \beta $$ \alpha $$ \beta $$ \alpha $$ \beta $$ \alpha $$ \beta $$ \alpha $$ \beta $$ \alpha $$ \beta $
    0010$ 1 * * * $0100$ * 1 * * $0010$ * * * 1 $0100$ * * * 1 $0100$ * * * 1 $0010$ * * 1 * $
    0100$ 1 * * * $1000$ * 1 * * $1000$ * * * 1 $1011$ * * * 1 $1011$ * * * 1 $0100$ * * 1 * $
    0110$ 0 * * * $1100$ * 0 * * $1010$ * * * 0 $1111$ * * * 0 $1111$ * * * 0 $0110$ * * 0 * $
    下载: 导出CSV

    表  4  ESF的S盒差分概率传播特性

    $ S $$ {S_0} $$ {S_6} $
    $ \alpha $$ 1000 $$ 0001 $
    $ \beta $$ * * * * $$ * * * * $
    $ P $$\dfrac{1}{8}$$\dfrac{1}{8}$
    下载: 导出CSV
    算法1 搜索 ESF 算法加密方向的有效差分路径
     输入: 64 bit的明文输入差分$ \Delta X $,
     输出:加密后的输出差分集合$ {\text{List}}{\text{.}} $
     1. $ {\text{set}} = \{ \Delta X\} $;
     2. 如果$ {\text{set}} $中包含部分比特已知的差分;
     3. for $ \Delta X $ in $ {\text{set}} $
     2.  $ {\text{List}}{\text{.append(}}\Delta X{\text{)}} $;
     4.  $ \Delta {x_0} - \Delta {x_1} - \Delta {x_2} + \Delta {x_3} - \Delta {y_0} + 2 \ge 0 $; #当$ {\alpha _0} = 0110, $ $ {\beta _0} = 0 * * * * $时的不等式约束,对于其他$ S $盒有类似性质
     5. $\Delta {r_1}{\text{ + } }\Delta { {\text{k} }_1} + \Delta {m_1} - 2d \ge 0,{{ d} } \ge \varDelta {r_1},{{ d} } \ge \varDelta { {\text{k} }_1},{{ d} } \ge \varDelta {m_1},{\text{ } }\varDelta {r_1}{\text{ + } }\varDelta { {\text{k} }_1} + \varDelta {m_1} \le 2$; #异或的约束条件
     6.  $\displaystyle\sum\limits_{i = 0}^3 {\Delta {x_i} - 4A \le 0,} {\text{ } }\displaystyle\sum\limits_{i = 0}^3 {\Delta {x_i} - A \ge 0,} {\text{ 4} }\displaystyle\sum\limits_{i = 0}^3 {\Delta {y_i} - \displaystyle\sum\limits_{i = 0}^3 {\Delta {x_i} \ge 0,} {\text{ } } } {\text{ 4} }\displaystyle\sum\limits_{i = 0}^3 {\Delta {x_i} - \displaystyle\sum\limits_{i = 0}^3 {\Delta {y_i} \ge 0} {\text{ } } }$; #$ S $盒约束条件
     7.  $ S $盒差分传播特性得到的213个不等式约束条件;
     8.  利用GUROBI求解MILP模型,判断是否存在可行解;
     9.  若存在可行解,则输出$ {\text{set}}{\text{.append}} $(满足上述条件的输出差分$ \Delta Y $);
     10. ${\text{set = set } }-\left( {\Delta X} \right)$,重复执行上述步骤1-步骤9,直到$ {\text{set}} $全为未知的比特;
     11. return List.
    下载: 导出CSV
    算法2 寻找最长不可能差分区分器轮数
     输入: 加密后的差分路径集合$ {\text{E}}{\text{.List}} $, 解密后的差分路径集合
         $ {\text{D}}{\text{.List}} $
     输出:输出最长不可能差分区分器轮数
     1. $ r = 0 $;
     2. for $ i $ in range len($ {\text{E}}{\text{.List}} $)
     3.  for $ j $ in range len($ {\text{D}}{\text{.List}} $)
     4.   if ${\text{E} }{{.{\rm{List}}[i]} } \ne {\text{D} }{{.{\rm{List}}[j]} }$;
     5.    if $ r > i + j $
     6.     $ r = r $;
     7.    else
     8.     $ r = i + j $;
     9. return $ r. $
    下载: 导出CSV

    表  5  ESF 分析方法结果对比

    攻击轮数分析方法时间复杂度数据复杂度文献
    11不可能差分分析$ {2^{75.5}} $$ {2^{59}} $文献[10]
    11不可能差分分析$ {2^{32}} $$ {2^{53}} $文献[11]
    12不可能差分分析$ {2^{60.45}} $$ {2^{53}} $文献[12]
    13截断不可能差分分析$ {2^{61.99}} $$ {2^{77.39}} $文献[14]
    14相关密钥不可能差分分析$ {2^{43.95}} $$ {2^{62}} $文献[13]
    15不可能差分分析$ {2^{70.02}} $$ {2^{64.3}} $文献[16]
    15不可能差分分析$ {2^{67.44}} $$ {2^{60.16}} $本文
    下载: 导出CSV
  • [1] BOGDANOV A, KNUDSEN L R, LEANDER G, et al. PRESENT: An ultra-lightweight block cipher[C]. Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems-CHES 2007, Vienna, Austria, 2007: 450–466.
    [2] WU Wenling and ZHANG Lei. LBlock: A lightweight block cipher[C]. Proceedings of the 9th International Conference on Applied Cryptography and Network Security, Nerja, Spain, 2011: 327–344.
    [3] BANIK S, BAO Zhenzhen, ISOBE T, et al. WARP: Revisiting GFN for lightweight 128-bit block cipher[C]. Proceedings of the 27th International Conference on Selected Areas in Cryptography, Halifax, Canada, 2021: 535–564.
    [4] 曹梅春, 张文英, 陈彦琴, 等. RAIN: 一种面向软硬件和门限实现的轻量分组密码算法[J]. 计算机研究与发展, 2021, 58(5): 1045–1055. doi: 10.7544/issn1000-1239.2021.20200933

    CAO Meichun, ZHANG Wenying, CHEN Yanqin, et al. RAIN: A lightweight block cipher towards software, hardware and threshold implementations[J]. Journal of Computer Research and Development, 2021, 58(5): 1045–1055. doi: 10.7544/issn1000-1239.2021.20200933
    [5] DAS A K, KAR N, DEB S, et al. bFLEX-γ: A lightweight block cipher utilizing key cross approach via probability density function[J]. Arabian Journal for Science and Engineering, 2022, 47(8): 10563–10578. doi: 10.1007/s13369-022-06651-6
    [6] LIU Xuan, ZHANG Wenying, LIU Xiangzhong, et al. Eight-sided fortress: A lightweight block cipher[J]. The Journal of China Universities of Posts and Telecommunications, 2014, 21(1): 104–108,128. doi: 10.1016/S1005-8885(14)60275-2
    [7] 吴文玲, 张蕾. 不可能差分密码分析研究进展[J]. 系统科学与数学, 2008, 28(8): 971–983. doi: 10.12341/jssms10197

    WU Wenling and ZHANG Lei. The state-of-the-art of research on impossible differential cryptanalysis[J]. Journal of Systems Science and Mathematical Sciences, 2008, 28(8): 971–983. doi: 10.12341/jssms10197
    [8] 韦永壮, 史佳利, 李灵琛. LiCi分组密码算法的不可能差分分析[J]. 电子与信息学报, 2019, 41(7): 1610–1617. doi: 10.11999/JEIT180729

    WEI Yongzhuang, SHI Jiali, and LI Lingchen. Impossible differential cryptanalysis of LiCi block cipher[J]. Journal of Electronics &Information Technology, 2019, 41(7): 1610–1617. doi: 10.11999/JEIT180729
    [9] 任炯炯, 侯泽洲, 李曼曼, 等. 改进的减轮MIBS-80密码的中间相遇攻击[J]. 电子与信息学报, 2022, 44(8): 2914–2923. doi: 10.11999/JEIT210441

    REN Jiongjiong, HOU Zezhou, LI Manman, et al. Improved meet-in-the-middle attacks on reduced-round MIBS-80 Cipher[J]. Journal of Electronics &Information Technology, 2022, 44(8): 2914–2923. doi: 10.11999/JEIT210441
    [10] 刘宣, 刘枫, 孟帅. 轻量级分组密码算法ESF的不可能差分分析[J]. 计算机工程与科学, 2013, 35(9): 89–93. doi: 10.3969/j.issn.1007-130X.2013.09.014

    LIU Xuan, LIU Feng, and MENG Shuai. Impossible differential cryptanalysis of lightweight block cipher ESF[J]. Computer Engineering &Science, 2013, 35(9): 89–93. doi: 10.3969/j.issn.1007-130X.2013.09.014
    [11] 陈玉磊, 卫宏儒. ESF算法的不可能差分密码分析[J]. 计算机科学, 2016, 43(8): 89–91,99. doi: 10.11896/j.issn.1002-137X.2016.08.018

    CHEN Yulei and WEI Hongru. Impossible differential cryptanalysis of ESF[J]. Computer Science, 2016, 43(8): 89–91,99. doi: 10.11896/j.issn.1002-137X.2016.08.018
    [12] 高红杰, 卫宏儒. 用不可能差分法分析12轮ESF算法[J]. 计算机科学, 2017, 44(10): 147–149,181. doi: 10.11896/j.issn.1002-137X.2017.10.028

    GAO Hongjie and WEI Hongru. Impossible differential attack on 12-round block cipher ESF[J]. Computer Science, 2017, 44(10): 147–149,181. doi: 10.11896/j.issn.1002-137X.2017.10.028
    [13] 谢敏, 杨盼. ESF算法的相关密钥不可能差分分析[J]. 计算机工程与科学, 2018, 40(7): 1199–1205. doi: 10.3969/j.issn.1007-130X.2018.07.008

    XIE Min and YANG Pan. Related-key impossible differential cryptanalysis on ESF[J]. Computer Engineering &Science, 2018, 40(7): 1199–1205. doi: 10.3969/j.issn.1007-130X.2018.07.008
    [14] 李明明, 郭建胜, 崔竞一, 等. ESF算法的截断不可能差分分析[J]. 密码学报, 2019, 6(5): 585–593. doi: 10.13868/j.cnki.jcr.000324

    LI Mingming, GUO Jiansheng, CUI Jingyi, et al. Truncated impossible difference cryptanalysis of ESF[J]. Journal of Cryptologic Research, 2019, 6(5): 585–593. doi: 10.13868/j.cnki.jcr.000324
    [15] LI Jun, WANG Hongyan, QIU Xueying, et al. Integral analysis of GRANULE and ESF block ciphers based on MILP[C]. Proceedings of 2021 12th International Conference on Information and Communication Systems (ICICS), Valencia, Spain, 2021: 10–16.
    [16] WU Xiaonian, YAN Jiaxu, LI Lingchen, et al. Impossible differential cryptanalysis on ESF algorithm with simplified MILP model[J]. KSII Transactions on Internet and Information Systems, 2021, 15(10): 3815–3833. doi: 10.3837/tiis.2021.10.018
    [17] 武小年, 李迎新, 韦永壮, 等. GRANULE和MANTRA算法的不可能差分区分器分析[J]. 通信学报, 2020, 41(1): 94–101. doi: 10.11959/j.issn.1000-436x.2020025

    WU Xiaonian, LI Yingxin, WEI Yongzhuang, et al. Impossible differential distinguisher analysis of GRANULE and MANTRA algorithm[J]. Journal on Communications, 2020, 41(1): 94–101. doi: 10.11959/j.issn.1000-436x.2020025
    [18] TEZCAN C. Improbable differential attacks on PRESENT using undisturbed bits[J]. Journal of Computational and Applied Mathematics, 2014, 259: 503–511. doi: 10.1016/j.cam.2013.06.023
  • 加载中
图(3) / 表(7)
计量
  • 文章访问数:  224
  • HTML全文浏览量:  91
  • PDF下载量:  66
  • 被引次数: 0
出版历程
  • 收稿日期:  2022-10-12
  • 修回日期:  2023-04-12
  • 网络出版日期:  2023-04-17
  • 刊出日期:  2023-12-26

目录

    /

    返回文章
    返回