Second-Order Differential Collisions for Reduced SHA-256

Alex Biryukov; Mario Lamberger; Florian Mendel; Ivica Nikolic

doi:10.1007/978-3-642-25385-0_15

Second-Order Differential Collisions for Reduced SHA-256

Alex Biryukov, Mario Lamberger, Florian Mendel, Ivica Nikolic

Institut für Angewandte Informationsverarbeitung und Kommunikationstechnologie (7050)

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

Abstract

In this work, we introduce a new non-random property for hash/compression functions using the theory of higher order differentials. Based on this, we show a second-order differential collision for the compression function of SHA-256 reduced to 47 out of 64 steps with practical complexity. We have implemented the attack and provide an example. Our results suggest that the security margin of SHA-256 is much lower than the security margin of most of the SHA-3 finalists in this setting. The techniques employed in this attack are based on a rectangle/boomerang approach and cover advanced search algorithms for good characteristics and message modification techniques. Our analysis also exposes flaws in all of the previously published related-key rectangle attacks on the SHACAL-2 block cipher, which is based on SHA-256. We provide valid rectangles for 48 steps of SHACAL-2

Originalsprache	englisch
Titel	Advances in Cryptology - ASIACRYPT 2011
Redakteure/-innen	Dong Hoon Lee, Xiaoyun Wang
Herausgeber (Verlag)	Springer
Seiten	270-287
ISBN (Print)	978-3-642-25384-3
DOIs	https://doi.org/10.1007/978-3-642-25385-0_15
Publikationsstatus	Veröffentlicht - 2011
Veranstaltung	International Conference on the Theory and Application of Cryptology and Information Security - Seoul, Südkorea Dauer: 4 Dez. 2011 → 8 Dez. 2011

Publikationsreihe

Name	Lecture Notes in Computer Science
Band	7073

Konferenz

Konferenz	International Conference on the Theory and Application of Cryptology and Information Security
Land/Gebiet	Südkorea
Ort	Seoul
Zeitraum	4/12/11 → 8/12/11

Fields of Expertise

Information, Communication & Computing

Zugriff auf Dokument

10.1007/978-3-642-25385-0_15

mendelEndgültige, publizierte Fassung, 410 KB

FWF - kryptographische Hashfu - Analyse von modernen kryptographischen Hashfunktionen II
Nad, T., Mendel, F., Schläffer, M., Lamberger, M. & Rijmen, V.
1/02/10 → 31/01/13
Projekt: Forschungsprojekt
EU - ECRYPT II - European network of excellence in cryptology - Phase II
Schmidt, J., Nad, T., Kirschbaum, M., Feldhofer, M., Schläffer, M., Aigner, M. J., Rechberger, C., Lamberger, M., Tillich, S., Medwed, M., Hutter, M., Rijmen, V., Mendel, F. & Posch, R.
1/08/08 → 31/07/12
Projekt: Forschungsprojekt
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
Projekt: Arbeitsgebiet

Dieses zitieren

Second-Order Differential Collisions for Reduced SHA-256. / Biryukov, Alex; Lamberger, Mario; Mendel, Florian et al.
Advances in Cryptology - ASIACRYPT 2011. Hrsg. / Dong Hoon Lee; Xiaoyun Wang. Springer, 2011. S. 270-287 (Lecture Notes in Computer Science; Band 7073).

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

Biryukov, A, Lamberger, M, Mendel, F & Nikolic, I 2011, Second-Order Differential Collisions for Reduced SHA-256. in DH Lee & X Wang (Hrsg.), Advances in Cryptology - ASIACRYPT 2011. Lecture Notes in Computer Science, Bd. 7073, Springer, S. 270-287, International Conference on the Theory and Application of Cryptology and Information Security, Seoul, Südkorea, 4/12/11. https://doi.org/10.1007/978-3-642-25385-0_15

@inproceedings{f380938d1ccd4584946f2903a436de1f,

title = "Second-Order Differential Collisions for Reduced SHA-256",

abstract = "In this work, we introduce a new non-random property for hash/compression functions using the theory of higher order differentials. Based on this, we show a second-order differential collision for the compression function of SHA-256 reduced to 47 out of 64 steps with practical complexity. We have implemented the attack and provide an example. Our results suggest that the security margin of SHA-256 is much lower than the security margin of most of the SHA-3 finalists in this setting. The techniques employed in this attack are based on a rectangle/boomerang approach and cover advanced search algorithms for good characteristics and message modification techniques. Our analysis also exposes flaws in all of the previously published related-key rectangle attacks on the SHACAL-2 block cipher, which is based on SHA-256. We provide valid rectangles for 48 steps of SHACAL-2",

author = "Alex Biryukov and Mario Lamberger and Florian Mendel and Ivica Nikolic",

year = "2011",

doi = "10.1007/978-3-642-25385-0_15",

language = "English",

isbn = "978-3-642-25384-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "270--287",

editor = "Lee, {Dong Hoon} and Xiaoyun Wang",

booktitle = "Advances in Cryptology - ASIACRYPT 2011",

note = "International Conference on the Theory and Application of Cryptology and Information Security ; Conference date: 04-12-2011 Through 08-12-2011",

}

TY - GEN

T1 - Second-Order Differential Collisions for Reduced SHA-256

AU - Biryukov, Alex

AU - Lamberger, Mario

AU - Mendel, Florian

AU - Nikolic, Ivica

PY - 2011

Y1 - 2011

N2 - In this work, we introduce a new non-random property for hash/compression functions using the theory of higher order differentials. Based on this, we show a second-order differential collision for the compression function of SHA-256 reduced to 47 out of 64 steps with practical complexity. We have implemented the attack and provide an example. Our results suggest that the security margin of SHA-256 is much lower than the security margin of most of the SHA-3 finalists in this setting. The techniques employed in this attack are based on a rectangle/boomerang approach and cover advanced search algorithms for good characteristics and message modification techniques. Our analysis also exposes flaws in all of the previously published related-key rectangle attacks on the SHACAL-2 block cipher, which is based on SHA-256. We provide valid rectangles for 48 steps of SHACAL-2

AB - In this work, we introduce a new non-random property for hash/compression functions using the theory of higher order differentials. Based on this, we show a second-order differential collision for the compression function of SHA-256 reduced to 47 out of 64 steps with practical complexity. We have implemented the attack and provide an example. Our results suggest that the security margin of SHA-256 is much lower than the security margin of most of the SHA-3 finalists in this setting. The techniques employed in this attack are based on a rectangle/boomerang approach and cover advanced search algorithms for good characteristics and message modification techniques. Our analysis also exposes flaws in all of the previously published related-key rectangle attacks on the SHACAL-2 block cipher, which is based on SHA-256. We provide valid rectangles for 48 steps of SHACAL-2

U2 - 10.1007/978-3-642-25385-0_15

DO - 10.1007/978-3-642-25385-0_15

M3 - Conference paper

SN - 978-3-642-25384-3

T3 - Lecture Notes in Computer Science

SP - 270

EP - 287

BT - Advances in Cryptology - ASIACRYPT 2011

A2 - Lee, Dong Hoon

A2 - Wang, Xiaoyun

PB - Springer

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

Y2 - 4 December 2011 through 8 December 2011

ER -

Second-Order Differential Collisions for Reduced SHA-256

Abstract

Publikationsreihe

Konferenz

Fields of Expertise

Zugriff auf Dokument

Fingerprint

Projekte

FWF - kryptographische Hashfu - Analyse von modernen kryptographischen Hashfunktionen II

EU - ECRYPT II - European network of excellence in cryptology - Phase II

Cryptography

Dieses zitieren