SHA－3轮函数中χ及θ变换的性质研究＊

王 淦，张文英

（1.山东师范大学信息科学与工程学院，山东 济南250014；2.山东省分布式计算机软件新技术重点实验室，山东 济南250014）

1 引言

近年来，由于一系列Hash 函数如 MD4、MD5、SHA－1和HAVAL等受到王小云教授提出的模差分和消息修改方法的重创［2～4］，因此美国国家标准与技术研究院NIST（National Institute of Standards and Technology）发起 了征集新Hash函数标准SHA－3的计划［5］。该计划于2007年启动，经过长达五年共计三轮的竞赛，NIST 于2012年10月2日宣布由Bertoni G、Daemen J、Peeters M 等人［6，7］设计的Keccak［5］为SHA－3标准。由于其不同于以往Hash函数的独特设计理念，Keccak成为当前Hash函数研究的热点。

χ是Keccak轮函数中唯一的非线性变换，它保证了整个轮函数的非线性。差分分析方法由Biham E和Shamir A［8］于1990年首先提出，它是对Hash函数攻击的有效方法，也是目前攻击Keccak的主要方法。在对Keccak的攻击中，构造使输入差分以高概率通过χ变换而不发生改变或使输出差分为指定状态的差分路径是降低攻击复杂度的重要手段之一。进行差分分析时常把χ看作一个输入输出均为5比特的S盒，其输入输出以一定概率相对应，构成一个线性仿射簇［6］。

由于布尔函数表达式的形式有利于进一步的差分扩散性质推导，因此本文将χ 变换表示为布尔函数数表达式，通过布尔函数表达式对输入差分的扩散性质进行了推导，得到了32种输入输出差分情况的分布表，并由此对χ 的差分分布规律进行了分析。

θ是Keccak算法规定的必须作为第一个的变换，因为其扩散能力很强，1 比特差分经过θ后可扩散至10比特。如何使差分顺利通过θ变换而不被扩散是对Keccak进行差分分析时要解决的首要问题。在众多对Keccak的攻击方法中，文献［1］首先提出利用符合Double Kernel形式的差分来构造差分路径，以保证差分不被θ变换扩散，并成功找到了Keccak－256的2轮完全碰撞和3轮近似碰撞。文献［9］在文献［1］的基础上提出了目标差分算法，并利用该算法得到了Keccak－256的4 轮完全碰撞和5 轮近似碰撞，这也是目前对Keccak－256攻击的最好结果。由于文献［1，9］的攻击方法都是以满足Double Kernel形式的差分为条件的，因此快速有效地搜索满足Double Kernel形式的差分是对Keccak进行差分攻击的基础。文献［1］中提出了一种搜索算法，但此算法近似于穷尽搜索，复杂度比较高。

本文提出了一种新的Double Kernel形式差分的搜索算法，通过施加限制条件缩小了搜索的范围，复杂度较之文献［1］中的算法有明显降低。实验表明，本算法能够快速有效地搜索符合给定条件的Double Kernel形式的差分，在差分汉明重量为6的情况下，算法搜索次数由25 600 降低到15 625。将本算法用于搜索汉明重量为4 的Double Kernel形式的差分时，实验表明，汉明重量为4的Double Kernel形式的差分不存在。对于汉明重量为2的Double Kernel的情况，本文从理论推导的角度证明其不存在。

2 Keccak算法简介

Keccak算法基于海绵结构［10］，海绵结构如图1所示，其处理过程分为吸收和挤压两个阶段。Keccak轮函数表示为Keccak－f［b］，b称为轮函数的宽度，也称为状态的个数，b＝25×2l，l∈｛0，1，2，3，4，5，6｝。b可表示为b＝r＋c，其中r称为外部部分，又称为比特率，c称为内部部分，又称为容量。消息经过填充后分割为r比特的块进行处理，输出长度为n的摘要，n∈｛224，256，384，512｝并满足c＝2n。Keccak算法共有12＋2l轮，每轮包含五个变换，表示为R＝ι◦χ◦π◦ρ◦θ，其运算均在GF（2）上进行。SHA－3 使用的是Keccak－f［1600］，共24轮，其1 600比特状态的每一比特可看作三维数组a［x］［y］［z］中的一个元素，其中0≤x≤4，0≤y≤4，0≤z≤63。

