Collision Resistance of Double-Block-Length Hash Function against Free-Start Attack

Shoichi HIROSE  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.1   pp.74-82
Publication Date: 2008/01/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.1.74
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Hash Functions
Keyword: 
double-block-length hash function,  random oracle model,  ideal cipher model,  collision resistance,  free-start collision attack,  

Full Text: PDF(186.5KB)>>
Buy this Article




Summary: 
In this article, we discuss the security of double-block-length (DBL) hash functions against the free-start collision attack. We focus on the DBL hash functions composed of compression functions of the form F(x) = (f(x), f(p(x))), where f is a smaller compression function and p is a permutation. We first show, in the random oracle model, that a significantly good upper bound can be obtained on the success probability of the free-start collision attack with sufficient conditions on p and the set of initial values. We also show that a similar upper bound can be obtained in the ideal cipher model if f is composed of a block cipher.