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

"特洛伊"消息攻击是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)。