Efficient Construction of Diamond Structures

摘要

A cryptographic hash function is a function H : {0, 1}~* → {0,1}~n, that takes an arbitrary long input and transforms it to an n-bit output, while keeping some basic properties that ensure its security. Because they are very useful in computer security, cryptographic hash functions are amongst the most important primitives in the modern cryptography. The Merkle-Damgard structure is an iterative construction for transforming a compression function f : {0, 1}~n × {0, 1}~m → {0, 1}~n into a hash function, and it is widely used by different hash functions such as MD4, MD5, SHA0 and SHA1. Some generic attacks on this structure were presented in the last 15 years. Some of these attacks use the diamond structure, first introduced by Kelsey and Kohno in the herding attack. This structure is a complete binary tree that allows 2~k different inputs to lead to the same hash value, and it used in numerous attacks on the Merkle-Damgard structure. Following the herding attack, other papers analyzed and optimized the diamond structure. The best time complexity of constructing a diamond structure to date is about a · 2~(n+k)/2+2 for a ≈ 2.732. In this work we suggest a new and simple method for constructing a diamond structure with better time complexity of c · 2~(n+k/2+2) for c ≈ 1.254. We present a pseudo-code for this new method, and a recursive formulation of it. We also present analysis supported by experiments of our new method.