Trojan message attack on the concatenated hash functions

Abstract

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 function 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 2l+2n−l+1+n·2k+1blocks and the time complexity is about O (n·2n+k+l·2l)computations of the compression function,much less than the ideal value O(n·22n+k).

Keywords

• hash functions;concatenated hash;Trojan message attack;multicollsion;complexity