Guozhen Liu, Shun Li, Huina Li, Weidong Qiu, Siwei Sun

SAT-Based Space Partitioning and Applications to Ascon-Hash256 Cryptanalysis

Introduction

Sat-based space partitioning and applications to ascon-hash256 cryptanalysis. Efficient SAT-based space partitioning technique for cryptanalysis. Applied to Ascon-Hash256, it improves collision & preimage attacks and discovers new SFS collision trails.

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 261.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 2116.74 to 2114.13 with memory complexity 2112 (improved from 2116), and the preimage attack complexity from 2162.80 to 2160.75 with memory complexity 2160 (improved from 2162).

Review

This paper introduces a novel SAT-based space partitioning technique that leverages combinatorial necklace generation to systematically explore large search spaces, particularly in cryptanalysis. The method promises efficient and complete coverage of complex problem domains by dividing them into manageable subsets, while precisely tracking explored regions. This innovative approach to search space management is a significant methodological contribution, offering a new tool for cryptanalysts tackling challenging problems with extensive search requirements. The ability to guarantee search completeness while handling large spaces is a particularly attractive feature of this proposed technique. The effectiveness of this technique is convincingly demonstrated through its application to the cryptanalysis of Ascon-Hash256, a finalist in the NIST Lightweight Cryptography standardization process. For differential-based collision attacks, the authors establish a strong lower bound by exhaustively proving no 2-round collision trail exists with a weight less than 156. Building upon this, they present an improved 2-round collision attack with a complexity of 2^61.79. Furthermore, the paper reports the discovery of new Semi-Free-Start (SFS) collision trails, yielding practical attacks on 3-round and 4-round Ascon-Hash256, notably reducing the best known 4-round SFS trail weight from 295 to 250. The technique also proves beneficial for Meet-in-the-Middle (MITM) attacks on 3-round Ascon-Hash256, achieving improved collision attack complexity from 2^116.74 to 2^114.13 (with reduced memory) and preimage attack complexity from 2^162.80 to 2^160.75 (also with reduced memory). Overall, this paper presents a compelling combination of methodological innovation and impactful practical results. The proposed SAT-based space partitioning technique appears robust and versatile, providing a systematic way to manage and explore vast combinatorial spaces. The concrete improvements achieved against Ascon-Hash256, encompassing stronger lower bounds, enhanced collision attacks, and more efficient SFS and MITM attacks, underscore the practical power of the new technique. These findings are highly relevant to the cryptographic community, particularly given Ascon's status, and highlight potential weaknesses in specific round variants. This work not only advances the cryptanalysis of Ascon-Hash256 but also introduces a generally applicable framework that could benefit cryptanalytic efforts against other cryptographic primitives.

Full Text

Comments

You need to be logged in to post a comment.