Paper 2008/110

On the Design of Secure and Fast Double Block Length Hash Functions

Zheng Gong, Xuejia Lai, and Kefei Chen

Abstract

In this work the security of double block length hash functions with rate 1, which are based on a block cipher with a block length of $n$ bits and a key length of $2n$ bits, is reconsidered. Counter-examples and new attacks are presented on this general class of fast double block length hash functions, which reveal unnoticed flaws in the necessary conditions given by Satoh \textit{et al.} and Hirose. Preimage and second preimage attacks are presented on Hirose's two examples which were left as an open problem. Our synthetic analysis show that all rate-1 hash functions in FDBL-II are failed to be optimally (second) preimage resistant. The necessary conditions are refined for ensuring a subclass of hash functions in FDBL-II to be optimally secure against collision attacks. In particular, one of Hirose's two examples, which satisfies our refined conditions, is proven to be indifferentiable from a random oracle in the ideal cipher model. The security results are extended to a new class of double block length hash functions with rate 1, where the key length of one block cipher used in the compression function is equal to the block length, whereas the other is doubled.

Note: Refined Abstract