代数系统求解4轮Keccak-256原像攻击的完善

裴君翎，陈鲁生

南开大学 数学科学学院，天津 300071

Keccak哈希函数[1]由比利时密码学家Bertoni等领衔设计，于2008年成为了美国国家标准技术研究所（NIST）开展的第三代安全哈希算法（SHA-3）竞赛[2]的候选作品，于2012年赢得了该竞赛，随后，美国国家标准技术研究所于2015年将其标准化为第三代安全哈希函数。自公开发布以来，Keccak哈希函数接受了深入的安全分析，包括传统的安全概念，如抗碰撞攻击、抗原像攻击、立方攻击[3]、零和区分器[4]以及在消息认证码[5]、流密码和认证密码模式下的安全性。

由于Keccak哈希函数在全球应用的广泛性和重要性，针对它的多种原像攻击方法被相继提出。文献[6]基于中间相遇攻击的方法实现了2轮Keccak哈希函数的原像攻击；文献[7]利用SAT求解器实现了2轮Keccak哈希函数的原像攻击且运行时间更短；文献[8]利用旋转密码分析法实现了4轮Keccak-384和Keccak-512的原像攻击；文献[9]基于多项式枚举算法实现了8轮Keccak哈希函数的原像攻击；文献[10]实现了9轮Keccak哈希函数的原像攻击。

2016年，文献[11]提出了基于代数系统求解的方法，利用线性结构得到原像攻击的更好分析结果。随后的一年，文献[12]沿用了这一方法并提出了更精细的交叉线性结构，在这个结构中，不同的多项式存在相同的线性因子，通过枚举这些线性因子可以得到更多线性方程，这进一步降低了3轮Keccak-256原像攻击的复杂度。2019年，文献[13]在文献[12]的基础上又进行了改进，基于非线性代数方法将攻击过程分为两个阶段，第一阶段受到一组新提出的中间状态的约束，第二阶段受到给定哈希值的约束，这两个阶段的约束条件均比直接由初始值和哈希值得到的条件弱，因此每次只需考虑较少的约束进而降低了复杂度，给出了目前3轮和4轮Keccak-256原像攻击的最好结果，4轮Keccak-256原像攻击的理论复杂度为2239。随后，文献[14]将这种非线性代数的思想引入到Keccak-384和Keccak-512的原像攻击中，给出了目前2轮、3轮和4轮Keccak-384以及2轮和3轮Keccak-512原像攻击的最好结果。

求解代数系统是目前Keccak哈希函数原像攻击的最有效方法之一，在构造代数系统时，降低系统的次数是攻击成功的关键。本文讨论4轮Keccak-256的原像攻击，对文献[13]的线性化过程进行了完善，将更多的非线性比特位线性化，理论复杂度由2239降低为2216。

1 Keccak哈希函数

关于Keccak哈希函数的完整描述参阅文献[1]，在此不再详述。为讨论方便起见，仅描述关键部分。

1.1 Keccak哈希函数的海绵结构

Keccak哈希函数采用了如图1的海绵结构[15]，其中M表示任意长度的消息，Z表示函数的输出，l表示函数的输出长度，r表示比特率，c表示容量，f表示置换，b=r+c表示置换宽度。

图1 Keccak哈希函数的海绵结构Fig.1 Sponge construction of Keccak Hash function

海绵结构分为吸收阶段和挤压阶段。在吸收阶段，消息M首先进行填充，填充后消息的长度是比特率r的倍数。接着，消息分为长度为r的若干消息块。随后，从全部为0的初始值开始，b比特状态的前r比特与消息块进行异或运算并与后c比特共同作为置换f的原像，重复此步骤，直到处理完所有消息块。在挤压阶段，首先输出前r比特。随后，在经过置换f后可以输出更多的r比特，重复该过程，直到获得所需长度l的所有比特位。最后输出这l比特。

根据参数集(b,c,l)取值的不同，Keccak哈希函数有不同的版本。本文仅考虑Keccak哈希函数的置换f的宽度b=1 600的情形，此时容量c=2l，其中l∈{224,256,384,512}，记为Keccak-l。Keccak哈希函数的填充规则形如“M10…1”，即，它首先填充单个比特“1”，后跟若干比特“0”，最后再填充单个比特“1”，填充后消息的长度为r的倍数。满足这一条件的“10…1”比特串有多个，选择其中长度最短的进行填充。因此，最少填充2比特，最多填充r+1比特。

1.2 Keccak哈希函数中的置换f

