一个阻止内部碰撞转状态碰撞的海绵建构变体

摘要 对海绵建构进行了洞察后，作者发觉海绵建构及其多数变体建构在对抗一些一般攻击（包过Joux 的多碰撞攻击，Dean的固定点技术，Kelsey and Schneier的长消息次原像攻击，Kelsey and Kohno的集群攻击等）时，主要采取的方法是提高内部状态的容量，本文给出了一个基于海绵建构的新的密码建构（简称为ESC），作者证明了ESC在带有相同内部状态容量时一般情况下将比海绵建构更加抵抗上述的一般攻击。作者的设计思想来源于海绵建构与建构的差别，由于海绵建构是基于变换（或置换）函数的迭代建构，变换（或置换）函数所处理的中间链值即整体状态下还有所谓的内部状态。当攻击者在对海绵建构发动上述等一般攻击时，一般情况下最好的方法是先寻找内部碰撞，然后将其转化为状态碰撞。因此如果能增加内部碰撞向状态碰撞转换的工作量，则自然增加了对上述一般攻击的抵抗性。最后作者还讨论了ESC的安全和效率问题。

关键词建构； 海绵建构； 多碰撞攻击； 长消息次原像攻击； 集群攻击

中图分类号 O29 文献标识码A 文章编号 1674-6708（2014）113-0149-02

1 ESC

如图1所示，与海绵建构不同的是ESC在吸收阶段每次调用完变换（或置换）函数后，再用刚被吸收过的消息块进行一个反馈异或。我们将用来表示ESC的位率，用来表示ESC的内部状态容量，用b来表示r+c。

定义1.ESC吸收路径P后的后尾状态指的是那个进行了消息反馈异或后得到的状态，我们将用来表示。我们将用，，和来分别表示ESC吸收路径P后后尾状态的内部状态，外部状态和整体状态。定义2. ESC的一对内部碰撞指的是吸收一对不同的路径P和P’后后尾状态的内部状态相等，即。定义3. ESC的一对状态碰撞指的是吸收一对不同的路径P和P’后后尾状态相等，即。

2 ESC的安全及效率分析

2.1 ESC的内部碰撞

类似于文献[3]中海绵建构的方法，我们可得到ESC内部碰撞具有与海绵建构相同的成本函数。

2.2 ESC的内部碰撞转状态碰撞

以下将讨论在吸收阶段给定一对ESC的内部碰撞，将其转换为状态碰撞（后尾状态）的概率或成本。

如果给定一对非回路的内部碰撞，即它们之间一个不是另一个的前缀，满足：和 。尽管攻击者还是可以找两块消息块满足：。然而由于消息块的反馈异或使得吸收完构造消息后后尾状态的外部状态又不相同了：。此种方法永远也不能产生后尾状态碰撞。但如果攻击者寻找两块消息满足：。当f是一个随机变换函数时，将以的小概率成立；当f是一个随机置换函数时，将以（其中N表示已调用置换函数的次数，不计重复，一般情况下N«）的小概率成立。

如果给定一对回路内部碰撞，即它们之间一个是另一个的前缀（不失一般性假设，且路径的最后一块消息块为，并且假设都不为零块），满足：和 。回路中包含K个超级节点（指内部状态相同的状态集），从上到下分别表示为，第一次进入超级节点的后首状态记为，对应的后尾状态记为，并且有，到达超级节点的前状态记为，

并且有，第一次进入超级节点的后首状态记为，对应的后尾状态记为，并且有，到达超级节点的前状态记为，并且有，如此一直到第K个超级节点，第一次进入超级节点的后首状态记为，对应的后尾状态记为，并且有，到达超级节点的前状态记为，并且有，第二次进入超级节点（即产生回路）的后首状态记为，对应的后尾状态记为，并且有，此时由假设只是内部碰撞所以有。当K=1时，即回路中只有一个超级节点，则有：，， 。由，则有：

。

。此时必有：

