1、3D密码的7轮子空间迹区分器杨 阳 刘文豪*曾 光(信息工程大学密码工程学院 郑州 450000)2193:12202:360:6%21282129:6212899:99%摘 要：子空间迹攻击是一种新型分组密码分析方法，该文对使用了类AES密码新结构的3D密码子空间性质进行研究。首先利用3D密码的3轮明确子空间迹，结合子空间的交集性质，首次构造出3D密码的7轮子空间迹不可能差分区分器，数据复杂度为个选择明文，时间复杂度为次查表操作，成功率为；“n倍”性质指子空间的全部明文对经过一轮加密，差分属于同一子空间的密文对个数为n的倍数。利用该性质，构造了3D密码的7轮结构区分器，数据复杂度为个选择明文
2、，时间复杂度为次查表操作，存储复杂度为 Byte，成功率大于。关键词：子空间迹；不可能差分；结构区分器；3D密码中图分类号：TN918.1文献标识码：A文章编号：1009-5896(2023)02-0617-09DOI:10.11999/JEIT2114387-round Subspace Trail Distinguisher of 3D CipherYANG Yang LIU Wenhao ZENG Guang(School of Cryptography Engineering,Information Engineering University,Zhengzhou 450000,Chi
3、na)2193.12202.360.6%21282129.6212899.99%Abstract:Subspace trail attack is a new analysis method for block ciphers.The properties of subspaces of 3Dcipher which uses a new structure of AES-like ciphers is studied.First of all,a 3-round definite subspace trail of3Dcipher is constructed in this paper,c
4、ombined with the intersection property of subspaces,and the 7-roundsubspace trail impossible differential distinguisher of 3D cipher is obtained for the first time.Its datacomplexity is chosen plaintexts，time complexity is look-up operations,and the success rate is.The multiple-of-n property means t
5、hat all plaintext pairs in the subspace undergo a round ofencryption，and the number of ciphertext pairs whose differences belong to a certain subspace is a multiple ofn.Using this property，a 7-round structural distinguisher of 3D cipher is constructed.The data complexity is chosen plaintexts，the tim
6、e complexity is look-up operations,the storage complexity is Byte，and the success rate is greater than.Key words:Subspace trail;Impossible difference;Structural distinguisher;3D cipher 1 引言4 44 4 42008年，Nakahara1在CANS2008上提出3D密码。3D密码可视为3维的AES算法，将的字节矩阵扩展为，分组长度和密钥规模均为512 bit，共22轮。3D密码设计理念新颖，对它的安全性分析自提
7、出起持续至今。2010年王美一等人2提出了9轮3D密码的Square攻击，唐学海等人3给出了9轮不可能差分攻击，之后Nakahara4将不可能差分攻击提升到10轮。2012年，苏崇茂等人5构造出3D密码的5轮中间相遇区分器，给出了10轮中间相遇攻击，Koyama等人6于同年给出11轮3D密码的截断差分分析，成功率约为24%。2014年，谢作敏等人7给出了11轮3D密码的不可能差分攻击。2015年，任炯炯等人8给出了11轮3D密码的中间相遇攻击。2021年，Hou等人9利用3D密码的6轮yoyo区分器，给出了实际可行的7轮3D密码算法的密钥恢复攻击。在关注对3D密码的攻击的同时，可以发现上述攻击
8、使用的区分器轮数均小于7轮。Square攻击使用了5.25轮、6.25轮区分器，11轮3D密码的不可能差分和中间相遇攻击均构造出6轮区分器，且区 收稿日期：2021-12-06；改回日期：2022-06-13；网络出版：2022-06-30*通信作者：刘文豪基金项目：数学工程与先进计算国家重点实验室开放基金课题(2020A08)Foundation Item:The Open Fund Project of the State KeyLaboratory of Mathematical Engineering and Advanced Compu-ting(2020A08)第45卷第2期电 子
9、 与 信 息 学 报Vol.45No.22023年2月Journal of Electronics&Information TechnologyFeb.202325042252.5分优势均为，区分3D密码与随机函数所需数据量不低于。7轮3D密码的yoyo攻击使用了6轮yoyo区分器。为突破现有的区分器轮数，本文研究子空间迹分析方法在3D密码上的应用。2016年，Grassi等人10提出了子空间迹的概念。子空间迹不强调子空间结构在轮函数下的不变性，而是表现了子空间结构在轮函数下变化的规律，进而利用具有一定规律的子空间迹建立区分器。自提出以来，子空间迹主要用于对AES,Midori等SPN密码算法
10、的分析11，利用该方法在构造区分器或进行密钥恢复时，不需要S盒的具体信息。下面描述基于子空间迹的区分器结构区分器。DiMJDiMJ2017年文献12利用子空间迹，找到了AES的新性质穷举子空间的全部明文对，经过5轮加密，将有固定倍数个密文对的差分属于子空间(子空间和将在第3节中定义)。将这样的“n倍”性质与明确子空间迹结合，构造出5轮AES子空间迹结构区分器。同年，Grassi 1 3 给出了基于AES结构区分器的混合差分攻击。2019年Boura等人14给出了结构区分器的构造条件。2020年，Grassi等人15利用子空间迹给出9轮AES-128的选择密钥区分器。2021年，Grassi等人
11、16对P-SPN结构及Hades结构进行子空间迹分析并给出判断线性层是否易受攻击的工具。子空间迹分析方法在构造区分器上有独特的优势，往往可以找到轮数更长的区分器。本文将基于子空间的性质，寻找3D密码的7轮区分器。第2节介绍3D密码算法，定义其子空间并研究子空间传播规律；第3节证明了3D密码两个子空间交集为0，由此给出在选择明文条件下，区分优势最大的6轮3D密码差分区分器，进一步给出首个7轮3D密码的子空间迹不可能差分区分器；第4节介绍兼容、信息集、等价关系的定义及相关定理，说明了3D密码特定子空间与S层的可兼容性，据此给出3D密码的7轮结构区分器；第5节总结成果并提出开放性问题。2 初步准备
12、2.1 3D密码算法3D密码算法的分组规模和密钥规模都是512 bit，迭代轮数为22轮。分组状态表示为64 Byte的形式，可视为4个子块的联结s0s4s8s12s1s5s9s13s2s6s10s14s3s7s11s15?s16s20s24s28s17s21s25s29s18s22s26s30s19s23s27s31?s32s36s40s44s33s37s41s45s34s38s42s46s35s39s43s47?s48s52s56s60s49s53s57s61s50s54s58s62s51s55s59s63(1)3D算法采用SPN结构，轮函数依次由非线性变换、行移位、列混合变换、密钥异或这
13、4个变换组成。具体介绍如下。非线性变换。使用AES的8 bit S盒。1,2121行移位。是对3D密码的4个子块做AES的行移位变换，是将字节块视为一个整体进行行移位。将式(1)中的状态矩阵变为s0s4s8s12s5s9s13s1s10s14s2s6s15s3s7s11?s16s20s24s28s21s25s29s17s26s30s18s22s31s19s23s27?s32s36s40s44s37s41s45s33s42s46s34s38s47s35s39s43?s48s52s56s60s53s57s61s49s58s62s50s54s63s51s55s592将式(1)中的状态矩阵变为s0s4
14、s8s12s17s21s25s29s34s38s42s46s51s55s59s63?s16s20s24s28s33s37s41s45s50s54s58s62s3s7s11s15?s32s36s40s44s49s53s57s61s2s6s10s14s19s23s27s31?s48s52s56s60s1s5s9s13s18s22s26s30s35s39s43s4712应用于奇数轮，应用于偶数轮。F4428MM(si,si+1,si+2,si+3)(si,si+1,si+2,si+3)i=0,4,.,60MM1列混合变换。使用上对合矩阵对状态中每一列进行有限域上乘法，即，其中，及其逆矩阵为618电
15、子 与 信 息 学 报第 45 卷M=01x02x04x06x02x01x06x04x04x06x01x02x06x04x02x01x,M1=01x02x04x06x02x01x06x04x04x06x01x02x06x04x02x01x。密钥异或KeyAdd。将状态矩阵与轮子密钥对应字节进行模2加运算。EkEkFmkaFk(a)=KeyAdd(a)密钥扩展算法与子空间迹分析无关，在此不做介绍。记和分别表示奇数轮和偶数轮加密函数，旨在突出两种行移位变换，不区分圈子密钥。使用表示m轮3D密码加密函数。加密一轮的结果为。为保证3D密码算法加脱密相似性，算法在最后一轮省略列混合变换。2.2 3D密码
16、的子空间与传播规律首先介绍子空间迹的定义。FK()=F()K(V1,V2,.,Vr+1)dim(Vi)dim(Vj)1 i j r+1Fn2aiViai+1Vi+1FK(Vi ai)Vi+1 ai+1(V1,V2,.,Vr+1)FKV1V2.Vr+1ViVi+1Vi+1ViUFK VVF1K UU V定义110设为某分组密码的轮函数，为满足，的r+1个子空间且他们包含于。若任意属于，存在属于，使得包 含 于，则 称为的长度为r的子空间迹，记为。称为的前驱，为的后继。若，且有，将这样加、脱密都以概率1成立的子空间迹称为明确子空间迹，记为。i,j,h3D密码可以视作3维的AES密码算法，因此，可利用文献10中的AES子空间刻画3D密码的子空间，并研究子空间传播规律。下面若不特别说明，下标为正整数，取值范围均为0,3。F4428F(V)=F(v)|v V 对于向量空间V和上的函数F，令。本文所有的子空间都定义为域F28F4428E=e0,0,0,e0,0,1,.,e3,3,3=e0,e1,.,e63F44428ei,j,hijh上空间的子空间。另外，记为的单位基空间，其中，是第 子块的第 行
