Thomas Peyrin, Quan Quan Tan, Hongyi Zhang, Chunning Zhou

Trail-Estimator: An Automated Verifier for Differential Trails in Block Ciphers

Introduction

Trail-estimator: an automated verifier for differential trails in block ciphers. Trail-Estimator automatically verifies differential trails in block ciphers. It detects hidden algebraic constraints and provides accurate probability distributions, improving cryptanalysis.

Abstract

Differential cryptanalysis is a powerful technique for attacking block ciphers, wherein the Markov cipher assumption and stochastic hypothesis are commonly employed to simplify the search and probability estimation of differential trails. However, these assumptions often neglect inherent algebraic constraints, potentially resulting in invalid trails and inaccurate probability estimates. Some studies identified violations of these assumptions and explored how they impose constraints on key material, but they have not yet fully captured all relevant ones. This study proposes Trail-Estimator, an automated verifier for differential trails on block ciphers, consisting of two parts: a constraint detector Cons-Collector and a solving tool Cons-Solver. We first establish the fundamental principles that will allow us to systematically identify all constraint subsets within a differential trail, upon which Cons-Collector is built. Then, Cons-Solver utilizes specialized preprocessing techniques to efficiently solve the detected constraint subsets, thereby determining the key space and providing a comprehensive probability distribution of differential trails. To validate its effectiveness, Trail-Estimator is applied to verify 17 differential trails for the SKINNY, LBLOCK, TWINE, and AES block ciphers. Experimental results show that Trail-Estimator consistently identifies previously undetected constraints for SKINNY and AES, and discovers constraints for the first time for LBLOCK and TWINE. Notably, it is the first tool to discover long nonlinear constraints extending beyond five rounds in these ciphers. Furthermore, Trail-Estimator’s accuracy is validated by experiments showing its predictions closely match the real probability distribution of short-round differential trails.

Review

This paper introduces Trail-Estimator, an innovative automated verifier designed to address critical limitations in differential cryptanalysis. The authors pinpoint a long-standing issue where common assumptions like the Markov cipher assumption and stochastic hypothesis often overlook inherent algebraic constraints, leading to inaccurate probability estimates and potentially invalid differential trails. Trail-Estimator tackles this by systematically identifying and solving these constraints, promising a more precise understanding of differential trails than previously possible. This work is highly relevant and timely, as it directly impacts the reliability of security analyses for block ciphers. The methodology behind Trail-Estimator is particularly noteworthy. It comprises two distinct components: Cons-Collector, which establishes fundamental principles to systematically identify all constraint subsets within a differential trail, and Cons-Solver, which employs specialized preprocessing techniques for efficient solving. This systematic and comprehensive approach for identifying *all* constraint subsets, combined with efficient solving, represents a significant technical advancement. The experimental results strongly validate its effectiveness, demonstrating the discovery of previously undetected constraints for established ciphers like SKINNY and AES, and *de novo* discoveries for LBLOCK and TWINE. Critically, Trail-Estimator is highlighted as the first tool capable of uncovering long nonlinear constraints extending beyond five rounds, a feature that significantly deepens our understanding of complex differential propagation. The implications of Trail-Estimator are substantial for the field of cryptanalysis and block cipher design. By providing a more accurate probability distribution of differential trails and a refined determination of the key space, it offers cryptanalysts a more reliable tool for evaluating cipher security. The validation showing its predictions closely match real probability distributions for short-round trails underscores its accuracy and practical utility. This work not only enhances the precision of differential cryptanalysis but also provides a valuable framework for future research into the algebraic properties of differential trails, making it a highly impactful contribution to cryptographic security analysis.

Full Text

Comments

You need to be logged in to post a comment.