Improving Local Collisions: New Attacks on Reduced SHA-256

Florian Mendel; Tomislav Nad; Martin Schläffer

doi:10.1007/978-3-642-38348-9_16

Improving Local Collisions: New Attacks on Reduced SHA-256

Florian Mendel, Tomislav Nad, Martin Schläffer

Institute of Information Security (7050)

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

Abstract

In this paper, we focus on the construction of semi-free-start collisions for SHA-256, and show how to turn them into collisions. We present a collision attack on 28 steps of the hash function with practical complexity. Using a two-block approach we are able to turn a semi-free-start collision into a collision for 31 steps with a complexity of at most 265.5. The main improvement of our work is to extend the size of the local collisions used in these attacks. To construct differential characteristics and confirming message pairs for longer local collisions, we had to improve the search strategy of our automated search tool. To test the limits of our techniques we present a semi-free-start collision for 38 steps.

Original language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2013
Place of Publication	Berlin; Heidelberg
Publisher	Springer
Pages	262-278
ISBN (Print)	978-3-642-38347-2
DOIs	https://doi.org/10.1007/978-3-642-38348-9_16
Publication status	Published - 2013
Event	32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques : EUROCRYPT 2013 - Athen, Greece Duration: 26 May 2013 → 30 May 2013

Conference

Conference	32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques
Abbreviated title	EUROCRYPT 2013
Country/Territory	Greece
City	Athen
Period	26/05/13 → 30/05/13

Fields of Expertise

Information, Communication & Computing

Access to Document

10.1007/978-3-642-38348-9_16

sha2eurocrypt.pdfFinal published version, 319 KB

FWF - ReSIT - Realizing a Secure Internet of Things
Hutter, M. (Co-Investigator (CoI)), Wenger, E. (Co-Investigator (CoI)), Schmidt, J.-M. (Co-Investigator (CoI)), Mendel, F. (Co-Investigator (CoI)), Mangard, S. (Co-Investigator (CoI)) & Posch, R. (Principal Investigator (PI))
1/07/12 → 31/05/16
Project: Research project
FWF - kryptographische Hashfu - Cryptanalysis of modern cryptographic hash functions II
Nad, T. (Co-Investigator (CoI)), Mendel, F. (Co-Investigator (CoI)), Schläffer, M. (Co-Investigator (CoI)), Lamberger, M. (Co-Investigator (CoI)) & Rijmen, V. (Principal Investigator (PI))
1/02/10 → 31/01/13
Project: Research project
EU - ECRYPT II - European network of excellence in cryptology - Phase II
Schmidt, J.-M. (Co-Investigator (CoI)), Nad, T. (Co-Investigator (CoI)), Kirschbaum, M. (Co-Investigator (CoI)), Feldhofer, M. (Co-Investigator (CoI)), Schläffer, M. (Co-Investigator (CoI)), Aigner, M. J. (Co-Investigator (CoI)), Rechberger, C. (Co-Investigator (CoI)), Lamberger, M. (Co-Investigator (CoI)), Tillich, S. (Co-Investigator (CoI)), Medwed, M. (Co-Investigator (CoI)), Hutter, M. (Co-Investigator (CoI)), Rijmen, V. (Co-Investigator (CoI)), Mendel, F. (Co-Investigator (CoI)) & Posch, R. (Principal Investigator (PI))
1/08/08 → 31/01/13
Project: Research project

Cite this

@inproceedings{4a02e161f58c4339a51f119bfa4eb073,

title = "Improving Local Collisions: New Attacks on Reduced SHA-256",

abstract = "In this paper, we focus on the construction of semi-free-start collisions for SHA-256, and show how to turn them into collisions. We present a collision attack on 28 steps of the hash function with practical complexity. Using a two-block approach we are able to turn a semi-free-start collision into a collision for 31 steps with a complexity of at most 265.5. The main improvement of our work is to extend the size of the local collisions used in these attacks. To construct differential characteristics and confirming message pairs for longer local collisions, we had to improve the search strategy of our automated search tool. To test the limits of our techniques we present a semi-free-start collision for 38 steps.",

author = "Florian Mendel and Tomislav Nad and Martin Schl{\"a}ffer",

year = "2013",

doi = "10.1007/978-3-642-38348-9_16",

language = "English",

isbn = "978-3-642-38347-2",

pages = "262--278",

booktitle = "Advances in Cryptology – EUROCRYPT 2013",

publisher = "Springer",

note = "32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques : EUROCRYPT 2013, EUROCRYPT 2013 ; Conference date: 26-05-2013 Through 30-05-2013",

}

TY - GEN

T1 - Improving Local Collisions: New Attacks on Reduced SHA-256

AU - Mendel, Florian

AU - Nad, Tomislav

AU - Schläffer, Martin

PY - 2013

Y1 - 2013

N2 - In this paper, we focus on the construction of semi-free-start collisions for SHA-256, and show how to turn them into collisions. We present a collision attack on 28 steps of the hash function with practical complexity. Using a two-block approach we are able to turn a semi-free-start collision into a collision for 31 steps with a complexity of at most 265.5. The main improvement of our work is to extend the size of the local collisions used in these attacks. To construct differential characteristics and confirming message pairs for longer local collisions, we had to improve the search strategy of our automated search tool. To test the limits of our techniques we present a semi-free-start collision for 38 steps.

AB - In this paper, we focus on the construction of semi-free-start collisions for SHA-256, and show how to turn them into collisions. We present a collision attack on 28 steps of the hash function with practical complexity. Using a two-block approach we are able to turn a semi-free-start collision into a collision for 31 steps with a complexity of at most 265.5. The main improvement of our work is to extend the size of the local collisions used in these attacks. To construct differential characteristics and confirming message pairs for longer local collisions, we had to improve the search strategy of our automated search tool. To test the limits of our techniques we present a semi-free-start collision for 38 steps.

U2 - 10.1007/978-3-642-38348-9_16

DO - 10.1007/978-3-642-38348-9_16

M3 - Conference paper

SN - 978-3-642-38347-2

SP - 262

EP - 278

BT - Advances in Cryptology – EUROCRYPT 2013

PB - Springer

CY - Berlin; Heidelberg

T2 - 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques

Y2 - 26 May 2013 through 30 May 2013

ER -

Improving Local Collisions: New Attacks on Reduced SHA-256

Abstract

Conference

Fields of Expertise

Access to Document

Fingerprint

Projects

FWF - ReSIT - Realizing a Secure Internet of Things

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

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

Cite this