Cryptanalysis of SHA-0 and reduced SHA-1
type: Item
instance of: scholarly article
title: Cryptanalysis of SHA-0 and reduced SHA-1
zbMATH Open document ID: 1334.94061
author: Eli Biham
author: Rafi Chen
author: Antoine Joux
published in: Journal of Cryptology
publication date: 2015-03-25T00:00:00Z
review text: 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 …
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 94A62
zbMATH DE Number: 6419545
zbMATH Keywords: differential cryptanalysis
zbMATH Keywords: SHA-1
zbMATH Keywords: hash function
reviewed by: Adrian Atanasiu
MaRDI profile type: Publication
full work available at URL: s00145-014-9179-8
OpenAlex ID: W1989313172
cites work: New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba
cites work: Advances in Cryptology – CRYPTO 2004
cites work: Q4035714
cites work: Q3136298
cites work: Collisions of SHA-0 and Reduced SHA-1
cites work: Q4934729
cites work: Q4249321
cites work: Q3212279
cites work: Finding SHA-1 Characteristics: General Results and Applications
cites work: Collisions for 70-Step SHA-1: On the Full Cost of Collision Search
cites work: Cryptanalysis of MD4
cites work: RIPEMD-160: A strengthened version of RIPEMD
cites work: Chosen IV Statistical Analysis for Key Recovery Attacks on Stream Ciphers
cites work: Hash Functions and the (Amplified) Boomerang Attack
cites work: New Directions in Cryptanalysis of Self-Synchronizing Stream Ciphers
cites work: One Way Hash Functions and DES
cites work: A fast software one-way hash function
cites work: Topics in Cryptology – CT-RSA 2005
cites work: Q4279583
cites work: New Collision Attacks on SHA-1 Based on Optimal Joint Local-Collision Analysis
cites work: Q4941810
cites work: Cryptanalysis of the Hash Functions MD4 and RIPEMD
cites work: How to Break MD5 and Other Hash Functions
cites work: Efficient Collision Search Attacks on SHA-0
cites work: Finding Collisions in the Full SHA-1
cites work: Cryptanalysis of the Full HAVAL with 4 and 5 Passes
cites work: Q4341675
DOI: 10.1007/S00145-014-9179-8
description: scientific article; zbMATH DE number 6419545