动态密码结构抵抗差分密码分析能力评估

王念平，郭祉成

（信息工程大学，河南 郑州 450001）

1 引言

随着分组密码研究的不断深入，一些学者为了提高分组密码算法的安全性，提出了动态分组密码算法[1-10]，这就为分组密码算法的设计提供了一条新的思路。“动态”是指分组密码算法的某些组件（例如S 盒、扩散层或轮函数等）有多种选择，或者说这些密码组件是动态可变的。但必须指出，这些动态分组密码算法的抗攻击能力很大程度上取决于所采用的分组密码结构的抗攻击能力，因此，对动态分组密码结构（即某些密码组件动态可变的分组密码结构）的研究具有重要的意义。

另一方面，差分密码分析[11]是攻击分组密码最有效的方法之一，对分组密码抵抗差分密码分析的能力进行评估一直都是密码学研究的热点。如果分组密码的最大差分特征概率足够小，就可以认为该分组密码能够抵抗差分密码分析。在评估分组密码抵抗差分密码分析的能力时，研究方法通常是给出多轮差分特征中活动轮函数或活动S 盒个数的下界，进而给出最大差分特征概率的上界。

一般来说，将分组密码结构的某些组件（例如S 盒、扩散层或轮函数等）动态化，就可以构成动态分组密码结构，但如果这些组件设计不当，就有可能导致动态分组密码结构中的某些密码结构抗攻击能力较弱。这样，密码分析者就有可能针对这一较弱的结构进行攻击，从而带来意想不到的后果。因此，在设计动态分组密码结构时，一定要尽量保证动态密码结构中的任一结构具有相同或相近的抗攻击能力，避免出现某一结构抗攻击能力较弱的情况。

基于上述的想法，本文根据差分传递规律，提出一种动态密码结构，并对其抵抗差分密码分析的能力进行了详细的评估，给出了多轮差分特征中活动轮函数个数的下界。该动态密码结构的特点是第6t(∀t≥ 1)轮中的扩散层可以从{0,1}4上的多个线性双射（对应于4 阶0-1 可逆矩阵）中任意选取，即6t(∀t≥ 1)轮中的扩散层是动态可变的。这里所说的“扩散层”是指整体结构中的扩散层，而不是轮函数中的扩散层。需要强调的是，本文提出的动态密码结构中的扩散层并不是随意选取的，也并非涵盖所有的4 阶0-1 可逆矩阵，而是根据差分传递规律设计的。扩散层的设计是本文的创新之处，给出多轮差分特征中活动轮函数个数的下界是本文首要解决的问题。

目前，与动态分组密码结构有关的研究主要有以下2 个方面。1) 对动态分组密码的设计思想和设计方法进行研究和探讨[1-3,12-19]。文献[1]设计了一种嵌套复用S 盒的动态密码算法，为不同用户提供不同的分组密码算法。文献[2]通过变换对称密码算法中的编制要素，实现动态对称密码算法。文献[3]提出“对称密码算法簇模型”，从混乱层和扩散层2 个方面研究分组密码的动态组件设计问题，并基于AES、Camellia、SMS4 算法给出了具体的密码算法簇，进而讨论了相应的硬件实现性能。文献[12-16]对几类动态分组密码结构的设计方法以及抵抗差分或线性密码分析的能力进行了分析。文献[17-19]通过选取不同的扩散矩阵，提升了密码算法中活动轮函数个数的下界，提高了密码算法抵抗差分或者线性密码分析能力。2) 针对具体的分组密码算法，将某些密码组件动态化，形成动态分组密码算法[4-10]。文献[4-6]基于SMS4 算法，利用时间戳动态改变算法中的固定参数，从而实现密码算法的动态化。文献[7,9-10]利用密钥控制动态可变的S 盒，能够使密码算法动态可变。文献[8]基于Feistel 结构，设计了结合密钥相关的动态S 盒和P 盒，提出了一种动态分组密码算法。除了文献[12-16]中的相应结果外，大多工作都是针对具体的密码算法中的组件（如S 盒、P 盒、某个参数等）进行研究的，针对动态分组密码结构本身的研究并不多。本文提出的动态密码结构与以上所述的这些研究都有所不同，因此本文的研究具有重要的意义。此外，动态分组密码结构的安全性研究对动态分组密码设计与分析具有重要的指导意义，可以根据本文提出的动态密码结构设计出相应的动态分组密码算法。本文对该动态密码结构进行抵抗差分密码分析，其分析结果可以保证基于该结构设计的动态分组密码算法抵抗差分密码分析的安全性，并为动态分组密码算法设计提供了一定的依据。

