Paper 2015/973

Some Cryptanalytic Results on Zipper Hash and Concatenated Hash

Ashwin Jha and Mridul Nandi

Abstract

At SAC 2006, Liskov proposed the zipper hash, a technique for constructing secure (indifferentiable from random oracles) hash functions based on weak (invertible) compression functions. Zipper hash is a two pass scheme, which makes it unfit for practical consideration. But, from the theoretical point of view it seemed to be secure, as it had resisted standard attacks for long. Recently, Andreeva {\em et al.} gave a forced-suffix herding attack on the zipper hash, and Chen and Jin showed a second preimage attack provided $f_1$ is strong invertible. In this paper, we analyse the construction under the random oracle model as well as when the underlying compression functions have some weakness. We show (second) preimage, and herding attacks on an $n$-bit zipper hash and its relaxed variant with $f_1 = f_2$, all of which require less than $ 2^{n} $ online computations. Hoch and Shamir have shown that the concatenated hash offers only $\frac{n}{2}$-bits security when both the underlying compression functions are strong invertible. We show that the bound is tight even when only one of the underlying compression functions is strong invertible.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
hash functionzipper hashconcatenated hashtimememory trade-off(second) preimageherding attack
Contact author(s)
ashwin jha1991 @ gmail com
History
2015-10-09: received
Short URL
https://ia.cr/2015/973
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/973,
      author = {Ashwin Jha and Mridul Nandi},
      title = {Some Cryptanalytic Results on Zipper Hash and Concatenated Hash},
      howpublished = {Cryptology ePrint Archive, Paper 2015/973},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/973}},
      url = {https://eprint.iacr.org/2015/973}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.