International Association
for Cryptologic Research

Developing automatic search tools to derive optimal characteristics is crucial for both the design and cryptanalysis of symmetric-key primitives. However, evaluating primitives that employ large S-boxes and complex linear layers remains a computationally demanding task. In this paper, we introduce a novel solver-aided automatic search tool based on the divide-and-conquer strategy that leverages the advantages of both MILP and SAT methods. Our method divides a given SAT model into multiple smaller SAT models, allowing to pre-eliminate as much of the space of Boolean variable assignments that make a given SAT model always “UNSAT”. In addition, we propose a new method for large S-boxes that involves the decimal parts of values, enabling us to efficiently derive optimal linear characteristics for a large S-box-based primitive, all within a practical time for the first time. The new tool is able to obtain optimal differential and linear characteristics in the significant number of rounds of AES, Camellia without FL function, ARIA, LED, Midori-128, SKINNY- 128, and Rijndael-256-256. Our results improve the required number of rounds for differential and linear attacks, based on a single characteristic, for Camellia, LED, and Midori-128. Besides, our tool identifies the longest distinguisher for extensivelyanalyzed ciphers of Camellia/ARIA/Midori-128 and SKINNY-128 by optimal linear and differential ones, respectively.

In this paper, we explore a new type of key collisions called target-plaintext key collisions of AES, which emerge as an open problem in the key committing security and are directly converted into single-block collision attacks on Davies-Meyer (DM) hashing mode. For this key collision, a ciphertext collision is uniquely observed when a specific plaintext is encrypted under two distinct keys. We introduce an efficient automatic search tool designed to find target-plaintext key collisions. This tool exploits bit-wise behaviors of differential characteristics and dependencies among operations and internal variables of both data processing and key scheduling parts. This allows us to hierarchically perform rebound-type attacks to identify key collisions. As a result, we demonstrate single-block collision attacks on 2/5/6-round AES-128/192/256-DM and semi-free-start collision attacks on 5/7/9-round AES-128/192/256-DM, respectively. To validate our attacks, we provide an example of fixed-target-plaintext key collision/semi-free-start collisions on 9-round AES-256-DM. Furthermore, by exploiting a specific class of free-start collisions with our tool, we present two-block collision attacks on 3/9-round AES-128/256-DM, respectively.