2 预备知识

CLEFIA 密码结构如图1 所示，它有4 个输入分支(x0,x1,x2,x3)和4 个输出分支(y0,y1,y2,y3)，每一轮中有2 个轮函数f0和f1，线性变换采用循环左移变换，其中k=(k0,k1)表示轮密钥，⊕表示异或运算。

图1 CLEFIA 密码结构

CLEFIA 变形密码结构如图2 所示，其主要特点是线性变换P（即扩散层）可以从形如的4阶0,1 可逆矩阵中任意选取，其中λi,μi∈{0,1}，0≤i≤ 4。显然，对任意给定的i,0≤i≤ 4，λi和μi都有2 种选取方法（即0 或1），故线性变换P共有 25×2=26种选取方法。

由图2 可知，CLEFIA 变形密码结构的输入与输出的关系式为

图2 CLEFIA 变形密码结构

6t+m(t≥0,0≤m≤ 5)轮基于CLEFIA 变形密码结构的动态密码结构（以下简称动态密码结构）如图3 所示，它由t个“单元”Gi（1 ≤i≤t）和m轮CLEFIA 密码结构组成。其中任一“单元”Gi（即第6i-5 轮～第6i轮，1≤i≤t，如图4 所示）由6 轮密码结构构成：前5 轮是如图1 所示的CLEFIA 密码结构，第6 轮是如图2 所示的CLEFIA变形密码结构。也就是说，6t+m轮动态密码结构中，第6 轮、第12 轮、…、第6t轮是如图2 所示的CLEFIA 变形密码结构，其他轮都是如图1 所示的CLEFIA 密码结构。需要强调的是，第6 轮、第12轮、…、第6t轮中的线性变换可以相同，也可以不同，换句话说，第6 轮、第12 轮、…、第6t轮中的线性变换是独立选取的，故6t+m（t0,0≤m≤5）轮动态密码结构共包含(25×2)t=26t种密码结构。

图3 基于CLEFIA 变形密码结构的动态密码结构

图4 “单元”Gi

定义1[20]设(X,+)和(Y,+)都是有限交换群，f:X→Y，α∈X，β∈Y，令

则称pf(α→β)为f在输入差为α条件下，输出差为β的差分概率。此外，也称α→β为f的一个差分对应，并称pf(α→β)为该差分对应的概率。其中“+”表示群(X,+)中的运算，和#{·} 都表示集合的元素个数。

定义2[20]设 (X,+)是有限交换群，，则 称的一个起点为α1，终点为αn1+的差分传递链。

定义3[21]设α→β是轮函数（包括f0和f1）的一个差分对应，若α≠0，则称该轮函数是活动的，或称该轮函数是活动轮函数。

引理1[16]对于图1 所示的CLEFIA 密码结构，设轮函数都是双射，则r（r≥ 0）轮差分特征至少有个活动轮函数。其中，rmod6表示r除以6 的最小非负余数，表示不小于x的最小整数。

3 CLEFIA 动态密码结构抵抗差分密码分析

首先，给出所有非0 输入差分经一轮CLEFIA密码结构（如图1 所示）迭代后的差分对应。

以输入差分为(0,0,1,1)=3 时的情形为例。此时，第3 分支与第4 分支输入差分不为0，CLEFIA密码结构的一轮差分对应为

其中，箭头上方括号中的1 表示轮函数f1的输入差分块为非0 差分块，即活动轮函数的个数为1。以下都用表示输入差分α经过u(u≥1) 轮迭代后输出差分为β，且活动轮函数的个数为v。

上述差分对应的计算过程如下：在轮函数f0和f1都为双射的条件下，当输入差分为3=(0,0,1,1)时，轮函数f0的输出差分块为0 差分块，轮函数f1的输出差分块为非0 差分块，故由“0⊕0=0”和“1⊕1=0或1”知，经过轮函数f0和f1以及异或运算作用后，其输出结果为(0,0,1,0)或(0,0,1,1)，再经过循环左移变换，其输出结果为(0,1,0,0) 或(0,1,1,0)，即4 或6。

类似地，所有非0 输入差分经一轮CLEFIA 密码结构迭代后的差分对应为

其次，给出所有非0 输入差分经一轮CLEFIA变形密码结构（如图2 所示）迭代后的差分对应。

