高级搜索

留言板

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

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

改进的Type-1型广义Feistel结构的量子攻击及其在分组密码CAST-256上的应用

倪博煜 董晓阳

倪博煜, 董晓阳. 改进的Type-1型广义Feistel结构的量子攻击及其在分组密码CAST-256上的应用[J]. 电子与信息学报, 2020, 42(2): 295-306. doi: 10.11999/JEIT190633
引用本文: 倪博煜, 董晓阳. 改进的Type-1型广义Feistel结构的量子攻击及其在分组密码CAST-256上的应用[J]. 电子与信息学报, 2020, 42(2): 295-306. doi: 10.11999/JEIT190633
Boyu NI, Xiaoyang DONG. Improved Quantum Attack on Type-1 Generalized Feistel Schemes and Its Application to CAST-256[J]. Journal of Electronics and Information Technology, 2020, 42(2): 295-306. doi: 10.11999/JEIT190633
Citation: Boyu NI, Xiaoyang DONG. Improved Quantum Attack on Type-1 Generalized Feistel Schemes and Its Application to CAST-256[J]. Journal of Electronics and Information Technology, 2020, 42(2): 295-306. doi: 10.11999/JEIT190633

改进的Type-1型广义Feistel结构的量子攻击及其在分组密码CAST-256上的应用

doi: 10.11999/JEIT190633
基金项目: 国家重点研发计划(2017YFA0303903),国家自然科学基金(61902207),国家密码发展基金(MMJJ20180101, MMJJ20170121)
详细信息
    作者简介:

    董晓阳:男,1988年生,助理研究员。研究方向为对称密码算法的安全性分析与设计

    通讯作者:

    董晓阳 xiaoyangdong@tsinghua.edu.cn

  • 中图分类号: TN918; TP309

Improved Quantum Attack on Type-1 Generalized Feistel Schemes and Its Application to CAST-256

