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

Institute of Applied Information Processing and Communications (7050)

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

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

Original language	English
Title of host publication	Advances in Cryptology - ASIACRYPT 2011
Editors	Dong Hoon Lee, Xiaoyun Wang
Publisher	Springer
Pages	270-287
ISBN (Print)	978-3-642-25384-3
DOIs	https://doi.org/10.1007/978-3-642-25385-0_15
Publication status	Published - 2011
Event	17th International Conference on the Theory and Application of Cryptology and Information Security: ASIACRYPT 2011 - Seoul, Korea, Republic of Duration: 4 Dec 2011 → 8 Dec 2011

Publication series

Name	Lecture Notes in Computer Science
Volume	7073

Conference

Conference	17th International Conference on the Theory and Application of Cryptology and Information Security
Abbreviated title	ASIACRYPT 2011
Country/Territory	Korea, Republic of
City	Seoul
Period	4/12/11 → 8/12/11

Fields of Expertise

Information, Communication & Computing

Access to Document

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

mendelFinal published version, 410 KB

FWF - kryptographische Hashfu - Cryptanalysis of modern cryptographic hash functions II
Nad, T., Mendel, F., Schläffer, M., Lamberger, M. & Rijmen, V.
1/02/10 → 31/01/13
Project: Research project
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/01/13
Project: Research project
Cryptography
Schläffer, M. (Co-Investigator (CoI)), Oswald, M. E. (Co-Investigator (CoI)), Lipp, P. (Co-Investigator (CoI)), Dobraunig, C. E. (Co-Investigator (CoI)), Mendel, F. (Co-Investigator (CoI)), Eichlseder, M. (Co-Investigator (CoI)), Nad, T. (Co-Investigator (CoI)), Posch, R. (Co-Investigator (CoI)), Lamberger, M. (Co-Investigator (CoI)), Rijmen, V. (Co-Investigator (CoI)) & Rechberger, C. (Co-Investigator (CoI))
1/01/95 → 31/01/19
Project: Research area

Cite this

Biryukov, A, Lamberger, M, Mendel, F & Nikolic, I 2011, Second-Order Differential Collisions for Reduced SHA-256. in DH Lee & X Wang (eds), Advances in Cryptology - ASIACRYPT 2011. Lecture Notes in Computer Science, vol. 7073, Springer, pp. 270-287, 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, Korea, Republic of, 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 = "17th International Conference on the Theory and Application of Cryptology and Information Security : ASIACRYPT 2011, ASIACRYPT 2011 ; 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 - 17th 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

Publication series

Conference

Fields of Expertise

Access to Document

Fingerprint

Projects

FWF - kryptographische Hashfu - Cryptanalysis of modern cryptographic hash functions II

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

Cryptography

Cite this