当线性变换P∈P1时，以输入差分为(0,0,1,1)=3时的情形为例。此时，第3 分支与第4分支输入差分不为0，CLEFIA 变形密码结构的一轮差分对应为

其中，λi∈{0,1},2≤i≤ 4，且运算⊕满足规则“0⊕0=0”“0⊕1=1”“1⊕0=1”“1⊕1=0或1”。当λi遍历 0,1 时，(1,λ2,λ3,1⊕λ4)的取值为(1,0,0,1⊕0)=(1,0,0,1)，(1,0,0,1⊕1)=(1,0,0,0)或(1,0,0,1)，(1,0,1,1⊕0)=(1,0,1,1)，(1,0,1,1⊕1)=(1,0,1,0) 或 (1,0,1,1)，(1,1,0,1⊕0)=(1,1,0,1)，(1,1,0,1⊕1)=(1,1,0,0)或(1,1,0,1)，(1,1,1,1⊕0)=(1,1,1,1)，(1,1,1,1⊕1)=(1,1,1,0)或 (1,1,1,1)，即(1,λ2,λ3,1⊕λ4)的取值∈{8,9,10,11,12,13,14,15}，故上述的一轮差分对应可简记为

其中，箭头上方括号中的1 表示轮函数f1的输入差分块为非0 差分块，即活动轮函数的个数为1。

当线性变换P∈P2时，仍以输入差分为(0,0,1,1)=3 时的情形为例。同样可以给出输入差分3 经一轮CLEFIA 变形密码结构迭代后的差分对应为

利用上述的P∈P1和P∈P2时的差分对应，进一步可以给出当线性变换P∈P1∪P2时，输入差分3 经一轮CLEFIA 变形密码结构迭代后的差分对应为

类似地，所有非0 输入差分经一轮CLEFIA 变形密码结构迭代后的差分对应为

利用上述的一轮CLEFIA 密码结构的差分对应和一轮CLEFIA 变形密码结构的差分对应，可以进一步给出所有非0 输入差分经6 轮动态密码结构（如图3 和图4 所示）迭代后的差分对应为

由上面的讨论，可得以下引理。

引理2对于图3 所示的动态密码结构，若轮函数都是双射，则有以下结论成立。

1) 6 轮差分特征中活动轮函数的个数 ≥6。

2) 活动轮函数为6 的6 轮差分特征只可能为

引理3对于图3 所示的动态密码结构，在轮函数都是双射的条件下，19 轮差分特征中活动轮函数的个数 ≥19，即对于

证明由引理2 的1)可知，6 轮差分特征中活动轮函数的个数 ≥ 6，故vi≥6（1≤i≤3）。

最后，将本文结果与文献[14]中的动态密码结构的相应结果进行比较，如表1 所示。

表1 本文结果与文献[14]中相应结果的比较

由表1 可知，对于本文提出的动态密码结构，当迭代轮数l=6t(t≥ 1)或l=6t+1(t≥ 3)时，l(l≥ 1)轮差分特征至少有l个活动轮函数，当迭代轮数l取其他值时，l(l≥ 1)轮差分特征至少有l-1个活动轮函数。与文献[14]中的I 型类CLEFIA 动态密码结构相比，6t+1(t≥ 3)轮差分特征的活动轮函数个数的下界增加了1。与文献[14]中的Ⅱ型类CLEFIA 动态密码结构相比，本文提出的动态密码结构在迭代轮数相同的情况下具有相同的活动轮函数个数的下界。另外还可以看出，在迭代轮数相同的情况下，本文提出的动态密码结构所包含的密码结构个数比I 型类CLEFIA 动态密码结构的相应结果略少（即，显然l=6t(t≥ 1)时二者相等），比Ⅱ型类CLEFIA 动态密码结构的相应结果要多（即）。这里，表示不大于x的最大整数，表示不小于x的最小整数。

本文的研究结果对分组密码算法的设计与分析具有重要的指导意义。根据定理2 可知，如果知道轮函数的最大差分概率Pmax，就能估计出任意轮最大差分特征概率的上界。当采用本文提出的动态密码结构设计分组密码算法时，其抵抗差分密码分析的能力就有了依据。例如，一个输入规模为128 bit的分组密码算法采用图3 所示的动态密码结构，且轮函数f0和f1（如图1 和图2 所示）都采用SDS结构（代替-扩散-代替结构）[22]。其中，SDS 结构中的S 变换是4 个AES[23]S 盒的并置，D 变换是4阶MDS 矩阵（显然其差分分支数[23]为5）。因S 盒的最大差分概率为2-6[23]，故轮函数的差分概率≤(2-6)4=2-24[22]，从而l(∀l≥ 1)轮最大差分特征概率≤2-24×N(l)。例如，l=6时，6 轮最大差分特征概率≤2-24×6=2-144。

