性质发现

\(\theta\) 运算性质

\(\theta\)运算结果受每个位置原有值与其两侧两个 column parity 的影响，即\(CP[x-1][z]\)与\(CP[x+1][z-1]\)。

通常情况，\(\theta\)具有扩散性，变量经\(\theta\)运算后会影响临近列，使区域由原本的定值状态变为代数一次的变量状态，或增加原有变量状态的变量元数。

我们在研究过程中希望尽量降低\(\theta\)带来的这类影响，故先分析该运算的一些特殊性质（与《新的低轮 Keccak 线性结构设计》中描述类似）。

性质 1 若进行\(\theta\)前，输入状态\(A\)的各\(CP\)核为定值\(c\)，\(c\)为\(0\)或\(1\)，则经过\(\theta\)运算的状态\(A'\)一定线性，且变量不扩散。

推论 1 若输入状态\(A\)的\(CP\)核均为\(0\)，则\(\theta\)为恒等运算（identity）。输出状态\(A'=A\)。

\(\chi\) 运算性质

\(\chi\)运算是 Keccak 轮函数五个运算中唯一的非线性运算，为代数二次。=，可以看作一个小型 S 盒。其运算每次在一个横行（row）进行。非线性运算是保证哈希函数不可逆性的关键，因而在破解低轮 Keccak 中，我们也特别研究了\(\chi\)运算的性质。（混编一轮、二轮 Keccak 攻击文献中的性质描述）

性质 2 考虑\(\chi\)运算与其逆运算\(\chi^{-1}\)，对于全部已知的输出序列\(b_0,b_1,b_2,b_3,b_4\)，我们可以直接逆运算得到输入序列。

\[a_i = b_i \oplus (b_{i+1} \oplus 1) \cdot (b_{i+2} \oplus (b_{i+3} \oplus 1) \cdot b_{i+4})\]

逆运算\(\chi^{-1}\)代数次数为 3。

性质 3 在\(\chi\)运算中，任意非相邻三位的值已知，所有输出可以写成输入的线性组合形式。

性质 4 对于\(a_{i+3}=1\)，可给出\(a_i,a_{i+1},a_{i+2}\)的线性构造式。

\[a_{n+2} = b_{n+2}\]

\[a_{n+1} = b_{n+1} \oplus (b_{n+2} \oplus 1)\]

\[a_n = b_n \oplus (b_{b+1} \oplus b_{n+2} ) \cdot b_{n+2}\]

一轮攻击

单消息块构造法

计算平台

• Dell
• 4-core 3.40 GHz Intel Core i7 CPU
• 500GB, 7200 RPM SATA disk
• 4096-byte block size
• 64-bit Windows

计算结果

原像值：

哈希值：

位数与得分：

证明截图：

攻击思路

根据\(\chi^{-1}\)与\(\iota^{-1}\)运算性质，我们知道\(h'\)可由\(h\)得到，且结果唯一。\(h_0',h_1',h_2',h_3'\)经\(\pi^{-1}\)的换道与\(\rho ^{-1}\)的 z 轴移动，我们发现道排布在\(y=x\)对角线上，对应输入的位置得到。

\[h'[0] = e[0]\] \[h'[1] = e[6]\] \[h'[2] = e[12]\] \[h'[3] = 0\]

由于\(h'[3]\)的限制下（其位置超过了与输入消息块的长度，处于容量 c 中），构造输入串满足\(\theta\)运算恒等，图 3 图 4 对应位置元素相等，从而可以得到如下 5 个方程。（\(h_0'-h_2'\)确定 \(e_0',e_6'\) 和 \(e_{12}'\)），可以构造信息值；由 \(h_3'=h_4'=0\)，\(h_0=h_3+RC\)，且希望前置 0 串最长，我们让 \(h_0=0,h_3=RC=1\)，即在一个消息块的情况下，最多满足输出前置 0 串 192 位。

攻击过程描述

Step 1 构造合适的 Hash 值所在行：

由 Hash 值出发，如果要进行\(\chi^{-1}\)逆变换的话必须要满足一个横行（row）五小块，，所以补一个块 \(h_4\)得到 \(h_0,h_1,h_2,h_3,h_4\)，再根据攻击思路中的分析，构造合适摘要值如图 1 所示，图 3 为初始信息值。

Step 2 执行\(\chi^{-1} \circ \iota^{-1}\)逆运算

计算\(h'\)值

Step 3 构造输入消息满足\(\theta\)恒等 Step2 得到的对角线的值（转换位置）后，依据推论 1 要求，构造剩余每列的输入值，使输入的\(CP\)核均为 0，保证\(\theta\)恒等。

双消息块构造法

计算平台

计算结果

原像值：

哈希值：

位数与得分：

证明截图：

攻击思路

完成单 Message block 的情况下，我们思考是什么导致了\(h_3\)的限制，实际上是由于初始 State，除 r 长度内可通过输入长度，其他位置均为 0，因此倒推过程中我们必须满足\(h'_3=0\)。

不过经过一个 Message 的轮转后，其他位置不再是固定的 0 值了，我们的想法：通过构造第一个 Message D 使\(h_0'h_1',h_2'h_3'\)达到一个合适状态\(F'\)（使得经最后两运算子后\(F = (\iota \circ \chi) F\)），\(F\)全为 0，即\(h_0h_1h_2h_3\)均为 0。

攻击过程描述

二轮攻击

Step 1 构造第一个消息块，满足\(\theta\)恒等，进行轮转：

需要保证状态尽量简单，两横行相等，其他七小块全为 0，执行第一轮轮转。

Step 2 构造全 0 哈希值，并进行逆运算：

得到的对角线需要符合 Step 1 轮转后结果异或第二消息块后的结果，由于构造第二消息块会满足\(\theta\)的恒等性质，所以这里不需要考虑\(\theta\)函数的影响。

Step 3 构造第二个消息块：

进行第二消息 Message E 的构造，目标有三个：

• 保持第二轮\(h_3'\)位置的状态位置
• 斜线（影响 hash 值）异或指定值达到\(F'\)
• 其他地方补 1 达到纵列\(CP\)值为 0，使\(\theta\)恒等

单消息块构建线性系统

计算平台

计算结果

原像值：

哈希值：

位数与得分：

证明截图：

攻击思路

利用线性结构（加引用，提出者），（提出者）给出一种在时间复杂度为\(O(1)\)的针对 Keccak256 的原像攻击方法。

我们构造了作者提出的 2 轮线性结构，利用该方法对全部 256 位为 0 的哈希值进行原像攻击，得到了符合要求的消息值。

攻击过程描述

（lemma：中间只要隔一列设置变量 即可以保证 X 变换之后 变量仍然线性）

Step 1 构造 2 轮线性结构的输入：

按照论文给出的构造方法构造原像值（只用一个信息块）。在该构造方法中，因为我们的输入值是 17（1088）个 line 且为了考虑 padding 规则最后一个 line 的最后一位应为 1; 为了满足 Lemma1，我们的未知数最多只有 7 个，即 x0-6; 为了满足 θ 变换 as identity，我们可以得到两个方程和第二列的前三个位置必有一个 1。如下图 10 所示

Step 2 变换后求解线性方程：

对该信息块进行一轮置换得到图 12，此时状态既不满足\(\theta\)是恒等的的（推论 1） 也不满足 Lemma1，如果我们继续进行第二轮变换无法保证线性。为了构造线性方程组解得原像，我们利用中间状态相等的原则，一轮变换后的图 12 进行 \(\theta\) 变换（结果可用变量线性表示）和将期望的最终结果（即 256 位全为 0）进行除了 θ 变换外其他四种变换的逆变换（结果已知）的对角线元素相等。从而可以列出 \(5*64+2*64\) 个满秩方程（\(7*64\) 个未知数），解得唯一解。