0 引言

对称密码算法由于具有加解密速度快、便于各种软件和硬件平台实现等优点，在网络与信息安全领域发挥着越来越重要的作用。对称密码的分析与设计是一对相互对立又相互统一的矛盾体，两者的互动推动着对称密码的发展^[1]。密码S盒是对称密码算法的核心部件，其安全强度与算法的安全性息息相关^[2]，比如经典的差分密码分析^[3]、线性密码分析^[4]、相关密码分析^[5]、代数密码分析^[6]等，都是基于密码S盒的统计特性来实现的。因此，设计及分析高强度的密码S盒是目前业界重要的研究热点。

在2011年美国国际密码年会上(Annual Cryptology Conference, CRYPTO 2011)，Leander等^[7]利用S盒混淆能力差的代数性质，提出一种新的分组密码攻击方法——不变子空间攻击，并对SP结构的分组密码算法PRINT进行不变子空间攻击，说明其存在严重的安全漏洞。进一步，在2015年的欧洲密码年会上(Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015)，Leander等^[8]提出了不变子空间攻击的一般方法，并对三个密码算法Robin、iSCREAM和Zorro进行分析，发现iSCREAM存在一定的安全漏洞。在2016年亚洲密码年会上(International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016)，Todo等^[9]利用密码S盒的输入和输出代数关系，提出了非线性不变攻击方法，并证明了不变子空间攻击是非线性不变攻击的一种特例。此外，针对轻量级分组密码算法Midori-64，他们还给出了一种非线性不变攻击方法。

在2017年国际快速软件加密会议上(International Conference on Fast Software Encryption, FSE 2017)，Guo等^[10]提出了几类高强度的密码S盒，并说明这些新S盒足以抵抗不变子空间攻击。注意到，Guo等提出的几类新密码S盒是否足够安全？特别是当这些S盒部署在具体算法(比如Midori-64算法)的非线性组件里时，算法整体的安全性如何评价呢？这两个问题亟待解决。

本文利用密码S盒输入和输出的代数关系，设计了一个算法来寻找S盒的非线性不变函数。基于该算法，针对Guo等的几类S盒进行测试，结果表明：其中三类S盒存在相同的二次非线性不变函数。最后讨论了这三类S盒替换Midori-64算法的S盒后得到的Midori-64变体算法的安全性。

1 基础知识 1.1 五类高强度S盒

在FSE 2017上，Guo等^[10]首先提出了两个概念：密码算法的密钥编排分类和S盒的设计目标。

密码算法的密钥编排分为以下两类：

1) 密钥编排函数1(Key Schedule Function 1, KSF1)：每一轮都使用单密钥，如Midori-128、LED-64^[11]；

2) 密钥编排函数2(Key Schedule Function 2, KSF2)：两个密钥交替使用，如Midori-64、LED-128^[11]。

S盒的设计目标按照其控制的弱密钥范围分为以下两类：

1) 目标1(Goal 1)：确保弱密钥空间中含有的弱密钥的数目为c*2^b，其中c为一个较小的常数，b为密钥含有的单元的个数；

2) 目标2(Goal 2)：确保仅含有一个弱密钥。

Guo等^[10]给出了五类新密码S盒的真值表，参见图 1。其中x为S盒输入，y为S盒输出。其中S₁，S₂，S₃是在KSF1和Goal 1的条件下，利用S盒的差分分布表，经过计算机搜索得到的；S₄是在KSF2和Goal 1的条件下，利用S盒的差分分布表，经过计算机搜索得到的；S₅是在KSF1和Goal 2的条件下，利用S盒的差分分布表，经过计算机搜索得到的。S₁，S₂，S₃，S₄，S₅的最大差分可能性都为2^-2，线性逼近的最大偏离值为2^-2。

1.2 Midori-64算法

在ASIACRYPT 2015上，Banik等^[12]提出Midori-64轻量级分组加密算法。Midori-64由于低功耗、低延时、轮数少等诸多优点得到了广泛关注。Midori-64的整体加密流程如图 2所示。其中：P为输入的明文，C为输出的密文，WK为一个64比特的白化密钥，K_i(i=0, 1, …, 14) 为第i轮加密时使用的子密钥，α_i为64比特的轮常数，RK_i(i=0, 1, …, 14) 为异或轮常数α_i之后的轮密钥。

