Kazuma Taka, Kosei Sakamoto, Ryoma Ito, Rentaro Shiba, Shion Utsumi, Takanori Isobe

Divide-and-Conquer SAT for Exploring Optimal Differential and Linear Characteristics and Its Applications

Introduction

Divide-and-conquer sat for exploring optimal differential and linear characteristics and its applications. Novel divide-and-conquer SAT/MILP tool efficiently finds optimal differential and linear characteristics for symmetric-key primitives. Improves cryptanalysis of AES, Camellia, LED, Midori-128, and more.

Abstract

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.

Review

The paper, "Divide-and-Conquer SAT for Exploring Optimal Differential and Linear Characteristics and Its Applications," introduces a significant advancement in the automated search for optimal differential and linear characteristics in symmetric-key primitives. Addressing the computational challenges posed by large S-boxes and complex linear layers, the authors propose a novel solver-aided automatic search tool. This tool leverages a sophisticated divide-and-conquer strategy that combines the strengths of both MILP and SAT methods, allowing for the decomposition of large SAT models into smaller, more manageable sub-problems. A key innovation of this approach is its ability to pre-eliminate substantial portions of the Boolean variable assignment space that would otherwise lead to "UNSAT" outcomes, thereby streamlining the search process. Beyond its innovative SAT partitioning strategy, the tool also features a new method specifically designed for large S-boxes, which efficiently utilizes the decimal parts of values. This particular technique reportedly enables the practical-time derivation of optimal linear characteristics for primitives based on large S-boxes, a feat claimed to be achieved for the first time. The efficacy and practical utility of the new tool are convincingly demonstrated across a diverse set of modern ciphers, including AES, Camellia (without FL function), ARIA, LED, Midori-128, SKINNY-128, and Rijndael-256-256. The results are impactful, improving the required number of rounds for single-characteristic differential and linear attacks on Camellia, LED, and Midori-128, and successfully identifying the longest distinguish for several extensively analyzed ciphers. While the abstract presents a compelling case for the tool's effectiveness and novelty, a deeper dive into the methodology, particularly the "decimal parts of values" method for large S-boxes, would be beneficial in the full paper to fully appreciate its technical underpinnings and generalizability. Further elaboration on the computational overheads and specific resources required to achieve "practical time" across the tested primitives would also provide crucial context for the efficiency claims. Additionally, an exploration of potential limitations or specific scenarios where the divide-and-conquer strategy might face challenges, perhaps in comparison to other specialized cryptanalytic tools or hybrid approaches, would enrich the overall understanding of the tool's unique position and future applicability.

Full Text

Comments

You need to be logged in to post a comment.