TY - JOUR

T1 - Generating graphs packed with paths

T2 - Estimation of linear approximations and differentials

AU - Hall-Andersen, Mathias

AU - Vejre, Philip Søgaard

PY - 2018

Y1 - 2018

N2 - When designing a new symmetric-key primitive, the designer must show resistance to known attacks. Perhaps most prominent amongst these are linear and differential cryptanalysis. However, it is notoriously difficult to accurately demonstrate e.g. a block cipher’s resistance to these attacks, and thus most designers resort to deriving bounds on the linear correlations and differential probabilities of their design. On the other side of the spectrum, the cryptanalyst is interested in accurately assessing the strength of a linear or differential attack. While several tools have been developed to search for optimal linear and differential trails, e.g. MILP and SAT based methods, only few approaches specifically try to find as many trails of a single approximation or differential as possible. This can result in an overestimate of a cipher’s resistance to linear and differential attacks, as was for example the case for present. In this work, we present a new algorithm for linear and differential trail search. The algorithm represents the problem of estimating approximations and differentials as the problem of finding many long paths through a multistage graph. We demonstrate that this approach allows us to find a very large number of good trails for each approximation or differential. Moreover, we show how the algorithm can be used to efficiently estimate the key dependent correlation distribution of a linear approximation, facilitating advanced linear attacks. We apply the algorithm to 17 different ciphers, and present new and improved results on several of these.

AB - When designing a new symmetric-key primitive, the designer must show resistance to known attacks. Perhaps most prominent amongst these are linear and differential cryptanalysis. However, it is notoriously difficult to accurately demonstrate e.g. a block cipher’s resistance to these attacks, and thus most designers resort to deriving bounds on the linear correlations and differential probabilities of their design. On the other side of the spectrum, the cryptanalyst is interested in accurately assessing the strength of a linear or differential attack. While several tools have been developed to search for optimal linear and differential trails, e.g. MILP and SAT based methods, only few approaches specifically try to find as many trails of a single approximation or differential as possible. This can result in an overestimate of a cipher’s resistance to linear and differential attacks, as was for example the case for present. In this work, we present a new algorithm for linear and differential trail search. The algorithm represents the problem of estimating approximations and differentials as the problem of finding many long paths through a multistage graph. We demonstrate that this approach allows us to find a very large number of good trails for each approximation or differential. Moreover, we show how the algorithm can be used to efficiently estimate the key dependent correlation distribution of a linear approximation, facilitating advanced linear attacks. We apply the algorithm to 17 different ciphers, and present new and improved results on several of these.

KW - Correlation distributions

KW - Differential cryptanalysis

KW - Differentials

KW - Graph theory

KW - Linear approximations

KW - Linear cryptanalysis

KW - Trail search

U2 - 10.13154/tosc.v2018.i3.265-289

DO - 10.13154/tosc.v2018.i3.265-289

M3 - Journal article

AN - SCOPUS:85061644648

VL - 2018

SP - 265

EP - 289

JO - IACR Transactions on Symmetric Cryptology

JF - IACR Transactions on Symmetric Cryptology

SN - 2519-173X

IS - 3

ER -