Douglas Stebila

Security analysis of a design variant of randomized hashing

Abstract

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

Reference

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.

Download

BibTeX

@inproceedings{ATIS:GauHirSte17,
 	Author = {Praveen Gauravaram and Shoichi Hirose and Douglas Stebila},
 	Booktitle = {Proc. 8th International Conference on Applications and Technologies in Information Security (ATIS) 2017},
 	Editor = {Lynn Batten and DongSeong Kim and Gang Li and Xuyun Zhang},
 	Month = {July},
 	Pages = {14--22},
 	Publisher = {Springer},
 	Series = {Communications in Computer Science},
 	Title = {Security analysis of a design variant of randomized hashing},
 	Volume = {719},
 	Year = {2017}
 }

Funding

• Australian Research Council (ARC) Discovery Project grant DP130104304
• JSPS KAKENHI Grant Number JP16H02828