The main contributions of this paper are two-fold. Firstly, we present a novel direction in the cryptanalysis of the cryptographic hash function {\SHA}. Our work builds on previous cryptanalytic efforts on {\SHA} based on combinations of local collisions. Due to dependencies, previous approaches used heuristic corrections when combining the success probabilities and message conditions of the individual local collisions. Although this leads to success probabilities that are seemingly sufficient for feasible collision attacks, this approach most often does not lead to the maximum success probability possible as desired. We introduce novel techniques that enable us to determine the theoretical maximum success probability for a given set of (dependent) local collisions, as well as the smallest set of message conditions that attains this probability. We apply our new techniques and present an implemented open-source near-collision attack on {\SHA} with a complexity equivalent to $2^{57.5}$ {\SHA} compressions. Secondly, we present an identical-prefix collision attack and a chosen-prefix collision attack on {\SHA} with complexities equivalent to approximately $2^{61}$ and $2^{77.1}$ {\SHA} compressions, respectively.

Additional Metadata
Keywords cryptography cryptanalysis hash functions collision attack SHA-1
THEME Other (theme 6)
Publisher Springer
Editor T. Johansson , P.Q. Nguyen
Series Lecture Notes in Computer Science
Project Cryptanalysis of Widely-used Hash Function Standards and Beyond
Conference Annual International Conference on the Theory and Applications of Cryptographic Techniques
Grant This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/617.001.201 - Cryptanalysis of Widely-used Hash Function Standards and Beyond
Citation
Stevens, M.M.J. (2013). New collision attacks on SHA-1 based on optimal joint local-collision analysis. In T Johansson & P.Q Nguyen (Eds.), Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques 2013 (EUROCRYPT 32) (pp. 245–261). Springer.