On Diamond Structures and Trojan Message Attacks

The first part of this paper considers the diamond structures which were first introduced and applied in the herding attack by Kelsey and Kohno [7]. We present a new method for the construction of a diamond structure with 2

d

chaining values the message complexity of which is

$\mathrm{O}(2^{\frac{n+d}{2}})$

. Here

n

is the length of the compression function used. The aforementioned complexity was (with intuitive reasoning) suggested to be true in [7] and later disputed by Blackburn et al. in [3]. In the second part of our paper we give new, efficient variants for the two types of Trojan message attacks against Merkle-Damgård hash functions presented by Andreeva et al. [1] The message complexities of the Collision Trojan Attack and the stronger Herding Trojan Attack in [1] are

$\mathrm{O}(2^{\frac{n}{2}+r})$

and

$\mathrm{O}(2^{\frac{2n}{3}}+2^{\frac{n}{2}+r})$

, respectively. Our variants of the above two attack types are the Weak Trojan Attack and the Strong Trojan Attack having the complexities

$\mathrm{O}(2^{\frac{n+r}{2}})$

and

$\mathrm{O}(2^{\frac{2n-s}{3}}+2^{\frac{n+r}{2}})$

, respectively. Here 2

r

is the cardinality of the prefix set and 2

s

is the length of the Trojan message in the Strong Trojan Attack.