4 实验分析

本文通过Python 编程对CLEFIA动态密码结构差分特征活动轮函数个数的下界进行验证（实验环境为Windows 10，I7-5500U 2.4 GHz，8 GB RAM），并将结果与I 型类CLEFIA 动态密码结构和Ⅱ型类CLEFIA 动态密码结构差分特征活动轮函数个数的下界进行比较。表2 给出了不同迭代轮数3 种密码结构差分特征活动轮函数个数下界的对比。

表2 3 种密码结构差分特征活动轮函数个数下界的对比

在实验分析中，将活动轮函数个数的下界的求解问题转换为混合整数线性规划（MILP,mixed integer linear programming）[24]问题，利用Gurobi软件求解MILP 问题得到活动轮函数个数的下界。但是在实际差分密码分析中，真实差分特征的活动轮函数个数往往大于MILP 方法得到的理论估计，所以实际的下界大于或等于估计的下界。

对l(l≥1) 轮CLEFIA 动态密码结构差分特征活动轮函数个数的下界进行求解，基本过程概括如下。

步骤1对于l轮CLEFIA 动态密码结构，其线性变换P的选择有种，并存储P的所有可能的组合。

步骤 2任意选择一种P的组合，当轮数imod6 ≠0(1≤i≤l)，对于CLEFIA 密码结构进行建模；当轮数imod6=0(1≤i≤l)，对于选定P的CLEFIA 变形密码结构进行建模，利用MILP 求解活动轮函数的个数并记录。

步骤3重复步骤2，直至遍历所有P的组合。

步骤4输出CLEFIA 动态密码结构差分特征活动轮函数个数的下界。

具体建模过程如下。对于密码结构中的异或操作，设其输入差分为(xin0,xin1)，输出差分为xout，引入辅助变量d，则上述变量的取值范围均为{0,1}，可以得到

以第i(1≤i≤l,imod6 ≠0)轮CLEFIA 密码结构的建模为例，设输入差分为(x4i-4,x4i-3,x4i-2,x4i-1)，输出差分为(x4i,x4i+1,x4i+2,x4i+3)，dj,dj+1为引入的辅助变量，可以构建

以第i(i=6t,t≥ 1)轮CLEFIA 动态密码结构的建模为例，当线性变换时，设输入差分为(x4i-4,x4i-3,x4i-2,x4i-1)，输出差分为(x4i,x4i+1,x4i+2,x4i+3)，dj,dj+1,dj+2为引入的辅助变量，可以构建

对于每一轮的输入差分(x4i,x4i+1,x4i+2,x4i+3)，活动轮函数的个数取决于输入差分的第一分支和第三分支，即f0和f1的输入差分，因此活动轮函数个数下界的求解可表示为。利用Gurobi 软件对该MILP 问题进行求解即可得到CLEFIA 动态密码结构差分特征活动轮函数个数的下界。

通过实验分析可得1～20 轮CLEFIA 动态密码结构差分特征活动轮函数个数的下界，并且实验结果与推导结果相同。

5 结束语

本文提出了一种动态密码结构，该动态密码结构的特点是第6t(∀t≥ 1)轮中的扩散层可以从{0,1}4上的多个线性双射（对应于4 阶0-1 可逆矩阵）中任意选取，即6t(∀t≥ 1)轮中的扩散层是动态可变的，因此该动态密码结构包含多个分组密码结构。本文通过对6 轮差分特征的传递规律的分析，在轮函数都是双射的条件下，证明了l(l≥ 1)轮差分特征中活动轮函数个数的下界为N(l)，从而若设轮函数的最大差分概率为Pmax，则l轮动态密码结构的最大差分特征概率≤[pmax]N(l)。对于本文提出的动态密码结构，还有一些问题需要进一步研究，例如，该动态密码结构抵抗不可能差分分析、零相关线性分析以及积分分析等分析方法的能力如何？同时，能否找到更合适的线性变换，使相同轮数的差分特征具有更多的活动轮函数，也值得进一步研究。