杨 阳 刘文豪 曾 光
(信息工程大学密码工程学院 郑州 450000)
2008年，Nakahara[1]在CANS2008上提出3D密码。3D密码可视为3维的AES算法，将 4 ×4的字节矩阵扩展为 4×4×4，分组长度和密钥规模均为512 bit，共22轮。
3D密码设计理念新颖，对它的安全性分析自提出起持续至今。2010年王美一等人[2]提出了9轮3D密码的Square攻击，唐学海等人[3]给出了9轮不可能差分攻击，之后Nakahara[4]将不可能差分攻击提升到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密码的攻击的同时，可以发现上述攻击使用的区分器轮数均小于7轮。Square攻击使用了5.25轮、6.25轮区分器，11轮3D密码的不可能差分和中间相遇攻击均构造出6轮区分器，且区分优势均为 2−504，区分3D密码与随机函数所需数据量不低于 2252.5。7轮3D密码的yoyo攻击使用了6轮yoyo区分器。为突破现有的区分器轮数，本文研究子空间迹分析方法在3D密码上的应用。
2016年，Grassi等人[10]提出了子空间迹的概念。子空间迹不强调子空间结构在轮函数下的不变性，而是表现了子空间结构在轮函数下变化的规律，进而利用具有一定规律的子空间迹建立区分器。自提出以来，子空间迹主要用于对AES,Midori等SPN密码算法的分析[11]，利用该方法在构造区分器或进行密钥恢复时，不需要S盒的具体信息。
下面描述基于子空间迹的区分器—结构区分器。
2017年文献[12]利用子空间迹，找到了AES的新性质——穷举子空间Di的全部明文对，经过5轮加密，将有固定倍数个密文对的差分属于子空间MJ(子空间Di和MJ将在第3节中定义)。将这样的“n倍”性质与明确子空间迹结合，构造出5轮AES子空间迹结构区分器。同年，Grassi[13]给出了基于AES结构区分器的混合差分攻击。2019年Boura等人[14]给出了结构区分器的构造条件。2020年，Grassi等人[15]利用子空间迹给出9轮AES-128的选择密钥区分器。2021年，Grassi等人[16]对P-SPN结构及Hades结构进行子空间迹分析并给出判断线性层是否易受攻击的工具。
子空间迹分析方法在构造区分器上有独特的优势，往往可以找到轮数更长的区分器。本文将基于子空间的性质，寻找3D密码的7轮区分器。
第2节介绍3D密码算法，定义其子空间并研究子空间传播规律；
第3节证明了3D密码两个子空间交集为0，由此给出在选择明文条件下，区分优势最大的6轮3D密码差分区分器，进一步给出首个7轮3D密码的子空间迹不可能差分区分器；
第4节介绍兼容、信息集、等价关系的定义及相关定理，说明了3D密码特定子空间与S层的可兼容性，据此给出3D密码的7轮结构区分器；
第5节总结成果并提出开放性问题。
2.1 3D密码算法
3D密码算法的分组规模和密钥规模都是512 bit，迭代轮数为22轮。分组状态表示为64 Byte的形式，可视为4个子块的联结
3D算法采用SPN结构，轮函数依次由非线性变换、行移位、列混合变换、密钥异或这4个变换组成。具体介绍如下。
非线性变换γ。使用AES的8 bit S盒。
行移位θ1, θ2。θ1是 对3D密码的4个子块做AES的行移位变换，θ2是将字节块视为一个整体进行行移位。θ1将式(1)中的状态矩阵变为
密钥异或KeyAdd。将状态矩阵与轮子密钥对应字节进行模2加运算。
密钥扩展算法与子空间迹分析无关，在此不做介绍。记Ek和Ek′分别表示奇数轮和偶数轮加密函数，旨在突出两种行移位变换，不区分圈子密钥。使用Fkm表示m轮3D密码加密函数。a加密一轮的结果为Fk(a)=π·θ·γ·KeyAdd(a)。为保证3D密码算法加脱密相似性，算法在最后一轮省略列混合变换。
2.2 3D密码的子空间与传播规律
本节研究3D密码子空间的交集性质，寻找交集为{0}的两个子空间，构造出区分优势最大的6轮3D密码不可能差分区分器。文献[10]介绍了一种将密钥恢复攻击转化成区分器的技术，能把基于子空间迹区分器的攻击变为新区分器，从而延长区分器轮数。将这种技术应用于3D密码，首次构造出3D密码的7轮子空间迹不可能差分区分器。
3.1 3D密码子空间的交集性质及6轮子空间迹不可能差分区分器
研究子空间的交集性质对子空间迹分析有重要意义，根据迹端点的交集属性，可以得到较长迹的可预测子空间属性，原因是两个子空间的交集经过密码函数时，交集属性被保持。而交集能够降低子空间的维数，故精确地刻画一个子空间是哪些子空间的交集，并以交集的形式进行传播，能有效降低子空间经过密码函数时增长的维数，从而寻找到更长的子空间迹。先定义两个新的子空间。
结合引理2，得到3D密码的一条6轮子空间迹不可能差分
截断不可能差分区分器从终点差分矩阵脱密到中间差分矩阵，再与起始差分加密得到的中间状态产生矛盾。为延长区分器，一般终点差分矩阵只有一个变量，例如3D密码的6轮截断不可能差分区分器[7]，其区分优势为 28/2512≈2−504，与3D密码的6轮中间相遇区分器[8]区分优势相同。
而子空间迹不可能差分区分器在中间矛盾处，利用的是两个子空间交集为{0}的性质，且后几轮为明确子空间迹，维数保持不变，故终点子空间的差分变量更多。上面给出的3D密码的6轮子空间迹不可能差分区分器的区分优势为24×4×8/2512≈2−384，这是目前选择明文条件下区分优势最大的6轮3D密码区分器。
注意到，上面的子空间迹不可能差分区分器与密码规模、S盒和密钥的具体信息无关，即对带一个秘密S盒的3D密码同样有效。
3.2 3D密码的7轮子空间迹不可能差分区分器
根据2.2节给出的3D密码子空间传播规律及引理5得到一条3D密码的子空间迹
为计算区分器的数据复杂度，首先介绍“生日悖论”，寻找所需输入明文的最小数目，以保证在随机情形中以高概率产生碰撞。
给定d值和n个变量，其中至少两个变量具有相同值的概率可以计算为
下面计算该区分器所需数据量及时间复杂度。
实验数据表明，256次碰撞中有63.8%的概率得到正确密钥对应的明文对。当函数为3D密码时，修改该明文对第 0 Byte、第5 Byte以外的值并加密，不会得到碰撞。512次碰撞对应概率为87.8%。
以256次碰撞为区分界限，使用 2193.1个选择明文，将以95%的概率得到256次碰撞，有63.8%的概率将7轮3D密码与随机函数区分开。故该3D密码的7轮子空间迹不可能差分区分器的数据复杂度为2193.1个 选择明文，成功率为9 5%×63.8%=60.6%。
最后给出3D密码的7轮子空间迹不可能差分区分器的具体算法：
离线阶段。建立表格T，存储S(x)⊕02x·S(y)⊕S(z)⊕02x·S(w)=0全部解。
步骤1 随机选择明密对，检测经逆列混合变换后的密文对差分是否属于子空间(IDi, IDi, IDi, IDi)，其中i=0,1,2,3。
若无碰撞且已经使用2193.1个明密对，输出1，否则返回步骤1；
若产生碰撞，进入步骤2；
步骤2 排除明文对与表格T中的解异或后的密钥值。若全部密钥被排除，输出0；
否则，返回步骤1。
第3节研究了3D密码子空间交集性质，给出了3D密码的7轮子空间迹不可能差分区分器，下面给出兼容、信息集、等价等概念的定义及相关定理，利用3 D 密码子空间与S 层的可兼容性，得到“n倍”性质并给出3D密码的7轮区分器。现有密码的结构区分器长度均不超过5轮，这是目前轮数最长的结构区分器。
4.1 兼容、信息集与等价关系
令d为S 盒操作在二元域F2上的扩张系数，Q=F2d，对于3D密码，d=8。设SPN密码作用于N个字，每个字的规模等于S盒的规模，则状态矩阵和圈密钥可表示为 QN上的向量，SPN密码的圈函数为R=K ◦L ◦S。
S是字节代替层，对状态矩阵中的比特块做非线性变换，{f0, f1,..., fN−1}为 QN一组基。
L是 QN上的一个F2- 线性双射。Q→Q。
K是轮密钥加操作，将内部状态与轮密钥异或。
定义5(兼容)[14]设V是 QN的子空间，如果V存在一组基在{f0, f1,..., fN−1}上表示为块对角矩阵时，则V与S兼容，并且称这类基为V的兼容基。
根据兼容的定义，文献[14]给出了信息集、等价关系的定义，并证明当存在与S层兼容的子空间时，密码算法有“n倍”性质，可以构造结构区分器，进一步给出结构区分器的构造条件。
根据子空间 (Mi, Mj, Ms, Mt)与S层的可兼容性，结合定理1，容易得到引理6。证明思路是交换碰撞对的某几列，得到等价消息对，结合定理1，等价消息对加密一轮差分相等，即仍然碰撞。
命题1说明当子空间V与S层兼容时，穷举V一个陪集中全部明文对并加密，差分属于同一子空间的密文对个数总是 2h−1的倍数，这种规律被称为密码算法的“n倍性质”。
4.2 3D密码的7轮结构区分器
以碰撞数模 215的数值作为区分依据，定理2说明穷举 (Di, Di, Di, Di)+a全部明文对，7轮3D密码得到的碰撞数模 215为0，而随机函数的碰撞数模 215为0的概率为2−15。区分成功的概率为1−2−15，大于99.99%，且利用的性质与密钥无关。需要3·2128≈2129.6次查表操作，存储复杂度为2128Byte。
本文对3D密码进行子空间迹分析，研究子空间传播规律，首先利用找到的3轮明确子空间迹，结合子空间的交集性质，构造了7轮3D密码的子空间迹不可能差分区分器。然后利用与S层兼容的子空间，给出了3D密码的7轮结构区分器，为基于子空间迹的攻击提供了基础。本文寻找子空间迹不可能差分区分器与结构区分器的方法，适用于任何SPN密码。
在利用子空间迹分析3D密码的过程中，发现其在寻找区分器上拥有优势。首先，截断不可能差分相比与子空间迹不可能差分，前者利用的中间相遇思想是从维数较小的终点差分矩阵脱密，在中间产生矛盾，因此区分优势较小，而后者利用的矛盾是两个子空间交集为{0}，脱密过程是一条明确子空间迹，维数保持不变，区分优势往往更大。结构区分器的原理是当输入子空间与S层兼容时，等价消息对经过一轮加密函数，差分为常数，这是SPN结构密码的新性质，但对明确子空间迹依赖很强，例如AES只有5轮结构区分器，而3D密码存在3轮明确子空间迹，故可以构造7轮结构区分器。
因此能否得到子空间迹区分器与明确子空间迹的关系，给出基于子空间迹攻击的轮数的下界是有待解决的问题。
猜你喜欢明文轮子区分你能区分平衡力与相互作用力吗中学生数理化·八年级物理人教版(2023年3期)2023-03-21两个轮子“走路”小学科学(学生版)(2021年7期)2021-07-28没有轮子的挖挖幼儿园(2020年22期)2020-03-29读北岛：一只轮子，寻找另一只轮子中学语文(2019年31期)2019-12-05奇怪的处罚民间故事选刊·上(2018年1期)2018-01-02教你区分功和功率中学生数理化·八年级物理人教版(2017年6期)2017-11-09怎祥区分天空中的“彩虹”(一)百科探秘·航空航天(2016年5期)2016-11-07奇怪的处罚小小说月刊·下半月(2016年6期)2016-05-14四部委明文反对垃圾焚烧低价竞争中国资源综合利用(2016年11期)2016-01-22罪数区分的实践判定中国检察官(2015年12期)2015-02-27