Paper 2005/443

Revised: Block Cipher Based Hash Function Construction From PGV

Duo Lei

Abstract

Preneel, Govaerts, and Vandewalle[12] considered the 64 most basic ways to construct a hash function from a block cipher, and regarded 12 of these 64 schemes as secure. Black, Pogaway and Shrimpton[3] proved that, in black-box model, the 12 schemes that PGV singled out as secure really are secure and given tight upper and lower bounds on their collision resistance. And also they pointed out, by stepping outside of the Merkle-Damgard[5] approach to analysis, an additional 8 of the 64 schemes are just as collision resistant as the first group of schemes. In this paper we point out that the 12 compression functions that PGV singled out are free start collision resistant and others are not, the additional 8 compression functions are only fix start collision resistant as singled out by BRS, the hash functions based on those 20 schemes are fix start collision resistant, the upper bound of collision resistance and preimage resistant are given based on conditional probability of compression function, not based on assumption of random oracle model, the bounds have more practical value than the bounds given by BRS. In view point of collision resistant, the best 4 schemes are not among the 12 schemes singled by PGV, and among the 8 schemes point out by BRS, and block cipher E itself is the best compression to build a collision resistant hash function. At the end of the paper, two recommend structure of block cipher based hash function are given, and a prove of their securities are also given.