Welcome to the resource topic for 2025/1542
Title:
SAT-Based Space Partitioning and Applications to Ascon-Hash256
Authors: Guozhen Liu, Shun Li, Huina Li, Weidong Qiu, Siwei Sun
Abstract:We introduce an efficient SAT-based space partitioning technique that enables systematic exploration of large search spaces in cryptanalysis. The approach divides complex search spaces into manageable subsets through combinatorial necklace generation, allowing precise tracking of explored regions while maintaining search completeness.
We demonstrate the technique’s effectiveness through extensive cryptanalysis of Ascon-Hash256. For differential-based collision attacks, we conduct an exhaustive search of 2-round collision trails, proving that no collision trail with weight less than 156 exists. Through detailed complexity analysis and parameter optimization, we present an improved 2-round collision attack with complexity 2^{61.79}. We also discover new Semi-Free-Start (SFS) collision trails that enable practical attacks on both 3-round and 4-round Ascon-Hash256, especially improving the best known 4-round SFS trail from weight 295 to 250.
Furthermore, applying the technique to Meet-in-the-Middle structure search yields improved attacks on 3-round Ascon-Hash256. We reduce the collision attack complexity from 2^{116.74} to 2^{114.13} with memory complexity 2^{112} (improved from 2^{116}), and the preimage attack complexity from 2^{162.80} to 2^{160.75} with memory complexity 2^{160} (improved from 2^{162}).
ePrint: https://eprint.iacr.org/2025/1542
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 .