One application of counter-cryptanalysis is detecting whether a message block is involved in a collision attack, such as the detection of MD5 and SHA-1. Stevens and Shumow speeded up the detection of SHA-1 by introducing unavoidable conditions in message blocks. They left a challenge: how to determine unavoidable conditions for MD5. Later, Shen et al. found that the unavoidable conditions of MD5 were the sufficient conditions located in the last round of differential paths. In this paper, we made further work. We discover sufficient conditions in the second round that can also be used as unavoidable conditions. With additional sufficient conditions, we subdivide three sets and distinguish seven more classes. As a result, compared with Shen's collision detection algorithm, our improved algorithm reduces the collision detection cost by 8.18%. Finally, we find that they do exist in the differential paths constructed by the automatic tool "HashClash".
Citation: Linan Fang, Ting Wu, Yongxing Qi, Yanzhao Shen, Peng Zhang, Mingmin Lin, Xinfeng Dong. Improved collision detection of MD5 with additional sufficient conditions[J]. Electronic Research Archive, 2022, 30(6): 2018-2032. doi: 10.3934/era.2022102
One application of counter-cryptanalysis is detecting whether a message block is involved in a collision attack, such as the detection of MD5 and SHA-1. Stevens and Shumow speeded up the detection of SHA-1 by introducing unavoidable conditions in message blocks. They left a challenge: how to determine unavoidable conditions for MD5. Later, Shen et al. found that the unavoidable conditions of MD5 were the sufficient conditions located in the last round of differential paths. In this paper, we made further work. We discover sufficient conditions in the second round that can also be used as unavoidable conditions. With additional sufficient conditions, we subdivide three sets and distinguish seven more classes. As a result, compared with Shen's collision detection algorithm, our improved algorithm reduces the collision detection cost by 8.18%. Finally, we find that they do exist in the differential paths constructed by the automatic tool "HashClash".
| [1] | I. B. Damgård, A design principle for hash functions, in Advances in Cryptology –- CRYPTO' 89 Proceedings (ed. G. Brassard), Springer, New York, NY, (1990), 416–427. https://doi.org/10.1007/0-387-34805-0_39 |
| [2] | R. C. Merkle, One way hash functions and DES, in Advances in Cryptology –- CRYPTO' 89 Proceedings (ed. G. Brassard), Springer, New York, NY, (1990), 428–446. https://doi.org/10.1007/0-387-34805-0_40 |
| [3] | X. Wang, H. Yu, How to break MD5 and other hash functions, in Advances in Cryptology – EUROCRYPT 2005 (ed. R. Cramer), Springer, Berlin, Heidelberg, (2005), 19–35. https://doi.org/10.1007/11426639_2 |
| [4] |
A. D. Dwivedi, S. Dhar, G. Srivastava, R. Singh, Cryptanalysis of round-reduced fantomas, robin and iSCREAM, Cryptography, 3 (2019), 4. https://doi.org/10.3390/cryptography3010004 doi: 10.3390/cryptography3010004
|
| [5] | M. Stevens, A. Lenstra, B. de Weger, Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities, in Advances in Cryptology - EUROCRYPT 2007 (ed. M. Naor), Springer, Berlin, Heidelberg, (2007), 1–22. https://doi.org/10.1007/978-3-540-72540-4_1 |
| [6] | M. Stevens, A. Sotirov, J. Appelbaum, A. Lenstra, D. Molnar, D. A. Osvik, et al., Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate, in Advances in Cryptology - CRYPTO 2009 (ed. S. Halevi), Springer, Berlin, Heidelberg, (2009), 55–69. https://doi.org/10.1007/978-3-642-03356-8_4 |
| [7] | M. Stevens, Counter-cryptanalysis, in Advances in Cryptology – CRYPTO 2013 (eds. R. Canetti and J. A. Garay), Springer, Berlin, Heidelberg, (2013), 129–146. https://doi.org/10.1007/978-3-642-40041-4_8 |
| [8] | X. Wang, H. Yu, W. Wang, H. Zhang, T. Zhan, Cryptanalysis on HMAC/NMAC-MD5 and MD5-MAC, in Advances in Cryptology - EUROCRYPT 2009 (ed. A. Joux), Springer, Berlin, Heidelberg, (2009), 121–133. https://doi.org/10.1007/978-3-642-01001-9_7 |
| [9] | M. Stevens, Attacks on hash functions and applications, Ph.D thesis, Leiden University in Leiden, 2012. https://doi.org/10.6100/ir749233 |
| [10] | M. Stevens, D. Shumow, Speeding up detection of {SHA-1} collision attacks using unavoidable attack conditions, in 26th USENIX Security Symposium (USENIX Security 17), USENIX Association, Vancouver, BC, (2017), 881–897. https://doi.org/10.5555/3241189.3241259 |
| [11] |
Y. Shen, T. Wu, G. Wang, X. Dong, H. Qian, Improved collision detection of MD5 using sufficient condition combination, Comput. J., (2021). https://doi.org/10.1093/comjnl/bxab109 doi: 10.1093/comjnl/bxab109
|
| [12] |
R. L. Rivest, The MD5 message-digest algorithm, RFC, 1321 (1992), 1–21. https://doi.org/10.17487/RFC1321 doi: 10.17487/RFC1321
|
| [13] | M. Stevens, Project HashClash - MD5 & SHA-1 cryptanalytic toolbox [Internet]. Available from: https: //github.com/cr-marcstevens/hashclash. |
Linan Fang, Ting Wu, Yongxing Qi, Yanzhao Shen, Peng Zhang, Mingmin Lin, Xinfeng Dong. Improved collision detection of MD5 with additional sufficient conditions[J]. Electronic Research Archive, 2022, 30(6): 2018-2032. doi: 10.3934/era.2022102
DownLoad: