SPN型密码的通用子空间迹分析
作者:
作者简介:

宋蝉(1997-),女,博士生,主要研究领域为认证加密算法的分析与设计.;张蕾(1981-),女,博士,副研究员,主要研究领域为分组密码算法的设计与分析.;吴文玲(1966-),女,博士,研究员,博士生导师,主要研究领域为对称密码算法的设计与分析.

通讯作者:

宋蝉,E-mail:songchan2020@iscas.ac.cn;张蕾,E-mail:zhanglei@iscas.ac.cn

中图分类号:

TP309

基金项目:

国家自然科学基金(62072445)


General Subspace Trail Cryptanalysis of SPN Ciphers
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [27]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    SPN结构是目前最广泛使用的一种分组密码整体结构, AES、ARIA等分组密码算法均采用此结构, 对此类SPN型密码的安全性分析是密码分析中的一个研究热点. 将子空间迹密码分析方法应用到典型二维SPN型密码和典型三维SPN型密码中, 可分别得到其相应的子空间迹和基于子空间迹的通用性质, 该性质与密钥、S盒以及列混淆矩阵的定义均无关, 可具体描述为: 针对一个状态可形式化为n×m二维数组的典型二维SPN型密码, 属于类对角子空间同一陪集的所有明文经过5轮加密得到的密文中属于混淆子空间同一陪集的不同密文对数量一定为$ {2^{n - 1}} $的倍数; 针对一个状态可形式化为l×n×m三维数组的典型三维SPN型密码, 属于类对角子空间同一陪集的所有明文经过7轮加密得到的密文中属于混淆子空间同一陪集的不同密文对数量一定为$ {2^{nl - 1}} $的倍数. 此外, 不仅对该性质进行了证明, 还在PHOTON算法的内部置换以及小规模版本Rijndael算法、3D算法、Saturnin算法上进行了实验验证, 结果与该性质完全一致.

    Abstract:

    SPN construction is the most widely used overall construction of block ciphers at present, which is adopted by block ciphers such as AES and ARIA. The security analysis of SPN ciphers is a research hotspot in cryptanalysis. The application of the subspace trail cryptanalysis to the typical two-dimensional SPN ciphers and typical three-dimensional SPN ciphers can yield the corresponding subspace trails and general properties based on the subspace trails separately. These properties are independent of the secret key and the detailed definitions of the S-box and MixColumns matrix. They can be specifically described as follows: For a typical two-dimensional SPN cipher whose state can be formalized into a two-dimensional array of n×m, the number of different ciphertext pairs belonging to the same coset of the mixed subspace in the ciphertexts obtained by five rounds of encryption of all plaintexts belonging to the same coset of the quasi-diagonal subspace must be a multiple of 2n–1. For a typical three-dimensional SPN cipher whose state can be formalized into a three-dimensional array of l×n×m, the number of different ciphertext pairs belonging to the same coset of the mixed subspace in the ciphertexts obtained by seven rounds of encryption of all plaintexts belonging to the same coset of the quasi-diagonal subspace must be a multiple of 2nl–1. In addition, this study not only proves these properties but also makes experimental verification on the internal permutations of PHOTON and small-scale variants of Rijndael, 3D, and Saturnin algorithms. The experimental results are completely consistent with these properties.

    参考文献
    [1] Feistel H. Cryptography and computer privacy. Scientific American, 1973, 228(5): 15–23. [doi: 10.1038/scientificamerican0573-15]
    [2] Daemen J, Rijmen V. The Design of Rijndael. Berlin: Springer, 2002.
    [3] 吴文玲, 张蕾, 郑雅菲, 李灵琛. 分组密码uBlock. 密码学报, 2019, 6(6): 690-703. [doi: 10.13868/j.cnki.jcr.000334]
    Wu WL, Zhang L, Zheng YF, Li LC. The block cipher uBlock. Journal of Cryptologic Research, 2019, 6(6): 690–703 (in Chinese with English abstract). [doi: 10.13868/j.cnki.jcr.000334]
    [4] Shannon CE. Communication theory of secrecy systems. The Bell System Technical Journal, 1949, 28(4): 656–715. [doi: 10.1002/j.1538-7305.1949.tb00928.x]
    [5] Lai XJ, Massey JL. A proposal for a new block encryption standard. In: Proc. of the 1991 Workshop on the Theory and Application of Cryptographic Techniques. Aarhus: Springer, 1991. 389–404.
    [6] Vaudenay S. On the Lai-Massey scheme. In: Proc. of the 1999 Int’l Conf. on the Theory and Application of Cryptology and Information Security. Singapore: Springer, 1999. 8–19.
    [7] Leander G, Abdelraheem MA, Alkhzaimi H, Zenner E. A cryptanalysis of PRINTcipher: The invariant subspace attack. In: Proc. of the 31st Annual Cryptology Conf. Santa Barbara: Springer, 2011. 206–221.
    [8] Leander G, Minaud B, Rønjom S. A generic approach to invariant subspace attacks: Cryptanalysis of Robin, iSCREAM and Zorro. In: Proc. of the 34th Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Sofia: Springer, 2015. 254–283.
    [9] Liu YW, Rijmen V. New observations on invariant subspace attack. Information Processing Letters, 2018, 138: 27–30. [doi: 10.1016/j.ipl.2018.01.015]
    [10] Todo Y, Leander G, Sasaki Y. Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and midori64. Journal of Cryptology, 2019, 32(4): 1383–1422. [doi: 10.1007/s00145-018-9285-0]
    [11] Beierle C, Canteaut A, Leander G, Rotella Y. Proving resistance against invariant attacks: How to choose the round constants. In: Proc. of the 37th Annual Int’l Cryptology Conf. Santa Barbara: Springer, 2017. 647–678.
    [12] Wei YZ, Ye T, Wu WL, Pasalic E. Generalized nonlinear invariant attack and a new design criterion for round constants. IACR Transactions on Symmetric Cryptology, 2018, 2018(4): 62–79. [doi: 10.13154/tosc.v2018.i4.62-79]
    [13] Grassi L, Rechberger C, Rønjom S. Subspace trail cryptanalysis and its applications to AES. IACR Transactions on Symmetric Cryptology, 2017, 2016(2): 192–225. [doi: 10.13154/tosc.v2016.i2.192-225]
    [14] Grassi L, Rechberger C, Rønjom S. A new structural-differential property of 5-round AES. In: Proc. of the 36th Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Paris: Springer, 2017. 289–317.
    [15] Boura C, Canteaut A, Coggia D. A general proof framework for recent AES distinguishers. IACR Transactions on Symmetric Cryptology, 2019, 2019(1): 170–191. [doi: 10.13154/tosc.v2019.i1.170-191]
    [16] Cui T, Jin CH. Finding impossible differentials for Rijndael-like and 3D-like Structures. KSII Transactions on Internet and Information Systems, 2013, 7(3): 509–521. [doi: 10.3837/tiis.2013.03.006]
    [17] Guo J, Peyrin T, Poschmann A. The PHOTON family of lightweight hash functions. In: Proc. of the 31st Annual Cryptology Conf. Santa Barbara: Springer, 2011. 222–239.
    [18] Nakahara Jr J. 3D: A three-dimensional block cipher. In: Proc. of the 7th Int’l Conf. Hong Kong: Springer, 2008. 252–267.
    [19] Canteaut A, Duval S, Leurent G, Naya-Plasencia M, Perrin L, Pornin T, Schrottenloher A. Saturnin: A suite of lightweight symmetric algorithms for post-quantum security. IACR Transactions on Symmetric Cryptology, 2020, 2020(S1): 160–207. [doi: 10.13154/tosc.v2020.iS1.160-207]
    [20] Shen X, Liu GQ, Sun B, Li C. Impossible differentials of SPN ciphers. In: Proc. of the 12th Int’l Conf. on Information Security and Cryptology. Beijing: Springer, 2017. 47–63.
    [21] Liu Y, Shi YF, Gu DW, Dai B, Zhao FY, Li W, Liu ZQ, Zeng ZQ. Improved impossible differential cryptanalysis of large-block Rijndael. Science China Information Sciences, 2019, 62(3): 32101. [doi: 10.1007/s11432-017-9365-4]
    [22] Li YJ, Wu WL. Improved integral attacks on Rijndael. Journal of Information Science and Engineering, 2011, 27(1): 2031–2045.
    [23] 谢作敏, 陈少真, 鲁林真. 11轮3D密码的不可能差分攻击. 电子与信息学报, 2014, 36(5): 1215–1220. [doi: 10.3724/SP.J.1146.2013.00948]
    Xie ZM, Chen SZ, Lu LZ. Impossible differential cryptanalysis of 11-round 3D cipher. Journal of Electronics & Information Technology, 2014, 36(5): 1215–1220 (in Chinese with English abstract). [doi: 10.3724/SP.J.1146.2013.00948]
    [24] 王美一, 唐学海, 李超, 屈龙江. 3D密码的Square攻击. 电子与信息学报, 2010, 32(1): 157–161. [doi: 10.3724/SP.J.1146.2008.01846]
    Wang MY, Tang XH, Li C, Qu LJ. Square attacks on 3D cipher. Journal of Electronics & Information Technology, 2010, 32(1): 157–161 (in Chinese with English abstract). [doi: 10.3724/SP.J.1146.2008.01846]
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

宋蝉,张蕾,吴文玲. SPN型密码的通用子空间迹分析.软件学报,2023,34(12):5807-5821

复制
分享
文章指标
  • 点击次数:591
  • 下载次数: 2428
  • HTML阅读次数: 1322
  • 引用次数: 0
历史
  • 收稿日期:2022-03-26
  • 最后修改日期:2022-06-28
  • 在线发布日期: 2023-04-19
  • 出版日期: 2023-12-06
文章二维码
您是第19985776位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号