The preimage security of double-block-length compression functions

Jooyoung Lee; Martijn Stam; John Steinberger

Paper 2011/210

The preimage security of double-block-length compression functions

Jooyoung Lee, Martijn Stam, and John Steinberger

Abstract

We give improved bounds on the preimage security of the three ``classical'' double-block-length, double-call, blockcipher-based compression functions, these being Abreast-DM, Tandem-DM and Hirose's scheme. For Hirose's scheme, we show that an adversary must make at least $2^{2n-5}$ blockcipher queries to achieve chance $0.5$ of inverting a randomly chosen point in the range. For Abreast-DM and Tandem-DM we show that at least $2^{2n-10}$ queries are necessary. These bounds improve upon the previous best bounds of $\Omega(2^n)$ queries, and are optimal up to a constant factor since the compression functions in question have range of size $2^{2n}$.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Hash functions preimage resistance ideal cipher model
Contact author(s): stam @ cs bris ac uk
History: 2011-05-06: received
Short URL: https://ia.cr/2011/210
License: CC BY

BibTeX

@misc{cryptoeprint:2011/210,
      author = {Jooyoung Lee and Martijn Stam and John Steinberger},
      title = {The preimage security of double-block-length compression functions},
      howpublished = {Cryptology ePrint Archive, Paper 2011/210},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/210}},
      url = {https://eprint.iacr.org/2011/210}
}