Midori-64密码算法每次可以处理64比特的数据，这64比特的数据被放在一个4×4的矩阵S中。

$S=\left[ \begin{matrix} {{S}_{0}} & {{S}_{4}} & {{S}_{8}} & {{S}_{12}} \\ {{S}_{1}} & {{S}_{5}} & {{S}_{9}} & {{S}_{13}} \\ {{S}_{2}} & {{S}_{6}} & {{S}_{10}} & {{S}_{14}} \\ {{S}_{3}} & {{S}_{7}} & {{S}_{11}} & {{S}_{15}} \\ \end{matrix} \right]$

Midori-64算法的轮函数包括以下4个组件：字节替代、字节置换、列混淆、轮密钥加。下面分别介绍这4个组件。

1) 字节替代(SubCell)。

使用一个非线性的4位S盒对每个单元的状态进行操作，Midori-64算法的S盒如图 3所示。x为S盒输入，y为S盒输出。

2) 字节置换(ShuffleCell)。

字节置换主要是对矩阵S中的每一个位置按照如下顺序进行替换。

$\left[ \begin{matrix} {{S}_{0}} & {{S}_{4}} & {{S}_{8}} & {{S}_{12}} \\ {{S}_{1}} & {{S}_{5}} & {{S}_{9}} & {{S}_{13}} \\ {{S}_{2}} & {{S}_{6}} & {{S}_{10}} & {{S}_{14}} \\ {{S}_{3}} & {{S}_{7}} & {{S}_{11}} & {{S}_{15}} \\ \end{matrix} \right]\to \left[ \begin{matrix} {{S}_{0}} & {{S}_{14}} & {{S}_{9}} & {{S}_{7}} \\ {{S}_{10}} & {{S}_{4}} & {{S}_{3}} & {{S}_{13}} \\ {{S}_{5}} & {{S}_{11}} & {{S}_{12}} & {{S}_{2}} \\ {{S}_{15}} & {{S}_{1}} & {{S}_{6}} & {{S}_{8}} \\ \end{matrix} \right]$

3) 列混淆(MixColumn)。

Midori-64算法的列混淆矩阵为一个二进制的正交矩阵，列混淆矩阵如下：

$\left[ \begin{matrix} {{S}_{i}} \\ {{S}_{i+1}} \\ {{S}_{i+2}} \\ {{S}_{i+3}} \\ \end{matrix} \right]=\left[ \begin{matrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \end{matrix} \right]\left[ \begin{matrix} {{S}_{i}} \\ {{S}_{i+1}} \\ {{S}_{i+2}} \\ {{S}_{i+3}} \\ \end{matrix} \right];\text{ }i\in \{0,4,8,12\}$

4) 轮密钥加(KeyAddition)。

轮密钥加将第i轮的密钥RK_i与第i轮的状态异或。

Midori-64算法的密钥编排非常简单。128比特的密钥被表示成为两个64比特key₀和key₁，K=key₀‖key₁。WK=key₀⊕key₁, RK_i=key_{(i mod 2)} ⊕α_i，其中，α_i每一个位置的最低位只有0或1两种情况，其他的位置为0，α_i的部分编排如表 1所示。

2 不变子空间攻击和非线性不变攻击 2.1 不变子空间攻击和非线性不变攻击的基本思想

不变子空间和非线性不变攻击是两种弱密钥条件下的攻击方法。当且仅当输入每一轮加密轮函数的密钥都是弱密钥时，才能构造出概率为1的全轮区分器，进而利用这两种方法对算法进行攻击。注意到，近几年设计的若干轻量级密码算法为了提高加密的速度，减少消耗的内存，密钥编排算法简单。甚至直接将主密钥用于加密，这可能为攻击者所利用，从而进行非线性不变攻击和不变子空间攻击。

不变子空间攻击^[7]的基本思想如下：首先，定义SP层的加密函数为F，则F_k(x)=F(x+k)。如果存在一个空间U⊆F₂ⁿ和两个常数c, d∈F₂ⁿ满足性质(1)：

$F(U+c)=U+d$

(1)

则对应的弱密钥为k=u+c+d，其中u∈U，且有式(2) 存在：

