Preimages for Step-Reduced SHA-2

Kazumaro Aoki; Jian Guo; Krystian Matusiewicz; Yu Sasaki; Lei Wang

doi:10.1007/978-3-642-10366-7_34

Preimages for Step-Reduced SHA-2

Kazumaro Aoki, Jian Guo, Krystian Matusiewicz, Yu Sasaki, Lei Wang

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

Abstract

In this paper, we present preimage attacks on up to 43-step SHA-256 (around 67% of the total 64 steps) and 46-step SHA-512 (around 57.5% of the total 80 steps), which significantly increases the number of attacked steps compared to the best previously published preimage attack working for 24 steps. The time complexities are 2^251.9, 2^509 for finding pseudo-preimages and 2^254.9, 2^511.5 compression function operations for full preimages. The memory requirements are modest, around 2^6 words for 43-step SHA-256 and 46-step SHA-512. The pseudo-preimage attack also applies to 43-step SHA-224 and SHA-384. Our attack is a meet-in-the-middle attack that uses a range of novel techniques to split the function into two independent parts that can be computed separately and then matched in a birthday-style phase.

Original language	English
Title of host publication	Advances in Cryptology -- ASIACRYPT 2009
Editors	Mitsuru Matsui
Number of pages	722
Volume	5912
Publisher	Springer
Publication date	2009
Pages	578-597
ISBN (Print)	978-3-642-10365-0
DOIs	https://doi.org/10.1007/978-3-642-10366-7_34
Publication status	Published - 2009
Event	15th Annual International Conference on the Theory and Application of Cryptology and Information Security - Tokyo, Japan Duration: 6 Dec 2009 → 10 Dec 2009 Conference number: 15 http://asiacrypt2009.cipher.risk.tsukuba.ac.jp/

Conference

Conference	15th Annual International Conference on the Theory and Application of Cryptology and Information Security
Number	15
Country/Territory	Japan
City	Tokyo
Period	06/12/2009 → 10/12/2009
Internet address	http://asiacrypt2009.cipher.risk.tsukuba.ac.jp/

Series	Lecture Notes in Computer Science
Number	5912
ISSN	0302-9743

Access to Document

10.1007/978-3-642-10366-7_34

http://www.springerlink.com/content/dwrt65440t416307/

OpenUrl availability

Full text

Cite this

@inproceedings{ed8a5a19f3254088adf4ee86526157fd,

title = "Preimages for Step-Reduced SHA-2",

abstract = "In this paper, we present preimage attacks on up to 43-step SHA-256 (around 67% of the total 64 steps) and 46-step SHA-512 (around 57.5% of the total 80 steps), which significantly increases the number of attacked steps compared to the best previously published preimage attack working for 24 steps. The time complexities are 2^251.9, 2^509 for finding pseudo-preimages and 2^254.9, 2^511.5 compression function operations for full preimages. The memory requirements are modest, around 2^6 words for 43-step SHA-256 and 46-step SHA-512. The pseudo-preimage attack also applies to 43-step SHA-224 and SHA-384. Our attack is a meet-in-the-middle attack that uses a range of novel techniques to split the function into two independent parts that can be computed separately and then matched in a birthday-style phase.",

author = "Kazumaro Aoki and Jian Guo and Krystian Matusiewicz and Yu Sasaki and Lei Wang",

year = "2009",

doi = "10.1007/978-3-642-10366-7_34",

language = "English",

isbn = "978-3-642-10365-0",

volume = "5912",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "5912",

pages = "578--597",

editor = "Mitsuru Matsui",

booktitle = "Advances in Cryptology -- ASIACRYPT 2009",

note = "15th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2009 ; Conference date: 06-12-2009 Through 10-12-2009",

url = "http://asiacrypt2009.cipher.risk.tsukuba.ac.jp/",

}

Aoki, K, Guo, J, Matusiewicz, K, Sasaki, Y & Wang, L 2009, Preimages for Step-Reduced SHA-2. in M Matsui (ed.), Advances in Cryptology -- ASIACRYPT 2009. vol. 5912, Springer, Lecture Notes in Computer Science, no. 5912, pp. 578-597, 15th Annual International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, 06/12/2009. https://doi.org/10.1007/978-3-642-10366-7_34

TY - GEN

T1 - Preimages for Step-Reduced SHA-2

AU - Aoki, Kazumaro

AU - Guo, Jian

AU - Matusiewicz, Krystian

AU - Sasaki, Yu

AU - Wang, Lei

N1 - Conference code: 15

PY - 2009

Y1 - 2009

N2 - In this paper, we present preimage attacks on up to 43-step SHA-256 (around 67% of the total 64 steps) and 46-step SHA-512 (around 57.5% of the total 80 steps), which significantly increases the number of attacked steps compared to the best previously published preimage attack working for 24 steps. The time complexities are 2^251.9, 2^509 for finding pseudo-preimages and 2^254.9, 2^511.5 compression function operations for full preimages. The memory requirements are modest, around 2^6 words for 43-step SHA-256 and 46-step SHA-512. The pseudo-preimage attack also applies to 43-step SHA-224 and SHA-384. Our attack is a meet-in-the-middle attack that uses a range of novel techniques to split the function into two independent parts that can be computed separately and then matched in a birthday-style phase.

AB - In this paper, we present preimage attacks on up to 43-step SHA-256 (around 67% of the total 64 steps) and 46-step SHA-512 (around 57.5% of the total 80 steps), which significantly increases the number of attacked steps compared to the best previously published preimage attack working for 24 steps. The time complexities are 2^251.9, 2^509 for finding pseudo-preimages and 2^254.9, 2^511.5 compression function operations for full preimages. The memory requirements are modest, around 2^6 words for 43-step SHA-256 and 46-step SHA-512. The pseudo-preimage attack also applies to 43-step SHA-224 and SHA-384. Our attack is a meet-in-the-middle attack that uses a range of novel techniques to split the function into two independent parts that can be computed separately and then matched in a birthday-style phase.

U2 - 10.1007/978-3-642-10366-7_34

DO - 10.1007/978-3-642-10366-7_34

M3 - Article in proceedings

SN - 978-3-642-10365-0

VL - 5912

T3 - Lecture Notes in Computer Science

SP - 578

EP - 597

BT - Advances in Cryptology -- ASIACRYPT 2009

A2 - Matsui, Mitsuru

PB - Springer

T2 - 15th Annual International Conference on the Theory and Application of Cryptology and Information Security

Y2 - 6 December 2009 through 10 December 2009

ER -

Preimages for Step-Reduced SHA-2

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this