Figure 1 Sponge construction of Keccak图1 Keccak海绵结构

Keccak轮函数的五个变换如下：

（2）ρ：a［x］［y］［z］←a［x］［y］［z－t（x，y）］，ρ使其沿z轴方向移动，移动的距离由t（x，y）指定。

（4）χ：a［x］［y］［z］←a［x］［y］［z］＋（﹁a［x＋1］［y］［z］∧a［x＋2］［y］［z］），χ对沿x轴方向一行中的比特进行非线性运算。

（5）ι：a［0］［0］［z］←a［0］［0］［z］＋RC［i］，ι添加一个每轮均不相同的64比特的常量。

有关Keccak算法的详细描述可参考文献［6］。

3 χ的差分分布

3.1 χ的布尔函数表达

我们可以将χ的布尔函数表达式写为：xi＝xi＋（xi＋1＋1）xi＋2＝xi＋xi＋1xi＋2＋xi＋2，1≤i≤5。χ可看作对某一行的5个比特同时进行运算，因此通常将χ作为一个输入输出均为5 比特的S盒。令X＝（x1，x2，x3，x4，x5）表示一行，则χ变换可表示为（x1，x2，x3，x4，x5）→χ（f（x1），f（x2），f（x3），f（x4），f（x5））。

3.2 χ的差分分布推导

分别考察当χ的输入差分的汉明重量为0、1、2、3、4、5 时的差分扩散情况。给定输入差分Δin，根据Δout＝χ（X）＋χ（X＋Δin）计算输出差分Δout。这里只给出输入差分汉明重量分别为1和3两种情况的详细推导。

输入差分汉明重量为1，令Δin＝（1，0，0，0，0），则：

x1＝［x1＋（x2＋1）x3］＋［x1＋1＋（x2＋1）x3］＝1

x2＝［x2＋（x3＋1）x4］＋［x2＋（x3＋1）x4］＝0

x3＝［x3＋（x4＋1）x5］＋［x3＋（x4＋1）x5］＝0

x4＝［x4＋（x5＋1）x1］＋［x4＋（x5＋1）（x1＋1）］＝1＋x5

x5＝［x5＋（x1＋1）x2］＋［x5＋（x1＋1＋1）x2］＝x2

可将Δin和Δout的对应关系表示为（1，0，0，0，0）→（1，0，0，1＋x5，x2）。

输入差分汉明重量为1的其它情况可直接移位得到。例如，只需将（1，0，0，0，0）→（1，0，0，1＋x5，x2）所有元素右移一位并同时增大其下标，即可得到（0，1，0，0，0）→（x3，1，0，0，1＋x1）。同理：

（0，0，1，0，0）→（1＋x2，x4，1，0，0）

（0，0，0，1，0）→（0，1＋x3，x5，1，0）

（0，0，0，0，1）→（0，0，1＋x4，x1，1）

输入差分汉明重量为3时有两种不同的情况，首先令Δin＝（1，1，1，0，0），则：

x1＝［x1＋（x2＋1）x3］＋［x1＋1＋（x2＋1＋1）（x3＋1）］＝1＋x2＋x3

x2＝［x2＋（x3＋1）x4］＋［x2＋1＋（x3＋1＋1）x4］＝1＋x4

x3＝［x3＋（x4＋1）x5］＋［（x3＋1）＋（x4＋1）x5］＝1

x4＝［x4＋（x5＋1）x1］＋［x4＋（x5＋1）（x1＋1）］＝1＋x5

x5＝［x5＋（x1＋1）x2］＋［x5＋（x1＋1＋1）（x2＋1）］＝x1＋x2

即（1，1，1，0，0）→（1＋x2＋x3，1＋x4，1，1＋x5，x1＋x2）。移位得：

（0，1，1，1，0）→（x2＋x3，1＋x3＋x4，1＋x5，1，1＋x1）

（0，0，1，1，1）→（1＋x2，x3＋x4，1＋x4＋x5，1＋x1，1）