Funds: The National Key Research and Development Program of China (2017YFA0303903), The National Natural Science Foundation of China (61902207), The National Cryptography Development Fund (MMJJ20180101, MMJJ20170121)
  • 摘要: 广义Feistel结构(GFS)是设计对称密码算法的重要基础结构之一,其在经典计算环境中受到了广泛的研究。但是,量子计算环境下对GFS的安全性评估还相当稀少。该文在量子选择明文攻击(qCPA)条件下和量子选择密文攻击(qCCA)条件下,分别对Type-1 GFS进行研究,给出了改进的多项式时间量子区分器。在qCPA条件下,给出了3d – 3轮的多项式时间量子区分攻击,其中$d(d \ge 3)$是Type-1 GFS的分支数,攻击轮数较之前最优结果增加$d - 2$轮。得到更好的量子密钥恢复攻击,即相同轮数下攻击的时间复杂度降低了${2^{(d - 2)n/2}}$。在qCCA条件下,对于Type-1 GFS给出了$3d - 2$轮的多项式时间量子区分攻击,比之前最优结果增加了$d - 1$轮。该文将上述区分攻击应用到CAST-256分组密码中,得到了12轮qCPA多项式时间量子区分器,以及13轮qCCA多项式时间量子区分器,该文给出19轮CAST-256的量子密钥恢复攻击。
  • 图  1  3轮的量子区分器

    图  2  FX结构

    图  3  Ito等人在Feistel上的4轮量子区分器

    图  4  $d$分支Type-1 GFS的第$i$

    图  5  4分支Type-1 GFS的选择明文量子区分器

    图  6  4分支Type-1 GFS的16轮密钥恢复攻击

    图  7  4分支CAST256-like GFS的10轮区分器

    图  8  CAST-256的12轮区分器

    图  9  CAST-256的14轮攻击

    图  10  CAST-256的13轮区分器

    表  1  Type-1 GFS的量子区分器的轮数

    来源攻击条件$r$$d = 3$$d = 4$$d = 5$$d = 6$$d = 7$
    文献[35]qCPA2d–15791113
    4.1节qCPA3d–369121518
    4.2节qCCA3d–2710131619
    下载: 导出CSV

    表  2  在量子环境下对Type-1 GFS的密钥恢复攻击

    来源区分器轮数密钥恢复轮数复杂度(log)穷搜复杂度(log)
    文献[35]$2d - 1$$r \ge {d^2}$$T + ({{r - {d^2} + d - 2)n} / 2}$ ${{rn} / 2}$
    4.1节$3d - 3$$r \ge {d^2}$$T + ({{r - {d^2})n} / 2}$${{rn} / 2}$
    下载: 导出CSV

    表  3  CAST-256的量子攻击

    来源攻击条件区分器轮数密钥恢复攻击轮数
    $r = 14$$r = 15$$r = 16$$r = 17$$r = 18$$r = 19$
    文献[35]qCPA7${2^{74}}$${2^{92.5}}$${2^{111}}$$ - $$ - $$ - $
    5.1节qCPA12${2^{37}}$${2^{55.5}}$${2^{74}}$${2^{92.5}}$${2^{111}}$$ - $
    5.2节qCCA13${2^{18.5}}$${2^{37}}$${2^{55.5}}$${2^{74}}$${2^{92.5}}$${2^{111}}$
    下载: 导出CSV

    表  4  针对CAST-256的经典攻击和量子攻击的比较

    来源密钥长度攻击轮数数据时间
    文献[39]128飞去来器16${2^{49.3}}$$ - $
    5.2节128qCCA16$ {2^{55.5}} $
    文献[40]192线性攻击24${2^{124.1}}$$ {2^{156.52}} $
    5.2节192qCCA17$ {2^{74}}$
    文献[41]256多维零相关28${2^{98.8}}$$ {2^{246.9}} $
    5.2节256qCCA19$ {2^{111}} $
    下载: 导出CSV
  • [1] KNUDSEN L R. The security of Feistel ciphers with six rounds or less[J]. Journal of Cryptology, 2002, 15(3): 207–222. doi:  10.1007/s00145-002-9839-y
    [2] ISOBE T and SHIBUTANI K. Generic key recovery attack on Feistel scheme[C]. The 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, 2013: 464–485.
    [3] GUO Jian, JEAN J, NIKOLIĆ I, et al. Meet-in-the-middle attacks on generic Feistel constructions[C]. The 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, China, 2014: 458–477.
    [4] DINUR I, DUNKELMAN O, KELLER N, et al. New attacks on Feistel structures with improved memory complexities[C]. The 35th Annual Cryptology Conference, Santa Barbara, USA, 2015: 433–454.
    [5] AOKI K, ICHIKAWA T, KANDA M, et al. Camellia: A 128-bit Block Cipher Suitable for Multiple Platforms - Design and Analysis[M]. Berlin, Heidelberg: Springer, 2001: 39–56.
    [6] National Soviet Bureau of Standards. GOST 28147-89 Information processing systems. cryptographic protection cryptographic transformation algorithm[S]. 1989.
    [7] ZHENG Yuliang, MATSUMOTO T, and IMAI H. On the construction of block ciphers provably secure and not relying on any unproved hypotheses[C]. Conference on the Theory and Application of Cryptology, Santa Barbara, USA, 1990: 461–480.
    [8] ANDERSON R and BIHAM E. Two practical and provably secure block ciphers: BEAR and LION[C]. The 3rd International Workshop on Fast Software Encryption, Cambridge, UK, 1996: 113–120.
    [9] LUCKS S. Faster luby-rackoff ciphers[C]. The 3rd International Workshop on Fast Software Encryption, Cambridge, UK, 1996: 189–203.
    [10] SCHNEIER B and KELSEY J. Unbalanced Feistel networks and block cipher design[C]. The 3rd International Workshop on Fast Software Encryption, Cambridge, UK, 1996: 121–144.
    [11] First AES Candidate Conference[EB/OL]. http://csrc.nist.gov/archive/aes/round1/conf1/aes1conf.htm.
    [12] SHIRAI T, SHIBUTANI K, AKISHITA T, et al. The 128-bit blockcipher CLEFIA (extended abstract)[C]. The 14th International Workshop on Fast Software Encryption, Luxembourg, Luxembourg, 2007: 181–195.
    [13] GUERON S and MOUHA N. Simpira v2: A family of efficient permutations using the AES round function[C]. The 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 2016: 95–125.
    [14] LUBY M and RACKOFF C. How to construct pseudorandom permutations from pseudorandom functions[J]. SIAM Journal on Computing, 1988, 17(2): 373–386. doi:  10.1137/0217022
    [15] MORIAI S and VAUDENAY S. On the pseudorandomness of top-level schemes of block ciphers[C]. The 6th International Conference on the Theory and Application of Cryptology and Information Security, Kyoto, Japan, 2000: 289–302.
    [16] HOANG V T and ROGAWAY P. On generalized Feistel networks[C]. The 30th Annual Cryptology Conference, Santa Barbara, USA, 2010: 613–630.
    [17] JUTLA C S. Generalized birthday attacks on unbalanced Feistel networks[C]. The 18th Annual International Cryptology Conference, Santa Barbara, USA, 1998: 186–199.
    [18] GUO Jian, JEAN J, NIKOLIC I, et al. Meet-in-the-middle attacks on classes of contracting and expanding Feistel constructions[J]. IACR Transactions on Symmetric Cryptology, 2016(2): 307–337.
    [19] NACHEF V, VOLTE E, and PATARIN J. Differential attacks on generalized Feistel schemes[C]. The 12th International Conference on Cryptology and Network Security, Paraty, Brazil, 2013: 1–19.
    [20] TJUAWINATA I, HUANG Tao, and WU Hongjun. Improved differential cryptanalysis on generalized Feistel schemes[C]. The 18th International Conference on Cryptology in India, Chennai, India, 2017: 302–324.
    [21] PATARIN J, NACHEF V, and BERBAIN C. Generic attacks on unbalanced Feistel schemes with contracting functions[C]. The 12th International Conference on the Theory and Application of Cryptology and Information Security, Shanghai, China, 2006: 396–411.
    [22] PATARIN J, NACHEF V, and BERBAIN C. Generic attacks on unbalanced Feistel schemes with expanding functions[C]. The 13th International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia, 2007: 325–341.
    [23] VOLTE E, NACHEF V, and PATARIN J. Improved generic attacks on unbalanced Feistel schemes with expanding functions[C]. The 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 2010: 94–111.
    [24] GROVER L K. A fast quantum mechanical algorithm for database search[C]. The 28th Annual ACM Symposium on Theory of Computing, Philadelphia, USA, 1996: 212–219.
    [25] KUWAKADO H and MORII M. Quantum distinguisher between the 3-round Feistel cipher and the random permutation[C]. IEEE International Symposium on Information Theory, Austin, USA, 2010: 2682–2685.
    [26] SIMON D R. On the power of quantum computation[J]. SIAM Journal on Computing, 1997, 26(5): 1474–1483. doi:  10.1137/S0097539796298637
    [27] KUWAKADO H and MORII M. Security on the quantum-type even-mansour cipher[C]. 2012 International Symposium on Information Theory and its Applications, Honolulu, USA, 2012: 312–316.
    [28] KAPLAN M, LEURENT G, LEVERRIER A, et al. Breaking symmetric cryptosystems using quantum period finding[C]. The 36th Annual International Cryptology Conference, Santa Barbara, USA, 2016: 207–237.
    [29] BONNETAIN X. Quantum key-recovery on full AEZ[C]. The 24th International Conference on Selected Areas in Cryptography, Ottawa, Canada, 2018: 394–406.
    [30] LEANDER G and MAY A. Grover meets simon - quantumly attacking the FX-construction[C]. The 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017: 161–178.
    [31] ZHANDRY M. How to construct quantum random functions[C]. The 53rd IEEE Annual Symposium on Foundations of Computer Science, New Brunswick, USA, 2012: 679–687.
    [32] ITO G, HOSOYAMADA A, MATSUMOTO R, et al. Quantum chosen-ciphertext attacks against Feistel ciphers[C]. The Cryptographers' Track at the RSA Conference, San Francisco, USA, 2019: 391–411.
    [33] HOSOYAMADA A and SASAKI Y. Quantum demiric-selçuk meet-in-the-middle attacks: Applications to 6-round generic Feistel constructions[C]. The 11th International Conference on Security and Cryptography for Networks, Amalfi, Italy, 2018: 386–403.
    [34] DONG Xiaoyang and WANG Xiaoyun. Quantum key-recovery attack on Feistel structures[J]. Science China Information Sciences, 2018, 61(10): 102501. doi:  10.1007/s11432-017-9468-y
    [35] DONG Xiaoyang, LI Zheng, and WANG Xiaoyun. Quantum cryptanalysis on some generalized Feistel schemes[J]. Science China Information Sciences, 2019, 62(2): 22501. doi:  10.1007/s11432-017-9436-7
    [36] DONG Xiaoyang, DONG Bingyou, and WANG Xiaoyun. Quantum attacks on some Feistel block ciphers[R]. Cryptology ePrint Archive, Report 2018/504, 2018.
    [37] BONNETAIN X, NAYA-PLASENCIA M, and SCHROTTENLOHER A. On quantum slide attacks[R]. Cryptology ePrint Archive, Report 2018/1067, 2018.
    [38] HOSOYAMADA A and IWATA T. Tight quantum security bound of the 4-round luby-rackoff construction[R]. Cryptology ePrint Archive, Report 2019/243, 2019.
    [39] WAGNER D. The boomerang attack[C]. The 6th International Workshop on Fast Software Encryption, Rome, Italy, 1999: 156–170.
    [40] WANG Meiqin, WANG Xiaoyun, and HU Changhui. New linear cryptanalytic results of reduced-round of CAST-128 and CAST-256[C]. The 15th International Workshop on Selected Areas in Cryptography, Sackville, Canada, 2009: 429–441.
    [41] BOGDANOV A, LEANDER G, NYBERG K, et al. Integral and multidimensional linear distinguishers with correlation zero[C]. The 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, 2012: 244–261.
  • [1] 李伟, 高嘉浩, 杜怡然, 陈韬.  一种密码专用可编程逻辑阵列的分组密码能效模型及其映射算法, 电子与信息学报. doi: 10.11999/JEIT200079
    [2] 欧庆于, 罗芳, 叶伟伟, 周学广.  分组密码算法抗故障攻击能力度量方法研究, 电子与信息学报. doi: 10.11999/JEIT160548
    [3] 李云强, 张小勇, 王爱兰.  AES-128 Biclique结构的分布特征, 电子与信息学报. doi: 10.11999/JEIT150597
    [4] 伊文坛, 鲁林真, 陈少真.  轻量级密码算法MIBS的零相关和积分分析, 电子与信息学报. doi: 10.11999/JEIT150498
    [5] 郭瑞, 金晨辉.  低轮FOX64算法的零相关-积分分析, 电子与信息学报. doi: 10.11999/JEIT140373
    [6] 郭建胜, 崔竞一, 罗伟, 刘翼鹏.  MD-64算法的相关密钥-矩形攻击, 电子与信息学报. doi: 10.11999/JEIT150049
    [7] 刘国强, 金晨辉.  一类动态S盒的构造与差分性质研究, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.00416
    [8] 郭瑞, 金晨辉.  Lai-Massey结构伪随机特性研究, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.00870
    [9] 李艳俊, 吴文玲, 郑秀林.  SP-GFS结构的积分性质研究, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.01577
    [10] 罗伟, 郭建胜.  Eagle-128算法的相关密钥-矩形攻击, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.01239
    [11] 谢作敏, 陈少真, 鲁林真.  11轮3D密码的不可能差分攻击, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.00948
    [12] 陈韬, 罗兴国, 李校南, 李伟.  一种基于流处理框架的可重构分簇式分组密码处理结构模型, 电子与信息学报. doi: 10.3724/SP.J.1146.2014.00023
    [13] 谢作敏, 陈少真.  对7轮ARIA-192的不可能差分分析, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.01615
    [14] 崔霆, 金晨辉.  嵌套代替-扩散网络的CLEFIA结构零相关线性逼近的构造, 电子与信息学报. doi: 10.3724/SP.J.1146.2011.00475
    [15] 海昕, 唐学海, 李超.  对Zodiac算法的中间相遇攻击, 电子与信息学报. doi: 10.3724/SP.J.1146.2011.01023
    [16] 苏崇茂, 韦永壮, 马春波.  10轮3D分组密码算法的中间相遇攻击, 电子与信息学报. doi: 10.3724/SP.J.1146.2011.00888
    [17] 崔霆, 金晨辉.  (2n,r,t)_GFNSP结构一类不可能差分对的构造方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2009.01494
    [18] 陈少真, 鲁林真.  对8轮ARIA算法的差分枚举攻击, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.01292
    [19] 唐学海, 李超, 王美一, 屈龙江.  3D密码的不可能差分攻击, 电子与信息学报. doi: 10.3724/SP.J.1146.2009.01375
    [20] 肖皇培, 张国基.  Rijndael算法的代数方程系统改进, 电子与信息学报. doi: 10.3724/SP.J.1146.2007.00533
  • 加载中
  • 图(10) / 表ll (4)
    计量
    • 文章访问数:  886
    • HTML全文浏览量:  316
    • PDF下载量:  42
    • 被引次数: 0
    出版历程
    • 收稿日期:  2019-08-26
    • 修回日期:  2019-11-26
    • 网络出版日期:  2019-11-29
    • 刊出日期:  2020-02-19

    目录

      /

      返回文章
      返回

      官方微信,欢迎关注