Cryptanalysis of SHA-0 and reduced SHA-1 (Q2018819)

The item is an extended paper (50 pages) which continues and completes the results from [\textit{E. Biham} and \textit{R. Chen}, Crypto 2004, Lect. Notes Comput. Sci. 3152, 290--305 (2004; Zbl 1104.94307), ``New results on SHA-1 and SHA-0'', in Crypto 2004, Rump Session] and E. Biham, R. Chen, A. Joux, P. Carribault, C. Lemmuer and W. Jalby, [\textit{E. Biham} et al., Eurocrypt 2005, Lect. Notes Comput. Sci. 3494, 36--57 (2005; Zbl 1137.94337)]. The main idea is to apply differential cryptanalysis -- originally defined to attack symmetric block-ciphers -- for finding collisions of hash functions (the paper analyses the cases of SHA-0 and SHA-1 with a large game of possible rounds, but the method can be extended to other iteratively generated hash functions). In fact the authors propose two ways of cryptanalysis: neutral bits technique (based on the behavior of bits values between rounds passing) and multi-block technique (which exploits some properties of Merkle-Damgard expansion). As a remark, the first method can be applied also for cryptanalysis of stream ciphers. The complexity of attacks is estimated by the number of SHA callings. The main sections of the paper are: Section 3 (The basic attack of SHA-0) uses the fact that SHA-0 assures local collisions: a disturbance consisting in a bit 1 which appears in a round \(R\) can be completely avoided in next five rounds \(R+1,\dots R+5\). Moreover, this difference bit can be considered in the first position of the first word. This collision is analyzed for the function XOR, the cases of functions IF and MAJORITY being similar. Other observation is that an attack can start from round 19 (the linearity of SHA-0 construction assures to the cryptanalyst full control over the first 15 rounds and a look ahead over next 3 rounds), therefore a disturbance vector with minimal disturbances between round 19 and the final round will generate a collision with maximum probability. For a single-block attack (only one pair of input messages) the best choice of disturbance vector is -- in a compact representation -- the string \(0880\). The attack is described (unfortunately not in an algorithmic form) and its complexity (number of SHA-0 calls) is analyzed. Section 4 describes the neutral bits technique, when the attack practically begins from round 22. A bit is neutral if its complementation does not change its information during at least \(R\) rounds. Each round begins with an input message \(M\) and a constant vector \(\Omega\) named characteristic. So, the pair \((M,M\otimes\Omega )\) keeps the same information on locations of neutral bits. Based on Observation 1 (unproven) the best results are obtained using pairs of neutral bits. So, an attack will consist of two steps: obtaining the maximal 2-neutral set (in general an NP-complete problem, but with additional properties that facilitate a solution), followed by an exhaustive search for all pairs of this set. A surprising results is presented in Section 5. Namely, the complexity of the attack is not monotonous in the number of rounds. For example, it is much more easier to find collisions for function SHA-0 with 81 or 82 rounds (complexity \(2^{43}\)) than in standard SHA-0 with 80 rounds (complexity \(2^{56}\)). Section 6 is dedicated to extend the basic attack for a multi-block, which concatenates partial results obtained with different pairs. It is based on the remark that the iterative structure of Merkle-Damgard construction permits concatenation of equal characteristics obtained from different block messages. New terms like near-collision and pseudo-collision are defined and it is shown that in some cases this way permits to find collisions with much lower complexity. Last sections treat different results concerning attacks on SHA-0 (Four-block attack) and different reduced versions of SHA-1 (40 rounds and 53 rounds are outlined to have a reduced complexity). Basically, ''Cryptanalysis of SHA-0 and Reduced SHA-1'' is small book or can be included easily in a book of differential cryptanalysis. It is very interesting, with fruitful ideas, full of possible follow-ups. The paper contains in fact the work of authors during a decade, and offers to all interested readers a background for future research.