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 7 such that for any natural т ^ 7 all the columns of M^T with the numbers 513, 514,..., 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 (7 = 21 for MD4, MD5, SHA-256 and 7 = 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.

Keywords

Authors

References