高级搜索

LiCi分组密码算法的不可能差分分析

韦永壮 史佳利 李灵琛

引用本文: 韦永壮, 史佳利, 李灵琛. LiCi分组密码算法的不可能差分分析[J]. 电子与信息学报, 2019, 41(7): 1610-1617. doi: 10.11999/JEIT180729 shu
Citation:  Yongzhuang WEI, Jiali SHI, Lingchen LI. Impossible Differential Cryptanalysis of LiCi Block Cipher[J]. Journal of Electronics and Information Technology, 2019, 41(7): 1610-1617. doi: 10.11999/JEIT180729 shu

LiCi分组密码算法的不可能差分分析

    作者简介: 韦永壮: 男,1976年生,教授,博士生导师,研究方向为密码函数、分组密码分析;
    史佳利: 女,1992年生,硕士生,研究方向为对称密码算法分析;
    李灵琛: 女,1988年生,博士生,研究方向为分组密码的分析与设计
    通讯作者: 史佳利,jiali00@126.com
  • 基金项目: 国家自然科学基金(61572148,61872103,61561016), 广西研究生教育创新计划资助项目(YCBZ2018051), 获桂林电子科技大学研究生优秀学位论文培育项目(16YJPYSS12), 桂林电子科技大学研究生教育创新计划(2018YJCX45)

摘要: LiCi是由Patil等人(2017)提出的轻量级分组密码算法。由于采用新型的设计理念,该算法具有结构紧凑、能耗低、占用芯片面积小等优点,特别适用于资源受限的环境。目前该算法的安全性备受关注,Patil等人声称:16轮简化算法足以抵抗经典的差分攻击及线性攻击。该文基于S盒的差分特征,结合中间相遇思想,构造了一个10轮的不可能差分区分器。基于此区分器,向前后各扩展3轮,并利用密钥编排方案,给出了LiCi的一个16轮的不可能差分分析方法。该攻击需要时间复杂度约为283.08次16轮加密,数据复杂度约为259.76选择明文,存储复杂度约为276.76数据块,这说明16轮简化的LiCi算法无法抵抗不可能差分攻击。

