A Modular Design for Hash Functions: Towards Making the Mix-Compress-Mix Approach Practical
Anja Lehmann and Stefano Tessaro
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.