Paper 2002/066

Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV

John Black, Phillip Rogaway, and Thomas Shrimpton

Abstract

Preneel, Govaerts, and Vandewalle considered the 64 most basic ways to construct a hash function $H:\{0,1\}^*\rightarrow\{0,1\}^n$ from a block cipher $E:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}^n$. They regarded 12 of these 64 schemes as secure, though no proofs or formal claims were given. The remaining 52 schemes were shown to be subject to various attacks. Here we provide a formal and quantitative treatment of the 64 constructions considered by PGV. We prove that, in a black-box model, the 12 schemes that PGV singled out as secure really \textit{are} secure: we give tight upper and lower bounds on their collision resistance. Furthermore, by stepping outside of the Merkle-Damgard approach to analysis, we show that an additional 8 of the 64 schemes are just as collision resistant (up to a small constant) as the first group of schemes. Nonetheless, we are able to differentiate among the 20 collision-resistant schemes by bounding their security as one-way functions. We suggest that proving black-box bounds, of the style given here, is a feasible and useful step for understanding the security of any block-cipher-based hash-function construction.

Metadata
Available format(s)
PS
Publication info
Published elsewhere. To appear in Advances in Cryptology -- CRYPTO'02
Keywords
Block cipherscryptographic hash functionsmodes of operationproving security
Contact author(s)
teshrim @ ucdavis edu
History
2002-06-03: received
Short URL
https://ia.cr/2002/066
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/066,
      author = {John Black and Phillip Rogaway and Thomas Shrimpton},
      title = {Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV},
      howpublished = {Cryptology ePrint Archive, Paper 2002/066},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/066}},
      url = {https://eprint.iacr.org/2002/066}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.