Constructing New Differential Paths and Algebraic Cryptanalysis for Full-SHA-1

摘要

Since the cryptanalysis for SHA-1 was proposed [19], many improvements have been proposed. Recently a new result was proposed which claims that it can compute collisions in 2~(52) SHA-1 computation, though it includes some problems [10]. Based on their attack, we had reconstructed their method algebraically using Grobner basis based formulation. In this formulation, we propose a new method to construct differentials and sufficient conditions automatically from disturbance vector and also propose some more new techniques: round-wise semi-neutral bits, global boomerang and adaptive amplified boomerang techniques. Using these new methods, we obtained sufficient conditions of full SHA-1 based on the new disturbance vector offered in [10] and succeeded in implementation.