Evaluation of mixing characteristics for Merkle–Damgard hash functions

The matrix-graph approach (MGA), which has been successfully applied to the evaluation of iterative block ciphers and key generators, is presented for the first time as a tool for estimating the mixing properties of hash algorithms. Feature of MGA application to hash functions is connected with the possibility of construction the mixing matrices which characterize dependence of the bits of the hash value on the bits of the input message. Mixing matrices of the order $512+n$ are constructed for hash functions MD4, MD5, SHA-1, SHA-256, where $n$ is the size of the digest produced by the compression function processing the $512$-bit block of the input message ($n=128$ for MD4 and MD5, $n=160$ for SHA-1 and $n=256$ for SHA-256). We calculate the local exponents of mixing matrices, i.e., for each matrix $M$, we obtain the smallest positive integer $\gamma$ such that for any natural $\tau \ge \gamma$ all the columns of $M^{\tau}$ with the numbers $513, 514, \ldots, 512+n$ are positive. The values of the local exponents are the lower bounds for the number of iterations, after which each bit of the output hash may essentially depend on all bits of the input message. The obtained values ($\gamma=21$ for MD4, MD5, SHA-256 and $\gamma=23$ for SHA-1) indirectly indicate the similar mixing properties of the considered hash algorithms despite the increase of block length and complexity of the compression function.