（1，0，0，1，1）→（1，1＋x3，x4＋x5，1＋x5＋x1，1＋x2）

（1，1，0，0，1）→（1＋x3，1，1＋x4，x5＋x1，1＋x1＋x2）

输入差分汉明重量为3的另一种情况，令Δin＝（1，1，0，1，0），则：

x1＝［x1＋（x2＋1）x3］＋［x1＋1＋（x2＋1＋1）x3］＝1＋x3

x2＝［x2＋（x3＋1）x4］＋［x2＋1＋（x3＋1）（x4＋1）］＝x3

x3＝［x3＋（x4＋1）x5］＋［x3＋（x4＋1＋1）x5］＝x5

x4＝［x4＋（x5＋1）x1］＋［（x4＋1）＋（x5＋1）（x1＋1）］＝x5

x5＝［x5＋（x1＋1）x2］＋［x5＋（x1＋1＋1）（x2＋1）］＝x1＋x2

即（1，1，0，1，0）→（1＋x3，x3，x5，x5，x1＋x2）。移位得：

（0，1，1，0，1）→（x2＋x3，1＋x4，x4，x1，x1）

（1，0，1，1，0）→（x2，x3＋x4，1＋x5，x5，x2）

（0，1，0 ，1，1）→（x3，x3，x4＋x5，1＋x1，x1）

（1，0，1 ，0，1）→（x2，x4，x4，x5＋x1，1＋x2）

χ的输入差分汉明重量为0、2、4、5的情况可通过类似推导得出。

3.3 χ的差分分布表

综上推导，可将χ的输入输出差分分布的32种情况列表如表1所示（采用Big－Endian表示）。

3.4 χ的差分分布规律

由表1可以看出，χ的输出差分分布是有规律的。定义Nχ为给定输入差分时输出差分的分布数，定义Mχ为任一输出差分分布中的差分数，则Nχ∈｛1，4，8，16｝，Mχ∈｛2，4，8，32｝，当且仅当差分为0时Nχ为1，当且仅当Nχ＝1时Mχ＝32，给定Nχ则Mχ唯一确定，当输入无差分时输出也无差分，当输入有差分时输出一定会有差分。

Table 1 Differential distribution table ofχ表1 χ的差分分布表

4 一种新的Double Kernel形式差分的搜索算法

4.1 Double Kernel的定义

若某列中差分的个数为偶数，则称此列奇偶性为偶，若某状态的所有列均为偶，则称此状态为Column Parity Kernel［6］或简称为Kernel。状态为Kernel的差分经过θ变换时差分不会扩散，否则一列中的差分会扩散至10比特。构造差分路径时，为了使Kernel状态能够维持尽可能多的轮数，不仅要求差分保持Kernel状态而且要求差分两两位于同一行，称为Double Kernel［1］，Double Kernel形式的差分为最优的Kernel形式的差分。

4.2 新的Double Kernel形式差分搜索算法

文献［1］中提出一种搜索符合条件的Double Kernel形式差分的算法，此算法近似于穷尽搜索，效率较低。其过程可简述为：随机选择某一道在xy面上的位置作为起始点，计算此位置上的点经过ρ和π置换后的位置；然后对与新位置位于同一列的另外四个点逐一进行π－1和ρ－1运算，对于得到的新位置再进行ρ和π变换；重复此过程直到达到所设定的片数k为止。本文提出了一种效率更高的Double Kernel形式差分的搜索算法，将要搜索的位置用数学变量表示，得到经过θ、ρ、π变换之后的数学形式。由Double Kernel的定义可得出此数学形式成立需要满足的条件，在搜索过程中，若不满足设定的条件则不进行计算和搜索，从而减少了计算量，缩小了搜索范围，提高了搜索效率。以搜索汉明重量为6 的Double Kernel形式差分为例，此时k＝3，假设6个差分初始位置为：

经过θ、ρ和π变换后其位置可表示为：

若式（2）为Double Kernel形式，则（y1，z1＋r1）、（y2，z1＋r2）、（y3，z2＋r3）、（y4，z2＋r4）、（y5，z3＋r5）、（y6，z3＋r6）必定两两对应相等。所有八种可能的对应情况如下：

