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
SN - 2519-173X
VL - 2018
SP - 265
EP - 289
JO - IACR Transactions on Symmetric Cryptology
JF - IACR Transactions on Symmetric Cryptology
IS - 3
ER -