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

Ewan Fleischmann; Michael Gorski; Stefan Lucks

Paper 2009/261

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

Ewan Fleischmann, 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.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: cryptographic hash function block cipher based proof of security double-block length ideal cipher model Abreast-DM
Contact author(s): ewan fleischmann @ uni-weimar de
History: 2009-06-03: received
Short URL: https://ia.cr/2009/261
License: CC BY

BibTeX

@misc{cryptoeprint:2009/261,
      author = {Ewan Fleischmann and Michael Gorski and Stefan Lucks},
      title = {Security of Cyclic Double Block Length Hash Functions including Abreast-DM},
      howpublished = {Cryptology ePrint Archive, Paper 2009/261},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/261}},
      url = {https://eprint.iacr.org/2009/261}
}