Collisions of SHA-0 and reduced SHA-1

Eli Biham; Rafi Chen; Antoine Joux; Patrick Carribault; Christophe Lemuet; William Jalby

doi:10.1007/11426639_3

Collisions of SHA-0 and reduced SHA-1

Eli Biham, Rafi Chen, Antoine Joux, Patrick Carribault, Christophe Lemuet, William Jalby

Research output: Contribution to journal › Conference article › peer-review

Abstract

In this paper we describe improvements to the techniques used to cryptanalyze SHA-0 and introduce the first results on SHA-1. The results include a generic multi-block technique that uses near-collisions in order to find collisions, and a four-block collision of SHA-0 found using this technique with complexity 2⁵¹. Then, extension of this and prior techniques are presented, that allow us to find collisions of reduced versions of SHA-1. We give collisions of variants with up to 40 rounds, and show the complexities of longer variants. These techniques show that collisions up to about 53-58 rounds can still be found faster than by birthday attacks.

Original language	English
Pages (from-to)	36-57
Number of pages	22
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3494
DOIs	https://doi.org/10.1007/11426639_3
Publication status	Published - 1 Jan 2005
Externally published	Yes
Event	24th Annual International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology - EUROCRYPT 2005 - Aarhus, Denmark Duration: 22 May 2005 → 26 May 2005

Access to Document

10.1007/11426639_3

Cite this

@article{f7413060b12542e4ba2069d1da1582b9,

title = "Collisions of SHA-0 and reduced SHA-1",

abstract = "In this paper we describe improvements to the techniques used to cryptanalyze SHA-0 and introduce the first results on SHA-1. The results include a generic multi-block technique that uses near-collisions in order to find collisions, and a four-block collision of SHA-0 found using this technique with complexity 251. Then, extension of this and prior techniques are presented, that allow us to find collisions of reduced versions of SHA-1. We give collisions of variants with up to 40 rounds, and show the complexities of longer variants. These techniques show that collisions up to about 53-58 rounds can still be found faster than by birthday attacks.",

author = "Eli Biham and Rafi Chen and Antoine Joux and Patrick Carribault and Christophe Lemuet and William Jalby",

year = "2005",

month = jan,

day = "1",

doi = "10.1007/11426639\_3",

language = "English",

volume = "3494",

pages = "36--57",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

note = "24th Annual International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology - EUROCRYPT 2005 ; Conference date: 22-05-2005 Through 26-05-2005",

}

TY - JOUR

T1 - Collisions of SHA-0 and reduced SHA-1

AU - Biham, Eli

AU - Chen, Rafi

AU - Joux, Antoine

AU - Carribault, Patrick

AU - Lemuet, Christophe

AU - Jalby, William

PY - 2005/1/1

Y1 - 2005/1/1

N2 - In this paper we describe improvements to the techniques used to cryptanalyze SHA-0 and introduce the first results on SHA-1. The results include a generic multi-block technique that uses near-collisions in order to find collisions, and a four-block collision of SHA-0 found using this technique with complexity 251. Then, extension of this and prior techniques are presented, that allow us to find collisions of reduced versions of SHA-1. We give collisions of variants with up to 40 rounds, and show the complexities of longer variants. These techniques show that collisions up to about 53-58 rounds can still be found faster than by birthday attacks.

AB - In this paper we describe improvements to the techniques used to cryptanalyze SHA-0 and introduce the first results on SHA-1. The results include a generic multi-block technique that uses near-collisions in order to find collisions, and a four-block collision of SHA-0 found using this technique with complexity 251. Then, extension of this and prior techniques are presented, that allow us to find collisions of reduced versions of SHA-1. We give collisions of variants with up to 40 rounds, and show the complexities of longer variants. These techniques show that collisions up to about 53-58 rounds can still be found faster than by birthday attacks.

U2 - 10.1007/11426639_3

DO - 10.1007/11426639_3

M3 - Conference article

AN - SCOPUS:24944584156

SN - 0302-9743

VL - 3494

SP - 36

EP - 57

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology - EUROCRYPT 2005

Y2 - 22 May 2005 through 26 May 2005

ER -

Collisions of SHA-0 and reduced SHA-1

Abstract

Access to Document

Fingerprint

Cite this