M.: 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 character-istics 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