实验已经证明八种情况是等价的，这里选择第一种情况，根据式（2）得：

y1＝y4，z1＋r1＝z2＋r4

y2＝y5，z1＋r2＝z3＋r5

y3＝y6，z2＋r3＝z3＋r6

若以上三式成立则必须满足r6－r3＝r1－r2＋r5－r4。算法中只需判断r6－r3＝r1－r2＋r5－r4是否满足即可，不满足条件者排除在搜索范围之外。另由Double Kernel的定义，x1≠x2且x1≠x3且x2≠x3且y1≠y2且y1≠y3且y2≠y3，不符合此条件者也应排除在搜索范围之外。以上施加的两个限制条件大大缩小了本算法的搜索范围，提高了搜索效率。算法伪代码如下：

算法 1

本算法采用C 语言实现，编译环境为Microsoft Visual Studio 2010。经过程序搜索，共有256个符合条件的结果，分为四组不同的Double Kernel，每组64个。四组Double Kernel如下（以每组第一个元素代表，其余63个元素可通过依次增大下标z得到）：

（0，3，0）（0，1，0）（1，2，60）（1，3，60）（3，1，45）（3，2，45）

（0，4，0）（0，2，0）（2，3，21）（2，4，21）（4，2，28）（4，3，28）

（1，2，0）（1，0，0）（2，3，31）（2，2，31）（4，0，38）（4，3，38）

（2，0，0）（2，4，0）（3，3，34）（3，0，34）（4，4，47）（4，3，47）

4.3 汉明重量为4及以下的Double Kernel形式差分的不存在性

选择Double Kernel的原则是尽可能选择低汉明重量的差分，即差分的汉明重量越小越好，高汉明重量意味着需要满足的条件较多，因此找到碰撞的概率减小。文献［1］中使用的是汉明重量为8的差分，而文献［9］对此进行了改进，使用了汉明重量为6 的差分进行攻击，因而其效率更高。由Double Kernel形式差分的定义，汉明重量低于6的差分还有汉明重量为4及汉明重量为2的差分。

本文对算法1进行修改，使之适用于汉明重量为4 的Double Kernel形式差分的搜索。实验结果显示，符合条件的Double Kernel形式差分个数为0，即汉明重量为4的Double Kernel形式差分不存在。

对于汉明重量为2的差分，本文从理论推导证明了其不存在。

证明 设两个差分初始位置为：

经过θ、ρ和π变换后其位置可表示为：

若要使式（3）为Double Kernel，则式（4）需满足y1＝y2且z1＋r1＝z1＋r2，由Double Kernel定义知，y1≠y2，由Keccak算法知，r1≠r2，矛盾！故假设不成立，即汉明重量为2的Double Kernel形式差分不存在。

综上，汉明重量为4及以下的Double Kernel形式差分不存在。

4.4 算法复杂度分析

文献［1］中提到其算法的复杂度为25＊42k－1，本文算法复杂度为52k。以差分汉明重量为6的情况（即k＝3）为例，文献［1］中算法复杂度为25＊45，本文算法复杂度为56，本算法复杂度明显小于文献［1］中的算法。本算法在差分汉明重量为4（k＝2）、差分汉明重量为6（k＝3）、差分汉明重量为8（k＝4）时均优于文献［1］中的算法。两种算法的复杂度见表2（文献［1］中算法复杂度以O1表示，本文算法复杂度以O2表示）。

Table 2 Complexities of two algorithms表2 两种算法的复杂度

5 结束语

本文分析研究了Keccak轮函数中最重要也是最复杂的两个变换θ和χ。对于Keccak轮函数中唯一的非线性变换χ，将χ表示为布尔函数表达式形式，由其布尔函数表达式进行差分扩散推导，得到了输入输出差分32种情况下的分布表并分析了其输出差分的分布规律。

对文献［1］中提出的搜索Double Kernel形式差分的算法进行了改进，通过施加限制条件减少了计算量，缩小了搜索的范围，提高了搜索效率，新算法复杂度较文献［1］中算法有明显降低。本文还通过程序验证了汉明重量为4 的Double Kernel形式差分不存在，通过理论推导证明了汉明重量为2的Double Kernel形式差分不存在。

