对联接杂凑函数的“特洛伊”消息攻击

Trojan message attack on the concatenated hash functions

"特洛伊"消息攻击是Andreeva等针对MD结构杂凑函数提出的一种攻击方法,首次将其应用于不同于MD结构的一类杂凑函数,即联接杂凑。结合联接杂凑的特点,综合利用Joux的多碰撞和深度为n-l的"钻石树"结构多碰撞,构造出了2n-bit联接杂凑函数的长度为n·2~k块的"特洛伊"消息,并据此首次提出了对其的固定前缀"特洛伊"消息攻击,其存储复杂性为2l+2^(n-l+1)+n·2^(k+1)块消息,时间复杂性为O(n·2^(n+k)+l·2~l)次压缩函数运算,远低于理想的时间复杂性O(n·2^(2n+k)。

The Trojan message attack was proposed by Andreeva, et al. aiming at the hash functions with MD structure. First it was applied on the hash fimction beyond MD structure, that was, concatenated hash. Utilizing the property of the concatenated hash, and combining the Joux＇s multicollision and the ＂diamond＂ structure with the depth of n-l, a Trojan message of the length n. 2k blocks for the 2n-bit concatenated hash was constructed, based on which a chosen-prefix Trojan message attack was first proposed. And the memory complexity of proposed attack is about 21 ＋ 2^n-1＋1 ＋ n- 2TM blocks and the time complexity is about O（n. 2^n＋1 ＋ l·2^l） computations of the compression function, much less than the ideal value O（n. 2^2b＋k）