So far there is a significant cost: to detect collision attacks against SHA-1 (respectively MD5) costs the equivalent of hashing the message 15 (respectively 224) times. In this paper we present a significant performance improvement for collision detection based on the new concept of unavoidable conditions. Unavoidable conditions are conditions that are necessary for all feasible attacks in a certain attack class. As such they can be used to quickly dismiss particular attack classes that may have been used in the construction of the message. To determine an unavoidable condition one must rule out any feasible variant attack where this condition might not be necessary, otherwise adversaries aware of counter-cryptanalysis could easily bypass this improved collision detection with a carefully chosen variant attack. We provide a formal model for unavoidable conditions for collision attacks on MD5-like compression functions.
Furthermore, based on a conjecture solidly supported by the current state of the art, we show how we can determine such unavoidable conditions for SHA-1. We have implemented the improved SHA-1 collision detection using such unavoidable conditions and which is about 16 times faster than without our unavoidable condition improvements. We have measured that overall our implemented SHA-1 with collision detection is only a factor 1.96 slower, on average, than SHA-1. Our work is very timely given the recently announced first SHA-1 collision proving that SHA-1 is now practically broken.
Category / Keywords: public-key cryptography / hash functions, SHA-1, counter-cryptanalysis, collision attack, detection Date: received 21 Feb 2017, last revised 28 Feb 2017 Contact author: marc stevens at cwi nl Available format(s): PDF | BibTeX Citation Version: 20170228:105224 (All versions of this report) Short URL: ia.cr/2017/173 Discussion forum: Show discussion | Start new discussion