Cryptology ePrint Archive: Report 2009/261

Security of Cyclic Double Block Length Hash Functions including Abreast-DM

Ewan Fleischmann and Michael Gorski and Stefan Lucks

Abstract: We provide the first proof of security 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 prove that when Abreast-DM is instantiated with AES-256, i.e. 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.

We generalize our techniques used in the proof of Abreast-DM to a huge class of double block length (DBL) hash functions that we will call Cyclic-DM. Using this generalized theorem we are able to derive several DBL constructions that lead to compression functions that even have a higher security guarantee and are more efficient than Abreast-DM. Furthermore we give DBL constructions that have the highest security guarantee of all DBL compression functions currently known in literature. We also provide an analysis of preimage resistance for Cyclic-DM compression functions. Note that this work has been already presented at Dagstuhl '09.

Category / Keywords: secret-key cryptography / cryptographic hash function, block cipher based, proof of security, double-block length, ideal cipher model, Abreast-DM

Date: received 2 Jun 2009

Contact author: ewan fleischmann at uni-weimar de

Available format(s): PDF | BibTeX Citation

Version: 20090603:102305 (All versions of this report)

Short URL: ia.cr/2009/261

Discussion forum: Show discussion | Start new discussion