A Modular Design for Hash Functions: Towards Making the Mix-Compress-Mix Approach Practical

Anja Lehmann and Stefano Tessaro

Advances in Cryptology — ASIACRYPT 2009, Lecture Notes in Computer Science, Springer-Verlag, vol. 5912, pp. 364–381, Dec 2009.

The design of cryptographic hash functions is a very complex and failure-prone process. For this reason, this paper puts forward a completely modular and fault-tolerant approach to the construction of a full-fledged hash function from an underlying simpler hash function $H$ and a further primitive $F$ (such as a block cipher), with the property that collision resistance of the construction only relies on $H$ , whereas indifferentiability from a random oracle follows from $F$ being ideal. In particular, the failure of one of the two components must not affect the security property implied by the other component.

The Mix-Compress-Mix (MCM) approach by Ristenpart and Shrimpton (ASIACRYPT 2007) envelops the hash function $H$ between two injective mixing steps, and can be interpreted as a first attempt at such a design. However, the proposed instantiation of the mixing steps, based on block ciphers, makes the resulting hash function impractical: First, it cannot be evaluated online, and second, it produces larger hash values than $H$ , while only inheriting the collision-resistance guarantees for the shorter output. Additionally, it relies on a trapdoor one-way permutation, which seriously compromises the use of the resulting hash function for random oracle instantiation in certain scenarios.

This paper presents the first efficient modular hash function with online evaluation and short output length. The core of our approach are novel block-cipher based designs for the mixing steps of the MCM approach which rely on significantly weaker assumptions: The first mixing step is realized without any computational assumptions (besides the underlying cipher being ideal), whereas the second mixing step only requires a one-way permutation without a trapdoor, which we prove to be the minimal assumption for the construction of injective random oracles.

BibTeX Citation

@inproceedings{LehTes09,
    author       = {Anja Lehmann and Stefano Tessaro},
    title        = {A Modular Design for Hash Functions: Towards Making the Mix-Compress-Mix Approach Practical},
    editor       = {Mitsuru Matsui},
    booktitle    = {Advances in Cryptology --- ASIACRYPT 2009},
    pages        = {364--381},
    series       = {Lecture Notes in Computer Science},
    volume       = {5912},
    year         = {2009},
    month        = {12},
    publisher    = {Springer-Verlag},
}