Improving SHA-1 counter-cryptanalysis using unavoidable conditions

The concept of counter-cryptanalysis and a collision detection algorithm that detects whether a given single message was constructed using a cryptanalytic collision attack on MD5 or SHA-1 was presented by Stevens at CRYPTO 2013. It was shown that collision detection is not only possible but also practical and a reference implementation was released. However, 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 \emph{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 test whether a message block may have been constructed using an attack from that class and significantly reduce the cost of more expensive collision detection operations. While necessary and sufficient conditions for an attack can be easily and manually derived, significant care must be taken in determining unavoidable conditions. To prevent adversaries aware of counter-cryptanalysis to easily bypass this improved collision detection with a carefully chosen variant attack, it is crucial that the used conditions are truly unavoidable by considering all feasible variant attacks in the same attack class. 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.