。则路径P与路径产生状态（后尾状态）碰撞，因此K=1时再进行一次循环即可找到状态碰撞（但是这种可能即变换或置换后保留内部状态不变的可能性少）。当K>1时，即回路中至少有两个超级节点，则可选择消息块，使得，则会到达，对应产生的后尾状态为，由于，所以，此时选择消息块，使得，则会到达，对应产生的后尾状态为，由于，所以，如此下去直到，此时选择消息块，使得，则会到达，对应产生的后尾状态为，由于，所以，此时，如果，则可选择消息块，使得，则会到达，对应产生的后尾状态为，由于，所以，如此重复上面的步骤，得到，进而得到，此时，如果，如此下去直到最小的Y（取值大于等于2，因为由假设第一次循环只是产生内部碰撞）次循环产生，则路径对产生状态（后尾状态）碰撞，而且不存在，因为如果，则可推出与Y是最小值矛盾，也不存在，因为如果，则可推出也与Y是最小值矛盾。经过Y次循环后还不产生后尾状态碰撞的概率为：。因此产生后尾状态碰撞的概率为：。当1«，我们使用来逼近，推出：

。异或成本函数为：

。推出平均情况下当Y至少为时会产生状态（后尾状态）碰撞。当f为置换函数时，K>1（中没有零块）的情形可用中间相遇攻击构造出。构造方法如下：

假设我们选择最终碰撞的后尾状态为，从开始找一块消息块，得到，然后求得到超级节点中的后首状态，进而求得到对应的后尾状态，如此一直到得到超级节点中的后尾状态，然后找个消息和个内部状态与超级节点相同且整体状态异于的后首状态，然后求得到个后首状态，求得到个前状态，根据概率知识会有一对和的内部状态一样，则可得到，这时再找，使得，然后便可进入K情况下的循环。若全是零块即时，则有：

此时有

则第二次循环就会产生状态（后尾状态）碰撞。若中有部分是零块的情形也可类似分析。总之，排除掉K=1及中含有零块等的特殊情况时，一般情况下将这对回路内部碰撞转化为状态碰撞平均需要多次异或，而且会导致状态碰撞对消息的长度差距为至少块，致使固定点的消息块数太多，这也降低了攻击的实效性。

读者还可尝试将多个内部碰撞转化为状态碰撞。

2.3 ESC与随机预言机的不可区分和不可区别

类似于文献[3]容易证明ESC（在吸收和挤压阶段位率相同时）与海绵建构具有相同的可区分和区别有利条件。

2.4 ESC的效率分析

我们以每次调用变换（或置换）函数f时多一个消息块的反馈异或为代价，增加了一般攻击的复杂度，作为效率上的补偿，类似于PHOTON，我们还可允许挤压阶段的位率与吸收阶段的位率不同，假设输出消息摘要比特位为n，根据文献[3]对摘要进行输出捆绑，当nb时则为，增大当然会导致输出捆绑和挤压阶段内部碰撞的容易化，但只要在安全允许范围内我们就可以适当的增加 来减少挤压阶段所花的时间。

3 结论

本文中作者提出了一个新的海绵变体建构ESC，消息块的反馈异或使得一般情况下内部碰撞转状态碰撞的工作量增加了，自然也就增加了上述一般攻击的复杂度，同时也维持了建构的简单性，类似于文献[3]容易证明ESC（在吸收和挤压阶段位率相同时）与海绵建构具有相同的区分和区别有利条件，我们还允许在安全范围内适当的增加挤压阶段的位率来减少挤压时间，提高效率。

参考文献

[1]Ivan D.:A Design Principle for Hash Functions[J].In Gilles Brassard，editor，Advances in CRYPTO 89，Lecture Notes in Computer Science， vol.435，pp.416-427.Springer-Verlag，1989.

[2]Gauravaram，P.，Kelsey，J.，Knudsen，L.R.， Thomsen，S.S.:On hash functions using checksums[J].Int.J.Inf.Secur.vol.9(2)，pp.137-151(2010).

[3]G.Bertoni，J.Daemen，M.Peeters，and G.Van Assche，Cryptographic sponge functions[OL]， (2012/02/15)[2013/11/30]/.[4]E.Biham，O.Dunkelman，The SHAvite-3 hash function[OL]，(2010/08/23)[2013/11/30].