高级搜索

留言板

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

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

全轮超轻量级分组密码PFP的相关密钥差分分析

严智广 韦永壮 叶涛

严智广, 韦永壮, 叶涛. 全轮超轻量级分组密码PFP的相关密钥差分分析[J]. 电子与信息学报. doi: 10.11999/JEIT240782
引用本文: 严智广, 韦永壮, 叶涛. 全轮超轻量级分组密码PFP的相关密钥差分分析[J]. 电子与信息学报. doi: 10.11999/JEIT240782
YAN Zhiguang, WEI Yongzhuang, YE Tao. Related-key Differential Cryptanalysis of Full-round PFP Ultra-lightweight Block Cipher[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT240782
Citation: YAN Zhiguang, WEI Yongzhuang, YE Tao. Related-key Differential Cryptanalysis of Full-round PFP Ultra-lightweight Block Cipher[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT240782

全轮超轻量级分组密码PFP的相关密钥差分分析

doi: 10.11999/JEIT240782
基金项目: 国家自然科学基金 (62162016, 62402132)
详细信息
    作者简介:

    严智广:男,硕士,研究方向为密码学、信息安全

    韦永壮:男,博士,教授,博导,广西密码学与信息安全重点实验室主任,研究方向为密码学与信息安全

    叶涛:男,博士,讲师,研究方向为对称密码算法设计与分析

    通讯作者:

    叶涛 yetao@guet.edu.cn

  • 中图分类号: TN918; TP309

Related-key Differential Cryptanalysis of Full-round PFP Ultra-lightweight Block Cipher

Funds: The National Natural Science Foundation of China (62162016, 62402132)
  • 摘要: 2017年PFP作为一种超轻量级分组密码被提出,而因其卓越的实现性能备受业界广泛关注。该算法不仅硬件开销需求低(仅需约1355 GE(等效门))、功耗小,而且加解密速度快(其速度甚至比国际著名算法 PRESENT的实现速度快1.5倍),非常适合在物联网环境中使用。在PFP算法的设计文档中,作者声称该算法具有足够的能力抵御差分攻击、线性攻击及不可能差分攻击等多种密码攻击方法。然而该算法是否存在未知的安全漏洞是目前研究的难点。该文基于可满足性模理论(SMT),结合PFP算法轮函数特点,构建两种区分器自动化搜索模型。实验测试结果表明:该算法在32轮加密中存在概率为2-62的相关密钥差分特征。由此,该文提出一种针对全轮PFP算法的相关密钥恢复攻击,即只需263个选择明文和248次全轮加密便可破译出80 bit的主密钥。这说明该算法无法抵抗相关密钥差分攻击。
  • 图  1  PFP算法加密流程

    图  2  32轮相关密钥差分区分器向后扩展2轮

    表  1  PFP算法攻击结果对比

    攻击方法攻击
    轮数
    恢复主密钥
    比特数(bit)
    数据
    复杂度
    时间
    复杂度
    文献
    不可能差分632237.00265.00[7]
    不可能差分936236.00258.00[19]
    不可能差分1052246.00275.00[20]
    积分攻击1240262.39263.12[21]
    差分攻击2648260.00254.30[22]
    差分攻击2973259.00278.14本文
    相关密钥差分攻击3480263.00248.00本文
    下载: 导出CSV

    表  2  PFP算法的S盒

    $x$0123456789ABCDEF
    $S(x)$C56B90AD3EF84712
    下载: 导出CSV

    表  3  S盒的差分分布表

    输入差分输出差分
    0123456789ABCDEF
    016000000000000000
    10004000404000400
    20002042000202220
    30202204200220000
    40000042202202020
    50200200002224200
    60020002020042004
    70420002020002004
    80002000202040204
    90020402020002040
    A0022040020200220
    B0200200042220200
    C0020040222200020
    D0242200200220000
    E0022002222002200
    F0400400000000044
    下载: 导出CSV

    表  4  PFP算法的差分界

    轮数最大期望差分特征概率轮数最大期望差分特征概率
    单密钥相关密钥单密钥相关密钥
    12020182-442-34
    22–220192-462-36
    32–420202-482-38
    42–620212-512-40
    52–820222-542-42
    62-122–3232-562-44
    72-162–5242-582-46
    82-182–9252-612-48
    92-212-14262-642-50
    102-242-18272-662-52
    112-262-20282-682-54
    122-282-22292-712-56
    132-312-24302-742-58
    142-342-26312-762-60
    152-362-28322-782-62
    162-382-30332-812-64
    172-412-32342-842-66
    下载: 导出CSV

    表  5  差分特征概率为2-61的25轮差分区分器

    轮数左分支差分右分支差分轮数左分支差分右分支差分
    00x00040D000x00000900130x000009000x00000900
    10x000009000x00000900140x000009000x00000D00
    20x000009000x00000D00150x00000D000x00000D00
    30x00000D000x00000D00160x00000D000x00000900
    40x00000D000x00000900170x000009000x00000900
    50x000009000x00000900180x000009000x00000D00
    60x000009000x00000D00190x00000D000x00000D00
    70x00000D000x00000D00200x00000D000x00000900
    80x00000D000x00000900210x000009000x00000900
    90x000009000x00000900220x000009000x00000D00
    100x000009000x00000D00230x00000D000x00000D00
    110x00000D000x00000D00240x00000D000x00000900
    120x00000D000x00000900250x000009000x00040D00
    下载: 导出CSV

    表  6  差分特征概率为2–62的32轮相关密钥差分区分器

    轮数左右分支差分相关密钥差分轮数左右分支差分相关密钥差分
    00x8BBBBA22D11111770xD111117777444445DDDD170xD11111778BBBBA220x8BBBBA22222EEEE88888
    10xD11111778BBBBA220x8BBBBA22222EEEE88888180x8BBBBA22D11111770xD111117777444445DDDD
    20x8BBBBA22D11111770xD111117777444445DDDD190xD11111778BBBBA220x8BBBBA22222EEEE88888
    30xD11111778BBBBA220x8BBBBA22222EEEE88888200x8BBBBA22D11111770xD111117777444445DDDD
    40x8BBBBA22D11111770xD111117777444445DDDD210xD11111778BBBBA220x8BBBBA22222EEEE88888
    50xD11111778BBBBA220x8BBBBA22222EEEE88888220x8BBBBA22D11111770xD111117777444445DDDD
    60x8BBBBA22D11111770xD111117777444445DDDD230xD11111778BBBBA220x8BBBBA22222EEEE88888
    70xD11111778BBBBA220x8BBBBA22222EEEE88888240x8BBBBA22D11111770xD111117777444445DDDD
    80x8BBBBA22D11111770xD111117777444445DDDD250xD11111778BBBBA220x8BBBBA22222EEEE88888
    90xD11111778BBBBA220x8BBBBA22222EEEE88888260x8BBBBA22D11111770xD111117777444445DDDD
    100x8BBBBA22D11111770xD111117777444445DDDD270xD11111778BBBBA220x8BBBBA22222EEEE88888
    110xD11111778BBBBA220x8BBBBA22222EEEE88888280x8BBBBA22D11111770xD111117777444445DDDD
    120x8BBBBA22D11111770xD111117777444445DDDD290xD11111778BBBBA220x8BBBBA22222EEEE88888
    130xD11111778BBBBA220x8BBBBA22222EEEE88888300x8BBBBA22D11111770xD111117777444445DDDD
    140x8BBBBA22D11111770xD111117777444445DDDD310xD11111778BBBBA220x8BBBBA22222EEEE88888
    150xD11111778BBBBA220x8BBBBA22222EEEE88888320x8BBBBA22D1111177-
    160x8BBBBA22D11111770xD111117777444445DDDD
    下载: 导出CSV

    表  7  相关密钥下PFP算法密钥恢复阶段的复杂度计算

    步数 猜测密钥 筛选后剩余明密文对数量 时间复杂度
    1 ${K_{33}}[31,30,29,28]$ ${2^{m - 33 - 4}}$ $ 2 \cdot {2^{m - 33}} \cdot {2^4} $
    2 ${K_{33}}[23,22,21,20]$ ${2^{m - 37 - 4}}$ $ 2 \cdot {2^{m - 37}} \cdot {2^8} $
    3 ${K_{33}}[15,14,13,12]$ ${2^{m - 41 - 4}}$ $ 2 \cdot {2^{m - 41}} \cdot {2^{12}} $
    4 ${K_{33}}[7,6,5,4]$ ${2^{m - 45 - 4}}$ $ 2 \cdot {2^{m - 45}} \cdot {2^{16}} $
    5 ${K_{33}}[27,26,25,24]$ ${2^{m - 49 - 3}}$ $ 2 \cdot {2^{m - 49}} \cdot {2^{20}} $
    6 ${K_{33}}[19,18,17,16]$ ${2^{m - 52 - 3}}$ $ 2 \cdot {2^{m - 52}} \cdot {2^{24}} $
    7 ${K_{33}}[11,10,9,8]$ ${2^{m - 55 - 3}}$ $ 2 \cdot {2^{m - 55}} \cdot {2^{28}} $
    8 ${K_{33}}[3,2,1,0]$ ${2^{m - 58 - 3}}$ $ 2 \cdot {2^{m - 58}} \cdot {2^{32}} $
    9 ${K_{32}}[31,30,29,28]$ ${2^{m - 61 - 4}}$ $ 2 \cdot {2^{m - 61}} \cdot {2^{32}} $
    总和 ${2^{m - 24}} + {2^{m - 26}}$
    下载: 导出CSV
  • [1] National Institute of Standards and Technology, DWORKIN M J, BARKER E, et al. Advanced encryption standard[R]. 197, 2001. doi: 10.6028/NIST.FIPS.197.
    [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. doi: 10.1007/978-3-642-21554-4_19.
    [3] 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. doi: 10.1007/978-3-642-23951-9_22.
    [4] BANIK S, PANDEY S K, PEYRIN T, et al. GIFT: A small present: Towards reaching the limit of lightweight encryption[C]. Proceedings of the 19th International Conference on Cryptographic Hardware and Embedded Systems, Taipei, China, 2017: 321–345. doi: 10.1007/978-3-319-66787-4_16.
    [5] 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. doi: 10.1145/2744769.2747946.
    [6] BOGDANOV A, KNUDSEN L R, LEANDER G, et al. PRESENT: An ultra-lightweight block cipher[C]. Proceedings of the 9th International Workshop, Vienna, Austria, 2007: 450–466. doi: 10.1007/978-3-540-74735-2_31.
    [7] 黄玉划, 代学俊, 时阳阳, 等. 基于Feistel结构的超轻量级分组密码算法(PFP)[J]. 计算机科学, 2017, 44(3): 163–167. doi: 10.11896/j.issn.1002-137X.2017.03.036.

    HUANG Yuhua, DAI Xuejun, SHI Yangyang, et al. Ultra-lightweight block cipher algorithm (PFP) based on Feistel structure[J]. Computer Science, 2017, 44(3): 163–167. doi: 10.11896/j.issn.1002-137X.2017.03.036.
    [8] BIHAM E and SHAMIR A. Differential cryptanalysis of DES-like cryptosystems[J]. Journal of Cryptology, 1991, 4(1): 3–72. doi: 10.1007/BF00630563.
    [9] MATSUI M. Linear cryptanalysis method for DES cipher[C]. Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology (EUROCRYPT'93), Lofthus, Norway, 1993: 386–397. doi: 10.1007/3-540-48285-7_33.
    [10] HADIPOUR H, SADEGHI S and EICHLSEDER M. Finding the impossible: Automated search for full impossible-differential, zero-correlation, and integral attacks[C]. Proceedings of the 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology (EUROCRYPT 2023), Lyon, France, 2023: 128–157. doi: 10.1007/978-3-031-30634-1_5.
    [11] HADIPOUR H, GERHALTER S, SADEGHI S, et al. Improved search for integral, impossible differential and zero-correlation attacks[J]. IACR Transactions on Symmetric Cryptology, 2024, 2024(1): 234–325. doi: 10.46586/tosc.v2024.i1.234-325.
    [12] LAI Xuejia. Higher order derivatives and differential cryptanalysis[M]. BLAHUT R E, COSTELLO D J, MAURER U, et al. Communications and Cryptography: Two Sides of One Tapestry. Boston: Springer, 1994: 227–233. doi: 10.1007/978-1-4615-2694-0_23.
    [13] AHMADIAN Z, KHALESI A, M’FOUKH D, et al. Truncated differential cryptanalysis: New insights and application to QARMAv1-n and QARMAv2–64[J]. Designs, Codes and Cryptography, 2024, 92(12): 4549–4591. doi: 10.1007/s10623-024-01486-8.
    [14] BIHAM E. New types of cryptanalytic attacks using related keys[J]. Journal of Cryptology, 1994, 7(4): 229–246. doi: 10.1007/BF00203965.
    [15] ROHIT R and SARKAR S. Reconstructing s-boxes from cryptographic tables with MILP[J]. IACR Transactions on Symmetric Cryptology, 2024, 2024(3): 200–237. doi: 10.46586/tosc.v2024.i3.200-237.
    [16] CHAKRABORTY D, HADIPOUR H, NGUYEN P H, et al. Finding complete impossible differential attacks on AndRX ciphers and efficient distinguishers for ARX designs[J]. IACR Transactions on Symmetric Cryptology, 2024, 2024(3): 84–176. doi: 10.46586/tosc.v2024.i3.84-176.
    [17] WANG Dachao, WANG Baocang, and SUN Siwei. SAT-aided automatic search of boomerang distinguishers for ARX ciphers[J]. IACR Transactions on Symmetric Cryptology, 2023, 2023(1): 152–191. doi: 10.46586/tosc.v2023.i1.152-191.
    [18] ERLACHER J, MENDEL F, and EICHLSEDER M. Bounds for the security of ascon against differential and linear cryptanalysis[J]. IACR Transactions on Symmetric Cryptology, 2022, 2022(1): 64–87. doi: 10.46586/tosc.v2022.i1.64-87.
    [19] 沈璇, 王欣玫, 何俊, 等. PFP算法改进的不可能差分分析[J]. 计算机科学, 2020, 47(7): 263–267. doi: 10.11896/jsjkx.200200034.

    SHEN Xuan, WANG Xinmei, HE Jun, et al. Revised impossible differential cryptanalysis of PFP block cipher[J]. Computer Science, 2020, 47(7): 263–267. doi: 10.11896/jsjkx.200200034.
    [20] 赵光耀, 沈璇, 余波, 等. 缩减轮的超轻量级分组密码算法PFP的不可能差分分析[J]. 计算机应用, 2023, 43(9): 2784–2788. doi: 10.11772/j.issn.1001-9081.2022091395.

    ZHAO Guangyao, SHEN Xuan, YU Bo, et al. Impossible differential cryptanalysis of reduced-round ultra-lightweight block cipher PFP[J]. Journal of Computer Applications, 2023, 43(9): 2784–2788. doi: 10.11772/j.issn.1001-9081.2022091395.
    [21] 刘道瞳, 袁征, 魏锦鹏, 等. 轻量级分组密码算法PFP和SLIM的积分分析[J]. 密码学报, 2023, 10(3): 609–621. doi: 10.13868/j.cnki.jcr.000617.

    LIU Daotong, YUAN Zheng, WEI Jinpeng, et al. Integral cryptanalysis of lightweight block cipher PFP and SLIM[J]. Journal of Cryptologic Research, 2023, 10(3): 609–621. doi: 10.13868/j.cnki.jcr.000617.
    [22] 李艳俊, 李寅霜, 杨明华, 等. 轻量级PFP算法的差分攻击[J]. 计算机工程与应用, 2023, 59(21): 296–302. doi: 10.3778/j.issn.1002-8331.2305-0193.

    LI Yanjun, LI Yinshuang, YANG Minghua, et al. Differential attack on lightweight PFP algorithm[J]. Computer Engineering and Applications, 2023, 59(21): 296–302. doi: 10.3778/j.issn.1002-8331.2305-0193.
    [23] COOK S A. The complexity of theorem-proving procedures[C]. Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC '71), Shaker Heights, USA, 1971: 151–158. doi: 10.1145/800157.805047.
    [24] DE MOURA L and BJØRNER N. Z3: An efficient SMT solver[C]. Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2008), Budapest, Hungary, 2008: 337–340. doi: 10.1007/978-3-540-78800-3_24.
    [25] BARRETT C, CONWAY C L, DETERS M, et al. CVC4[C]. Proceedings of the 23rd International Conference on Computer aided verification (CAV 2011), Snowbird, USA, 2011: 171–177.
    [26] CIMATTI A, GRIGGIO A, SCHAAFSMA B J, et al. The MathSAT5 SMT solver[C]. Proceedings of the 19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2013), Rome, Italy, 2013: 93–107. doi: 10.1007/978-3-642-36742-7_7.
    [27] BRUMMAYER R and BIERE A. Boolector: An efficient SMT solver for bit-vectors and arrays[C]. Proceedings of the 15th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2009), York, UK, 2009: 174–177. doi: 10.1007/978-3-642-00768-2_16.
    [28] GANESH V and DILL D L. A decision procedure for bit-vectors and arrays[C]. Proceedings of the 19th International Conference on Computer Aided Verification (CAV 2007), Berlin, Germany, 2007: 519–531. doi: 10.1007/978-3-540-73368-3_52.
    [29] STUMP A, BARRETT C W, and DILL D L. CVC: A cooperating validity checker[C]. Proceedings of the 14th International Conference on Computer Aided Verification (CAV 2002), Copenhagen, Denmark, 2002: 500–504. doi: 10.1007/3-540-45657-0_40.
    [30] SELÇUK A A. On probability of success in linear and differential cryptanalysis[J]. Journal of Cryptology, 2008, 21(1): 131–147. doi: 10.1007/s00145-007-9013-7.
  • 加载中
图(2) / 表(7)
计量
  • 文章访问数:  104
  • HTML全文浏览量:  18
  • PDF下载量:  0
  • 被引次数: 0
出版历程
  • 收稿日期:  2024-09-11
  • 修回日期:  2025-01-07
  • 网络出版日期:  2025-01-11

目录

    /

    返回文章
    返回