Paper 2006/467

Do We Need to Vary the Constants? (Methodological Investigation of Block-Cipher Based Hash Functions)

Donghoon Chang and Moti Yung

Abstract

The recent collision attacks on the MD hash function family do not depend on the constants used in the function, but rather on its structure (i.e., changing the constants will not affect the differential analysis based attacks). Thus, is seems that the role of constants in maintaining security and preventing these attacks is unclear, at best, for this case and in particular fixing or varying the constants will not matter for these analyses. % In this work we present a methodological investigation into the case of block-cipher based PGV hash functions family, and investigate the importance of constants in securing these designs. % To this end we consider the twelve variants of the PGV family that yield secure hash in the generic ideal cipher case (as was shown by Black, Rogaway and Shrimpton), but consider them under concrete instantiation. % % To investigate the role of constant in the key derivation procedure we just ignore the constants. In this more uniform setting we further consider a very regular cipher, namely AES modified to have Mixcolumn also in the last round (which should still be a strong cipher). % Analyzing this modified-AES based hashing, we show that with about 16\% probability we can find collisions with complexity $2^{49}$ (much smaller than the birthday attack complexity $2^{64}$). While we do not claim to break the AES based version, this nevertheless shows that constants in block cipher have an important role in resisting collision attack (in particular there is a need to vary the constant). It also shows that (in the symmetric modified version) merely the concrete AES structure does not guarantee the security of AES-based hash function (shown secure under the ideal cipher model). This is undesirable and non-robust, because this means that even though a block cipher has complicated structures in its round function and its key scheduling algorithm, we can not have a confidence about the security of hash functions based solely on it (note that there are several block ciphers such as IDEA, 3-key triple DES which do not use any constants). % Given the above methodological findings, we suggest new AES-based hash function constructions (essentially modified PGV) which can be generalized to any block cipher. The functions inherit the security under the ideal cipher model on the one hand, while, on the other hand, concretely assure in their structure that the weakness exhibited herein is dealt with.