Cryptology ePrint Archive: Report 2020/1152

An Automatic Search Tool for Iterative Trails and its Application to estimation of differentials and linear hulls

Tianyou Ding and Wentao Zhang and Chunning Zhou and Fulei Ji

Abstract: The design and cryptanalysis are the both sides from which we look at symmetric-key primitives. If a symmetric-key primitive is broken by a kind of cryptanalysis, it's definitely insecure. If a designer claims a symmetric-key primitive to be secure, one should demonstrate that the primitive resists against all known attacks. Differential and linear cryptanalysis are two of the most important kinds of cryptanalysis. To conduct a successful differential (linear) cryptanalysis, a differential (linear) distinguisher with significant differential probability (linear correlation) is needed.

We observe that, for some lightweight symmetric-key primitives, their significant trails usually contain iterative trails. In this work, We propose an automatic tool for searching iterative trails. We model the problem of searching itrative trails as a problem of finding elementry ciucuits in a graph. Based on the iterative trails found, we further propose a method to estimate the probability (correlation) of a differential (linear hull).

We apply our methods to the 256-bit KNOT permutation, PRESENT, GIFT-64 and RECTANGLE. Iterative trails are found and visualized. If iterative trails are found, we show our method can efficiently find good differentials and linear hulls. What's more, the results imply that for the primitives we test with bit permutations as their linear layers, the good differentials and linear hulls are dominated by iterative trails.

Category / Keywords: secret-key cryptography / Differential Cryptanalysis, Linear Cryptanalysis, Automatic Search Tools, Iterative Trails, Lightweight Cryptography

Date: received 21 Sep 2020

Contact author: dingtianyou at iie ac cn,zhangwentao@iie ac cn

Available format(s): PDF | BibTeX Citation

Note: The writing and experiments are still in progress. More experiment results will be added on.

Version: 20200925:183722 (All versions of this report)

Short URL: ia.cr/2020/1152