Gröbner Basis Based Cryptanalysis of SHA-1.
誠 杉田, Mitsuru Kawazoe, Hideki Imai · 2006
Recently, Wang proposed a new method to cryptanalyze SHA-1 and found collisions of the 58-round SHA-1. The complexity of Wang's method to cryptanalyze the 58-round SHA-1 is 2 34 SHA-1 computation. Moreover, Wang et al. gave the complexity evaluation against the full SHA-1 which is claimed to be 2 62. The aim of this article is to sophisticate and improve Wang's attack by using Gröbner basis techniques and to reduce the complexity of the attack for SHA-1. In this article, we apply Gröbner basis techniques to a cryptanalysis of SHA-1. We introduce a new notion of "semi-neutral bit" and propose an improved message modification technique based on Gr"obner basis technique. In the case of the 58-round SHA-1, the complexity of an attack based on our improved message modification is 2