Generalizing Bit-based Rebound Attacks on AES-like Hashing

At ASIACRYPT 2024, Taiyama et al. introduced the bit-based rebound attack, which exploits bit-wise behaviors of differential characteristics, as well as dependencies among operations and internal variables. Their approach employs a tree-based structure to represent these relations to optimize inbound and outbound phases and is applied to Davies-Meyer (DM) hashing with AES. However, it is limited to AES as it relies on the property of MixColumns of AES, and suffers from inefficiencies due to its independent search processes of differential characteristics and the rebound phase, which may evaluate differential characteristics unsuitable for rebound attacks. In this paper, we generalize bit-based rebound attacks by introducing a Directed Acyclic Graph representation, enabling a more precise estimation of degrees of freedom (DoF) across a broader range of ciphers. Besides, we integrate differential characteristic search with rebound-based collision evaluation to develop a SAT-based fully automated tool, which eliminates ineffective differential characteristics and improves the efficiency of the search. By applying this tool to AES-DM, SKINNY-DM, and Hirose’s double-block-length compression function instantiated with AES (HCF-AES), we show more efficient collision attacks on AES-DM, reducing time complexity and increasing the number of attackable rounds. Furthermore, we propose the first collision and semi-free-start collision attacks on SKINNY-DM, as well as the first semi-free-start collision attack on HCF-AES. To ensure the validity of our results, we experimentally verify some attacks by finding actual collisions.