密码技术学习——Keccak攻击进度工作文档

性质发现

$\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$,我们可以直接逆运算得到输入序列。

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

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

性质 4 对于$a_{i+3}=1$,可给出$a_i,a_{i+1},a_{i+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’[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)进行除了 θ 变换外其他四种变换的逆变换(结果已知)的对角线元素相等。从而可以列出 $564+264$ 个满秩方程($7*64$ 个未知数),解得唯一解。