English

    1. [1]

      BIRYUKOV A and PERRIN L. State of the art in lightweight symmetric cryptography[R]. Cryptology ePrint Archive: Report 2017/511, 2017: 1–11.

    2. [2]

      GUO Jian, PEYRIN T, POSCHMANN A, et al. The LED block cipher[C]. Proceedings of the 13th International Workshop on Cryptographic Hardware and Embedded Systems, Nara, Japan, 2011: 326–341.

    3. [3]

      BOGDANOV A, KNUDSEN L R, LEANDER G, et al. PRESENT: An ultra-lightweight block cipher[C]. Proceedings of 9th International Workshop on Cryptographic Hardware and Embedded Systems, Vienna, Austria, 2007: 450–466.

    4. [4]

      BANIK S, PANDEY S K, PEYRIN T, et al. GIFT: A small present[C]. Proceedings of the 19th International Conference on Cryptographic Hardware and Embedded Systems, Taipei, China, 2017: 321–345.

    5. [5]

      BANIK S, BOGDANOV A, ISOBE T, et al. Midori: A block cipher for low energy[C]. Proceedings of the 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, 2015: 411–436.

    6. [6]

      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.

    7. [7]

      国家商用密码管理办公室. 无线局域网产品使用的SMS4密码算法[EB/OL]. http://www.oscca.gov.cn/sca/c100061/201611/1002423/files/330480f731f64e1ea75138211ea0dc27.pdf, 2018.
      Office of State Commercial Cipher Administration. Block cipher for WLAN products-SMS4[EB/OL]. http://www.oscca.gov.cn/sca/c100061/201611/1002423/files/330480f731f64e1ea75138211ea0dc27.pdf, 2018.

    8. [8]

      BEAULIEU R, TREATMAN-CLARK S, SHORS D, et al. The SIMON and SPECK lightweight block ciphers[C]. Proceedings of the 52nd ACM/EDAC/IEEE Design Automation Conference, San Francisco, USA, 2015: 1–6.

    9. [9]

      AOKI K, ICHIKAWA T, KANDA M, et al. Camellia: A 128-bit block cipher suitable for multiple platforms-design and analysis[C]. Proceedings of the 7th Annual International Workshop on Selected Areas in Cryptography, Ontario, Canada, 2000: 39–56.

    10. [10]

      PATIL J, BANSOD G, and KANT K S. LiCi: A new ultra-lightweight block cipher[C]. Proceedings of 2017 International Conference on Emerging Trends & Innovation in ICT, Pune, India, 2017: 40–45.

    11. [11]

      KNUDSEN L R. DEAL-a 128-bit block cipher[R]. Technical Report, 1998.

    12. [12]

      BIHAM E, BIRYUKOV A, and SHAMIR A. Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials[M]. Berlin, Germany, 1999: 12–23.

    13. [13]

      BIHAM E and SHAMIR A. Differential cryptanalysis of DES-like cryptosystems[C]. Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, 1991: 2–21.

    14. [14]

      TJUAWINATA I, HUANG Tao, and WU Hongjun. Improved differential cryptanalysis on generalized feistel schemes[C]. Proceedings of the 18th International Conference on Cryptology in India, Chennai, India, 2017: 302–324.

    15. [15]

      LIU Ya, GU Dawu, LIU Zhiqiang, et al. Impossible differential attacks on reduced-round LBlock[C]. Proceedings of the 8th International Conference on Information Security Practice and Experience, Hangzhou, China, 2012: 97–108.

    16. [16]

      KONDO K, SASAKI Y, TODO Y, et al. Analyzing key schedule of SIMON: Iterative key differences and application to related-key impossible differentials[C]. Proceedings of the 12th International Workshop on Security, Hiroshima, Japan, 2017: 141–158.

    17. [17]

      MEHRDAD A, MOAZAMI F, and SOLEIMANY H. Impossible differential cryptanalysis on Deoxys-BC-256[R]. Cryptology ePrint Archive: Report 2018/048, 2018.

    18. [18]

      SHAHMIRZADI A R, AZIMI S A, SALMASIZADEH M, et al. Impossible differential cryptanalysis of reduced-round Midori64 block cipher[J]. ISeCure, 2018, 10(1): 3–14.

    19. [19]

      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

    1. [1]

      谢敏, 曾琦雅. 轻量级分组密码算法ESF的相关密钥不可能差分分析. 电子与信息学报, 2019, 41(5): 1173-1179.

    2. [2]

      沈璇, 孙兵, 刘国强, 李超. 数字视频广播通用加扰算法的不可能差分分析. 电子与信息学报, 2019, 41(1): 46-52.

    3. [3]

      罗钧, 杨永松, 侍宝玉. 基于改进的自适应差分演化算法的二维Otsu多阈值图像分割. 电子与信息学报, 2019, 41(8): 2017-2024.

    4. [4]

      陈路昭, 朱万华, 吴佩霖, 费春娇, 方广有. 地磁背景环境中基于分形特征的磁异常信号检测算法. 电子与信息学报, 2019, 41(2): 332-340.

    5. [5]

      张刚, 赵畅畅, 张天骐. 短参考正交多用户差分混沌键控方案的性能分析. 电子与信息学报, 2019, 41(9): 2055-2062.

    6. [6]

      张刚, 陈和祥, 张天骐. 多用户降噪差分混沌键控通信方案. 电子与信息学报, 2019, 41(2): 362-368.

    7. [7]

      杜永兆, 范宇凌, 柳培忠, 唐加能, 骆炎民. 多种群协方差学习差分进化算法. 电子与信息学报, 2019, 41(6): 1488-1495.

    8. [8]

      许杰, 徐珂, 黄志祥. 一种新型的高阶时域有限差分方法. 电子与信息学报, 2019, 41(0): 1-5.

    9. [9]

      王满利, 田子建, 张元刚. 曲率差分驱动的极小曲面滤波器. 电子与信息学报, 2019, 41(0): 1-8.

    10. [10]

      李保珠, 关键, 董云龙. 基于航迹矢量检测的雷达与电子支援设施抗差关联算法. 电子与信息学报, 2019, 41(1): 123-129.

    11. [11]

      李保珠, 张林, 董云龙, 关键. 基于航迹矢量分级聚类的雷达与电子支援措施抗差关联算法. 电子与信息学报, 2019, 41(6): 1310-1316.

    12. [12]

      任凯强, 孙正波. 基于虚拟参考站的同步三星时差定位系统广域差分校正算法. 电子与信息学报, 2019, 41(2): 433-439.

    13. [13]

      张鹤玖, 余宁梅, 吕楠, 刘尕. 一种用于时延积分CMOS图像传感器的10 bit全差分双斜坡模数转换器. 电子与信息学报, 2019, 41(6): 1466-1471.

    14. [14]

      赵军, 曾学文, 郭志川. 支持国产密码算法的高速PCIe密码卡的设计与实现. 电子与信息学报, 2019, 41(10): 2402-2408.

    15. [15]

      杨磊, 李埔丞, 李慧娟, 方澄. 稳健高效通用SAR稀疏特征增强算法. 电子与信息学报, 2019, 41(12): 2826-2835.

    16. [16]

      王宗原, 周卫东. 学生t量测分布下鲁棒粒子滤波算法的设计与实现. 电子与信息学报, 2019, 41(0): 1-8.

    17. [17]

      赵辉, 张静, 张乐, 刘莹莉, 张天骐. 基于非局部低秩和加权全变分的图像压缩感知重构算法. 电子与信息学报, 2019, 41(8): 2025-2032.

    18. [18]

      李杰, 阎跃鹏, 梁晓新, 万晶, 王魁松. 一种基于天牛须算法的新型超宽带功分器研究. 电子与信息学报, 2019, 41(0): 1-7.

    19. [19]

      孙彦景, 石韫开, 云霄, 朱绪冉, 王赛楠. 基于多层卷积特征的自适应决策融合目标跟踪算法. 电子与信息学报, 2019, 41(10): 2464-2470.

    20. [20]

      崔维嘉, 张鹏, 巴斌. 基于贝叶斯自动相关性确定的稀疏重构正交频分复用信号时延估计算法. 电子与信息学报, 2019, 41(10): 2318-2324.

  • 图 1  LiCi算法的轮函数

    图 2  LiCi算法的10轮不可能差分路线

    图 3  LiCi算法的16轮不可能差分分析

    表 1  S盒输入/输出差分特征

    输入差分00010100100011001101**11**1***0****1***0
    输出差分1******1***11**00***00010010001101000101
    下载: 导出CSV

    表 2  S盒输入/输出差分特征概率

    输入差分**11**1****1****00010****0**01***000
    输出差分00010010010010001*******************
    概率1/41/81/81/161/81/21/21/41/8
    下载: 导出CSV

    表 3  不可能差分分析16轮LiCi算法的密钥恢复各步骤的时间复杂度

    步骤恢复的密钥比特猜测比特数目时间复杂度(单位:次16轮加密所用的时间)
    (1)0${2^{m + 49}} \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 42}}$
    (2)${\rm{Rk}}{0_1}\left[ {24 \sim 21} \right]$4${2^{m + 21}} \times {2^4} \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 18}}$
    (3)${\rm{Rk}}{15_2}\left[ {15 \sim 12} \right]$4${2^{m + 18}} \times {2^4} \times {2^4} \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 19}}$
    (4)${\rm{Rk}}{15_2}\left[ {31 \sim 28} \right]$4${2^{m + 15}} \times {2^4} \times {2^4} \times {2^4} \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 20}}$
    (5)${\rm{Rk}}{15_2}\left[ {23 \sim 20} \right]$4${2^{m + 14}} \times {2^4} \times {2^4} \times {2^4} \times {2^4} \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 23}}$
    (6)${\rm{Rk}}{15_1}\left[ {16 \sim 13} \right]$, ${\rm{Rk}}{14_2}\left[ {23 \sim 20} \right]$8${2^{m + 13}} \times {2^4} \times {2^4} \times {2^4} \times {2^4} \times {2^8} \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 30}}$
    (7)${\rm{Rk}}{15_2}\left[ {19 \sim 16,11 \sim 9} \right]$, ${\rm{Rk}}{15_1}\left[ {12 \sim 9} \right]$, ${\rm{Rk}}{14_2}\left[ {19 \sim 16} \right]$12${2^{m + 10}} \times {2^{16}} \times {2^8} \times {2^{12}} \times 2 \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 40}}$
    (8)${\rm{Rk}}{15_2}\left[ {27 \sim 24} \right]$, ${\rm{Rk}}{15_1}\left[ {20 \sim 17} \right]$, ${\rm{Rk}}{14_2}\left[ {27 \sim 24} \right]$12${2^{m + 7}} \times {2^{24}} \times {2^{12}} \times {2^{12}} \times 2 \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 49}}$
    (9)${\rm{Rk}}{15_2}\left[ {8 \sim 6} \right]$, ${\rm{Rk}}{15_1}\left[ {8 \sim 6} \right]$, ${\rm{Rk}}{15_2}\left[ {15 \sim 13} \right]$, ${\rm{Rk}}{14_1}\left[ {16 \sim 13} \right]$10${2^{m + 5}} \times {2^{24}} \times {2^{12}} \times {2^{12}} \times {2^{10}} \times 2 \times \frac{1}{{8 \times 16}} = {2^{{{m}} + 56}}$
    (10)${\rm{Rk}}{0_1}\left[ {20 \sim 9} \right]$, ${\rm{Rk}}{0_2}\left[ {23 \sim 20} \right]$, ${\rm{Rk}}{1_1}\left[ {16 \sim 13} \right]$20${2^{m{\rm{ - }}16}} \times {2^{58}} \times {2^{20}} \times 3 \times \frac{1}{{8 \times 16}} + {2^{74}} = {2^{{{m}} + 56.58}} + {2^{74}}$
    下载: 导出CSV

    表 4  LiCi算法的攻击结果对比

    分析方法攻击轮数选择明文量时间复杂度存储复杂度参考文献
    线性分析162106文献[10]
    差分分析16296文献[10]
    不可能差分分析16259.76283.08276.76本文
    下载: 导出CSV
  • 加载中
图(3)表(4)
计量
  • PDF下载量:  46
  • 文章访问数:  620
  • HTML全文浏览量:  387
文章相关
  • 通讯作者:  史佳利, jiali00@126.com
  • 收稿日期:  2018-07-19
  • 录用日期:  2018-10-29
  • 网络出版日期:  2019-03-18
  • 刊出日期:  2019-07-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章