Welcome to the resource topic for 2024/349
Title:
New Records in Collision Attacks on SHA-2
Authors: Yingxin Li, Fukang Liu, Gaoli Wang
Abstract:The SHA-2 family including SHA-224, SHA-256, SHA-384,
SHA-512, SHA-512/224 and SHA512/256 is a U.S. federal standard pub-
lished by NIST. Especially, there is no doubt that SHA-256 is one of the
most important hash functions used in real-world applications. Due to
its complex design compared with SHA-1, there is almost no progress
in collision attacks on SHA-2 after ASIACRYPT 2015. In this work, we
retake this challenge and aim to significantly improve collision attacks
on the SHA-2 family. First, we observe from many existing attacks on
SHA-2 that the current advanced tool to search for SHA-2 characteristics
has reached the bottleneck. Specifically, longer differential characteristics
could not be found, and this causes that the collision attack could not
reach more steps. To address this issue, we adopt Liu et al.’s MILP-based
method and implement it with SAT/SMT for SHA-2, where we also add
more techniques to detect contradictions in SHA-2 characteristics. This
answers an open problem left in Liu et al.’s paper to apply the technique
to SHA-2. With this SAT/SMT-based tool, we search for SHA-2 charac-
teristics by controlling its sparsity in a dedicated way. As a result, we
successfully find the first practical semi-free-start (SFS) colliding message
pair for 39-step SHA-256, improving the best 38-step SFS collision attack
published at EUROCRYPT 2013. In addition, we also report the first
practical free-start (FS) collision attack on 40-step SHA-224, while the
previously best theoretic 40-step attack has time complexity 2110. More-
over, for the first time, we can mount practical and theoretic collision
attacks on 28-step and 31-step SHA-512, respectively, which improve the
best collision attack only reaching 27 steps of SHA-512 at ASIACRYPT
2015. In a word, with new techniques to find SHA-2 characteristics, we
have made some notable progress in the analysis of SHA-2 after the major
achievements made at EUROCRYPT 2013 and ASIACRYPT 2015.
ePrint: https://eprint.iacr.org/2024/349
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .