Preimages for Reduced SHA-0 and SHA-1

Christophe De Cannière; Christian Rechberger

doi:10.1007/978-3-540-85174-5_11

Preimages for Reduced SHA-0 and SHA-1

Christophe De Cannière, Christian Rechberger

Institute of Applied Information Processing and Communications (7050)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Abstract

In this paper, we examine the resistance of the popular hash function SHA-1 and its predecessor SHA-0 against dedicated preimage attacks. In order to assess the security margin of these hash functions against these attacks, two new cryptanalytic techniques are developed:

Reversing the inversion problem: the idea is to start with an impossible expanded message that would lead to the required digest, and then to correct this message until it becomes valid without destroying the preimage property.

P3graphs: an algorithm based on the theory of random graphs that allows the conversion of preimage attacks on the compression function to attacks on the hash function with less effort than traditional meet-in-the-middle approaches.

Combining these techniques, we obtain preimage-style shortcuts attacks for up to 45 steps of SHA-1, and up to 50 steps of SHA-0 (out of 80)

Original language	English
Title of host publication	Advances in Cryptology - Proceedings CRYPTO 2008
Editors	David Wagner
Publisher	Springer
Pages	179-202
ISBN (Print)	978-3-540-85173-8
DOIs	https://doi.org/10.1007/978-3-540-85174-5_11
Publication status	Published - 2008
Event	28th Annual International Cryptology Conference: CRYPTO 2008 - Santa Barbara, United States Duration: 17 Aug 2008 → 21 Aug 2008

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	5157

Conference

Conference	28th Annual International Cryptology Conference
Abbreviated title	CRYPTO 2008
Country/Territory	United States
City	Santa Barbara
Period	17/08/08 → 21/08/08

Access to Document

10.1007/978-3-540-85174-5_11

shapreAccepted author manuscript, 243 KB

FWF - Kryptoanalyse - Cryptanalysis by means of numerical methods
Mendel, F., Nad, T., Lamberger, M., Rechberger, C., Schläffer, M. & Rijmen, V.
1/10/07 → 31/12/09
Project: Research project
Cryptography
Schläffer, M., Oswald, M. E., Lipp, P., Dobraunig, C. E., Mendel, F., Eichlseder, M., Nad, T., Posch, R., Lamberger, M., Rijmen, V. & Rechberger, C.
1/01/95 → 31/01/19
Project: Research area

Cite this

@inproceedings{621be256ba9a4013b8d244707cc42313,

title = "Preimages for Reduced SHA-0 and SHA-1",

abstract = "In this paper, we examine the resistance of the popular hash function SHA-1 and its predecessor SHA-0 against dedicated preimage attacks. In order to assess the security margin of these hash functions against these attacks, two new cryptanalytic techniques are developed: Reversing the inversion problem: the idea is to start with an impossible expanded message that would lead to the required digest, and then to correct this message until it becomes valid without destroying the preimage property. P3graphs: an algorithm based on the theory of random graphs that allows the conversion of preimage attacks on the compression function to attacks on the hash function with less effort than traditional meet-in-the-middle approaches.Combining these techniques, we obtain preimage-style shortcuts attacks for up to 45 steps of SHA-1, and up to 50 steps of SHA-0 (out of 80)",

author = "{De Canni{\`e}re}, Christophe and Christian Rechberger",

year = "2008",

doi = "10.1007/978-3-540-85174-5_11",

language = "English",

isbn = "978-3-540-85173-8 ",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "179--202",

editor = "David Wagner",

booktitle = "Advances in Cryptology - Proceedings CRYPTO 2008",

note = "28th Annual International Cryptology Conference : CRYPTO 2008, CRYPTO 2008 ; Conference date: 17-08-2008 Through 21-08-2008",

}

TY - GEN

T1 - Preimages for Reduced SHA-0 and SHA-1

AU - De Cannière, Christophe

AU - Rechberger, Christian

PY - 2008

Y1 - 2008

N2 - In this paper, we examine the resistance of the popular hash function SHA-1 and its predecessor SHA-0 against dedicated preimage attacks. In order to assess the security margin of these hash functions against these attacks, two new cryptanalytic techniques are developed: Reversing the inversion problem: the idea is to start with an impossible expanded message that would lead to the required digest, and then to correct this message until it becomes valid without destroying the preimage property. P3graphs: an algorithm based on the theory of random graphs that allows the conversion of preimage attacks on the compression function to attacks on the hash function with less effort than traditional meet-in-the-middle approaches.Combining these techniques, we obtain preimage-style shortcuts attacks for up to 45 steps of SHA-1, and up to 50 steps of SHA-0 (out of 80)

AB - In this paper, we examine the resistance of the popular hash function SHA-1 and its predecessor SHA-0 against dedicated preimage attacks. In order to assess the security margin of these hash functions against these attacks, two new cryptanalytic techniques are developed: Reversing the inversion problem: the idea is to start with an impossible expanded message that would lead to the required digest, and then to correct this message until it becomes valid without destroying the preimage property. P3graphs: an algorithm based on the theory of random graphs that allows the conversion of preimage attacks on the compression function to attacks on the hash function with less effort than traditional meet-in-the-middle approaches.Combining these techniques, we obtain preimage-style shortcuts attacks for up to 45 steps of SHA-1, and up to 50 steps of SHA-0 (out of 80)

U2 - 10.1007/978-3-540-85174-5_11

DO - 10.1007/978-3-540-85174-5_11

M3 - Conference paper

SN - 978-3-540-85173-8

T3 - Lecture Notes in Computer Science

SP - 179

EP - 202

BT - Advances in Cryptology - Proceedings CRYPTO 2008

A2 - Wagner, David

PB - Springer

T2 - 28th Annual International Cryptology Conference

Y2 - 17 August 2008 through 21 August 2008

ER -

Preimages for Reduced SHA-0 and SHA-1

Abstract

Publication series

Conference

Access to Document

Fingerprint

Projects

FWF - Kryptoanalyse - Cryptanalysis by means of numerical methods

Cryptography

Cite this