New Attacks on the Concatenation and XOR Hash Combiners

摘要: We study the security of concatenation combiner $$H_1M \Vert H_2M$$H1Mi¾?H2M for two independent iterated hash functions with n-bit outputs that are built using Merkle-Damgard construction. In 2004 Joux showed an internal state does not offer better collision and preimage resistance compared to a single strong function. On other hand, problem devising second attacks faster than $$2^n$$2n against this has remained open since 2005 when Kelsey Schneier function optimal long messages. In paper, we develop new algorithms cryptanalysis combiners use them devise first attack on combiner. The finds preimages messages longer $$2^{2n/7}$$22n/7 complexity $$2^{3n/4}$$23n/4. This shows is as ideal function. Our methods also applicable well-studied combiners, $$2^{2n/3}$$22n/3 XOR \oplus functions. improves upon by Leurent Wang presented at Eurocrypt 2015 whose $$2^{5n/6}$$25n/6 but unlike our HAIFA functions. Our exploit properties random mappings generated fixing message block input compression $$H_1$$H1 $$H_2$$H2. Such have been widely used in cryptanalysis, ways combiners.