Security of Cyclic Double Block Length Hash Functions

摘要

We provide a proof of security for a huge class of double block length hash function that we will call Cyclic-DM. Using this result, we are able to give a collision resistance bound for Abreast-DM, one of the oldest and most well-known constructions for turning a block cipher with n-bit block length and 2n-bit key length into a 2n-bit cryptographic hash function. In particular, we show that when Abreast-DM is instantiated using a block cipher with 128-bit block length and 256-bit key length, any adversary that asks less than 2~(124.42) queries cannot find a collision with success probability greater than 1/2. Surprisingly, this about 15 years old construction is one of the few constructions that have the desirable feature of a near-optimal collision resistance guarantee.rnWe are also able to derive several DBL constructions that lead to compression functions offering an even higher security guarantee and more efficiency than Abreast-DM (e.g. share a common key). Furthermore we give a practical DBL construction that has the highest security guarantee of all DBL compression functions currently known in literature. We also provide a (relatively weak) analysis of preimage resistance for Cyclic-DM.