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

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