Keccak哈希函数中的置换f的宽度共1 600 bit，表示为如图2（a）所示的5×5个64 bit的道。每一比特都可以表示为二元域上的一个三维数组a[x][y][z]，消息串M通过M[64(5y+x)+z]=a[x][y][z]进入三维数组进行变换。x轴和y轴构成的二维平面称为“面”，如图2（b）所示。[x]表示列的索引，[y]表示行的索引，[z]表示道的索引，[x]和[y]的取值均从0到4，[z]的取值从0到63。有时省略索引[z]、索引[y][z]或全部3个索引，这表示该条陈述适用于省略的索引中的所有值。当某些比特被设定为未知量时，如果一个比特可以表示为关于这些未知比特的线性多项式，则称这个比特是线性的，类似地，如果一个比特可以表示为关于这些未知比特的二次多项式，则称这个比特是二次的。

图2 数据状态Fig.2 Data state

Keccak哈希函数中的置换f是迭代置换，由24轮置换R组成。每轮置换R=ι∘χ∘π∘ρ∘θ由以下5个部件组成：

在上述定义中，“⊕”表示二元域上的加法，“⊕”表示二元域上的求和，“·”表示二元域上的乘法，“RCz”表示轮常数，省略了RCz的细节，因为它不影响攻击。“r[x][y]”是与道相关的旋转常数，表示针对二维状态a[x][y]的z轴进行移位操作，取值如表1所示。

表1 r[x][y]的取值Table 1 Value of r[x][y]

通过对θ、ρ、π、χ和ι共5个部件的表达式进行分析，不难发现部件ρ、π和ι属于线性运算，其输出结果均保持线性。部件θ虽然属于线性运算，但未知量经过θ会扩散到周围两列，这大幅度增加了输入部件χ的未知量个数，不利于线性化操作。若各列列和均为0或1，则经过部件θ的状态一定可以保持线性且未知量不扩散，因此，在经过部件θ前设定含未知量的各列的和均为常数是防止未知量扩散的一个重要思想。部件χ是唯一的非线性部件，处于同一行的未知量经过χ后会相互影响。文献[8]和[10]分别给出了如下关于部件χ的两个命题，这两个命题在后续原像攻击的分析中起到至关重要的作用。

命题1给定部件χ的5个输出比特中的连续t个，可以建立至少t-1个关于输入比特的线性方程。给定连续的输出比特数与线性方程个数的关系如表2所示。

表2 给定连续的输出比特数与方程个数的关系Table 2 Relationship between number of given continuous output bits and number of equations

命题2令初始状态（a′）（内部比特用a[x][y][z]表示）如图3所示，如果：

图3 初始状态为(a′)的2轮置换fFig.3 2-round permutation f with initial state(a′)

则存在一组常数{s[x][z]}使得当各列和为定值{s[x][z]}时，一定能够通过θ由状态(a′)得到状态(b)，进而Keccak哈希函数中的置换f能够以194的自由度保持2轮线性结构。

2 4轮Keccak-256原像攻击

4轮Keccak-256的输出长度l=256，置换f由24轮置换R组成。本文采用与文献[10]一致的分析方法和相同的代数系统。将攻击过程分为两个阶段，两阶段分别得到一个消息块，它们共同构成原像，其中第一阶段受到一组新提出的中间状态的约束，第二阶段受到给定哈希值的约束，这样每次考虑较少的约束以获得更多的自由度，进而有效降低复杂度。

具体来说，如图4所示，状态（A）（内部比特用e[x][y][z]表示）是第一阶段的输出状态，也是攻击的中间状态，对于Keccak-256，它的容量c=512意味着最后8个道不能通过异或第二个消息块而改变，因此为了使状态（B）满足式（1）和（2），需要确保下述64+64+64+1=193个方程全部成立：

图4 异或第二个消息块后的状态变化Fig.4 State change after XOR the second message

2.1 4轮Keccak-256原像攻击第一阶段

原像攻击的第一阶段同文献[10]，为完整起见，现简要描述过程。该阶段的输出状态满足式（3），且根据填充规则还需满足e[1][3][63]⊕1=e[1][4][63]⊕1，因此，第一阶段需要满足193+1=194个等式。在原像的所有取值中，有一半数量的取值能够使得等式e[2][3][63]⊕1=e[2][4][63]成立，对(e[3][3][z],e[3][4][z])、(e[4][3][z],e[4][4][z])和(e[1][3][63],e[1][4][63])的情况，分析是相同的，因此，至多选取原像的2194个可能的值就能确保上述194个等式全部成立，故第一阶段复杂度为2194。使得194个等式全部成立的原像即为第一个消息块。

2.2 4轮Keccak-256原像攻击第二阶段

