高级搜索

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

倪博煜 董晓阳

引用本文: 倪博煜, 董晓阳. 改进的Type-1型广义Feistel结构的量子攻击及其在分组密码CAST-256上的应用[J]. 电子与信息学报, doi: 10.11999/JEIT190633 shu
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, doi: 10.11999/JEIT190633 shu

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

    作者简介: 董晓阳: 男,1988年生,助理研究员。研究方向为对称密码算法的安全性分析与设计
    通讯作者: 董晓阳,xiaoyangdong@tsinghua.edu.cn
  • 基金项目: 国家重点研发计划(2017YFA0303903),国家自然科学基金(61902207),国家密码发展基金(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的量子密钥恢复攻击。

English

    1. [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. [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. [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. [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, 2015: 433–454.

    5. [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. [6]

      National Soviet Bureau of Standards. GOST 28147-89 Information processing systems. cryptographic protection cryptographic transformation algorithm[S]. 1989.

    7. [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. [8]

      ANDERSON R and BIHAM E. Two practical and provably secure block ciphers: BEAR and LION[C]. The Third International Workshop on Fast Software Encryption, Cambridge, UK, 1996: 113–120.

    9. [9]

      LUCKS S. Faster luby-rackoff ciphers[C]. The Third International Workshop on Fast Software Encryption, Cambridge, UK, 1996: 189–203.

    10. [10]

      SCHNEIER B and KELSEY J. Unbalanced Feistel networks and block cipher design[C]. The Third International Workshop on Fast Software Encryption, Cambridge, UK, 1996: 121–144.

    11. [11]

      First AES Candidate Conference[EB/OL]. http://csrc.nist.gov/archive/aes/round1/conf1/aes1conf.htm.

    12. [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. [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. [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. [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. [16]

      HOANG V T and ROGAWAY P. On generalized Feistel networks[C]. The 30th Annual Cryptology Conference, Santa Barbara, USA, 2010: 613–630.

    17. [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. [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. [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. [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. [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. [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. [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. [24]

      GROVER L K. A fast quantum mechanical algorithm for database search[C]. The Twenty-eighth Annual ACM Symposium on Theory of Computing, Philadelphia, USA, 1996: 212–219.

    25. [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. [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. [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. [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. [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. [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. [31]

      ZHANDRY M. How to construct quantum random functions[C]. 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, New Brunswick, USA, 2012: 679–687.

    32. [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. [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. [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. [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. [36]

      DONG Xiaoyang, DONG Bingyou, and WANG Xiaoyun. Quantum attacks on some Feistel block ciphers[R]. Cryptology ePrint Archive, Report 2018/504, 2018.

    37. [37]

      BONNETAIN X, NAYA-PLASENCIA M, and SCHROTTENLOHER A. On quantum slide attacks[R]. Cryptology ePrint Archive, Report 2018/1067, 2018.

    38. [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. [39]

      WAGNER D. The boomerang attack[C]. The 6th International Workshop on Fast Software Encryption, Rome, Italy, 1999: 156–170.

    40. [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. [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.

    42. [42]

      SANTOLI T and SCHAFFNER C. Using simon's algorithm to attack symmetric-key cryptographic primitives[J]. Quantum Information and Computation, 2017, 17(1/2): 65–78.

    1. [1]

      任炯炯, 李航, 陈少真. 减轮Simeck算法的积分攻击. 电子与信息学报,

    2. [2]

      李付鹏, 刘敬彪, 王光义, 王康泰. 基于混沌集的图像加密算法. 电子与信息学报,

    3. [3]

      黄海, 冯新新, 刘红雨, 厚娇, 赵玉迎, 尹莉莉, 姜久兴. 基于随机加法链的高级加密标准抗侧信道攻击对策. 电子与信息学报,

    4. [4]

      陈艳浩, 刘中艳, 周丽宴. 基于差异混合掩码与混沌Gyrator变换的光学图像加密算法. 电子与信息学报,

    5. [5]

      王旭, 谢菊兰, 何子述, 李会勇. 一种基于空频结构与空时结构权值转换的精确宽带波束赋形算法. 电子与信息学报,

    6. [6]

      伊鹏, 谢记超, 张震, 谷允捷, 赵丹. 抗侧信道攻击的服务功能链部署方法. 电子与信息学报,

    7. [7]

      路新华, MANCHÓNCarles Navarro, 王忠勇, 张传宗. 大规模MIMO系统上行链路时间-空间结构信道估计算法. 电子与信息学报,

    8. [8]

      陈鸿昶, 明拓思宇, 刘树新, 高超. 基于整数线性规划重构抽象语义图结构的语义摘要算法. 电子与信息学报,

    9. [9]

      刘浩然, 张力悦, 范瑞星, 王海羽, 张春兰. 基于改进鲸鱼优化策略的贝叶斯网络结构学习算法. 电子与信息学报,

    10. [10]

      杨英杰, 冷强, 常德显, 潘瑞萱, 胡浩. 基于属性攻击图的网络动态威胁分析技术研究. 电子与信息学报,

    11. [11]

      杨英杰, 冷强, 潘瑞萱, 胡浩. 基于属性攻击图的动态威胁跟踪与量化分析技术研究. 电子与信息学报,

    12. [12]

      于涵, 水鹏朗, 施赛楠, 杨春娇. 广义Pareto分布海杂波模型参数的组合双分位点估计方法. 电子与信息学报,

    13. [13]

      申滨, 吴和彪, 崔太平, 陈前斌. 基于最优索引广义正交匹配追踪的非正交多址系统多用户检测. 电子与信息学报,

    14. [14]

      李海, 李怡静, 吴仁彪. 载机偏航下基于广义相邻多波束自适应处理的低空风切变风速估计. 电子与信息学报,

    15. [15]

      李如春, 程云霄, 覃亚丽. 稀疏信号结构性噪声干扰下的感知矩阵优化. 电子与信息学报,

    16. [16]

      庄陵, 关鹃, 马靖怡, 王光宇. 一种基于结构优化的FIR滤波器舍入噪声性能改进方案. 电子与信息学报,

    17. [17]

      费高雷, 张亚萌, 胡志宇, 周磊, 胡光岷. 基于网络结构特征的IP所属区域识别. 电子与信息学报,

    18. [18]

      谷允捷, 胡宇翔, 谢记超. 基于重叠网络结构的服务功能链时空优化编排策略. 电子与信息学报,

    19. [19]

      牛淑芬, 王金风, 王伯彬, 贾向东, 杜小妮. 区块链上基于B+树索引结构的密文排序搜索方案. 电子与信息学报,

    20. [20]

      王艳, 薛改娜, 李顺波, 惠飞飞. 一类新的周期为2pmq阶二元广义分圆序列的线性复杂度. 电子与信息学报,

  • 图 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]qCPA$2d - 1$ 5791113
    4.1节qCPA$3d - 3$ 69121518
    4.2节qCCA$3d - 2$710131619
    下载: 导出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
  • 加载中
图(10)表(4)
计量
  • PDF下载量:  6
  • 文章访问数:  69
  • HTML全文浏览量:  53
文章相关
  • 通讯作者:  董晓阳, xiaoyangdong@tsinghua.edu.cn
  • 收稿日期:  2019-08-26
  • 录用日期:  2019-11-26
  • 网络出版日期:  2019-11-29
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章