高级搜索

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]

      袁庆军, 张勋成, 高杨, 王永娟. 轻量级分组密码PUFFIN的差分故障攻击. 电子与信息学报, 2020, 42(6): 1519-1525.

    2. [2]

      贺利芳, 吴雪霜, 张天骐. 正交多用户短参考差分混沌移位键控通信系统性能分析. 电子与信息学报, 2020, 42(0): 1-9.

    3. [3]

      贺利芳, 陈俊, 张天骐. 短参考多用户差分混沌移位键控通信系统性能分析. 电子与信息学报, 2020, 42(0): 1-8.

    4. [4]

      姚敏立, 王旭健, 张峰干, 戴定成. 基于动态参数差分进化算法的多约束稀布矩形面阵优化. 电子与信息学报, 2020, 42(5): 1281-1287.

    5. [5]

      张天骐, 范聪聪, 葛宛营, 张天. 基于ICA和特征提取的MIMO信号调制识别算法. 电子与信息学报, 2020, 41(0): 1-8.

    6. [6]

      王永娟, 王涛, 袁庆军, 高杨, 王相宾. 密码算法旁路立方攻击改进与应用. 电子与信息学报, 2020, 42(5): 1087-1093.

    7. [7]

      夏晓峰, 向宏, 肖震宇, 蔡挺. 基于国产密码算法的数控网络的双层安全防护模型研究及安全评估. 电子与信息学报, 2020, 42(0): 1-7.

    8. [8]

      佟鑫, 李莹, 陈岚. SVM算法在硬件木马旁路分析检测中的应用. 电子与信息学报, 2020, 42(7): 1643-1651.

    9. [9]

      陈华, 习伟, 范丽敏, 焦志鹏, 冯婧怡. 密码产品的侧信道分析与评估. 电子与信息学报, 2020, 42(0): 1-10.

    10. [10]

      贾连印, 陈明鲜, 李孟娟, 游进国, 丁家满. 基于状态视图的高效Hilbert编码和解码算法. 电子与信息学报, 2020, 42(6): 1494-1501.

    11. [11]

      游凌, 李伟浩, 张文林, 王科人. 基于深度神经网络的Morse码自动译码算法. 电子与信息学报, 2020, 41(0): 1-6.

    12. [12]

      蒲磊, 冯新喜, 侯志强, 余旺盛. 基于自适应背景选择和多检测区域的相关滤波算法. 电子与信息学报, 2020, 41(0): 1-7.

    13. [13]

      高东, 梁子林. 基于能量效率的双层非正交多址系统资源优化算法. 电子与信息学报, 2020, 42(5): 1237-1243.

    14. [14]

      陈根华, 陈伯孝. 复杂多径信号下基于空域变换的米波雷达稳健测高算法. 电子与信息学报, 2020, 42(5): 1297-1302.

    15. [15]

      归伟夏, 陆倩, 苏美力. 关于系统级故障诊断的烟花-反向传播神经网络算法. 电子与信息学报, 2020, 42(5): 1102-1109.

    16. [16]

      张斌, 吴浩明. 一种面向连接的快速多维包分类算法. 电子与信息学报, 2020, 42(6): 1526-1533.

    17. [17]

      赵国繁, 唐伦, 胡彦娟, 赵培培, 陈前斌. 面向可靠性的5G网络切片重构及映射算法. 电子与信息学报, 2020, 42(6): 1478-1485.

    18. [18]

      王威丽, 陈前斌, 唐伦. 虚拟网络切片中的在线异常检测算法研究. 电子与信息学报, 2020, 42(6): 1460-1467.

    19. [19]

      张凯, 陈彬, 许志伟. 基于多目标进化策略算法的DNA核酸编码设计. 电子与信息学报, 2020, 42(6): 1365-1373.

    20. [20]

      曹祥红, 李欣妍, 魏晓鸽, 李森, 黄梦溪, 李栋禄. 基于Dijkstra-ACO混合算法的应急疏散路径动态规划. 电子与信息学报, 2020, 42(6): 1502-1509.

  • 图 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下载量:  61
  • 文章访问数:  1174
  • HTML全文浏览量:  734
文章相关
  • 通讯作者:  史佳利, 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搜索

/

返回文章