Security analysis of a design variant of randomized hashing


At EUROCRYPT 2009, Gauravaram and Knudsen presented an online birthday attack on the randomized hashing scheme standardized in NIST SP800-106. This attack uses a fact that it is easy to find fixed points for the Davies-Meyer-type compression functions of standardized hash functions such as those in the SHA-2 family. This attack is significant in that it is an attack on the target collision resistance (TCR) of the randomized hashing scheme which is claimed to be enhanced TCR (eTCR). TCR is a property weaker than eTCR. In this paper, we will present a randomized hashing scheme called RMC. We will also prove that RMC satisfies both TCR and eTCR in the random oracle model and in the ideal cipher model. In particular, the proof for the TCR security in the ideal cipher model implies that the attack by Gauravaram and Knudsen is not effective against RMC.

Keywords: iterated hash function, randomized hashing, target collision resistance, Davies-Meyer compression function, provable security


Praveen Gauravaram, Shoichi Hirose, Douglas Stebila. Security analysis of a design variant of randomized hashing. In Lynn Batten, DongSeong Kim, Gang Li, Xuyun Zhang, editors, 8th International Conference on Applications and Technologies in Information Security (ATIS) 2017, Communications in Computer Science, vol. 719, pp. 14-22. Springer, July 2017. © Springer.




This research was supported by:
  • Australian Research Council (ARC) Discovery Project grant DP130104304
  • JSPS KAKENHI Grant Number JP16H02828