$\begin{align} & {{F}_{k}}\left( U+d \right)=F\left( \left( U+d \right)+\left( u+c+d \right) \right)= \\ & \quad \quad \quad \quad \quad F\left( U+c \right)=U+d \\ \end{align}$

(2)

注意到，不变子空间攻击的本质思想是利用轮函数将空间U+c映射到U+d。如果输入的所有轮密钥为弱密钥，则上述性质(2) 对于任意轮都是满足的。此外，U的维数决定了弱密钥空间的大小。假设U的维数为b，密钥一共含有m个单元，则对应的弱密钥空间为m^b。

非线性不变攻击是不变子空间攻击的推广形式^[9]，不变子空间攻击为非线性不变攻击的特例，在不变子空间中使用的非线性不变函数为指示函数δ_A(x)。

${{\delta }_{A}}\left( x \right)=\text{ }\left\{ \begin{align} & 1,\text{ }x\in A\text{ } \\ & 0,\text{ }其他 \\ \end{align} \right.$

(3)

寻找轮函数的非线性不变函数g是非线性不变攻击的关键。非线性不变函数必须满足式(4) 对于所有的输入x_i-1都成立，其中，x_i-1为轮函数的输入，x_i为轮函数的输出，Constant为常数，此时输入的密钥定义为弱密钥。

$g({{x}_{i-1}})\oplus g({{x}_{i}})=Constant\oplus g(ke{{y}_{i-1}})$

(4)

进一步，如果存在一个非线性不变函数可以穿透轮函数，并且每一轮输入的密钥都为弱密钥，那么此非线性不变函数同样也可以穿透这个轮函数相对应的密码算法，最终得到输入的明文和输出的密文之间满足g(P)+g(C)=Constant这样的关系，利用这种关系可以对SPN结构的分组密码算法进行弱密钥条件下的区分攻击。弱密钥空间为2^m×(n-f)，其中n为S盒的位数，f代表非线性不变函数非线性部分所含的变量个数。

2.2 S盒非线性不变函数的求解方法

假设S盒的非线性不变函数存在，将S盒的非线性不变函数用代数正规型进行表示：

$g=\sum\limits_{u\in F_{2}^{n}}{{{\lambda }_{u}}{{x}^{u}}}$

(5)

式(5) 中，λ_u是有待于确定的系数，x^u定义为$\prod\limits_{i=1}^{n}{x{{[i]}^{u[i]}}}$。只要确定了系数λ_u，就可以确定非线性不变函数g。下面介绍两种确定非线性不变函数g的方法：

方法一  如果函数g为S盒的非线性不变函数，则对于所有的n比特的输入x和相应的n比特S盒的输出S(x)都满足式(6)：

$g(x)+g(S(x))=Constant$

(6)

转化为代数正规型的形式即为式(7)：

$\sum\limits_{u\in F_{2}^{n}}{{{\lambda }_{u}}x{}^{u}}={{\sum\limits_{u\in F_{2}^{n}}{{{\lambda }_{u}}S(x)}}^{u}}\oplus Constant$

(7)

具体求解步骤如下：

步骤1  对于式(7)，固定λ₁, λ₂, …, λ_u的值(u的最大汉明重量取2)，固定常数Constant的值为0。

步骤2  遍历所有的x的值，如果对于所有的x和S(x)都有式(7) 成立，则对应的Constant为0，保存此时的系数λ₁，λ₂, …, λ_u。

如果都有式(7) 不成立，则对应的Constant为1，将此时的系数λ₁, λ₂, …, λ_u保存。

步骤3  改变λ₁, λ₂, …, λ_u的值，进行步骤2操作，直到遍历所有的λ₁, λ₂, …, λ_u。针对Constant取0和取1，分别得到若干组λ₁, λ₂, …, λ_u。

方法二  将式(7) 进行变形得到如下的等式关系(8)：

$\sum\limits_{u\in F_{2}^{n}}{{{\lambda }_{u}}(x{}^{u}\oplus S{{(x)}^{u}}})=Constant$

(8)

对于式(8)，固定Constant为0，遍历所有的输入x，计算x^u⊕S(x)^u(u的最大汉明重量取2)，可以得到一个关于系数λ₁，λ₂，…，λ_u的方程组。如果方程组有解，则得到的解即为λ₁, λ₂, …, λ_u的值。固定Constant为1，利用上述Constant取0的同样方法求解λ₁, λ₂, …, λ_u。

方法一在求解2次非线性不变函数时，所需的计算复杂度为${{2}^{C_{n}^{2}+C_{n}^{1}+n}}$次运算，方法二的计算复杂度为2ⁿ次运算。可以看出：针对4位S盒，方法一与方法二都可以用来求解非线性不变函数，方法二计算机复杂度较低。但是针对8位S盒，方法二的优势明显。

3 五类高强度S盒的安全性新分析

本章设计了一个求解S盒非线性不变函数的算法，利用它对Guo等的几类S盒进行测试。进一步利用其中三类S盒存在非线性不变函数的缺陷，构造弱密钥条件下的区分器，进而对Midori-64变体进行非线性不变攻击。

3.1 S盒的非线性不变函数求解算法及其应用

本节设计了一个算法来求解4位S盒的非线性不变函数。具体步骤如下：

步骤1  针对S盒遍历所有的输入x，得到对应的输出为y，并将对应的x、y按行分别存储在矩阵X、Y中。

步骤2  建立两个16×10的矩阵X₁、Y₁，其中，X₁[0][0]~X₁[0][3]中存储x[0][0]~x[0][3]的值，X₁[0][4]~X₁[0][9]中存储x[0][i]*x[0][j]的值，i，j为[1，2，3，4]中两个不重复的数。Y₁[0][0]~Y₁[0][3]中存储的为y[0][0]~y[0][3]的值，Y₁[0][4]~Y₁[0][9]中存储y[0][i]*y[0][j]的值，i，j为[1，2，3，4]中两个不重复的数。同理，按照以上的方法对X₁、Y₁、X、Y第1~15行执行同样的操作。最终输出矩阵X₁，Y₁。

步骤3  X₁，Y₁中每一个位置的值按位异或，得到一个新的矩阵Z。

步骤4  定义一个10维的向量A，向量中的每一个位置的值只有0或1两种情况，遍历A中的所有的值，对于每一种情况，用Z*A，最终得到一个列向量。如果列向量中的值都相等，则保存A中的对应的值到A₁中。

步骤5  A₁中的每一行代表一个非线性不变函数的表达式。第1~3列代表的系数为λ₁~λ₃，第4~9列代表的系数为λ₁₂, λ₁₃, λ₁₄, λ₂₃, λ₂₄, λ₃₄。每一行数值为1时表示系数存在，数值为0时表示系数不存在。至此恢复二次非线性不变函数的一次和二次项系数，也就得到了此S盒的二次非线性不变函数。

利用此算法对Guo等提出的几类S盒进行测试，结果表明：S₁、S₂、S₃存在相同的二次非线性不变函数，参见式(9)。S₄、S₅不存在二次非线性不变函数。

$g(x)=x[2]\oplus x[3]\oplus x[4]\oplus x[2]\cdot x[3]$

(9)

3.2 Midori-64变体的非线性不变攻击

分别用含有非线性不变函数的三类S盒即S₁、S₂、S₃部署在Midori-64的S盒组件上，结果表明：Midori-64变体算法存在严重的安全漏洞，即弱密钥空间为2⁶⁴。

具体分析过程如下：

对于S盒，利用寻找到的非线性不变函数g，可以得到式(10) 对于所有的S盒都成立：

$g({{x}_{i}})\oplus g(S({{x}_{i}}))=0$

(10)

其中:x_i为一个第i个S盒的输入，S(x_i)为第i个S盒输入为x_i时对应的输出。又知Midori-64的S层一共采用了16个相同的S盒，可以得到关于S层的非线性不变函数，参见式(11) :

$\sum\limits_{i=1}^{16}{g({{x}_{i}})\oplus \sum\limits_{i=1}^{16}{g(S({{x}_{i}}))}}=0$

(11)

经过S层后，算法将通过字节置换，由于字节置换作用于每一个位置。所以，式(11) 经过字节置换后仍旧成立。又知Midori-64的列混淆矩阵为正交矩阵，y_i为第i个位置经过L层后的输出。利用Todo等^[9]的结论：如果针对S层的非线性不变函数的最高阶数为二次，并且列混淆矩阵是正交矩阵，则S层的非线性不变函数对于L层同样也是成立的。可得式(12) 是恒成立的：

$\sum\limits_{i=1}^{16}{g({{x}_{i}})\oplus \sum\limits_{i=1}^{16}{g({{y}_{i}})}}=0\text{ }$

(12)

最后进行轮密钥加，轮密钥RK_i的编排为RK_i=K_{i mod 2}⊕α_i，α_i为轮常数。Midori-64的轮常数每一个位置的十六进制形式仅包含0或1，转化为4位的二进制后，在第2、3位都为零。为了保证密钥RK_i对于非线性不变函数为线性的运算，需要K₀，K₁每个单元的第2、3位固定为0，其他的位置可以为任意的值。此时的密钥为弱密钥，弱密钥空间为2⁶⁴。如果输入的密钥满足以上条件，则轮函数经过轮密钥加后存在式(13) 成立：

$\sum\limits_{i=1}^{16}{g({{x}_{i}})\oplus \sum\limits_{i=1}^{16}{g({{y}_{i}})}}=g(R{{K}_{i}})$

(13)

Midori-64一共加密了16轮，如果每一轮输入的密钥都为弱密钥，则根据式(13) 可以得到输入的明文和密文之间的关系如式(14)、(15)：

$\sum\limits_{i=1}^{16}{g\left( {{p}_{i}} \right)\oplus \sum\limits_{i=1}^{16}{g\left( {{c}_{i}} \right)}}=\sum\limits_{i=1}^{15}{g\left( R{{K}_{i}} \right)}\oplus g\left( WK \right)\oplus g\left( WK \right)$

(14)

$\text{ }\sum\limits_{i=1}^{16}{g({{p}_{i}})\oplus \sum\limits_{i=1}^{16}{g({{c}_{i}})}}=\sum\limits_{i=1}^{15}{g(R{{K}_{i}})}$

(15)

当输入的密钥不是弱密钥时，式(15) 成立的概率为0.5。当输入的密钥为弱密钥时，式(15) 以概率1成立。所以，判断输入的密钥是否为弱密钥时，需要输入明文和密文对进行验证，输入N对明密文，如果均满足式(15)，则使用的密钥不是弱密钥的概率为2^-N+1；如果至少存在一对明密文不满足，则使用的密钥不是弱密钥。当明密文对的数目取40时，可知弱密钥条件下，可以以概率1-2^-40+1=1构造出区分器。随后利用此区分器对密码算法进行区分攻击。在Midori-64的密码分组链接(Cipher Block Chaining, CBC)工作模式下，输入相同的明文和不同的初始向量IV，得到不同的密文。根据非线性不变函数式(6) 得到式(16)：

$g({{P}_{1}}\oplus I{{V}^{i}})\oplus g({{P}_{1}}\oplus I{{V}^{j}})\oplus g(C_{1}^{i})\oplus g(C_{1}^{j})=0$

(16)

此公式包含32个未知数，需要输入33个不同的IV得到32个不同的表达式。利用高斯消元方法求解此32个表达式组成的方程所需的时间复杂度为32³次简单运算。存储复杂度为N个分组长度，数据复杂度为N。

综上，利用Guo等提出的S盒替换Midori-64的S盒后，Midori-64变体算法的弱密钥为2⁶⁴个。注意到，Guo等设计的S₁、S₂、S₃是应用在KSF1模式下，达到的目标为：存在的弱密钥为c*2^b个。Midori-64的密钥编排模式遵循KSF2，此时Midori-64变体的弱密钥空间远远大于c*2^b。因此Guo等设计的S₁，S₂，S₃三类S盒没有达到最初的设计目标，无法抵抗非线性不变攻击。

4 结语

本文主要对Guo等设计的几类S盒的安全性进行了新的评估。给出了求解S盒非线性不变函数的新算法，利用新算法测试Guo等的五类S盒。结果表明：其中S₁、S₂、S₃存在相同的二次非线性不变函数。此外，用这三类S盒直接替换Midori-64的S盒来得到Midori-64变体算法，结果表明：Midori-64变体算法存在严重的安全漏洞。因此，这三类S盒是不安全的。