目前对Keccak进行差分攻击所构造的差分路径均是满足Kernel或Double Kernel形式的差分路径，本文也只是对Double Kernel形式差分的搜索算法进行了改进，以更高效率地找到符合条件的Double Kernel形式差分。一些研究者已经指出，Kernel或Double Kernel形式的差分路径至多只能维持两轮，两轮之后差分便会急剧扩散，汉明重量大大增加。文献［9］及文献［11］中均对Kernel或Double Kernel形式的差分路径进行倒推以增加攻击的总轮数，然而倒推也遇到了极大的困难。鉴于上述情况，要想得到更多轮数的攻击，最好的方法是寻找能维持更多轮数的高概率差分路径，而不仅仅局限于Kernel或Double Kernel形式，这也是进一步研究Keccak的重要方向之一。

［1］ María Naya－Plasencia，Rock A，Meier W.Practical analysis of reduced－round Keccak［C］∥Proc of INDOCRYPT’11，2011：236－254.

［2］ Wang Xiao－yun，Yiqun Lisa Yin，Yu Hong－bo.Finding collisions in the full SHA－1［C］∥Proc of CRYPTO，2005：17－36.

［3］ Wang Xiao－yun，Feng Deng－guo，Yu Xiu－yuan.An attack on hash function HAVAL－128［J］.Science in China（ser.F），2005，48（5）：545－556.

［4］ Wang Xiao－yun，Yu Hong－bo.How to break MD5and other Hash functions［C］∥Proc of EUROCRYPT’05，2005：19－35.

［5］ NIST.SHA－3Competition（2007－2012）［EB/OL］.［2012－12－13］.http：//csrc.nist.gov/groups/ST/hash/sha－3/index.html.

［6］ Bertoni G，Daemen J，Peeters M，et al.The Keccak reference［EB/OL］.［2011－11－17］.http：//KECCAK.noekeon.org/KECCAK－reference－3.0.0.pdf.

［7］ Bertoni G，Daemen J，Peeters M，et al.The Keccak SHA－3 submission［EB/OL］.［2011－11－17］.http：//www.keccak.noekeon.org/keccak－submission－3.pdf.

［8］ Biham E，Shamir A.Differential cryptanalysis of DES－like cryptosystems［C］∥Proc of CRYPTO’09，1990：2－21.

［9］ Dinur I，Dunkelman O，Shamir A.Improved practical attacks on round－reduced Keccak［J］.Journal of Cryptography，2014，27（2）：183－209.

［10］ Bertoni G，Daemen J，Peeters M，et al.Sponge functions［C］∥Proc of ECRYPT Hash Workshop，2007：1.

［11］ Duc A，Guo Jian，Peyrin T，et al.Unaligned rebound attack：Application to Keccak［C］∥Proc of FSE’12，2012：402－421.

［12］ Dinur I，Dunkelman O，Shamir A.Collision attacks on up to 5rounds of SHA－3using generalized internal differentials［C］∥Proc of FSE’13，2013：219－240.

［13］ Lin Dong－dai，Cao Tian－jie.Applied cryptography［M］.Beijing：Science Press，2009.（in Chinese）

［14］ Zhang Shi－bin，Sun Wu－nan，Zhang Jin－quan，et al.Applied cryptography［M］.Xi’an：Xidian University Press，2009.（in Chinese）

［15］ Li Qian－nan，Li Yun－qiang，Jiang Shu－jing，et al.Research on differential properties of Keccak－like nonlinear transform［J］.Journal of Communications，2012，33（9）：140－146.（in Chinese）

附中文参考文献

［13］ 林东岱，曹天杰.应用密码学［M］.北京：科学出版社，2009.

［14］ 张仕斌，孙武南，张金全，等.应用密码学［M］.西安：西安电子科技大学出版社，2009.

［15］ 李倩男，李云强，蒋淑静，等.Keccak类非线性变换的差分性质研究［J］.通信学报，2012，33（9）：140－146.