同文献[10]构造代数系统的方法，根据命题2，在精心设置第二个消息块之后得到图5中的初始状态。初始状态中深色格子为未知量，因此代数系统包含10×64=640个未知量。为防止第1轮和第2轮置换的部件θ引起未知量扩散，设定含未知量的各列的和均为常数，得到5×64+2×64=448个线性方程，其中2个方程线性相关。第3轮置换中，经过部件χ之后的比特全部变为二次的，因此根据命题1可以得到256个二次方程，这些二次方程是难解的，需要线性化。本文提出的线性化方法不同于文献[10]，更充分地利用了各多项式比特之间的关系。

图5 4轮Keccak-256原像攻击第二阶段Fig.5 Second stage of 4-round Keccak-256 preimage attack

如图5，第3轮置换经过部件χ之前的状态为(a)，设其中比特为l[x][y][z]；第3轮置换经过部件χ之后的状态为(b)，设其中比特为q[x][y][z]；第4轮置换经过部件θ之后的状态为(c)，设其中比特为r[x][y][z]。将二次方程线性化的过程就是将r[x][y][z]线性化的过程。根据部件θ的表达式可得：

其中所有q[x][y][z]是二次比特。注意到：

q[x][y]=l[x][y]⊕(l[x+1][y]⊕1)·l[x+2][y]

即q[x][y][z]中只有一个二次项，它由l[x+1][y][z]和l[x+2][y][z]生成，因此，如果设l[x+1][y][z]或l[x+2][y][z]为常数则可以将q[x][y][z]线性化。同时，还发现枚举l[x+2][y][z]的值可以将q[x][y][z]和q[x+1][y][z]线性化。

接下来以r[1][1][Z]、r[2][2][Z]和r[3][3][Z-1]为例描述线性化的过程。

如图6所示，枚举l[2][y][Z]的值将q[0][y][Z]和q[1][y][Z]线性化，枚举l[4][2][Z]的值将q[2][2][Z]线性化，枚举l[4][y][Z-1]的值将q[3][y][Z-1]和q[2][y][Z-1]线性化，由于：

图6 4轮Keccak-256二次方程线性化过程Fig.6 Linearization processes of 4-round Keccak-256 quadratic equations

因此枚举l[2][y][Z]、l[4][2][Z]和l[4][y][Z-1]的值之后可以将r[1][1][Z]和r[2][2][Z]线性化。再枚举l[1][y][Z-2]和l[3][1][Z-2]的值将q[0][y][Z-2]、q[1][1][Z-2]和q[4][y][Z-2]线性化，由于：

因此r[3][3][Z-1]可以被线性化。依照上述步骤还可以将r[0][0][Z-2]、r[1][1][Z-2]、r[2][2][Z-3]、r[3][3][Z-3]、r[0][0][Z-4]……线性化，每5个线性化过程后，线性化的二次比特出现在面上的同一位置。表3列出了5个线性化过程中每个面上枚举的线性多项式个数、线性化的二次比特数以及得到的线性方程个数。5个面共枚举29个线性多项式，线性化二次比特8个，得到37个线性方程。

表3 5个线性化过程中各面上的情况Table 3 Situation on each side in 5 linearization processes

不失一般性地，假设线性化的二次比特分布在第Z-K面至第Z面上，则在这个过程中不仅需要枚举第Z-K面至第Z面的线性多项式的值，还需枚举第Z-K-1面的线性多项式的值。因此，在代数系统中，如果枚举=150个线性多项式，则可以将个二次比特线性化并得到个线性方程，为解该代数系统，再猜测640-446-190=4个线性比特的值即可。此时，系统包含640个未知量，446+190+4=640个线性方程，256-40=216个二次方程。该代数系统的解为图5初始状态深色格子的值，将该状态与第一阶段的输出状态进行异或运算即得到第二个消息块，两个消息块共同构成了原像。

根据文献[8]，利用代数系统求解进行原像攻击的复杂度由解线性方程组的次数来衡量。为了得到这个系统的解，可以变换第2轮已固定的列和的值以及被枚举的线性多项式的值。因此，需要枚举2216次来确保216个二次方程全部成立，即，需要解2216次线性方程组，这一阶段的复杂度为2216，它高于找到第一个消息块的复杂度，故4轮Keccak-256原像攻击复杂度为2216。

3 结束语

本文讨论了基于代数系统求解的4轮Keccak-256原像攻击。在已有的最好方法中，线性化过程是以两个面为基本单位对一个面的二次比特线性化，理论复杂度为2239。本文完善了上述线性化过程，每两个相邻的面都可以将一个面的二次比特线性化，更充分地利用了各线性比特之间的关系，将理论复杂度降低为2216。这种完善后的线性化方法对基于代数系统求解的其他具有海绵结构的哈希函数的原像攻击同样具有参考意义。